Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 66 ยท Projects and Practice

Project: Page Replacement Lab

Build a page replacement laboratory in Python: simulate FIFO, LRU, Optimal and Clock, plot fault rates against frame count, reproduce Belady's anomaly and test workloads with locality.

When physical memory is full and a page fault occurs, the OS must evict one page to make room. Which page it picks changes how many future faults occur, and since a fault costs about as much as a million instructions, the choice matters a great deal. Textbooks give formulas; a laboratory gives intuition. In this project you build a small page replacement lab that you can point at any reference string.

Background is in page replacement algorithms. The vocabulary:

  • A reference string is the sequence of page numbers a program touches.
  • A frame is one slot of physical memory that can hold a page.
  • A hit means the page is already in a frame; a fault means it is not and must be loaded.
  • Fault rate = faults / references.

Step 1: FIFO, LRU and OPT

Write each policy as a function that takes the reference string and number of frames and returns the number of faults, along with a trace so you can check it by hand.

  • FIFO evicts the page that has been in memory longest.
  • LRU (least recently used) evicts the page unused for the longest time, betting on locality.
  • OPT (optimal, Belady's algorithm) evicts the page that will not be used for the longest time in the future. It needs the future, so it cannot be implemented in a real OS, but it provides a lower bound to compare against.
Python Step 1: three policies on the textbook reference string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With three frames the counts are FIFO 15, LRU 12 and OPT 9. OPT is the floor nobody can beat; LRU comes close because the past predicts the future when programs have locality.

Step 2: Clock (second chance)

True LRU needs a timestamp update on every memory reference, which hardware cannot afford. Real systems use an approximation: the Clock algorithm. Each frame has a reference bit, set by the hardware when the page is touched. Frames are arranged in a circle with a hand. To pick a victim, advance the hand: if the bit is 1, clear it and move on (a second chance); if it is 0, evict that page.

Python Step 2: the Clock algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Clock usually lands between FIFO and LRU: nearly as good as LRU at a tiny fraction of the cost.

Step 3: fault curves and Belady's anomaly

You would expect more frames to mean fewer faults. For LRU and OPT that is always true (they are stack algorithms). For FIFO it is not. Belady's anomaly is a reference string where adding a frame increases faults. This experiment checks the famous example and plots a text chart of faults versus frames for all four policies.

Python Step 3: fault curves and Belady's anomaly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see FIFO go from 9 faults with 3 frames to 10 with 4: the anomaly. LRU does not suffer from it. On the locality workload, OPT is always lowest, and LRU and Clock usually beat FIFO (with plenty of frames all three converge).

Step 4: thrashing

If the number of frames is smaller than the program's working set (the pages it actively uses), nearly every reference faults. Run the lab with a cyclic reference string slightly bigger than memory to see the worst case for LRU: a loop over n + 1 pages with n frames faults on every reference.

Python Step 4: the loop that defeats LRU

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 4 or fewer frames every access is a fault; with 5 frames only the first 5 are. This cliff is why working-set and page-fault-frequency policies exist. See thrashing.

Extensions

  1. Add LFU (least frequently used) and MRU, and find a workload where MRU wins (the loop above).
  2. Add the enhanced second-chance algorithm using both a reference bit and a dirty bit.
  3. Give each fault a cost, 8 ms for a dirty-page eviction (write plus read) and 4 ms for a clean one, and compare policies by time rather than by count.
  4. Read a real access trace and replay it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can the OPT algorithm not be used in a real operating system?

    OPT evicts the page whose next use is farthest in the future, which cannot be known. It is used as a benchmark.
  2. 2. What does the Clock algorithm approximate?

    Reference bits and a sweeping hand give each page a second chance, which approximates least-recently-used cheaply.
  3. 3. What is Belady's anomaly?

    For FIFO on a particular reference string, 4 frames cause more faults than 3. Stack algorithms like LRU never show it.
  4. 4. A loop touches 5 pages repeatedly with LRU and 4 frames. How many references fault?

    Each access needs the page that was just evicted as least recently used, so the loop faults every time.

Summary

  • A lab for page replacement needs reference strings, a frame count and policy functions that count faults.
  • OPT gives the lower bound, LRU approximates it using the past, Clock approximates LRU cheaply, and FIFO is simple but can suffer Belady's anomaly.
  • Locality of reference makes LRU and Clock effective; loops larger than memory defeat LRU and demand a different strategy.
  • Measure policies by fault count first, then by time cost.

Next: Project: Build a Mini File System