The First-In, First-Out(FIFO) Page Replacement Algorithm
The operating system maintains a list of all pages currently in memory, with the page at the head of the list the oldest one and the page at the tail the most recent arrival. On a page fault, the page at the head is removed and the new page added to the tail of the list.
The Second Chance Page Replacement Algorithm
A simple modification to FIFO that avoids the problem of throwing out a heavily used page is to inspect the R bit of the oldest page. If it is 0, the page is both old and unused, so it is replaced immediately. If the R bit is 1, the bit is cleared, the page is put onto the end of the list of pages, and its load time is updated as though it had just arrived in memory. The search continues.
The Clock Page Replacement Algorithm
Although second chance is a reasonable algorithm, it is unnecessarily inefficient because it is constantly moving pages around on its list. A better approach is to keep all the pages on a circular list in the form of a clock. A hand points to the oldest page.
When a page fault occurs, the page being pointed to by the hand is inspected. If its R bit is 0, the page is evicted, the new page is inserted into the clock in its place, and the hand is advanced on position. If R is 1, it is cleared and the hand is advanced to the next page. This process is repeated until a page is found with R=0. It differs from second chance only in the implementation.
Least Recently Used(LRU) Page Replacement Algorithm
A good approximation to the optimal algorithm is based on the observation that pages that have been heavily used in the last few instructions will probably be heavily used again in the next few. Conversely, pages that have not been used for ages will probably remain unused for a long time. This idea suggests a realizable algorithm: when a page fault occurs, throw out the page that has been unused for the longest time. This strategy is called LRU(Least Recently Used) paging.
LRU with the Matrix algorithm
For a machine with n page frames, the LRU can maintain a matrix of nxn bits, initially all zero. Whenever page frame k is referenced, the hardware first sets all the bits of row k to 1, then sets all the bits of column k to 0. At any instant, the row whose binary value is lowest is the least recently used, the row whose value is next lowest is next least recently used, and so forth.
LRU with the Aging algorithm
To simulate LRU in software requires a software counter associated with each page, initially zero. At each clock interrupt, the operating system scans all the pages in memory. For each page, the R bit, which is 0 or 1, is added to the counter. In effect, the counters are an attempt to keep track of how often each page has been referenced. When a page fault occurs, the page with the lowest counter is chosen for replacement. Moreover, the counters are each shifted right 1 bit before the R bit is added on. The R bit is added to the leftmost, rather than the rightmost bit.
Comments or suggestions about the PAGE, please send Email to khuri@mathcs.sjsu.edu or hsu0832@sundance.sjsu.edu