---
title: "Page faults: LRU, FIFO, Optimum"
subject: "Operating System"
chapter: 4
key: "semester_6/operating_system:page-faults-lru-fifo-optimum"
source: https://www.bctengineer.com/q/semester_6/operating_system/page-faults-lru-fifo-optimum
site: BCT Engineering
---

# Page faults: LRU, FIFO, Optimum

Operating System · Chapter 4: Memory Management

- Asked in: 2072 Magh, 2+8 marks
- Video: [Lec29 Page Replacement Algorithms | LRU and optimal | Operating Systems](https://www.youtube.com/watch?v=DXU7SqsYDvg) — Jenny's Lectures CS IT
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/page-faults-lru-fifo-optimum
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4

## Question

What is page fault? Consider the following page reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. How many page faults would occur in LRU, FIFO and Optimum replacement algorithm?

## Short answer

A page fault is a trap when a page is not in memory. With three frames, LRU causes 15 faults, FIFO 16, and Optimal 11.

## Answer

#### Page fault
A **page fault** is a trap raised when a process refers to a page that is not in main memory. The OS reads the page from disk into a free frame (using a replacement algorithm if no frame is free) and restarts the instruction.

#### Simulation
Reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 (20 references). The number of frames is not stated; **three frames** are assumed (all initially empty). `*` = fault.

**LRU**
```text
ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2
F2   - 2 2 2 2 2 2 6 6 6 6 3 3 3 3 3 3 3 3 3
F3   - - 3 3 3 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6
     * * * *   * * * * *   * * *   * *     *
```
Faults = 15.

**FIFO**
```text
ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6
F2   - 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1
F3   - - 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3
     * * * *   * * * * *   * * *   * *   * *
```
Faults = 16.

**Optimum**
```text
ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 6
F2   - 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2
F3   - - 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 1
     * * * *     * *       * *     * *     *
```
Faults = 11.

#### Result
| Frames | LRU | FIFO | Optimum |
|---|---|---|---|
| 3 (assumed) | 15 | 16 | 11 |
| 4 | 10 | 14 | 8 |
| 5 | 8 | 10 | 7 |

**Answer (3 frames): LRU = 15, FIFO = 16, Optimum = 11 page faults.** Optimum is always the lowest; with more frames faults reduce.

## Check yourself

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

1. What is a page fault?
   A. Disk error
   B. Reference to a page not in main memory
   C. Invalid opcode
   D. Cache miss
   Answer: B. OS loads the page and restarts. (Key point: Page fault)

2. With 3 frames faults for LRU, FIFO, Optimum?
   A. 15, 16, 11
   B. 13, 13, 13
   C. 11, 15, 16
   D. 16, 15, 11
   Answer: A. Optimum is lowest. (Key point: 3-frame results)

3. Which algorithm always has fewest faults?
   A. Optimum
   B. All equal
   C. FIFO
   D. LRU
   Answer: A. It uses future knowledge. (Key point: Optimum lowest)

4. With more frames, usually?
   A. Faults decrease
   B. Faults always increase
   C. Doubled
   D. Unchanged
   Answer: A. Here LRU: 15, 10, 8 for 3, 4, 5 frames. (Key point: More frames)

## 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×
- [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
- [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
- [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 fault; allocation and replacement](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-allocation-replacement) — 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