When a program asks for a page that isn't in memory, that's a page fault, and if every frame is full the operating system has to evict one. Which page it evicts is the page replacement algorithm. Exam questions give a reference string and a number of frames and ask for the number of faults; this page works the classic example through the three algorithms every course covers.
The example (from Silberschatz's Operating System Concepts): 3 frames, reference string
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
| Algorithm | Page faults | Hits |
|---|---|---|
| FIFO | 15 | 5 |
| LRU | 12 | 8 |
| Optimal | 9 | 11 |
The first three references always fault (the frames start empty) whatever the algorithm; the differences start at the fourth.
FIFO: evict the page that arrived first
FIFO keeps a queue in load order and evicts the oldest page, even if it was just used. Frames keep their slots: a new page goes into the victim's frame.
| Step | Page | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|---|
| 1 | 7 | 7 | – | – | fault |
| 2 | 0 | 7 | 0 | – | fault |
| 3 | 1 | 7 | 0 | 1 | fault |
| 4 | 2 | 2 | 0 | 1 | fault, evict 7 |
| 5 | 0 | 2 | 0 | 1 | hit |
| 6 | 3 | 2 | 3 | 1 | fault, evict 0 |
| 7 | 0 | 2 | 3 | 0 | fault, evict 1 |
| 8 | 4 | 4 | 3 | 0 | fault, evict 2 |
| 9 | 2 | 4 | 2 | 0 | fault, evict 3 |
| 10 | 3 | 4 | 2 | 3 | fault, evict 0 |
| 11 | 0 | 0 | 2 | 3 | fault, evict 4 |
| 12 | 3 | 0 | 2 | 3 | hit |
| 13 | 2 | 0 | 2 | 3 | hit |
| 14 | 1 | 0 | 1 | 3 | fault, evict 2 |
| 15 | 2 | 0 | 1 | 2 | fault, evict 3 |
| 16 | 0 | 0 | 1 | 2 | hit |
| 17 | 1 | 0 | 1 | 2 | hit |
| 18 | 7 | 7 | 1 | 2 | fault, evict 0 |
| 19 | 0 | 7 | 0 | 2 | fault, evict 1 |
| 20 | 1 | 7 | 0 | 1 | fault, evict 2 |
Look at step 6: page 3 evicts 0, the oldest page, even though 0 was used one step earlier, and 0 faults straight back in at step 7. FIFO ignores how recently a page was used, which is why it does worst here.
LRU: evict the least recently used page
LRU evicts the page whose last use is furthest in the past. It approximates "evict what you won't need soon" by assuming the recent past predicts the near future.
| Step | Page | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|---|
| 1 | 7 | 7 | – | – | fault |
| 2 | 0 | 7 | 0 | – | fault |
| 3 | 1 | 7 | 0 | 1 | fault |
| 4 | 2 | 2 | 0 | 1 | fault, evict 7 |
| 5 | 0 | 2 | 0 | 1 | hit |
| 6 | 3 | 2 | 0 | 3 | fault, evict 1 |
| 7 | 0 | 2 | 0 | 3 | hit |
| 8 | 4 | 4 | 0 | 3 | fault, evict 2 |
| 9 | 2 | 4 | 0 | 2 | fault, evict 3 |
| 10 | 3 | 4 | 3 | 2 | fault, evict 0 |
| 11 | 0 | 0 | 3 | 2 | fault, evict 4 |
| 12 | 3 | 0 | 3 | 2 | hit |
| 13 | 2 | 0 | 3 | 2 | hit |
| 14 | 1 | 1 | 3 | 2 | fault, evict 0 |
| 15 | 2 | 1 | 3 | 2 | hit |
| 16 | 0 | 1 | 0 | 2 | fault, evict 3 |
| 17 | 1 | 1 | 0 | 2 | hit |
| 18 | 7 | 1 | 0 | 7 | fault, evict 2 |
| 19 | 0 | 1 | 0 | 7 | hit |
| 20 | 1 | 1 | 0 | 7 | hit |
At step 6, page 3 replaces 1, not 0: 0 was used at step 5, 2 at step 4, and 1 not since step 3. That single better choice saves the fault FIFO took at step 7.
Optimal: evict the page used furthest in the future
Optimal (also called OPT or MIN) looks ahead and evicts the page that won't be needed for the longest time, or never again. It gives the fewest possible faults but needs the future, so it can't be built in a real OS; it's the benchmark the others are measured against.
| Step | Page | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|---|
| 1 | 7 | 7 | – | – | fault |
| 2 | 0 | 7 | 0 | – | fault |
| 3 | 1 | 7 | 0 | 1 | fault |
| 4 | 2 | 2 | 0 | 1 | fault, evict 7 |
| 5 | 0 | 2 | 0 | 1 | hit |
| 6 | 3 | 2 | 0 | 3 | fault, evict 1 |
| 7 | 0 | 2 | 0 | 3 | hit |
| 8 | 4 | 2 | 4 | 3 | fault, evict 0 |
| 9 | 2 | 2 | 4 | 3 | hit |
| 10 | 3 | 2 | 4 | 3 | hit |
| 11 | 0 | 2 | 0 | 3 | fault, evict 4 |
| 12 | 3 | 2 | 0 | 3 | hit |
| 13 | 2 | 2 | 0 | 3 | hit |
| 14 | 1 | 2 | 0 | 1 | fault, evict 3 |
| 15 | 2 | 2 | 0 | 1 | hit |
| 16 | 0 | 2 | 0 | 1 | hit |
| 17 | 1 | 2 | 0 | 1 | hit |
| 18 | 7 | 7 | 0 | 1 | fault, evict 2 |
| 19 | 0 | 7 | 0 | 1 | hit |
| 20 | 1 | 7 | 0 | 1 | hit |
At step 8, page 4 evicts 0: 2 is next needed at step 9 and 3 at step 10, but 0 not until step 11. Ties (two pages never used again) go to the page loaded first, the usual exam convention.
Belady's anomaly: more frames, more faults
You'd expect more frames to mean fewer faults. For FIFO that isn't guaranteed. With the reference string
1 2 3 4 1 2 5 1 2 3 4 5
FIFO gives 9 faults with 3 frames but 10 with 4 frames. LRU and Optimal are stack algorithms: the pages held with n frames are always a subset of those held with n + 1, so they can never show the anomaly. For the textbook string above, LRU faults fall 20, 17, 12, 8, 7 as frames go from 1 to 5, while FIFO goes 20, 15, 15, 10, 9.
Common mistakes
- Counting the first loads as hits. Filling an empty frame is still a page fault.
- Updating LRU order only on faults. A hit makes that page the most recently used.
- Evicting by position instead of age in FIFO. The victim is the page that has been in memory longest, which cycles through the frames in turn.
- Looking backwards in Optimal. It uses the next use of each page, not the last.
Check your own answers
The page replacement calculator runs FIFO, LRU, Optimal, LFU, MFU and Second Chance (Clock) on any reference string, prints the frame table with a reason for every step, and plots faults against frame count so you can spot Belady's anomaly. For the rest of the memory-management unit, see first fit, best fit and worst fit and cache mapping.
Use the CPU Scheduling Calculator to trace CPU scheduling as another operating systems exercise.