Page replacement algos (8+9) Flashcards
goal of page replacement algorithm (policy)
manage page access from pages referenced in virtual address space so as to minimize page faults for all pages belonging to a process
Replacement algos run on which data structure?
Strings of memory page references - page references are pointers to actual memory pages
Basic steps followed when page fault occurs
Select a page from a string of referenced pages (pages scheduled to be run)
retrieve page from memory storage and find free frame - if full, evict a victim frame
selected frame loaded into victim frame
victim frame loaded into TLB or secondary storage
update page table
OS exits kernel mode and continues from where it was interrupted (by page fault trap)
Explain random page replacement
Simplest
random frame evicted
issues with random page replacement
unpredictable doesn’t achieve goal of minimizing page faults and does not fit with principle of locality
principle of locality
tendency of CPU to access same set of mem locations repetitively over a short period of time - since these locations correspond to a few processes that CPU scheduled to execute during the given period
Basic idea of FIFO page replacement
allow every page to spend same amount of time in phys mem - first in first out - page that has been loaded in the longest is the first to be swapped out when a new page needs to be swapped in
maintains a linked list of all pages which keeps the order in which pages entered memory - page at front of list is replaced
advantage of FIFO
easy to implement - single pointer needed
Main disadvantage of FIFO
doesnt keep frequently used pages in main mem - page that has been in longest could be the most used page but FIFO will swap it out (and cause page faults)
Explain the OPT algorithm (page replacement)
used as benchmark algorithm
Assumes that page that will not be used for longest time should be selected for replacements
BUT - needs to assume perfect knowledge of the future
If an algorithm is within 5% of OPT then it’s effective
Explain LRU page replacement algorithm
Least Recently Used uses a record of page page replacement to replace pages that have not been used recently
On each page replacement, it places new page at head of list. The list tail is removed.
Implemented with linked list
Main advantage of LRU
accounts for principle of locality - same set of pages tend to be frequently used while the process is executing, so these pages should not be swapped out of main mem
How LRU implements a counter
Every page has associated counter, every time a page is used, counter is incremented (represents time at which page was used in main mem) - we now replace the page with the smallest time value (oldest page)
Relationship between number of frames and number of faults (FIFO)
more frames = more faults
What is Belady’s anomaly?
increasing number of page frames increases the page faults for a given mem access pattern. Seen in fifo, random and second chance algorithms. Does not occur for stack based algorithms
Stack based algorithm?
can be shown that if there are N pages in memory, then that set of pages is a subset of the pages that would be in memory with N+1 frames
e.g. for LRU - using K frames will always be a subset of k+N frames and any page faults that occur for k+N frames will also occur for k+N frames
Explain MRU algorithm
Most recently used page is replaced
Based on argument that page with the largest count has been used enough and new pages have yet to be used
Assumptions that perfect LRU makes and issues with this
OS keeps time stamp for each page referenced and keeps doubly linked list of pages ordered by time referenced
too expensive
clock replacement algorithm
uses a reference bit to approximate LRU - achieve benefits of LRU without overhead. Reference bit corresponds to used-bit that is set for each page reference
What does it mean if the used bit is not set and where is used-bit stored
not seet - page not been referenced in a long time
stored for each page in page table or TLB
Explain the 3 stages that a page can be in - that is determined by the referenced bit
bit = 1: page present in memory and recently used - no page fault
bit = 0: page is present in memory but not recently used. If page fault - if page in TLB (for example), the page replacement algorithm will only change reference bit to 1
page not in mem - look at clock hand
Explain how the clock algo works
arranges physical pages in a conceptual circle with single pointer (clock hard) pointing to one page at a given time
hand pointing to page with ubit = 1: flip to 0 and increment pointer (clock hand) to next page
If find a page where ubit = 0: replace that page and then mark as recently used (flip ubit to 1) and increment pointer again
Best and worst case for clock algorithm
best - next page will have a cleared reference bit (reference-bit = 0)
worst - all reference bits = 1
More accurate way to implement clock algorithm
extra reference bits
Page fault would require a search through all pages to check which one is oldest
Issues with clock algorithm
best - next page will have a cleared reference bit (reference-bit = 0)
worst - all reference bits = 1 - have to loop through all pages
Computational cost for placing pages whose dirty bits are set - before dirty page is replaced must be written to disk before it is replaced
what does it mean if the clock hand s moving fast vs slow
slow - many page faults
fast - fewer page faults
Dirty page
page which is modified in a buffer cache (been swapped out of secondary storage and into a main mem frame) - dirty bit is set in page table
one dirty bit for each physical page frame -
How does the clock algorithm account for dirty pages?
give additional preference to dirty pages
e.g. if reference bit is cleared but dirty bit is set - algorithm will not replace the page now but rather clear the dirty bit and start writing the page to secondary storage - dirty pages always survive one sweep of the clock hand
Second chance clock algorithm
if reference bit is cleared but dirty bit is set - algorithm will not replace the page now but rather clear the dirty bit and start writing the page to secondary storage - dirty pages always survive one sweep of the clock hand
to be replaced reference and dirty bits both have to be cleared
Basic reasoning behind N-chance clock algorithm
give frequently used pages as much of a chance of possible to remain in main mem before being replaced
Algorithm keeps a counter for each page - clock hand can pass each page N times before replacing it
How N-chance clock algorithm works
Counter is stored (per page in cache) to indicate no. sweeps
Given page fault - check ubit. If 1, used bit is cleared and counter also cleared (because recently used in the last sweep). used bit = 0, increment counter. If counter = N, replace page and set its used bit = 1
Disadvantage of N-chance clock algorithm
Extra parameter
more expensive - overhead because uses additional cache mem to store N and account for dirty pages
larger vs smaller values for N in N-chance clock algorithm
Larger values approximate LRU better since least recently used pages spend longer in main mem. Lower N - selects more recently used pages for replacement but is more efficient because for large N - more revolutions of the clock need to be done searching for a page where counter = N
