Page replacement design Flashcards
What design decisions have to be made?
Frame allocation algorithm: How memory frames are allocated among processes
Page replacement algorithm: How victims will be chosen
How are algorithms evaluated?
Run the algorithm against some test data, where the test data is a sequence of reference strings.
Can also trace a running system to produce large amounts of data.
What is a reference string??
Record only page number, consecutive duplicates are eliminated.
How does FIFO replacement work?
Replace the page that was brought in first.
Record the time that each page was faulted.
How can we optimise the FIFO solution?
Interested in order, not time. Create FIFO queue and replace pages at the head of the queue.
When page is faulted, insert at back.
What are the drawback of FIFO replacement?
May replace heavily used pages. IE:
Variable written at start of program that is used throughout but will be replaced.
What is the FIFO anomaly?
intuitive results due to Belady’s anomaly.
Page fault rate may increase when number of frames is increased.
What is an optimal algorithm for page replacement?
Replace the page that will not be used for the longest time
What is the implication of the optimal algorithm?
Impossible to implement as we can’t predict the future.
What is the optimal algorithm used for?
Comparison purposes, calculate the best possible performance of a reference string.
What is LRU?
Least recently used , replace the page that hasn’t been used for the longest time.
Optimal algorithm except it looks back in time.
How is memory determined by the LR?
Pages in memory are the n most recently used pages.
For n+1 frames these n pages would still be in memory.
How does LRU work with counters?
Logical CPU clock held in register, incremented on each memory reference.
Page table entry contains counter value at last use, have to search page table for smallest value.
How does LRU work with the stack?
Maintain a stack of page numbers.
On reference, remove from stack and push on top.
Replace page at bottom of stack.
What support does LRU require?
Hardware support, clock or stack approach require memory update on every reference.
Interrupt on ever memory reference.
What is used when there isn’t enough hardware support for LRU?
Reference bits, associated with each page table entry and set by hw when page is referenced. All bits cleared periodically.
Identifies pages used since bits were last cleared.
What is the drawback of reference bits?
Can’t tell what order pages were used in.
How does the OS interact with reference bits?
OS records reference bits at regular intervals.
On timer interrupt, OS shifts byte for each page right 1 bit and copies in current value of reference bit into left-most bit.
Interpret this as integers and replace lowest number.
How can reference bits be used in FIFO?
Pages have their reference bit checked before being replaced.
If it is kept in the queue, clear reference but and reset arrival time to present.
How does the clock algorithm work?
Circular queue of pages, pointer indicates next victim. When page is needed pointer advances until page with a 0 reference bit is found.
Reference bits cleared as they are passed.
What is the worst case of the clock algorithm?
All bits are set and pointer cycles through all pages. Head then becomes the victim.
How can we enhance second chance?
Use reference bit and modified bit as ordered par.
Use clock algorithm, interpret pair as integer and replace a page in the lowest non-empty class.
How does free frame pool work?
Keep some frames free all the time.
Choose victim frame as normal, read new page into a free frame immediately, don’t wait on write back.
Victim frame added to free pool when write completes.
what is Background write back?
List of modified pages, opportunistically write modified pages back to disk and reset dirty bit.
Page more likely to be unmodified when replaced.
