PowerPoint Presentation
Page Replacement Algorithms
Copyright By PowCoder代写 加微信 powcoder
Operating Systems
University of Toronto
Introduction
Page replacement algorithms
Paging issues
Introduction
CPU generates page fault when it accesses an address not in memory
OS allocates memory frames to programs on demand
If no frame is available, OS needs to evict another page to free a frame
Which page should be evicted?
A page miss is similar to a TLB miss or a cache miss
However, a miss may require accessing the disk
So miss handling can be very expensive
Disk access latency can be close to a million times slower!
20 ns versus 10 ms
Paging Effectiveness relies on
Memory Access Locality
Paging will only work if it occurs rarely
Paging schemes depend on locality of reference
Spatial locality
Programs tend to use a small fraction of their memory, or
Memory accesses are near memory accessed recently
Temporal locality
Programs use same memory over short periods of time, or
Memory accessed recently will be accessed again
Programs normally have both kinds of locality
Hence, overall cost of paging is not very high
spatial locality: accesses are spatially close to each other
temporal locality: same location is accessed again, close in time
Page Replacement Algorithms
Objective: minimize number of page misses
Page table, MMU, TLB handling are VM mechanisms
Page replacement is a VM policy
Several Algorithms
Optimal Algorithm
First In First Out (FIFO)
Least Recently Used (LRU)
Working Set Clock
Page Fault Frequency
The Optimal Page Replacement Algorithm
Select page that will not be needed for longest time
Why is this algorithm optimal?
Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d
Page 0 a
Frames 1 b
Page faults
a a a a
b b b b
c c c c
d d d d
a a a a a
b b b b b
c c c c c
e e e e e
X X
(page numbers: a, b, c, d, e, …)
x is a page fault
a, b, c, d are page numbers (generated by the same or different process), so at time 0, a is mapped to frame 0, b is mapped to frame 1, etc.
inductive proof about optimality:
Say you chose some other page to replace. By definition, it will generate a page fault earlier than this optimal algorithm.
The Optimal Page Replacement Algorithm
Optimal algorithm is the best page replacement algo
But it is unrealizable
Don’t know the future of a program!
Don’t know when a given page will be next needed
However, it can be used to compare to compare the performance of other algorithms
Run the program once
Generate a log of all virtual memory accesses. Do we need all accesses?
Use log to simulate various replacement algorithms
Use optimal algorithm as a control case for evaluating other algorithms
First In First Out (FIFO)
Replace the page that has been in memory for the longest time (i.e., replace oldest page)
Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c a
Page 0 a
Frames 1 b
Page faults
c c c c
a a a a
b b b b
e e e e
d d d d
X X
FIFO Implementation
Implementation
Keep list of all page frames in memory
E.g., add linked list in coremap
When a frame is allocated (e.g., when page is mapped to a new frame), move the frame to the front of list
On a page fault, choose frame at end of list for replacement
The oldest page may be needed again soon
E.g., some page may be important throughout execution, when it gets old, replacing it will soon cause a page fault
Faults may increase if algorithm is given more memory!
Known as Belady’s Anomaly
Can We Do Better that FIFO?
We need to know page reference pattern in the future
We can take advantage of locality of reference
Pages that have been accessed in the recent past are likely to be accessed again and should not be replaced
How can page accesses be tracked?
Tracking each memory access is very expensive
Ideally, tracking page access requires hardware support
Recall: Page Table Entry Bits
Page table entry
frame number (PFN)
Referenced
1 bit could be used for COW
Tracking Page Accesses
Bits in page table entry allow tracking page accesses
Referenced (R) bit
Set by processor when page is read OR written
Cleared by OS/software (not by hardware)
Dirty (D) bit
Set by processor when page is written
Cleared by OS/software (not by hardware)
OS/hardware must synchronize the TLB bits with PTE bits
What if h/w doesn’t maintain these bits?
OS can simulate them
When TLB read fault occurs
Set referenced bit, make page read-only (why read-only)?
When TLB read-only protection fault, or write fault occurs
Set referenced & dirty bits, make page writeable
Synchronizing TLB and PTE:
1. for hardware managed TLB, the hardware could use a write-through cache (i.e., it could update the page table entry reference/dirty bits when TLB reference/dirty bits are updated) or it could use a write-back cache (it could update the page table entry when the TLB entry is invalidated).
2. for software managed TLB, the OS needs to synchronize the TLB R/D bits with PTE R/D bits
Least Recently Used (LRU)
Replace page that has been used least recently using a list of pages kept sorted in LRU order
Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d
Page 0 a
Frames 1 b
Page faults
a a a a
b b b b
c c c c
d d d d
a a a a
b b b b
e e e e
d d d d
LRU Implementation
Updating LRU list on each memory access is too expensive
Suppose MMU maintains a counter that is incremented at each clock cycle
When page is accessed
MMU writes counter value to the page table entry
This timestamp value is the time of last use
On a page fault
Software looks through the page table
Identifies entry with the oldest timestamp
Problem is MMU may not provide such a counter
LRU Approximation
OS can maintain a counter in software
Periodically (i.e., timer interrupt)
Increment counter in each page that has referenced bit set
Write counter value
Clear the referenced bit, why?
On a page fault
Software looks through the page table
Identifies entry with the oldest timestamp
If several have oldest time, choose one arbitrarily
Why does this method approximate LRU?
Why clear the referenced bit? So that if page is not referenced after the counter is written, the counter will not be incremented
Why is it approximate: Granularity of counter is the timer interrupt
Clock Algorithm
FIFO, while giving second chance to referenced pages
Keep circular list of all page frames in memory
Maintain a clock hand, from where frames are evicted
Newly allocate frames is added behind the clock hand
On a page fault, when we need to evict a page frame:
Choose page starting from clock hand
If referenced bit is set
Unset referenced bit, go to next
Else if referenced bit is not set
If page is dirty
Schedule page write, go to next
Else page is clean
Select it for replacement, done
Next: advance clock hand to next page
referenced
From now on, we assume that the page table entry maintains a referenced and dirty bit for each page.
Comparison with FIFO: the clock is like a circular buffer implementation of FIFO. The clock hand is maintained at the end of the list. In FIFO, the clock hand will point to the page that will be evicted next. Pages are added behind the clock hand, so this is the front of the list.
Working Set Model
Working set is the set of pages a program needs currently
To measure working set, look at the last time interval T
T is also called working set interval
WS(T) = { pages accessed in interval (now, now – T) }
As T gets bigger, more pages are needed
However, working set varies slowly after a while
# of unique memory
references over time T
Set of pages accessed (working set)
When someone asks, how much memory does a program need, they mean max(WS).
Example: Working Set of gcc over time
From https://cseweb.ucsd.edu/classes/fa07/cse120/replace.pdf
Goal of algorithm is to keep working set in memory, so few page faults will occur due to locality of reference
Variant of Clock algorithm
Each entry contains time of last use rather than just a referenced bit
On a page fault, clock sweeps over circular list
If referenced bit is set
Update time-of-last-use field to current virtual time
Virtual time is time application has run
Unset referenced bit, continue
Else if referenced bit is not set
Compute age by comparing current time with time-of-last-use
If age of the page is less than working set interval (T)
Else if page is dirty
Schedule page write, continue
Else if page is clean
Select it for replacement, done
Compare with Clock algorithm
The changes to clock algorithm are shown in red
Page Fault Frequency
Working set clock requires knowing working set interval for each process
Page fault frequency can provide estimate of working set needs of a program
It declines as a program is assigned more pages
Can be used to ensure fairness in working set allocation
Too High: need to give this
program some more frames
Too Low: take some frames
away, give to other programs
Page Fault Frequency Algorithm
Measuring page fault frequency:
For each thread
On each fault, count fault (f)
Every second, update faults/second (fe) via aging for all threads
fe = (1 – a) * fe + a * f, f = 0
0 < a < 1, when a -> 1, history is ignored, a is weighting factor
Goal: Allocate frames so PFF is equal for programs
Two step process:
Choose a victim process whose PFF is lowest (global replacement)
Within victim process, use a previously described algorithm like WS/Clock or LRU to evict a page (local replacement)
Which Algorithm is Best?
Compare algorithms based on a reference string
Run a program
Look at which virtual memory addresses are accessed
Pages accessed: 0000001222333300114444001123444
Eliminate duplicates
012301401234, Why?
Defines the reference string
Use the same reference string for evaluating different page replacement algorithms
Count total page faults
a duplicate will not cause replacement for any algorithm.
Example: gcc
From https://cseweb.ucsd.edu/classes/fa07/cse120/replace.pdf
Algorithm Comment
Optimal Not implementable, but useful as a benchmark
FIFO Might throw out important pages
Clock Realistic
LRU Excellent, but difficult to implement efficiently
Working Set Clock Efficient working set algorithm
Page Fault Frequency Fairness in working set allocation
Paging Issues
Paging and I/O interaction
Paging performance
Paging and I/O Interaction
Example: A thread performs a read system call, suspends during I/O, then another thread runs, has a page fault
If enough frames are not available, a frame needs to be evicted
The frame selected for eviction is the one that is involved in the read
This frame is allocated to another (unrelated) page
When I/O returns, OS will copy data from disk to new page!
Solution: Each frame has a ‘do not evict me’ flag, called pinned page because the page is pinned/locked in memory and cannot be evicted during I/O
Must always remember to un-pin the page, e.g., after the I/O completes
Paging Performance
Paging works best if there are plenty of free frames
If all pages are full of dirty pages, then two disk operations are needed for each page fault, one to swap out the dirty page that is being invalidated, one to read in the new page
Two methods for improving performance:
Paging daemon: swap out, in advance
Prefetching: swap in, in advance
Paging Daemon
OS can use a paging thread/daemon to maintain a pool of free frames
Daemon runs replacement algorithm periodically or when pool reaches low watermark
Writes out dirty pages, marks them as free
Frees enough pages until pool reaches high watermark
Frames in pool still hold previous contents of pages
Can be rescued if page is referenced before reallocation
If a page is going to be written again, then it would have been better to not swap it (since then the page is written twice)
Prefetching
Page faults can only be processed one page at a time, because disk has to be read one page at a time
Suppose we can predict future page usage at current fault, then we can prefetch other pages
For example, if a large array is being accessed sequentially, we can load the next page of the array
What if we are wrong?
wasted disk accesses, memory
Thrashing is a situation where OS spends most time paging data from disk, and user programs do not make much progress
A livelock situation
System is over-committed:
Either, page replacement algorithm is not working
Or, system doesn’t have enough memory to hold working set of all currently running programs
Run more programs because CPU is idle – no!
Swapping – suspend some programs for a while
Buy more memory
Think Time
What the optimal page replacement policy?
Is it achievable in practice? Why is it used?
What is the problem with FIFO page replacement?
What is the assumption used by most replacement policies to improve on FIFO?
What is the working set of a process?
Which of the policies described in these slides take working set into account?
What happens when working set does not fit in memory?
Think Time
How does virtual memory interact with I/O?
When should a paging daemon start operation and stop operation?
Describe some situations when prefetching of pages will work well
vm interaction with IO: pages involved in IO cannot be evicted
paging daemon: starts when too few clean or free frames are available (low threshold), stops when a sufficient number of clean or free frames are available (high threshold)
prefetching with work well: when a sequence of virtual pages are read (say page 8, 9, 10), then keep reading the pages in the sequence (e.g., 11, 12). This will work with a large array, and for files that are read sequentially.
/docProps/thumbnail.jpeg