Skip to main content

LRU algorithm; page faults on string

Short answer

LRU replaces the page unused for the longest time, using recent history. For the given reference string with 3 frames, 13 page faults occur (hit rate 35%).

What is LRU algorithm? How many page faults would occur for the following reference string for page frames using LRU algorithm. 1,2,3,4,5,5,3,4,1,6,7,8,7,8,9,5,4,5,4,2

LRU algorithm

LRU (Least Recently Used) replaces the page that has not been used for the longest time. It is based on the idea that pages used recently will be used again soon (locality of reference). It does not suffer from Belady's anomaly (it is a stack algorithm) but needs hardware support (counter or stack) to track the order of use.

Page faults

The number of frames is not given, so three frames are assumed (initially empty). Reference string (20 pages): 1,2,3,4,5,5,3,4,1,6,7,8,7,8,9,5,4,5,4,2.

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

Faults occur at references: 1,2,3,4,5,1,6,7,8,9,5,4,2 = 13 faults; hits = 7.

Answer: 13 page faults with 3 frames (hit ratio 7/20 = 35%).

For other frame counts the same string gives (LRU): 2 frames = 15, 4 frames = 13, 5 frames = 12 faults.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 4 questions →