In this post, we implement the FIFO (First In, First Out) Page Replacement Algorithm in C++. When the OS needs to load a new page into memory but all frames are occupied, FIFO evicts the page that has been in memory the longest — the one that arrived first. It is one of the simplest page replacement strategies and serves as a baseline for comparing more sophisticated algorithms.

What is FIFO Page Replacement?

Physical memory is divided into frames. When a process references a page not currently in a frame (a page fault), it must be loaded. If all frames are full, an existing page must be evicted. FIFO chooses the oldest resident page for eviction, regardless of how frequently it has been used.

• Page Hit — Referenced page is already in a frame. No disk I/O needed.
• Page Fault (Miss) — Referenced page is not in any frame. Must load from disk.
• FIFO Queue — Tracks the order in which pages were loaded. Front = oldest; back = newest.

A notable weakness of FIFO is Bélady’s Anomaly — adding more frames can sometimes cause more page faults, counter-intuitively.

C++ Code Implementation

// ============================================================
// FIFO Page Replacement Algorithm in C++
// Evicts the oldest (first-loaded) page when a page fault occurs
// ============================================================

#include <iostream>
#include <vector>
using namespace std;

int main() {

    int frameCount, pageRefCount;

    // -------------------------------------------------------
    // Step 1: Read frame size and page reference string
    // -------------------------------------------------------
    cout << "\n Enter Frame Size (number of frames in memory): ";
    cin  >> frameCount;

    cout << "\n Enter Number of Pages in the reference string: ";
    cin  >> pageRefCount;

    vector<int> pageReferenceString(pageRefCount);
    vector<int> frameContents(frameCount, -1);  // -1 means the frame is empty
    vector<int> fifoLoadOrder;                  // Tracks frame indices in load order (front = oldest)

    cout << "\n Enter the Page Reference String: ";
    for (int i = 0; i < pageRefCount; i++) cin >> pageReferenceString[i];

    int hitCount  = 0;
    int faultCount = 0;

    // -------------------------------------------------------
    // Step 2: Process each page reference one by one
    // -------------------------------------------------------
    for (int refIndex = 0; refIndex < pageRefCount; refIndex++) {
        int currentPage = pageReferenceString[refIndex];

        // --- Check if the page is already in a frame (Hit) ---
        bool isHit = false;
        for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
            if (frameContents[frameIdx] == currentPage) {
                isHit = true;
                break;
            }
        }

        if (isHit) {
            hitCount++;
            cout << "\n Page " << currentPage << " [HIT]  | Frames: ";
        } else {
            faultCount++;

            // --- Page Fault: first try to find an empty frame ---
            bool placedInEmptyFrame = false;
            for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
                if (frameContents[frameIdx] == -1) {
                    frameContents[frameIdx] = currentPage;  // Load page into empty frame
                    fifoLoadOrder.push_back(frameIdx);      // Record it at back of FIFO queue
                    placedInEmptyFrame = true;
                    break;
                }
            }

            // --- If no empty frame available, apply FIFO replacement ---
            if (!placedInEmptyFrame) {
                // The front of fifoLoadOrder holds the index of the oldest frame
                int oldestFrameIndex = fifoLoadOrder.front();
                fifoLoadOrder.erase(fifoLoadOrder.begin());  // Remove oldest from front

                frameContents[oldestFrameIndex] = currentPage;  // Load new page into that frame
                fifoLoadOrder.push_back(oldestFrameIndex);      // Record as newest at back
            }

            cout << "\n Page " << currentPage << " [MISS] | Frames: ";
        }

        // Display current state of all frames after this reference
        for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
            if (frameContents[frameIdx] == -1) cout << "- ";
            else cout << frameContents[frameIdx] << " ";
        }
    }

    // -------------------------------------------------------
    // Step 3: Display summary statistics
    // -------------------------------------------------------
    cout << "\n\n ------- Summary -------";
    cout << "\n Total Page References : " << pageRefCount;
    cout << "\n Page Hits             : " << hitCount;
    cout << "\n Page Faults (Misses)  : " << faultCount;
    cout << "\n Hit Ratio             : " << (float)hitCount  / pageRefCount * 100 << "%";
    cout << "\n Fault Ratio           : " << (float)faultCount/ pageRefCount * 100 << "%";
    cout << endl;

    return 0;
}

Explanation of the Code

1. frameContents[] — Initialized to -1 (empty). Holds the page number currently in each physical frame.
2. fifoLoadOrder — A vector acting as the FIFO queue. Stores frame indices in the order pages were loaded. The front holds the index of the oldest page’s frame; the back holds the newest. This allows O(1) identification of which frame to evict.
3. Hit detection — Scans frameContents[] for currentPage. If found, it’s a hit; no frame changes.
4. Empty frame placement — On a miss, empty frames (-1) are filled first. The frame index is recorded at the back of fifoLoadOrder.
5. FIFO eviction — When all frames are occupied, fifoLoadOrder.front() gives the oldest frame’s index. That frame is overwritten, the old index is removed from the front, and the same index is re-inserted at the back (since it now holds the newest page).

Sample Output

 Enter Frame Size (number of frames in memory): 3
 Enter Number of Pages in the reference string: 12
 Enter the Page Reference String: 1 2 3 4 1 2 5 1 2 3 4 5

 Page 1 [MISS] | Frames: 1 - -
 Page 2 [MISS] | Frames: 1 2 -
 Page 3 [MISS] | Frames: 1 2 3
 Page 4 [MISS] | Frames: 4 2 3       <-- page 1 evicted (loaded first)
 Page 1 [MISS] | Frames: 4 1 3       <-- page 2 evicted
 Page 2 [MISS] | Frames: 4 1 2       <-- page 3 evicted
 Page 5 [MISS] | Frames: 5 1 2       <-- page 4 evicted
 Page 1 [HIT]  | Frames: 5 1 2
 Page 2 [HIT]  | Frames: 5 1 2
 Page 3 [MISS] | Frames: 5 3 2       <-- page 1 evicted
 Page 4 [MISS] | Frames: 5 3 4       <-- page 2 evicted
 Page 5 [HIT]  | Frames: 5 3 4

 ------- Summary -------
 Total Page References : 12
 Page Hits             : 3
 Page Faults (Misses)  : 9
 Hit Ratio             : 25%
 Fault Ratio           : 75%

Step-by-Step Explanation of Input/Output

Reference string: 1 2 3 4 1 2 5 1 2 3 4 5 | Frame size: 3

• Pages 1, 2, 3: Compulsory misses — frames are empty, pages load into available slots. FIFO queue: [F0, F1, F2] (F0 = oldest).
• Page 4: All frames full. FIFO evicts frame F0 (holds page 1, loaded first). Page 4 enters F0. Queue: [F1, F2, F0].
• Page 1: F1 (page 2) is now oldest. Page 2 evicted, page 1 loaded. Queue: [F2, F0, F1].
• Pages 1, 2 (references 8–9): Hit — both still in frames. No eviction.
• Page 3: Miss. Oldest frame is now F2 (page 3) — wait, page 3 was evicted earlier. The oldest is page 5 (in F0 from step 7). Actually F2 holds page 2, F0 holds page 5, F1 holds page 1. Oldest = F0 (page 5, last loaded at step 7). But page 5 is being referenced again at step 12 — it hits. The miss at step 10 evicts whatever is oldest at that point, resulting in page 3 being loaded.
• The 25% hit ratio shows FIFO’s weakness: it evicted page 1 when page 4 was loaded, only for page 1 to be immediately needed again. FIFO has no awareness of usage frequency.

See Also

• Implementation of LRU Page Replacement Algorithm in C++

Bottom line is…

FIFO page replacement is simple and cheap to implement — it only needs a queue of frame indices. However, it ignores actual page usage, frequently evicting pages that are still needed, and it is the only common algorithm susceptible to Bélady’s Anomaly. In practice, approximations of the Least Recently Used (LRU) algorithm, such as the Clock algorithm, are used in real operating system kernels because they achieve much higher hit rates with comparable overhead.