Shared Flashcard Set

Details

Page Replacement Algorithms
page replacement algorithms from usafa cs483
15
Computer Science
Undergraduate 4
11/15/2011

Additional Computer Science Flashcards

 


 

Cards

Term
Optimal
Definition
o Label each page with the next time it will be referenced

o When a page fault occurs, evict the one with the highest label
Term
NRU
Definition
o Two status bits, R and M (Read and Modified)

o These bits are updated on every memory reference

o When a process starts, R and M are set to zero for all pages

o If accessed, set R, if modified, set M

o Periodically clear R (set a timer for this)

o Evict a page in the lowest numbered non-empty class
Term
FIFO
Definition
o Self explanatory

o Ignores locality of reference

o Rarely used
Term
2nd Chance
Definition
o Inspect the R bit of the oldest page, if 0 replace, if 1, set to 0, update the load time (i.e. move to the end of the list) and move on
Term
Clock
Definition
o Second chance is inefficient because it keeps moving pages around on its list

o Keep a pointer instead
Term
LRU
Definition
o Pages referenced in the last few instructions will likely be referenced in the next few (locality of reference)

o For n pages, need an nxn matrix of bits

o When a page k is referenced, set row k to all 1’s and column k to all 0’s

o At a page fault, choose the page with the lowest number to evict
Term
NFU
Definition
o Assign each page a counter of some number of bits (say 8), set them all to zero

o At each clock tick, shift all the counters to the right one bit, then add the R bit to the left most bit (aging)

o At a page fault, again, evict the page with the lowest counter

o counters are finite, but 8 is probably enough
Term
Optimal
Definition
Use it to compare performance of implementable algorithms!
Term
Optimal
Definition
impossible to implement
Term
NRU
Definition
o Periodically clear R (set a timer for this)
Term
NRU
Definition
o Four states now are possible

§ Class 0: not referenced, not modified

§ Class 1: not referenced, modified

§ Class 2: referenced, not modified

§ Class 3: referenced, modified
Term
Clock
Definition
o Differs from second chance only in implementation, the selected page is the same
Term
LRU
Definition
o At any instant, the page with the lowest row value is the next to be replaced
Term
NFU
Definition
implements aging
Term
LRU
Definition
implements locality of reference
Supporting users have an ad free experience!