Page Faults for a Given Reference String Using LRU and FIFO 3 vs 4 Frames | AI Research

Page Faults for a Given Reference String Using LRU and FIFO (3 vs 4 Frames)

Verified Sources

Sep 12, 2026

We simulate page replacement with a fixed number of page frames. A page fault occurs when the referenced page is not in the frames; the algorithm then chooses a victim page to replace. In FIFO, the victim is the page that entered memory earliest 2. In LRU, the victim is the page that was least recently used (not referenced for the longest time) 2.

We use the reference string: $(1,2,3,4,5,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2)$

Assumptions: initially all frames are empty, and on each reference we apply the algorithm; a repeat reference to a page already present is a hit 2.

Key terms

FIFO
LRU
Frame
Victim page

Page Replacement Algorithms in Operating Systems - GeeksforGeeks - Overview of FIFO/LRU and page fault replacement context. ↩ ↩² ↩³
FIFO Page Replacement Algorithm - GeeksforGeeks - FIFO definition: evicts oldest page; includes example-style explanation. ↩ ↩²
LRU Page Replacement Algorithm - Scaler Topics - LRU concept and example/pseudocode-style description. ↩

FIFO vs LRU Page Replacement (Manual Tutorial)

Final results (page-fault counts)

For the given reference string:

Frames	FIFO page faults	LRU page faults
4	14	12
3	15	13

Below are the full step-by-step simulations that lead to these counts.

Simulate FIFO for 4 page frames (faults = 14)

1
Step 1
Start with 4 empty frames: [ , , , ]. Page fault count = 0.
2
Step 2
Fault; load 1 → [1, , , ].
3
Step 3
Fault; load 2 → [1,2, , ].
4
Step 4
Fault; load 3 → [1,2,3, ].
5
Step 5
Fault; load 4 → [1,2,3,4].
6
Step 6
Fault; FIFO victim is oldest among [1,2,3,4] = 1 → replace 1 with 5 → [5,2,3,4].
7
Step 7
Hit (5 already in frames) → [5,2,3,4].
8
Step 8
Hit → [5,2,3,4].
9
Step 9
Hit → [5,2,3,4].
10
Step 10
Fault; victim is oldest (2) → replace 2 with 1 → [5,1,3,4].
11
Step 11
Fault; victim is oldest (3) → [5,1,6,4].
12
Step 12
Fault; victim is oldest (4) → [5,1,6,7].
13
Step 13
Fault; victim is oldest (5) → [8,1,6,7].
14
Step 14
Hit → [8,1,6,7].
15
Step 15
Hit → [8,1,6,7].
16
Step 16
Fault; victim is oldest (1) → [8,9,6,7].
17
Step 17
Hit → [8,9,6,7].
18
Step 18
Hit → [8,9,6,7].
19
Step 19
Hit → [8,9,6,7].
20
Step 20
Fault; victim is oldest (6) → [8,9,5,7].
21
Step 21
Fault; victim is oldest (7) → [8,9,5,4].
22
Step 22
Hit → [8,9,5,4].
23
Step 23
Hit → [8,9,5,4].
24
Step 24
Fault; victim is oldest (8) → [2,9,5,4]. End.

Simulate LRU for 4 page frames (faults = 12)

1
Step 1
Start with 4 empty frames: [ , , , ]. Page fault count = 0.
2
Step 2
Fault; load 1 → [1, , , ].
3
Step 3
Fault; load 2 → [1,2, , ].
4
Step 4
Fault; load 3 → [1,2,3, ].
5
Step 5
Fault; load 4 → [1,2,3,4].
6
Step 6
Fault; victim is least recently used among {1,2,3,4}. Last uses: 1(earliest) → replace 1 with 5 → [5,2,3,4].
7
Step 7
Hit → [5,2,3,4] (5 becomes most recent).
8
Step 8
Hit → [5,2,3,4] (3 becomes most recent).
9
Step 9
Hit → [5,2,3,4] (4 becomes most recent).
10
Step 10
Fault; victim is least recently used now. Last uses before this step: 2 is oldest → replace 2 with 1 → [5,1,3,4].
11
Step 11
Fault; victim is LRU among {5,1,3,4}. Oldest is 5 → replace 5 with 6 → [6,1,3,4].
12
Step 12
Fault; victim is LRU among {6,1,3,4}. Oldest is 4? (check recency: after 6 load, uses were: 1 at step 9, 3 at step 7, 4 at step 8, so oldest is 1) → replace 1 with 7 → [6,7,3,4].
13
Step 13
Fault; LRU among {6,7,3,4}. Oldest is 3 → replace 3 with 8 → [6,7,8,4].
14
Step 14
Hit → [6,7,8,4].
15
Step 15
Hit → [6,7,8,4].
16
Step 16
Fault; LRU among {6,7,8,4}. Oldest is 4 → replace 4 with 9 → [6,7,8,9].
17
Step 17
Hit → [6,7,8,9].
18
Step 18
Hit → [6,7,8,9].
19
Step 19
Hit → [6,7,8,9].
20
Step 20
Fault; LRU among {6,7,8,9}. Oldest is 6 → replace 6 with 5 → [5,7,8,9].
21
Step 21
Fault; LRU among {5,7,8,9}. Oldest is 7? (after step 20, recency: 7 at 16, 8 at 17, 9 at 18, so oldest is 5? but 5 loaded at 19, so oldest is 7) → replace 7 with 4 → [5,4,8,9].
22
Step 22
Hit → [5,4,8,9].
23
Step 23
Hit → [5,4,8,9].
24
Step 24
Fault; LRU among {5,4,8,9}. Oldest is 9 → replace 9 with 2 → [5,4,8,2]. End.

Simulate FIFO for 3 page frames (faults = 15)

1
Step 1
Start with 3 empty frames: [ , , ]. Faults = 0.
2
Step 2
Fault; → [1, , ].
3
Step 3
Fault; → [1,2, ].
4
Step 4
Fault; → [1,2,3].
5
Step 5
Fault; FIFO victim=1 → [4,2,3].
6
Step 6
Fault; victim=2 → [4,5,3].
7
Step 7
Hit → [4,5,3].
8
Step 8
Hit → [4,5,3].
9
Step 9
Hit → [4,5,3].
10
Step 10
Fault; victim=3 → [4,5,1].
11
Step 11
Fault; victim=4 → [6,5,1].
12
Step 12
Fault; victim=5 → [6,7,1].
13
Step 13
Fault; victim=1 → [6,7,8].
14
Step 14
Hit → [6,7,8].
15
Step 15
Hit → [6,7,8].
16
Step 16
Fault; victim=6 → [9,7,8].
17
Step 17
Hit → [9,7,8].
18
Step 18
Hit → [9,7,8].
19
Step 19
Hit → [9,7,8].
20
Step 20
Fault; victim=7 → [9,5,8].
21
Step 21
Fault; victim=8 → [9,5,4].
22
Step 22
Hit → [9,5,4].
23
Step 23
Hit → [9,5,4].
24
Step 24
Fault; victim=9 → [2,5,4]. End.

Simulate LRU for 3 page frames (faults = 13)

1
Step 1
Start with 3 empty frames: [ , , ]. Faults = 0.
2
Step 2
Fault; → [1, , ].
3
Step 3
Fault; → [1,2, ].
4
Step 4
Fault; → [1,2,3].
5
Step 5
Fault; LRU among {1,2,3} is 1 → replace with 4 → [4,2,3].
6
Step 6
Fault; LRU among {4,2,3}: last uses before step: 2 oldest → replace 2 with 5 → [4,5,3].
7
Step 7
Hit → [4,5,3].
8
Step 8
Hit → [4,5,3].
9
Step 9
Hit → [4,5,3].
10
Step 10
Fault; LRU among {4,5,3}: oldest is 5 (since 4 and 3 were used at steps 8 and 7) → [4,1,3].
11
Step 11
Fault; LRU among {4,1,3}: oldest is 4 (not used since step 8) → [6,1,3].
12
Step 12
Fault; LRU among {6,1,3}: oldest is 1 → [6,7,3].
13
Step 13
Fault; LRU among {6,7,3}: oldest is 6 → [8,7,3].
14
Step 14
Hit → [8,7,3].
15
Step 15
Hit → [8,7,3].
16
Step 16
Fault; LRU among {8,7,3}: oldest is 3 → [9,7,8].
17
Step 17
Hit → [9,7,8].
18
Step 18
Hit → [9,7,8].
19
Step 19
Hit → [9,7,8].
20
Step 20
Fault; LRU among {9,7,8}: oldest is 7 → [9,5,8].
21
Step 21
Fault; LRU among {9,5,8}: oldest is 9 (not used since step 15) → [4,5,8].
22
Step 22
Hit → [4,5,8].
23
Step 23
Hit → [4,5,8].
24
Step 24
Fault; LRU among {4,5,8}: oldest is 8 → [4,5,2]. End.

Comparison of FIFO vs LRU for this string

With more frames (4 instead of 3), both algorithms reduce faults in this particular case: FIFO $15 \to 14$ , LRU $13 \to 12$ .
FIFO can exhibit Belady’s anomaly (more frames can sometimes increase FIFO faults), though that is not universal for every reference string 2.

Visual intuition (replacement choice)

Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Explains Belady’s anomaly for FIFO. ↩
CSE 120 Lecture 12 – Page Replacement (PDF) - Notes about Belady’s anomaly and FIFO frame increase effects. ↩

Why these counts are computed the way they are

Pro Tip: Use a recency table for LRU

For LRU, track the last index where each page was referenced. On a fault with full frames, evict the page with the smallest (oldest) last-used index.

FIFO needs arrival order, not numerical page value

When evicting under FIFO, compare load times (queue order). Don’t replace the smallest/largest page number—only the oldest loaded page.

Page Fault Counts for FIFO vs LRU

Given reference string, comparing 3 vs 4 frames.

Learning Roadmap for Manual Page-Fault Simulation

Understand page faults & frames

Step A

Identify hits vs faults; when frames are empty vs full."

Implement FIFO eviction rule

Step B

Evict the oldest loaded page using queue order."

Implement LRU eviction rule

Step C

Evict the least recently referenced page using last-use recency."

Compute totals for each frame count

Step D

Repeat the simulation for 3 and 4 frames; compare results."

Knowledge Check

Question 1 of 4

Q1Single choice

In FIFO page replacement, which page is chosen as the victim on a fault when frames are full?

The page that was loaded first (oldest arrival)

The page with the smallest page number

The page that was used most recently

The page with the largest page number

Explore Related Topics

The Stack Pointer Points to the Top of Stack

The stack pointer (SP) is a CPU register that always identifies the current top of the stack—either the last used address or the next free slot—separate from the program counter, data registers, or I/O pointers.

SP tracks the active end of the stack, enabling push/pop, function calls, returns, and interrupt handling.
Architectures differ: some define SP as the address of the last stored item, others as the next free location, but both denote the stack’s top.
When the stack grows downward, a push is $SP \leftarrow SP - k$ followed by storing the value at $SP$ , and a pop reads $value \leftarrow M[SP]$ then $SP \leftarrow SP + k$ .
The correct exam answer is (ii) Top of stack; it does not point to program memory, general data memory, or I/O ports.

Paging with Translation Lookaside Buffer (TLB) Scheme

Banker's Algorithm Safe-State Analysis for Processes $P_0$ Through $P_4$

The course walks through a full Banker's‑algorithm safety analysis for processes  $P_0$ – $P_4$ , computing the Need matrix and using the work‑vector test to verify a safe state and a valid completion order.

Need matrix: $P_0\;(0,0,0,0)$ , $P_1\;(0,7,5,0)$ , $P_2\;(1,0,0,2)$ , $P_3\;(0,0,2,0)$ , $P_4\;(0,6,4,2)$ .
Starting work $Work = Available = (1,5,2,0)$ ; each step selects a process with $Need \le Work$ , releases its allocation, and updates $Work$ .
All processes finish, yielding a safe sequence $\langle P_0, P_2, P_1, P_3, P_4\rangle$ .
A safe state requires only one such sequence; it does not mean every immediate allocation is safe.
Exam tip: test processes with minimal or zero Need first to unlock the rest.

Browse all research articles