Page replacement: FIFO, LRU and Optimal with a worked example

Difficulty: Advanced

Question

Explain the FIFO, LRU and Optimal page replacement algorithms. For the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames, count the page faults of each.

Answer

When memory is full and a new page must come in, the OS has to pick a victim. The quality of that choice determines the page fault rate, and since a fault costs milliseconds of disk time, it is worth studying the algorithms carefully. All are compared by counting page faults on a reference string for a given number of frames.

FIFO evicts the page that has been in memory the longest. It is trivial to implement with a queue, but it ignores usage: a page that has been loaded early might be heavily used, like a page of code containing a hot loop, and evicting it is costly. It also suffers from Belady's anomaly, which we will discuss in the next question.

Optimal (Belady's OPT, also called MIN) replaces the page that will not be used for the longest time in the future. It gives the lowest possible fault rate, but requires knowing the future, so it cannot be implemented in a real OS. Its value is as a benchmark against which other algorithms are measured.

Least Recently Used (LRU) approximates OPT by looking backwards instead of forwards: evict the page that has not been used for the longest time, on the assumption that the past predicts the future because of locality. It performs well and does not suffer from Belady's anomaly, since it is a stack algorithm. Exact LRU is expensive in hardware or software, needing a timestamp per page or a stack updated on each reference. Real systems use approximations: the clock (second-chance) algorithm with a reference bit, or aging counters.

Now the worked example with 3 frames. The reference string is 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, twenty references.

For FIFO, the sequence of faults is: 7, 0, 1 (three initial faults filling the frames), 2 (evicts 7), 0 is a hit, 3 (evicts 0), 0 (evicts 1), 4 (evicts 2), 2 (evicts 3), 3 (evicts 0), 0 (evicts 4), 3 and 2 are hits, 1 (evicts 2), 2 (evicts 3), 0 and 1 are hits, 7 (evicts 0), 0 (evicts 1), 1 (evicts 2). That totals 15 page faults.

For LRU, the faults are 7, 0, 1 (3), 2 (evicts 7), hit on 0, 3 (evicts 1), hit 0, 4 (evicts 2), 2 (evicts 3), 3 (evicts 0), 0 (evicts 4), hit 3, hit 2, 1 (evicts 0), hit 2, 0 (evicts 3), hit 1, 7 (evicts 2), hit 0, hit 1. That totals 12 page faults.

For Optimal, the faults are 7, 0, 1 (3), 2 (evicts 7, never used again), hit 0, 3 (evicts 1), hit 0, 4 (evicts 0), hit 2, hit 3, 0 (evicts 4), hit 3, hit 2, 1 (evicts 3), hit 2, hit 0, hit 1, 7 (evicts 2), hit 0, hit 1. That totals 9 page faults, the minimum possible.

Results: FIFO 15, LRU 12, OPT 9. Fault rates are 75 percent, 60 percent and 45 percent. Note the first three faults are compulsory (cold-start) misses that no algorithm can avoid. A good sanity check is that OPT is never worse than LRU, and LRU is usually better than FIFO on programs with locality.

Two further practical notes. The clock algorithm arranges frames in a circle with a reference bit: the hand sweeps, clearing bits to give a second chance, and evicts the first page whose bit is already 0. Enhanced clock also considers the dirty bit, preferring to evict clean pages because they need no write-back. Also, Linux uses an approximation of LRU with active and inactive lists rather than exact LRU.

Code examples

Frame-by-frame worked example (3 frames)

Reference: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

FIFO   F = fault, H = hit          frames after each reference
7:F[7]  0:F[7,0]  1:F[7,0,1]  2:F[0,1,2]  0:H  3:F[1,2,3]  0:F[2,3,0]
4:F[3,0,4]  2:F[0,4,2]  3:F[4,2,3]  0:F[2,3,0]  3:H  2:H
1:F[3,0,1]  2:F[0,1,2]  0:H  1:H  7:F[1,2,7]  0:F[2,7,0]  1:F[7,0,1]
Total FIFO faults = 15

LRU
7:F  0:F  1:F  2:F[0,1,2]  0:H  3:F[0,2,3]  0:H  4:F[0,3,4]
2:F[0,4,2]  3:F[4,2,3]  0:F[2,3,0]  3:H  2:H  1:F[2,3,1]  2:H
0:F[2,0,1]  1:H  7:F[7,0,1]  0:H  1:H
Total LRU faults = 12

OPT
7:F  0:F  1:F  2:F[2,0,1]  0:H  3:F[2,0,3]  0:H  4:F[2,4,3]  2:H  3:H
0:F[2,0,3]  3:H  2:H  1:F[2,0,1]  2:H  0:H  1:H  7:F[7,0,1]  0:H  1:H
Total OPT faults = 9

Compulsory misses are the first three loads. OPT looks ahead to evict the page used furthest in the future; LRU looks back; FIFO looks only at load order.

Key points

• FIFO 15, LRU 12, OPT 9 faults for this string with 3 frames.
• OPT is a theoretical lower bound and cannot be implemented.
• LRU is a stack algorithm and is free from Belady's anomaly.
• Clock (second chance) approximates LRU using a reference bit.
• Prefer evicting clean pages, since dirty pages need a disk write first.

Concepts covered

page replacement, FIFO, LRU, Optimal, page fault count