Term
|
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
|
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
|
Definition
o Self explanatory
o Ignores locality of reference
o Rarely used |
|
|
Term
|
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
|
Definition
o Second chance is inefficient because it keeps moving pages around on its list
o Keep a pointer instead |
|
|
Term
|
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
|
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
|
Definition
| Use it to compare performance of implementable algorithms! |
|
|
Term
|
Definition
|
|
Term
|
Definition
| o Periodically clear R (set a timer for this) |
|
|
Term
|
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
|
Definition
| o Differs from second chance only in implementation, the selected page is the same |
|
|
Term
|
Definition
| o At any instant, the page with the lowest row value is the next to be replaced |
|
|
Term
|
Definition
|
|
Term
|
Definition
| implements locality of reference |
|
|
