---
title: "LRU algorithm; page faults on string"
subject: "Operating System"
chapter: 4
key: "semester_6/operating_system:lru-page-faults-ref-string"
source: https://www.bctengineer.com/q/semester_6/operating_system/lru-page-faults-ref-string
site: BCT Engineering
---

# LRU algorithm; page faults on string

Operating System · Chapter 4: Memory Management

- Asked in: 2068 Magh, 2+6 marks
- Video: [L-5.25: Least Recently Used  Page Replacement Algorithm | Operating System](https://www.youtube.com/watch?v=dYIoWkCvd6A) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/lru-page-faults-ref-string
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4

## Question

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

## 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%).

## Answer

#### 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.

```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which page does LRU replace?
   A. The page used least often
   B. The page that arrived first
   C. The page needed farthest in future
   D. The page unused for the longest time in the past
   Answer: D. LRU uses recency, relying on locality of reference. (Key point: LRU definition)

2. Does LRU suffer Belady's anomaly?
   A. Only with 3 frames
   B. Only with large strings
   C. No, it is a stack algorithm
   D. Yes, always
   Answer: C. Stack algorithms never get more faults with more frames. (Key point: Belady)

3. With 3 frames, how many faults occur for the string?
   A. 15
   B. 13
   C. 20
   D. 7
   Answer: B. 13 faults and 7 hits. (Key point: Fault count)

4. What is the hit ratio?
   A. 20%
   B. 13/20 = 65%
   C. 7/13
   D. 7/20 = 35%
   Answer: D. Hits = 20 - 13 = 7. (Key point: Hit ratio)

## Related in Operating System

- [Page faults with 3 frames: LRU, FIFO, OPT](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-circumstances-lru-fifo-optimal) — Operating System, chapter 4, asked 2×
- [Page faults: FIFO, Optimal, LFU, LRU](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-fifo-optimal-lfu-lru-5frames) — Operating System, chapter 4, asked 2×
- [Thrashing; page faults on 3 frames](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Athrashing-page-faults-fifo-opt-lru-lfu) — Operating System, chapter 4
- [Page faults: LRU, FIFO, Optimum](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-lru-fifo-optimum) — Operating System, chapter 4
- [Hits and faults: FIFO, LRU, Optimal](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ahits-faults-fifo-lru-optimal-3frames) — Operating System, chapter 4