- The Optimal Page Replacement Algorithm
- The Not Recently Used Page Replacement Algorithm
- The First-In, First-Out (FIFO) Page Replacement Algorithm
- The Second Chance Page Replacement Algorithm
- The Clock Page Replacement Algorithm
- The Least Recently Used (LRU) Page Replacement Algorithm
- Simulating LRU in Software
- The Working Set Page Replacement Algorithm
- The WSClock Page Replacement Algorithm
- Summary of Page Replacement Algorithms
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
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 page frames on a circular list in the form of a clock, as shown in Fig. 4-2. A hand points to the oldest page.
){kind=link}
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 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
Figure 4-2. The clock page replacement algorithm.
R = 0. Not surprisingly, this algorithm is called clock. It differs from second chance only in the implementation.