CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes eighth

In this module you will

  • Explain why page replacement is needed, and what a victim is.
  • Trace FIFO, LRU, the optimal rule and the clock algorithm on a reference string, and count the faults.
  • Show Belady's anomaly on a small example, and say which algorithms are free of it.
  • Explain what the reference bit and the dirty bit add to the choice of a victim.
  • Compare the algorithms by the number of faults for several numbers of frames.

Page 7 ended with a hard limit: the fault rate must stay below about one access in 500,000 if the slowdown is to stay at 10%. A system reaches that only if it keeps the right pages in its frames. When all frames are full and a new page is needed, one old page must go, and the choice decides the fault count. This page compares the main rules for the choice. The next page asks how many frames each process should get. The sources are OSTEP chapter 22, OSC chapter 10 and MOS chapter 3. The traces were computed by a short script and checked by hand.

About this example About this example

Real: The facts, definitions and algorithms on this page come from the books named in the text. No program on this page was timed.

Scripted: The worked traces use small numbers chosen so they can be followed by hand.

Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.