Part 5 of 7 · 3 min read
The clock algorithm
In plain words: The hardware gives a cheap hint. Each page table entry has a reference bit. The hardware sets it to 1 whenever the page is read or written, and the kernel clears it to 0 when it wishes. A page with a reference bit of 0 has not been touched since the last clear. That does not give the exact order of use, only a yes or no, and it is enough for a good guess.
The clock algorithm, also called second chance, uses this bit. The frames are arranged in a circle, and a "hand" points at one of them. To find a victim, the kernel looks at the frame under the hand:
- If the reference bit is 1, clear it to 0 and move the hand to the next frame. The page has had a "second chance".
- If the reference bit is 0, this page is the victim. Put the new page in this frame, with its bit set to 1, and move the hand to the next frame.
A page that is used often has its bit set again before the hand returns, so it stays. A page that is not used loses its bit, and when the hand arrives again, it is removed. The clock looks like FIFO that skips pages in use.
The trace uses S and 3 frames. Each frame shows the page and its reference bit, and the frames are in fixed positions (the hand moves around them):
| Ref | Frames (page / bit) |
|---|---|
| 5 | 5/1 - - * |
| 2 | 5/1 2/1 - * |
| 4 | 5/1 2/1 4/1 * |
| 5 | 5/1 2/1 4/1 (hit) |
| 6 | 6/1 2/0 4/0 * (all bits cleared in one sweep, the first frame is taken) |
| 4 | 6/1 2/0 4/1 |
| 6 | 6/1 2/0 4/1 |
| 5 | 6/1 5/1 4/1 * |
| 3 | 6/0 5/0 3/1 * |
| 6 | 6/1 5/0 3/1 |
| 4 | 6/0 4/1 3/1 * |
| 6 | 6/1 4/1 3/1 |
| 1 | 6/0 4/0 1/1 * |
| 1 | 6/0 4/0 1/1 |
| 2 | 2/1 4/0 1/1 * |
| 3 | 2/1 3/1 1/1 * |
| 6 | 2/0 3/0 6/1 * |
| 2 | 2/1 3/0 6/1 |
The clock causes 11 faults on S, between LRU (10) and FIFO (12). It does so with one bit for each page and a hand, and it needs no update on each access, because the hardware sets the bit. Real kernels, Linux among them, use refinements of this idea, such as lists of recently used and idle pages.
Clock algorithm
The clock algorithm (second chance) is a page replacement rule that keeps the frames in a circle with one reference bit each, and moves a hand around the circle, clearing bits that are 1 and choosing the first page whose bit is 0 as the victim.
Example: with bits 1, 1, 0 and the hand on the first frame, the hand clears the first two bits and removes the page in the third frame.
Check yourself: 1. Who sets the reference bit, and who clears it? 2. Why does a page used often stay in memory under the clock? 3. What happens if all reference bits are 1 when a victim is needed?