Before you start
- Pages, frames, page faults and what happens when no frame is free (lesson Virtual memory and paging).
Theory
A process uses its pages in some order: the reference string. Memory has a fixed number of frames. If the page is already in a frame, it is a hit; otherwise, a page fault. If no frame is free, the algorithm picks a victim that leaves memory.
| Algorithm | Who it evicts |
|---|---|
| FIFO | The page that was loaded first. Hits do not change the order. |
| LRU (least recently used) | The page whose last use is the oldest. Every hit refreshes it. |
| OPT (optimal, Belady’s) | The page whose next use is farthest in the future, or that will never be used again. It needs to know the future. |
| Clock (second chance) | Frames form a circle and each has a use bit, set to 1 when the page is loaded or used. On a fault the hand looks at its frame: bit 1, clear it and move on; bit 0, evict that page, put the new one there with bit 1 and move one frame on. |
Free frames are filled in order, starting with frame 0. The first use of each page always faults.
Predict
The reference string is 1 2 3 4 1 2 5 1 2 3 4 5. With FIFO and 3 frames it causes 9 page faults.
The board starts with FIFO and 4 frames. How many faults will there be now? Pick a number in the Your prediction panel before you run.
Run
References and frames
Pages 0 to 9 separated by spaces, up to 20.
Algorithm
FIFO evicts the page loaded longest ago. Hits change nothing.
Your prediction
How many page faults will there be with 4 frames?
The board before the first turn
FIFO evicts the page loaded longest ago. Hits change nothing.
Frames, reference by reference
| Reference | Reference 1:1 | Reference 2:2 | Reference 3:3 | Reference 4:4 | Reference 5:1 | Reference 6:2 | Reference 7:5 | Reference 8:1 | Reference 9:2 | Reference 10:3 | Reference 11:4 | Reference 12:5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 0 | ||||||||||||
| Frame 1 | ||||||||||||
| Frame 2 | ||||||||||||
| Frame 3 | ||||||||||||
| Fault | ||||||||||||
| Out |
FIFO queue
Oldest on the left: it leaves first.
- Empty
What happened this turn
Press Run or step one reference at a time. Here you will see every hit, every fault and which page leaves.
As it runs, watch three moments:
- References 5 and 6 (pages 1 and 2): they are hits. Does the FIFO queue change?
- Reference 7 (page 5): which page leaves? When was it last used?
- References 8 to 12: how many of them hit?
When the run ends, the comparison table appears: the four algorithms with 1 to 6 frames on the same string.
Explain
This stage opens when you run the simulation to the end.
Go to the simulationThe right answer was 10 faults: one more than with 3 frames.
More frames are not always better. This is Belady’s anomaly. With 4 frames, FIFO keeps pages 1 to 4 until page 5 arrives at reference 7. From then on it evicts 1, 2, 3, 4 and 5 just before each one is needed again: references 7 to 12 all fault. The set of pages FIFO keeps with 4 frames does not always include the set it would keep with 3.
FIFO does not look at use. At reference 7 it evicts page 1, used two references earlier, because it was the first one loaded. The hits at references 5 and 6 did not move the queue.
LRU and OPT do not suffer the anomaly. They are stack algorithms: with n + 1 frames they always keep what they would keep with n, plus one more page. On this string LRU goes from 10 to 8 faults and OPT from 7 to 6 when going from 3 to 4 frames.
What each one bets on. FIFO ignores use. LRU assumes the recent past predicts the near future (locality). OPT reads the future, which can only be done after the fact: it is the yardstick, because no algorithm can fault less. On the Classic string with 3 frames: OPT 9, LRU 12, Clock 14, FIFO 15.
Why Clock. Exact LRU would have to record a time or move a list node on every memory access, billions per second. Instead, the hardware sets a use bit in the page-table entry, and Clock only reads and clears those bits when it needs a victim. If every bit is 1, Clock clears them all and behaves like FIFO: that is why it also shows the anomaly on this string.
Faults no one can avoid. The first reference to each page always faults. The Belady string has 5 different pages, so 5 faults is the minimum for any algorithm; with 5 frames or more, they all reach it.
In real systems. Linux approximates LRU with active and inactive page lists driven by the accessed bit, and since version 6.1 it includes the multi-generational LRU (MGLRU). Whether it is on depends on how the kernel was built; it can be switched on or off in /sys/kernel/mm/lru_gen/enabled, and distributions such as Fedora and Arch ship it enabled. Windows trims each process’s working set. All of them approximate LRU; none is FIFO or OPT.
Experiment
This stage opens when you run the simulation to the end.
Go to the simulationUse the board to solve these challenges. Each one has a possible solution when you expand it.
1. Find an algorithm and a frame count where adding a frame adds faults.
FIFO (or Clock) with the Belady string: from 3 to 4 frames, from 9 to 10 faults. Neither keeps, with more frames, everything it kept with fewer.
2. Show that LRU does not suffer the anomaly on this string.
LRU with 1 to 6 frames: 12, 12, 10, 8, 5, 5. It never goes up: LRU is a stack algorithm.
3. Rank the four algorithms on the Classic string with 3 frames.
OPT 9, LRU 12, Clock 14, FIFO 15. Clock’s second chances save it one fault over FIFO; LRU’s exact recency saves three more.
4. Make all four algorithms fault the same number of times on Belady.
With 5 or 6 frames, they all have 5 faults. Every page fits and only the unavoidable faults remain.
Check
This stage opens when you run the simulation to the end.
Go to the simulationGo deeper
- Working sets and thrashing: what happens when a process has fewer frames than the pages it actively uses.
- Enhanced Clock with the dirty bit: prefer clean pages, which do not have to be written to disk before eviction.
- Linux active and inactive lists and MGLRU, in detail.
- Stack algorithms: why the inclusion property makes Belady’s anomaly impossible.
Further reading:
- Belady, “A study of replacement algorithms for a virtual-storage computer”, IBM Systems Journal 5(2), 1966.
- Belady, Nelson and Shedler, “An anomaly in space-time characteristics of certain programs running in a paging machine”, Communications of the ACM 12(6), 1969.
- Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, ch. 22. Free online.
- Silberschatz, Galvin and Gagne, Operating System Concepts, 10th ed., section 10.4.
- Linux kernel documentation, Multi-Gen LRU: docs.kernel.org.