Skip to main content

Hits and faults: FIFO, LRU, Optimal

Short answer

With 3 frames, FIFO yields 8 page faults and 2 hits; LRU yields 8 faults and 2 hits; Optimal yields 7 faults and 3 hits.

Calculate Hit and Faults using various page replacement algorithm policies (FIFO, LRU, Optimal) for the following page sequence (The page frame size is 3). 2 3 5 4 2 5 7 3 8 7

Reference string: 2 3 5 4 2 5 7 3 8 7 (10 references), 3 frames, initially empty. * marks a fault (miss); blank is a hit.

FIFO (replace the oldest page)

ref  2 3 5 4 2 5 7 3 8 7
F1   2 2 2 4 4 4 4 3 3 3
F2   - 3 3 3 2 2 2 2 8 8
F3   - - 5 5 5 5 7 7 7 7
     * * * * *   * * *

Faults = 8, hits = 2 (the second 5 and the second 7).

LRU (replace the least recently used page)

ref  2 3 5 4 2 5 7 3 8 7
F1   2 2 2 4 4 4 7 7 7 7
F2   - 3 3 3 2 2 2 3 3 3
F3   - - 5 5 5 5 5 5 8 8
     * * * * *   * * *

Faults = 8, hits = 2.

Optimal (replace the page not needed for the longest time)

ref  2 3 5 4 2 5 7 3 8 7
F1   2 2 2 2 2 2 7 7 7 7
F2   - 3 3 4 4 4 4 3 8 8
F3   - - 5 5 5 5 5 5 5 5
     * * * *     * * *

Faults = 7, hits = 3 (2, 5 and the final 7). At the reference 7 (position 7), the pages 2, 4 and 5 are in memory and none of them is used again, so any of them may be replaced (2 is taken here).

Summary

AlgorithmPage faultsHitsHit ratio
FIFO8220%
LRU8220%
Optimal7330%

Answer: FIFO 8 faults/2 hits, LRU 8 faults/2 hits, Optimal 7 faults/3 hits.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 4 questions →