Home/Learn/Operating Systems/Page Replacement Algorithms

Page Replacement Algorithms

Intermediate

Memory Management

When physical memory is full and a page fault occurs, the OS uses a page replacement algorithm to evict a victim page — FIFO, Optimal, LRU, and the Clock algorithm offer different trade-offs.

Overview

When all physical frames are occupied and a major page fault occurs, the OS must choose a victim page to evict (write to swap if dirty, then reuse the frame). The choice of victim determines future page fault rates. FIFO evicts the oldest-loaded page — simple but can cause Belady's anomaly where giving more frames causes more faults. Optimal (OPT/Belady's algorithm) evicts the page that will not be used for the longest time — theoretically best but impossible to implement (requires future knowledge); used only as a benchmark. LRU (Least Recently Used) evicts the page unused for the longest time — excellent in practice but expensive to implement in pure hardware. The Clock algorithm (second-chance) approximates LRU cheaply using the reference bit set by hardware on every page access.

FIFO vs LRU vs Optimal: Step-by-Step Trace

Given the reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames, each algorithm produces different fault counts. Optimal is always best; LRU is usually close to Optimal; FIFO is unpredictable and can exhibit Belady's anomaly. This trace is a classic interview question.

Java — FIFO vs LRU page replacement simulation on reference string

// Reference string: 1,2,3,4,1,2,5,1,2,3,4,5  — 3 frames
int[] refs   = {1,2,3,4,1,2,5,1,2,3,4,5};
int   frames = 3;

// ── FIFO ──────────────────────────────────────────────────────
Queue<Integer> fifo   = new LinkedList<>();
Set<Integer>   inMem  = new HashSet<>();
int fifoPF = 0;
for (int page : refs) {
    if (!inMem.contains(page)) {
        fifoPF++;
        if (fifo.size() == frames) {
            int evict = fifo.poll();   // remove oldest
            inMem.remove(evict);
        }
        fifo.add(page);
        inMem.add(page);
    }
}
System.out.println("FIFO page faults: " + fifoPF);   // 9

// ── LRU ───────────────────────────────────────────────────────
LinkedHashMap<Integer,Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
int lruPF = 0;
for (int page : refs) {
    if (!lru.containsKey(page)) {
        lruPF++;
        if (lru.size() == frames) {
            // Remove least recently used (first entry in access-order map)
            lru.remove(lru.keySet().iterator().next());
        }
        lru.put(page, 1);
    } else {
        lru.get(page);  // access-order map: moves page to tail
    }
}
System.out.println("LRU  page faults: " + lruPF);   // 8

// Optimal = 6 faults (requires future knowledge — theoretical minimum)
System.out.println("OPT  page faults: 6  (theoretical minimum)");

Belady's Anomaly and the Clock Algorithm

Belady's anomaly: with FIFO, adding more frames can increase page faults. Example: with 3 frames on string 1,2,3,4,1,2,3,1,2,3 FIFO gives 9 faults; with 4 frames it gives 10 faults. LRU and Optimal are stack algorithms — they never exhibit Belady's anomaly. The Clock algorithm (second-chance) approximates LRU: pages are arranged in a circular list; a hand sweeps around; if reference bit = 1, clear it and advance; if 0, evict. Used by Linux for page eviction.

Java — Clock (Second-Chance) page replacement algorithm

// Clock (Second-Chance) Algorithm
// Each frame has: page number + reference bit (set by hardware on every access)
// Clock hand sweeps; clears reference bit first, evicts on second sweep

class ClockPage {
    int page; boolean ref;
    ClockPage(int page) { this.page = page; this.ref = true; } // ref=true on load
}

ClockPage[] clock = new ClockPage[3]; // 3 frames
int hand = 0; // clock hand position
int clockPF = 0;

int[] refs = {1,2,3,4,1,2,5,1,2,3,4,5};

for (int page : refs) {
    // Check if page already in memory
    boolean hit = false;
    for (ClockPage cp : clock) {
        if (cp != null && cp.page == page) {
            cp.ref = true;  // hardware sets reference bit on access
            hit = true; break;
        }
    }
    if (!hit) {
        clockPF++;
        // Find victim: advance hand, clearing reference bits
        while (clock[hand] != null && clock[hand].ref) {
            clock[hand].ref = false;  // second chance: clear bit, move on
            hand = (hand + 1) % clock.length;
        }
        clock[hand] = new ClockPage(page);  // evict victim, load new page
        hand = (hand + 1) % clock.length;
    }
}
System.out.println("Clock page faults: " + clockPF);
// Clock typically close to LRU fault count with O(1) overhead

Key Points to Remember

1FIFO evicts the oldest-loaded page — simple but susceptible to Belady's anomaly.
2Optimal (OPT) evicts the page used furthest in the future — minimum faults but requires future knowledge.
3LRU evicts the least recently used page — excellent in practice, approximated by the Clock algorithm.
4Belady's anomaly: more frames can cause more page faults with FIFO — does not occur with LRU or OPT.
5Clock algorithm: circular list of frames; clears reference bit first, evicts on second encounter.
6Java LinkedHashMap with access-order=true is a ready-made LRU structure for application-level caches.

Interview Questions

Compare FIFO, LRU, and Optimal page replacement with a reference string trace.

MediumGoogle

What is Belady's anomaly and which algorithms are immune to it?

MediumMicrosoft

How does the Clock algorithm approximate LRU without the full LRU overhead?

HardAmazon

How would you implement an LRU cache in Java? What data structures would you use?

MediumFlipkart

Ask Aria about Page Replacement Algorithms

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Translation Lookaside Buffer (TLB)

Thrashing