Page Replacement Design Flashcards
what is a reference string?
test data for a page replacement algorithm
pros and cons of FIFO?
may replace heavily used pages
e.g. if a variable is initialised at the beginning of a program and used several times throughout, this would be an issue with many page faults
prone to beladys anomaly
what is the optimal algorithm?
replace the page that will not be used for the longest time
but its impossible, we can’t forecast future page references
but can be used for comparison purposes
what is LRU? pros and cons?
replace the page that hasn’t been used for the longest time
an approximation of the optimal algorithm
not prone to belady’s
what is belady’s anomaly?
for some page replacement algorithms, increasing the number of pages may increase the number of page faults
how can LRU be implemented?
using counters but we hav eto search the page table for the smallest value
instead we can use a stack
- maintain a stack of page numbers
- on reference remove from stack and push on top
- replacing page at bottom of stack
requires hardware support
what is a reference bit?
- many systems will not provide HW support for real LRU
- but some support reference bits
- reference bit associated with each page table entry
- bit set by HW when page is referenced
- all bits cleaned peroidically
- this allows us to see what pages have been referenced, but not the order
how are additional reference bits used?
can use a byte for each page
- shift byte for each page right 1 bit
- byte gives a history of usage over the last 8 time periods
- if the bits are interpreted as unsigned integers, the lowest number is the LRU page
what is the second chance scheme?
- select pages for replacement in FIFO order
- check reference bit before replacing the page
- give the page a second chance if the bit is set
- clear the reference bit and reset arrive time to present
- move to next page
- if a page is referenced enough it will never be replaced
implemented as the clock algorithm, using a circular queue of pages. advance the pointer until we find a ref bit 0. reference bits are cleared as the pointer advances!
the worst case is all the bits are set and we cycle through all the page, degenerating to simple FIFO
what is enhanced second chance?
uses the reference bit and the dirty bit in comination, as a pair. the page with the lowest value are chosen as victims
0,0 not recently used, not modified - best option
0, 1 not recently used, modified - good option, but page will need to be written on the way out
1, 0 recently used but clean - likely to be used again
1, 1 probably will be used again soon, and we need to write to disk
we may have to search the list multiple times
reduces I/O overhead
what is a free frame pool?
a pool of free frames is kept and processes are written into a free frame before the victim is removed. this keeps us from waiting for the victim to leave and restart the process ASAP
what is a background write back?
we maintain a list of modified pages
when the paging device is idle we opportunistically write those modified pages back, reseting the modified bit
this increases the probability that a page will be unmodified when replaced
why do we need a minimum number of frames for processes?
in the absense of belady’s, increasing the frame number will increase performance.
also, instructions restart if they page fault, so we need to be able to allocate all pages a single instruction can reference
what are two frame allocation strats?
equal share, just split the frames equally
proportional allocation, allocate frames in proportion to size of the process
what are the replacement scopes?
global
- frame can be selected from the set of all frames
- one process can take from another
- performance of a process depends on external circumstances
- the potential for widely varying performance
local replacement
- process must choose only from its allocated frames
- system may have under-used frames
