PAGE REPLACEMENT ALGORITHMS: FIFO VS LRU

In virtual memory management, physical memory is divided into fixed-size blocks called frames, and logical memory is divided into pages. When a process requests a page that is not currently in physical memory, a page fault occurs. If all physical frames are occupied, the operating system must choose a page to replace. This decision is governed by page replacement algorithms.

Almost every undergraduate Operating Systems lab requires implementing these algorithms. Below, we compare the two most common algorithms: First-In, First-Out (FIFO) and Least Recently Used (LRU).

First-In, First-Out (FIFO)

FIFO is the simplest page replacement algorithm. The operating system associates a timestamp with each page in memory, tracking when it was loaded. When a page must be replaced, the oldest page is selected.

While simple, FIFO suffers from a counterintuitive phenomenon known as Belady's Anomaly. Normally, adding more physical frames should reduce page faults. With FIFO, however, certain page reference strings will actually trigger more page faults when the frame count increases.

FIFO Visual Trace Example

Let's trace a reference string: 7, 0, 1, 2, 0, 3 with 3 frames:

• ▸Page 7: Loaded into Frame 1 (Page Fault). Frames: [7, -, -]
• ▸Page 0: Loaded into Frame 2 (Page Fault). Frames: [7, 0, -]
• ▸Page 1: Loaded into Frame 3 (Page Fault). Frames: [7, 0, 1]
• ▸Page 2: Page 7 is the oldest and is replaced (Page Fault). Frames: [2, 0, 1]
• ▸Page 0: Already in memory (Hit). Frames: [2, 0, 1]
• ▸Page 3: Page 0 is now the oldest in memory and is replaced (Page Fault). Frames: [2, 3, 1]

Least Recently Used (LRU)

LRU addresses the weakness of FIFO by looking backward in time. Instead of replacing the oldest page, it replaces the page that has not been referenced for the longest duration.

LRU is a stack algorithm, meaning it does not suffer from Belady's Anomaly. It generally results in fewer page faults than FIFO. However, it requires hardware support to maintain access histories, making it more expensive to implement.

LRU Visual Trace Example

Using the same reference string: 7, 0, 1, 2, 0, 3 with 3 frames:

• ▸Page 7: Loaded into Frame 1 (Page Fault). Frames: [7, -, -]
• ▸Page 0: Loaded into Frame 2 (Page Fault). Frames: [7, 0, -]
• ▸Page 1: Loaded into Frame 3 (Page Fault). Frames: [7, 0, 1]
• ▸Page 2: Page 7 was referenced longest ago and is replaced (Page Fault). Frames: [2, 0, 1]
• ▸Page 0: Already in memory. Its 'last used' timestamp is updated (Hit). Frames: [2, 0, 1]
• ▸Page 3: Page 1 was referenced longest ago and is replaced (Page Fault). Frames: [2, 0, 3]

C++ Code Implementation

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;

int countFIFO(const vector<int>& pages, int capacity) {
    unordered_set<int> s;
    vector<int> indexes;
    int page_faults = 0;
    for (int page : pages) {
        if (s.size() < capacity) {
            if (s.find(page) == s.end()) {
                s.insert(page);
                page_faults++;
                indexes.push_back(page);
            }
        } else {
            if (s.find(page) == s.end()) {
                int val = indexes.front();
                indexes.erase(indexes.begin());
                s.erase(val);
                s.insert(page);
                indexes.push_back(page);
                page_faults++;
            }
        }
    }
    return page_faults;
}

int countLRU(const vector<int>& pages, int capacity) {
    unordered_set<int> s;
    unordered_map<int, int> indexes;
    int page_faults = 0;
    for (int i = 0; i < pages.size(); i++) {
        int page = pages[i];
        if (s.size() < capacity) {
            if (s.find(page) == s.end()) {
                s.insert(page);
                page_faults++;
            }
            indexes[page] = i;
        } else {
            if (s.find(page) == s.end()) {
                int lru = INT_MAX, val;
                for (auto it = s.begin(); it != s.end(); ++it) {
                    if (indexes[*it] < lru) {
                        lru = indexes[*it];
                        val = *it;
                    }
                }
                s.erase(val);
                s.insert(page);
                page_faults++;
            }
            indexes[page] = i;
        }
    }
    return page_faults;
}

int main() {
    vector<int> pages = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3};
    int capacity = 3;
    cout << "FIFO Page Faults: " << countFIFO(pages, capacity) << endl;
    cout << "LRU Page Faults: " << countLRU(pages, capacity) << endl;
    return 0;
}

Structuring Your Lab Report

For page replacement algorithms, university evaluators expect your report to include: an Aim specifying the algorithm to be implemented, a detailed Theory section explaining cache hit/miss and Belady's Anomaly, the source Code, and an Output trace table showing the contents of each frame at every step.

Drawing trace tables in Word is highly time-consuming. You can automate the entire documentation layout using Assignment Bot.