CoursifyCoursify

Page Replacement Analysis: FIFO vs LRU for a 4-Frame Reference String

Page Replacement Analysis: FIFO vs LRU for a 4-Frame Reference String

Verified Sources
May 27, 2026

In virtual memory systems, a page replacement policy is invoked when a page fault occurs and all available page frames are occupied. The objective is to minimize faults, because each fault may require disk I/O and significantly slow execution.2

This section evaluates the reference string

1,3,4,4,3,2,1,7,5,6,4,2,1,21, 3, 4, 4, 3, 2, 1, 7, 5, 6, 4, 2, 1, 2

for a main memory of 4 frames under two classic policies:

  • FIFO
  • LRU

We will compute the total number of page faults for each policy, compare them, and explain why one is better for this workload. In general, FIFO is simple but may evict pages that are still useful, while LRU attempts to exploit temporal locality by keeping recently referenced pages in memory longer.2

A key result of this analysis is that LRU produces fewer page faults than FIFO for the given string, so LRU is the better policy in this case.2

Footnotes

  1. Page replacement algorithm - Wikipedia - Overview of page replacement, page faults, FIFO, and virtual memory concepts. ↩

  2. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩ ↩2 ↩3

  3. Page Replacement in OS - Scaler Topics - Educational explanation of LRU and locality of reference. ↩

  4. Day 20: Page Replacement Algorithms - Exploring Operating Systems - Discusses page-fault rate as a core metric for comparing replacement policies. ↩

FIFO vs Optimal vs LRU Page Replacement Algorithms Comparison with Example | Operating Systems

Final Answer in One Line

For 4 page frames and the reference string 1,3,4,4,3,2,1,7,5,6,4,2,1,21,3,4,4,3,2,1,7,5,6,4,2,1,2, LRU is better because it causes 99 page faults, while FIFO causes 1010 page faults.2

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

  2. Day 20: Page Replacement Algorithms - Exploring Operating Systems - Discusses page-fault rate as a core metric for comparing replacement policies. ↩

FIFO Simulation for 4 Frames

  1. 1
    Step 1

    Start with 4 empty frames. The first distinct references must all cause page faults because nothing is loaded yet.

    Footnotes

    1. Page replacement algorithm - Wikipedia - Overview of page replacement, page faults, FIFO, and virtual memory concepts. ↩

  2. 2
    Step 2

    References 11, 33, and 44 each produce a fault. After that, memory contains [1,3,4,−][1,3,4,-]. The second reference to 44 and the next reference to 33 are hits.

  3. 3
    Step 3

    Reference 22 causes a fault, giving memory [1,3,4,2][1,3,4,2]. At this point, memory is full.

  4. 4
    Step 4

    Reference 11 is a hit, so FIFO order does not change. FIFO cares about arrival time, not recent use.

    Footnotes

    1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

  5. 5
    Step 5

    Reference 77 is a fault. The oldest loaded page is 11, so FIFO evicts 11. Memory becomes [7,3,4,2][7,3,4,2].

  6. 6
    Step 6

    Reference 55 is a fault. The oldest remaining page is 33, so memory becomes [7,5,4,2][7,5,4,2].

  7. 7
    Step 7

    Reference 66 is a fault. The oldest remaining page is 44, so memory becomes [7,5,6,2][7,5,6,2].

  8. 8
    Step 8

    Reference 44 is now a fault because FIFO previously removed it. The oldest page is 22, so memory becomes [7,5,6,4][7,5,6,4].

  9. 9
    Step 9

    Reference 22 is a fault. FIFO removes 77, producing memory [2,5,6,4][2,5,6,4].

  10. 10
    Step 10

    Reference 11 is a fault. FIFO removes 55, producing memory [2,1,6,4][2,1,6,4]. The final reference to 22 is a hit. Total FIFO page faults: 1010.

FIFO reference trace

The following table shows the state transition for FIFO. A hit means the page is already resident; a fault means a replacement may be needed once memory is full.2

StepReferenceFrames after referenceResult
11[1, -, -, -]Fault
23[1, 3, -, -]Fault
34[1, 3, 4, -]Fault
44[1, 3, 4, -]Hit
53[1, 3, 4, -]Hit
62[1, 3, 4, 2]Fault
71[1, 3, 4, 2]Hit
87[7, 3, 4, 2]Fault
95[7, 5, 4, 2]Fault
106[7, 5, 6, 2]Fault
114[7, 5, 6, 4]Fault
122[2, 5, 6, 4]Fault
131[2, 1, 6, 4]Fault
142[2, 1, 6, 4]Hit

Therefore,

FIFO page faults=10\text{FIFO page faults} = 10

FIFO is easy to implement with a queue, but it may evict a page simply because it is old, even if it will be used again soon.2

Footnotes

  1. Page replacement algorithm - Wikipedia - Overview of page replacement, page faults, FIFO, and virtual memory concepts. ↩

  2. Day 20: Page Replacement Algorithms - Exploring Operating Systems - Discusses page-fault rate as a core metric for comparing replacement policies. ↩

  3. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

  4. Operating System - Belady's Anomaly - TutorialsPoint - Explains FIFO weakness and Belady's anomaly, contrasted with stack-based algorithms like LRU. ↩

LRU Simulation for 4 Frames

  1. 1
    Step 1

    Start with 4 empty frames. As with FIFO, the first new pages must fault.

    Footnotes

    1. Page replacement algorithm - Wikipedia - Overview of page replacement, page faults, FIFO, and virtual memory concepts. ↩

  2. 2
    Step 2

    The first three distinct references load these pages. The next references to 44 and 33 are hits, and they update recency information.

  3. 3
    Step 3

    Reference 22 faults and fills the fourth frame, giving the set {1,3,4,2}\{1,3,4,2\}.

  4. 4
    Step 4

    Reference 11 is a hit, but it becomes the most recently used page. This matters for future replacement.

  5. 5
    Step 5

    The least recently used page among {1,3,4,2}\{1,3,4,2\} is 44, so LRU evicts 44 and loads 77.

  6. 6
    Step 6

    Among the current pages, 33 is least recently used, so LRU replaces 33 with 55.

  7. 7
    Step 7

    Now 22 is the least recently used, so LRU replaces 22 with 66.

  8. 8
    Step 8

    Reference 44 faults, and 11 is least recently used at that moment, so LRU replaces 11 with 44.

  9. 9
    Step 9

    Reference 22 faults, and 77 is the least recently used, so LRU replaces 77 with 22.

  10. 10
    Step 10

    Reference 11 faults and replaces 55, which is least recently used. The final reference to 22 is a hit. Total LRU page faults: 99.

LRU reference trace

LRU tries to preserve pages with recent access history, reflecting the common operating-system assumption that recent past usage predicts near-future usage reasonably well.2

StepReferenceFrames after referenceResult
11[1, -, -, -]Fault
23[1, 3, -, -]Fault
34[1, 3, 4, -]Fault
44[1, 3, 4, -]Hit
53[1, 3, 4, -]Hit
62[1, 3, 4, 2]Fault
71[1, 3, 4, 2]Hit
87[1, 3, 7, 2]Fault
95[1, 5, 7, 2]Fault
106[1, 5, 7, 6]Fault
114[4, 5, 7, 6]Fault
122[4, 5, 2, 6]Fault
131[4, 1, 2, 6]Fault
142[4, 1, 2, 6]Hit

Hence,

LRU page faults=9\text{LRU page faults} = 9

Since

9<109 < 10

LRU is better than FIFO for this reference string.2

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩ ↩2

  2. Page Replacement in OS - Scaler Topics - Educational explanation of LRU and locality of reference. ↩

  3. Day 20: Page Replacement Algorithms - Exploring Operating Systems - Discusses page-fault rate as a core metric for comparing replacement policies. ↩

Page Fault Comparison for the Given Reference String

Lower is better

Why LRU performs better here

The main reason is locality of reference.2 In the given sequence, some pages are reused after relatively short gaps, and LRU keeps pages that were used recently, whereas FIFO ignores recency and tracks only arrival order.

A particularly important moment occurs after the memory becomes full with pages {1,3,4,2}\{1,3,4,2\}. The next references are:

1,7,5,6,4,2,1,21, 7, 5, 6, 4, 2, 1, 2

Under FIFO, when page 77 arrives, it evicts page 11 because 11 was loaded earliest, even though page 11 had just been used at the previous step. That is a poor eviction choice for this workload.2 LRU, in contrast, evicts page 44 at that moment because 44 is the least recently used among the resident pages, which is more consistent with the observed access pattern.2

This difference illustrates a broader principle:

  • FIFO uses age in memory.
  • LRU uses recent usage history.

For workloads with temporal locality, LRU often outperforms FIFO because recently used pages are more likely to be referenced again soon.3

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩ ↩2 ↩3 ↩4 ↩5

  2. Page Replacement in OS - Scaler Topics - Educational explanation of LRU and locality of reference. ↩ ↩2 ↩3

  3. Operating System - Belady's Anomaly - TutorialsPoint - Explains FIFO weakness and Belady's anomaly, contrasted with stack-based algorithms like LRU. ↩

  4. Chapter 9: Virtual Memory | UTC PDF - Course notes describing FIFO, LRU, page-fault comparisons, and why LRU often outperforms FIFO. ↩

Exam Strategy

When comparing FIFO and LRU on a reference string, do not guess from definitions alone. Build the frame table step by step and count faults exactly. Small differences, such as 1010 vs 99, determine the correct answer.

Common Conceptual Questions

With 44 page frames and reference string 1,3,4,4,3,2,1,7,5,6,4,2,1,21,3,4,4,3,2,1,7,5,6,4,2,1,2, FIFO gives 1010 page faults while LRU gives 99. Therefore, LRU is better because it replaces the least recently used page, which better captures temporal locality in this sequence.2

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

  2. Page Replacement in OS - Scaler Topics - Educational explanation of LRU and locality of reference. ↩

Reasoning Roadmap for Solving Page Replacement Questions

Identify Inputs

Step 1

Extract the frame count and the full reference string."

Simulate FIFO

Step 2

Track frame contents in arrival order and count every fault."

Simulate LRU

Step 3

Track frame contents and update recency after each reference."

Compare Fault Totals

Step 4

The policy with fewer faults is better for that string."

Explain the Cause

Step 5

Relate the result to temporal locality and the replacement rule."

Common Mistake

Do not update FIFO order on a hit. In FIFO, only loading order matters. By contrast, LRU must update recency on every hit and every fault. Confusing these rules changes the answer.

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

Conclusion

For the given page-reference string and 4 available frames:

FIFO faults=10,LRU faults=9\text{FIFO faults} = 10,\qquad \text{LRU faults} = 9

Therefore,

LRU is better than FIFO in this case\boxed{\text{LRU is better than FIFO in this case}}

because LRU uses recent access history and better preserves pages that are likely to be reused soon, while FIFO may evict a recently useful page simply because it has been in memory longer.3

Footnotes

  1. Page replacement (CS 4410, Cornell) - Lecture notes explaining FIFO, LRU, temporal locality, and replacement trade-offs. ↩

  2. Page Replacement in OS - Scaler Topics - Educational explanation of LRU and locality of reference. ↩

  3. Operating System - Belady's Anomaly - TutorialsPoint - Explains FIFO weakness and Belady's anomaly, contrasted with stack-based algorithms like LRU. ↩

Knowledge Check

Question 1 of 5
Q1Single choice

For the reference string 1,3,4,4,3,2,1,7,5,6,4,2,1,21,3,4,4,3,2,1,7,5,6,4,2,1,2 with 44 frames, how many page faults occur under FIFO?

Explore Related Topics

1

Paging with Translation Lookaside Buffer (TLB) Scheme

2

Lexical Analysis and the Main Structure Used: Finite Automata

Lexical analysis relies on finite automata—typically deterministic finite automata (DFA)—to recognize token patterns defined by regular expressions.

  • Regular expressions for identifiers, numbers, etc., are converted to NFAs then to a DFA for fast scanning.
  • The DFA processes the source character by character, tracking a single current state and emitting a token at each accepting state.
  • Queues, stacks, and trees support other compiler phases (parsing, AST construction) but are not the primary model for token recognition.
  • Lexers output a stream of tokens that the parser consumes for syntax analysis.
3

Round Robin Scheduling Analysis for Five Processes with Time Quantum 3 ms

Research more with Coursify
Chat with Kiro