Virtual Memory, Demand Paging, Intro Page Replacement
1
Reading
Dinosaur: Chapter 8, 9 Comet: Ch 21 22
2
Virtual Memory
3
Virtual Memory
Definition: Virtual memory permits a process to run with only some of its virtual address space loaded into physical memory
Key idea: Virtual address space translated to either Physical memory (small, fast) or
Disk (backing store), large but slow
Deep thinking – what made above possible?
Objective:
To produce the illusion of memory as big as necessary
4
Virtual Memory
“To produce the illusion of memory as big as necessary”
Without suffering a huge slowdown of execution
What makes this possible?
Principle of locality
Knuth’s estimate of 90% of the time in 10% of the code There is also significant locality in data references
5
Virtual Memory Implementation
Virtual memory is typically implemented via demand paging
demand paging:
Load memory pages (from storage) “on demand”
paging with swapping, e.g., physical pages are swapped in and out of memory
6
Demand Paging
(paging with swapping)
If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
How to detect this? In software?
virtual address
physical address
CPU
Translation (MMU)
Physical memory
I/O device
7
Demand Paging
(paging with swapping)
If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
Hardware/software cooperate to make things work
Extend PTEs with an extra bit “present” (valid bit)
Any page not in main memory right now has the “present” bit cleared in its PTE
If “present” isn’t set, a reference to the page results in a trap by the paging hardware, called page fault
What needs to happen when page fault occurs?
8
x86 Page Table Entry
Page frame number
U
P
Cw
Gl
L
D
A
Cd
Wt
O
W
V
31 12 Reserved
Valid (present) Read/write
Owner (user/kernel) Write-through
Cache disabled Accessed (referenced) Dirty
PDE maps 4MB Global
9
What is happening before and after malloc()?
Before malloc()?
After malloc()?
Upon first access?
How to capture the first write to a virtual page? e.g. want to trap into page fault handler
Use valid bit
In handler, check if vpage is allocated (and access permitted)
If not, segmentation fault
Else allocate physical page
10
Page Fault Handling in Demand Paging
mem ref
Load M
fault
vi
vi
Inst seq.
Page Table (TLB)
VM subsystem
physical pages
11
Page fault handling (cont)
On a page fault
Find an unused phy. page or a used phy. page (how?)
If the phy. page is used
If it has been modified (how to know?), write it to disk
Invalidate its current PTE and TLB entry (how?)
Load the new page from disk
Update the faulting PTE and its TLB entry
Restart the faulting instruction
Supporting data structure
For speed: A list of unused physical pages (more later)
Data structure to map a phy. page to its pid(s) and virtual address(es)
Sounds faimiliar?
12
Deep thinking:
Virtual Address vs. Virtual Memory
Virtual address
Supported with dynamic memory relocation Segmentation
Paging
Virtual memory
Dynamic memory relocation + swapping Demand paging
Demand segmentation
13
Tasks of the VM subsystem
Once the hardware has provided basic capabilities for VM, OS must make two kinds of decisions
Page selection: when to bring pages into memory
Page replacement: which page(s) should be thrown out, and when
14
Page selection (when)
Prepaging
Allocate physical page and (if from swap) bring a page into memory
before it is referenced
Hard to do without a “prophet”, may unnecessarily bring pages
Request paging
Let user say which pages are needed when Users don’t always know best
And aren’t always impartial
Demand paging
Start up process with no pages loaded
Load a page when a page fault occurs, i.e., wait till it MUST be in memory
Almost all paging systems are demand paging
15
Page replacement algorithms? (which)
mem ref
Load M
VM
fault
vi
vi
Page table
physical pages
16
The BIG picture:
Running at Memory Capacity
Expect to run with all phy. pages in use
Every “page-in” requires an eviction
Goal of page replacement
Maximize hit ratekick out the page that’s least useful
Challenge: how do we determine utility?
Kick out pages that aren’t likely to be used again
Page replacement is a difficult policy problem
17
What makes finding the least useful page hard?
Don’t know future!
Past behavior is a good indication of future behavior! (e.g. LRU)
temporal localitykick out pages that have not been used recently
Perfect (past) reference stream hard to get
Every memory access would need bookkeeping Is this feasible (in software? In hardware?)
Minimize overhead
If no memory pressure, ideally no bookkeeping
In other words, make the common case fast (page hit)
Get imperfect information, while guaranteeing foreground perf What is minimum hardware support that need to added?
18
Definitions
(or, jargons asked during interviews)
Pressure – the demand for some resource (often used when demand exceeds supply)
ex: the system experienced memory pressure
Eviction – throwing something out
ex: cache lines and memory pages got evicted
Pollution – bringing in useless pages/lines ex: this strategy causes high cache pollution
19
More definitions
Thrashing – extremely high rate of moving things in and out (usually unnecessarily)
Locality – re-use – it makes the world go rounds! Temporal Locality – re-use in time
Spatial Locality – re-use of close by locations
20
Performance metric for page replacement policies
Give a sequence of memory accesses, minimize the # of page faults
Similar to cache miss rate
What about hit latency and miss latency?
21
Optimal or MIN
Algorithm (also called Belady’s Algorithm) Replace the page that won’t be used for the
longest time
Pros
Minimal page faults (can you prove it?)
Used as an off-line algorithm for perf. analysis
Cons
No on-line implementation
What was the CPU scheduling algorithm of similar nature?
22
What can we do without extra hardware support?
23
First-In-First-Out (FIFO)
Recently Page loaded out
Algorithm
Throw out the oldest page
Pros
Low-overhead implementation
Cons
No frequency/no recencymay replace the heavily used pages
5
3
4
7
9
11
2
1
15
24
Belady’s anomaly
Belady’s anomaly states that it is possible to have more page faults when increasing the number of page frames while using FIFO method of frame management. Laszlo Belady demonstrated this in 1970. Previously, it was believed that an increase in the number of page frames would always provide the same number or fewer page faults.
Example
Page Requests 321032432104
Example (Page Faults in Red)
Page Requests – 3 frames
Frame 1 Frame 2 Frame 3
3
2
1
0
3
2
4
3
2
1
0
4
3
3
3
0
0
0
4
4
4
4
4
4
2
2
2
3
3
3
3
3
1
1
1
1
1
1
2
2
2
2
2
0
0
Example (Page Faults in Red)
Page Requests – 4 frames
Frame 1
Frame 2
Frame 3
Frame 4
3
2
1
0
3
2
4
3
2
1
0
4
3
3
3
3
3
3
4
4
4
4
0
0
2
2
2
2
2
2
3
3
3
3
4
1
1
1
1
1
1
2
2
2
2
0
0
0
0
0
0
1
1
1
Ideal curve of # of page faults v.s. # of physical pages
29
FIFO illustrating Belady’s anomaly
30
Predicting future based on past
“Principle of locality” Recency:
Page recently used are likely to be used again in the near future
Frequency:
Pages frequently used (recently) are likely to be used
frequently again in the near future
Is this temporal or spatial locality? Why not spatial locality?
31
How to record locality in the past?
Software solution?
32
Exploiting locality needs some hardware support
Reference bit
A hardware bit that is set whenever the page is referenced (read or written)
33
x86 Page Table Entry
Page frame number
U
P
Cw
Gl
L
D
A
Cd
Wt
O
W
V
31 12 Reserved
Valid (present) Read/write
Owner (user/kernel) Write-through
Cache disabled Accessed (referenced) Dirty
PDE maps 4MB Global
34
FIFO with Second Chance
Recently loaded
Algorithm
Page out
5
3
4
7
9
11
2
1
15
If reference bit is 1
Check the reference-bit of the oldest page (first in)
If it is 0, then replace it
If it is 1, clear the referent-bit, put it to the end of the list, and continue searching
Pros Fast
Frequencydo not replace a heavily used page
Cons
The worst case may take a long time
35