1. Introduction
In a demand paging system, when a page fault occurs and all frames are occupied, the operating system must decide which page to remove from memory.
This decision is made by a Page Replacement Algorithm.
One of the simplest page replacement algorithms is FIFO (First-In, First-Out).
FIFO replaces the page that has been in memory for the longest time.
2. What is FIFO Page Replacement?
FIFO (First-In, First-Out) is a page replacement algorithm that removes the page that entered memory first whenever a replacement is required.
Key Idea
Oldest Page in Memory
↓
Removed First
FIFO treats memory pages like a queue.
3. Basic Principle
Pages enter memory in a particular order.
When memory becomes full:
The oldest page is removed.
The new page is inserted.
The algorithm does not consider:
How frequently a page is used
How recently a page was used
It only considers arrival time.
4. Data Structure Used
FIFO uses a simple queue.
Front Rear
[ Oldest ] [ Page ] [ Page ] [ Newest ]
Operations
Insert new page → Rear
Remove old page → Front
5. Working Mechanism
Whenever a page reference occurs:
Case 1: Page Already Present
The page is found in memory.
Page Hit
No replacement occurs.
Case 2: Page Not Present
The page is missing.
Page Fault
If Free Frame Exists
Insert page directly.
If Memory Full
Remove Oldest Page
↓
Insert New Page
6. FIFO Algorithm
For each page reference:
If page exists:
Page Hit
Else:
Page Fault
If free frame exists:
Load page
Else:
Remove oldest page
Insert new page
7. Example
Given
Reference String:
1 2 3 4 1 2 5 1 2 3 4 5
Frames = 3
8. Step-by-Step Execution
| Reference | Frames | Result |
|---|---|---|
| 1 | 1 - - | Fault |
| 2 | 1 2 - | Fault |
| 3 | 1 2 3 | Fault |
| 4 | 2 3 4 | Fault (1 removed) |
| 1 | 3 4 1 | Fault (2 removed) |
| 2 | 4 1 2 | Fault (3 removed) |
| 5 | 1 2 5 | Fault (4 removed) |
| 1 | 1 2 5 | Hit |
| 2 | 1 2 5 | Hit |
| 3 | 2 5 3 | Fault (1 removed) |
| 4 | 5 3 4 | Fault (2 removed) |
| 5 | 5 3 4 | Hit |
9. Result
Total Page Faults = 9
Total Hits = 3
10. Queue Visualization
After loading first three pages:
Front Rear
1 → 2 → 3
Reference = 4
Remove:
1
Insert:
Front Rear
2 → 3 → 4
Reference = 1
Remove:
2
Insert:
Front Rear
3 → 4 → 1
The process continues similarly.
11. Characteristics of FIFO
Simple replacement policy
Uses arrival order only
Does not track usage history
Low implementation overhead
Easy to implement using a queue
12. Advantages of FIFO
12.1 Simple Implementation
Very easy to understand and code.
12.2 Low Overhead
Only queue operations are required.
12.3 Minimal Bookkeeping
No timestamps or counters required.
13. Disadvantages of FIFO
13.1 Ignores Usage Pattern
Frequently used pages may be removed.
Example:
Page heavily used
↓
Still removed if oldest
13.2 Higher Page Fault Rate
Often performs worse than LRU and Optimal.
13.3 Poor Locality Awareness
Does not consider:
Recent usage
Future usage
14. Belady's Anomaly (Very Important)
FIFO suffers from a phenomenon called Belady's Anomaly.
15. What is Belady's Anomaly?
Belady's Anomaly is a situation where increasing the number of frames results in an increase in page faults.
Normally we expect:
More Frames
↓
Fewer Page Faults
But FIFO can violate this expectation.
16. Example of Belady's Anomaly
Consider:
Reference String:
1 2 3 4 1 2 5 1 2 3 4 5
Using 3 Frames
Page Faults = 9
Using 4 Frames
Page Faults = 10
More memory produced more faults.
This is Belady's Anomaly.
17. Why Belady's Anomaly Occurs
FIFO blindly removes pages based on age.
It does not know:
Which pages are important
Which pages will be used again soon
Therefore:
Useful Page
↓
Becomes Old
↓
Removed
↓
Fault Occurs Again
18. FIFO and Locality of Reference
Programs usually exhibit:
Temporal locality
Spatial locality
FIFO ignores both.
Hence:
Recently Needed Page
↓
May Still Be Removed
This reduces performance.
19. Performance Analysis
| Feature | FIFO |
|---|---|
| Implementation | Very Easy |
| Overhead | Low |
| Page Fault Rate | Moderate to High |
| Locality Awareness | No |
| Belady's Anomaly | Yes |
| Practical Usage | Limited |
20. FIFO vs Optimal and LRU
| Feature | FIFO | LRU | Optimal |
|---|---|---|---|
| Complexity | Low | Medium | High |
| Performance | Moderate | Better | Best |
| Practicality | High | High | Theoretical |
| Belady's Anomaly | Yes | No | No |
21. Real-World Analogy
Imagine people standing in a queue.
First Person Enters
↓
First Person Leaves
Even if that person still needs to stay, FIFO removes them simply because they arrived first.
Similarly:
Oldest Page
↓
Removed First
regardless of how useful it currently is.
Most Important Point
FIFO is simple and easy to implement, but its major drawback is Belady's Anomaly, where increasing memory frames may unexpectedly increase the number of page faults.