Introduction
FIFO page replacement is one of the simplest page replacement algorithms used in operating systems. FIFO stands for First-In, First-Out, which means the page that entered memory first is removed first.
It is used when a page fault occurs and all available frames in RAM are already occupied. Since no free frame is available, the operating system must evict one existing page before loading the new page.
FIFO Page Replacement Meaning
FIFO follows a very direct rule: the oldest loaded page becomes the victim page. It does not check whether that page was used recently or whether it may be needed again soon.
This makes FIFO easy to understand, but also limited. A page can be accessed many times after entering memory, yet FIFO still treats it as old because the algorithm only cares about entry order.
FIFO can be understood using a queue. The front of the queue stores the oldest page, and the back of the queue stores the newest page.
Front: The page that entered memory earliest.
Back: The page most recently loaded into memory.
Replacement: Remove from the front and insert the new page at the back.
Hit: Do not change the queue order.
The last point is important. In FIFO, a page does not become newer just because it was accessed again. Hits do not move pages to the back of the queue.
How FIFO Works
FIFO checks each page reference and handles it based on whether the page is already present in RAM.
If the page is already in memory: It is a page hit, so no replacement is needed.
If the page is absent and a free frame exists: The page is loaded into the free frame and added to the back of the queue.
If the page is absent and frames are full: FIFO removes the page at the front of the queue and loads the new page at the back.
So FIFO updates the queue only when a new page is loaded. It does not update the queue on a hit, because FIFO is based on loading order, not recent usage.
FIFO Page Replacement Algo
FIFO Worked Example
Consider this setup:
Reference string:
1, 2, 3, 2, 4, 1, 2, 5Number of frames:
3Initial memory: Empty
The frame order below is shown as FIFO queue order: left side is oldest, right side is newest.
Step | Page | Result | Victim | Frames After Access |
|---|---|---|---|---|
1 | 1 | Fault | - | 1, -, - |
2 | 2 | Fault | - | 1, 2, - |
3 | 3 | Fault | - | 1, 2, 3 |
4 | 2 | Hit | - | 1, 2, 3 |
5 | 4 | Fault | 1 | 2, 3, 4 |
6 | 1 | Fault | 2 | 3, 4, 1 |
7 | 2 | Fault | 3 | 4, 1, 2 |
8 | 5 | Fault | 4 | 1, 2, 5 |
In this trace, the total number of page faults is 7, and the total number of page hits is 1. The page fault rate is 7 / 8.
FIFO Pseudocode
The FIFO algorithm can be written using a queue and a set of frames. The queue changes only when a page is loaded or replaced.
void pageReference(int page) { if (pageIsInFrames(page)) { recordHit(); } else { recordPageFault(); if (freeFrameExists()) { loadPage(page); queue.push_back(page); } else { int victim = queue.front(); queue.pop_front(); replacePage(victim, page); queue.push_back(page); } }}The key rule is simple: on a page fault with full frames, remove from the front and insert at the back.
Strengths of FIFO
FIFO is useful because it is simple and easy to apply. It does not need complex tracking of future use or recent access time.
Simple logic: The oldest loaded page is always selected as the victim.
Easy implementation: A queue is enough to maintain FIFO order.
Low hit overhead: A hit does not require changing the queue.
These strengths make FIFO a good starting point for understanding page replacement, even though it is not always the best practical policy.
Strengths & Weaknesses of FIFO
Weaknesses of FIFO
FIFO’s main weakness is that it ignores locality of reference. Locality means pages used recently or repeatedly are likely to be used again soon.
An old page may still be very important. For example, a loop’s code page may enter memory early and continue to be used many times, but FIFO may still remove it just because it is the oldest page in the queue.
FIFO can also suffer from Belady’s anomaly. In some reference strings, increasing the number of frames can unexpectedly increase the number of page faults, which is counterintuitive for a memory management algorithm.
Summary
FIFO page replacement removes the page that entered memory earliest when a page fault occurs and all frames are full. It uses a queue where the front contains the oldest page and the back contains the newest loaded page.
FIFO is simple, predictable, and easy to simulate, but it does not consider recent usage or future need. Because of this, it can evict useful pages, ignore locality, and suffer from Belady’s anomaly in some cases.
Be the first to add a comment.