CSE Roadmap

Core tier · about 6 hours · 7 parts

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.