Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Full Explanation

Introduction

Imagine your computer's memory is full, but it needs to load new information. It must decide which old information to remove to make space. Page replacement algorithms help the computer choose which data to remove when memory is full.

Explanation

FIFO (First-In, First-Out)

This method removes the oldest page in memory first, like a queue where the first item added is the first removed. It does not consider how often or recently a page was used, only the order of arrival. This simplicity can sometimes cause poor choices if old pages are still needed.

FIFO removes the oldest loaded page without considering usage.

LRU (Least Recently Used)

LRU removes the page that has not been used for the longest time, assuming that pages used recently will likely be used again soon. It tracks page usage over time to make smarter decisions. This method often performs better than FIFO but requires more tracking effort.

LRU removes the page that was least recently accessed.

Optimal Page Replacement

This algorithm removes the page that will not be used for the longest time in the future. It gives the best possible performance but requires knowing future requests, which is usually impossible in real life. It is mainly used as a benchmark to compare other algorithms.

Optimal removes the page that won’t be needed for the longest future time.

Real World Analogy

Imagine a small desk with limited space for books. FIFO means you remove the book you placed first, no matter if you still need it. LRU means you remove the book you haven't looked at for the longest time. Optimal means you magically know which book you won't need for the longest time and remove that one.

FIFO (First-In, First-Out) → Removing the oldest book placed on the desk first, regardless of use.

LRU (Least Recently Used) → Removing the book you haven't read or looked at for the longest time.

Optimal Page Replacement → Removing the book you know you won’t need for the longest time in the future.

Diagram

Diagram

┌───────────────┐
│ Memory Frames │
├───────────────┤
│ FIFO          │
│ ┌───────────┐ │
│ │ Oldest    │ │
│ │ page out  │ │
│ └───────────┘ │
├───────────────┤
│ LRU           │
│ ┌───────────┐ │
│ │ Least     │ │
│ │ recently  │ │
│ │ used page │ │
│ └───────────┘ │
├───────────────┤
│ Optimal       │
│ ┌───────────┐ │
│ │ Future    │ │
│ │ longest   │ │
│ │ unused    │ │
│ │ page out  │ │
│ └───────────┘ │
└───────────────┘

Diagram showing three page replacement strategies and which page they choose to remove.

Key Facts

Page Replacement → The process of deciding which memory page to remove when new pages need space.

FIFO → Removes the oldest page loaded into memory first.

LRU → Removes the page that has not been used for the longest time.

Optimal Algorithm → Removes the page that will not be used for the longest time in the future.

Page Fault → An event when a requested page is not in memory and must be loaded.

Common Confusions

Believing FIFO always removes the least useful page.

Believing FIFO always removes the least useful page. FIFO removes the oldest page without checking if it is still needed, so it can remove useful pages.

Thinking LRU predicts future page use.

Thinking LRU predicts future page use. LRU only tracks past usage, not future requests.

Assuming Optimal algorithm is practical for real systems.

Assuming Optimal algorithm is practical for real systems. Optimal requires future knowledge, which is usually impossible, so it is mainly theoretical.

Summary

Page replacement algorithms decide which memory page to remove when space is needed.

FIFO removes the oldest page, LRU removes the least recently used page, and Optimal removes the page not needed for the longest future time.

Optimal is the best in theory but not practical; LRU often performs better than FIFO in real systems.

Practice

1. Which page replacement algorithm removes the page that has been in memory the longest, regardless of usage?

easy

A. FIFO (First In First Out)

B. LRU (Least Recently Used)

C. Optimal

D. Random

Solution

1. Step 1: Understand FIFO behavior

   FIFO removes the oldest page loaded into memory first, ignoring how often it is used.

2. Step 2: Compare with other algorithms

   LRU removes the least recently used page, Optimal removes the page not needed for the longest future time, Random removes any page randomly.

3. Final Answer:

   FIFO (First In First Out) -> Option A

4. Quick Check:

   Oldest page removed = FIFO [OK]

Hint: Oldest page out means FIFO [OK]

Common Mistakes:

• Confusing FIFO with LRU
• Thinking Optimal removes oldest page
• Assuming Random is FIFO

2. Which of the following is the correct description of the LRU page replacement algorithm?

easy

A. Removes the page that will not be used for the longest time in the future

B. Removes the least recently used page

C. Removes the oldest page loaded into memory

D. Removes a random page

Solution

1. Step 1: Recall LRU definition

   LRU removes the page that has not been used for the longest time recently.

2. Step 2: Match options with definitions

   Removes the page that will not be used for the longest time in the future describes Optimal, C describes FIFO, B is random removal.

3. Final Answer:

   Removes the least recently used page -> Option B

4. Quick Check:

   Least recently used = LRU [OK]

Hint: Least recent use means LRU [OK]

Common Mistakes:

• Mixing LRU with Optimal
• Confusing LRU with FIFO
• Choosing random removal as LRU

3. Given the page reference string 7, 0, 1, 2, 0, 3, 0, 4 and 3 page frames, how many page faults occur using the FIFO algorithm?

medium

A. 6

B. 5

C. 7

D. 4

Solution

1. Step 1: Simulate FIFO with 3 frames

   Load pages in order: 7 (fault), 0 (fault), 1 (fault), then 2 replaces 7 (fault), 0 is in memory (no fault), 3 replaces 0 (fault), 0 replaces 1 (fault), 4 replaces 2 (fault).

2. Step 2: Count total faults

   Faults occur at 7,0,1,2,3,0,4 = 7 faults, but 0 at position 6 is already in memory, so no fault there. Total faults = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count page faults in FIFO = 6 [OK]

Hint: Count faults when page not in frames FIFO order [OK]

Common Mistakes:

• Counting repeated pages as faults
• Mixing FIFO with LRU results
• Forgetting to replace oldest page

4. Identify the error in this LRU page replacement simulation with 2 frames and reference string 1, 2, 3, 2, 1, 4: The algorithm replaces page 1 first instead of page 3.

medium

A. Algorithm should replace page 2 first

B. Algorithm should replace oldest page, which is page 1

C. Algorithm should replace least recently used page, which is page 3

D. Algorithm should replace a random page

Solution

1. Step 1: Simulate LRU up to replacement point

   1(fault)[1], 2(fault)[1,2], 3 replaces LRU=1 [2,3], 2(hit) updates LRU=3 MRU=2 [3,2]. Next 1 should replace LRU=3.

2. Step 2: Check replacement choice

   The error is replacing page 1 instead of the least recently used page 3.

3. Final Answer:

   Algorithm should replace least recently used page, which is page 3 -> Option C

4. Quick Check:

   LRU replaces least recently used page [OK]

Hint: Replace least recently used page in LRU [OK]

Common Mistakes:

• Replacing oldest page instead of least used
• Confusing LRU with FIFO
• Replacing wrong page due to usage order

5. You have 4 page frames and the reference string 1, 2, 3, 4, 2, 1, 5, 1, 2, 3, 4, 5. Using the Optimal page replacement algorithm, how many page faults will occur?

hard

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Simulate Optimal with 4 frames

   1,2,3,4 (4 faults). 2 hit, 1 hit. 5 replaces 4 (farthest next at pos11, fault 5). 1 hit, 2 hit, 3 hit. 4 replaces 1 (no future use, fault 6). 5 hit.

2. Step 2: Count total faults

   Total faults = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Optimal page faults counted = 6 [OK]

Hint: Replace page not needed longest in future [OK]

Common Mistakes:

• Counting repeated pages as faults
• Using FIFO or LRU logic instead of Optimal
• Forgetting to check future references