6.2Page replacement: FIFO, LRU and Optimal
The idea
When all frames are full a replacement policy picks a victim: FIFO, LRU or Optimal.
Think of it like this: A small desk: when it is full you remove either the paper that has been there longest (FIFO), the one you have not touched for longest (LRU), or the one you will not need for longest (OPT).
Why it exists
The policy decides how many faults you suffer, and each fault costs about a million times a memory access.
How it works
- Write the reference string; one column per reference.
- Hit: page already in a frame. Fault: bring it in.
- If a frame is free use it, otherwise evict by the policy: FIFO oldest loaded, LRU least recently used, OPT farthest next use.
- Count the faults.
Worked example: String 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, 3 frames
FIFO 15 faults, LRU 12, Optimal 9. OPT is the lower bound for any policy.
Now play with it
- →Switch the policy between FIFO, LRU and OPT and compare the fault counts.
- →Add more frames and watch faults drop (for these policies).
| ref | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| frame 1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 |
| frame 2 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | |
| frame 3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | ||
| fault? | F | F | F | F | hit | F | F | F | F | F | F | hit | hit | F | F | hit | hit | F | F | F |
Faults with 1 to 7 frames using this policy and string:
| 1 frame | 2 frames | 3 frames | 4 frames | 5 frames | 6 frames | 7 frames |
|---|---|---|---|---|---|---|
| 20 | 15 | 15 | 10 | 9 | 6 | 6 |
A red number means more frames caused more faults: Belady's anomaly. It can happen with FIFO, never with LRU or OPT (stack algorithms). Try the Belady preset with FIFO.
Check yourself
Which policy has the fewest page faults on any reference string with a given number of frames?
Exam notes (the dense version)
When no frame is free, a policy picks the victim. FIFO: evict the page that has been in memory longest. LRU: evict the page not used for the longest time (good approximation of the future, costly to implement exactly; hardware uses reference bits, the clock / second-chance algorithm). Optimal (OPT): evict the page used farthest in the future: the minimum possible faults, but impossible in practice, so it is the benchmark. To count faults draw one column per reference and mark hits and faults.
Previous year questions: Virtual Memory (9)
PYQs are grouped by topic, so this is the full set for Virtual Memory; try the ones that match this subtopic. Open all 9 on the topic page.