---
title: "Hits and faults: FIFO, LRU, Optimal"
subject: "Operating System"
chapter: 4
key: "semester_6/operating_system:hits-faults-fifo-lru-optimal-3frames"
source: https://www.bctengineer.com/q/semester_6/operating_system/hits-faults-fifo-lru-optimal-3frames
site: BCT Engineering
---

# Hits and faults: FIFO, LRU, Optimal

Operating System · Chapter 4: Memory Management

- Asked in: 2070 Bhadra, 2+6 marks
- Video: [FIFO | LRU | OPTIMAL PAGE REPLACEMENT ALGORITHMS | OPERATING SYSTEM | OS](https://www.youtube.com/watch?v=mgIzXoIViCQ) — Perfect Computer Engineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/hits-faults-fifo-lru-optimal-3frames
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4

## Question

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

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

## Answer

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)
```text
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)
```text
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)
```text
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
| Algorithm | Page faults | Hits | Hit ratio |
|---|---|---|---|
| FIFO | 8 | 2 | 20% |
| LRU | 8 | 2 | 20% |
| Optimal | 7 | 3 | 30% |

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

## Check yourself

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

1. FIFO on 2 3 5 4 2 5 7 3 8 7 with 3 frames gives?
   A. 8 faults, 2 hits
   B. 7 faults, 3 hits
   C. 9 faults, 1 hit
   D. 6 faults, 4 hits
   Answer: A. Hits are the second 5 and the second 7. (Key point: FIFO result)

2. Optimal gives how many faults?
   A. 9
   B. 6
   C. 8
   D. 7
   Answer: D. Optimal gets 3 hits: 2, 5 and the last 7. (Key point: Optimal result)

3. What does Optimal replace?
   A. The oldest page
   B. The most recent page
   C. The page not needed for the longest time ahead
   D. The least recently used
   Answer: C. It looks at future references. (Key point: Optimal rule)

4. Hit ratio of LRU here?
   A. 80%
   B. 30%
   C. 10%
   D. 20%
   Answer: D. 2 hits out of 10. (Key point: Hit ratios)

## Related in Operating System

- [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×
- [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: LRU, FIFO, Optimum](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-lru-fifo-optimum) — Operating System, chapter 4
- [LRU algorithm; page faults on string](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Alru-page-faults-ref-string) — Operating System, chapter 4
- [Race condition; optimal page replacement limits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-optimal-limitation) — Operating System, chapter 3
- [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

## Related in other subjects

- [LRU replacement with hit and miss](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Alru-replacement) — Computer Organization and Architecture, chapter 6
- [Cache replacement policies](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-replacement-policies) — Embedded System, chapter 4