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 page frames on a circular list in the form of a clock.

The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the oldest page in the list. When a page fault occurs and no empty frames exist, then the R (referenced) bit is inspected at the hand's location.
* 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 one 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.



Variants on Clock :
- Clock-Pro keeps a circular list of information about recently-referenced pages, including all M pages in memory as well as the most recent M pages that have been paged out. This extra information on paged-out pages, like the similar information maintained by ARC, helps it work better than LRU on large loops and one-time scans.
- WSclock: The "aging" algorithm and the "WSClock" algorithm are probably the most important page replacement algorithms in practice.
- CAR is a page replacement algorithm that has performance comparable to ARC, and substantially outperforms both LRU and CLOCK. The algorithm CAR is self-tuning and requires no user-specified magic parameters.