Part 6 of 7 · 4 min read
Which rule wins
Comparing the rules, and the dirty bit
The table gives the faults for string S, for several numbers of frames:
| Frames | FIFO | LRU | Clock | OPT |
|---|---|---|---|---|
| 2 | 15 | 15 | 15 | 11 |
| 3 | 12 | 10 | 11 | 7 |
| 4 | 7 | 8 | 7 | 6 |
| 5 | 6 | 7 | 6 | 6 |
| 6 | 6 | 6 | 6 | 6 |
In plain words: Three points follow from the table. OPT is never beaten, as it must be. With 6 frames, one for each different page, every rule gives only the 6 cold faults. LRU does not always lead (4 and 5 frames). A single short string is only a hint, and the real comparison uses long traces from real programs. On such traces, LRU and the clock come close to OPT for programs with strong locality, and FIFO is usually worse. LRU and OPT never show Belady's anomaly: with more frames, their fault counts never rise.
A second cost matters too. Not all victims are equal. A page that has not been changed since it was loaded is clean: the copy on disk is still right, so the frame can be reused at once. A page that was written is dirty: the kernel must write it to disk first, which costs another disk operation of several milliseconds. A good rule prefers a clean victim when two pages are equally good. The hardware sets a dirty bit (also called the modify bit) in the page table entry on each write, so the kernel knows which is which. Some systems write dirty pages back in the background, so that clean frames are ready when a fault comes.
Dirty bit
The dirty bit (modify bit) of a page table entry is set by the hardware when the page is written, and it tells the kernel that the page differs from its copy on disk and must be written back before its frame is reused.
Example: a page of program code is never dirty, so removing it costs no write, while a changed page of an array is dirty and costs one disk write.
Interview angle
"Explain LRU and say how an operating system can approximate it." A strong answer defines LRU, says that exact LRU needs an update on every access, and describes the clock with its reference bit. It mentions that the dirty bit makes a clean victim cheaper than a dirty one.
Check yourself: 1. In the table, which rule is best at 4 frames, and which is worst? 2. Why does a dirty victim cost more than a clean one? 3. Which rules never show Belady's anomaly?
Words you will meet
| Word | Meaning |
|---|---|
| Victim | The page chosen to leave memory |
| Reference string | The ordered list of pages that a program touches |
| FIFO | Remove the page that arrived first |
| Belady's anomaly | More frames causing more faults |
| OPT (MIN) | Remove the page whose next use is farthest, a rule that cannot be built |
| LRU | Remove the page unused for the longest time |
| Reference bit | A bit set by the hardware on each use of a page |
| Clock (second chance) | A circle of frames with a hand and reference bits |
| Dirty bit | A bit set by the hardware when a page is written |
| Cold fault | The first fault on a page, on empty frames |
Quick notes
- Page replacement is the choice, made when the kernel needs a frame and every frame is in use, of a victim page to remove from memory so that its frame can hold the page that has just been asked for.
- Belady's anomaly is the effect that a page replacement rule causes more page faults when it is given more frames, which FIFO can show and which rules such as LRU and the optimal rule can never show.
- Least recently used (LRU) is the replacement rule that removes the page whose last use lies farthest in the past, on the guess that pages unused for a long time will stay unused.
- 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.
- The dirty bit (modify bit) of a page table entry is set by the hardware when the page is written, and it tells the kernel that the page differs from.