Page Replacement Policies in C: FIFO, LRU, and Clock

How operating systems select victim frames under memory pressure: Bélády's anomaly in FIFO, the hardware cost of exact LRU, and the Second-Chance Clock approximation.

Eviction Under Memory Pressure

Demand paging allows the aggregate virtual memory of running processes to exceed physical RAM. As long as the active working set of pages fits in physical memory, execution proceeds at native RAM speed.

When a page fault occurs and every physical frame is already occupied, the kernel must evict an existing page to make room (writing it to swap first if its PTE dirty bit is set). Evicting the wrong page is catastrophic: if the chosen victim belongs to an active loop, the CPU will fault on it again microseconds later—triggering thrashing, where the system spends nearly $100%$ of its time waiting on disk I/O.

The theoretical lower bound on page faults is Bélády’s Optimal Policy (OPT / MIN): evict the page whose next reference lies furthest in the future. Because an operating system kernel cannot see future instructions, real systems approximate OPT using historical access patterns. Let’s analyze the three classic eviction policies—FIFO, LRU, and Clock (Second Chance)—and benchmark them in C on a famous pathological workload.


1. First-In-First-Out (FIFO) and Bélády’s Anomaly

The simplest policy tracks resident pages in a circular queue ordered strictly by arrival time, evicting whichever page has been in RAM the longest.

While FIFO requires zero hardware support from the MMU ($O(1)$ enqueue/dequeue only on page faults), it suffers from two fatal flaws:

  1. Blindness to Hot Pages: A page containing frequently executed code or core global state loaded at startup is the oldest page in memory; FIFO evicts it repeatedly regardless of how heavily it is used.
  2. Bélády’s Anomaly: Intuitively, giving a computer more physical RAM should never increase the number of page faults. Yet in 1969, László Bélády proved that for FIFO, certain reference strings (such as 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5) suffer more page faults with 4 physical frames (10 faults) than with 3 frames (9 faults).

2. Least Recently Used (LRU)

To exploit temporal locality—the observation that pages accessed in the recent past are likely to be accessed again in the near future—Least Recently Used (LRU) evicts the resident page whose most recent access timestamp is oldest.

Crucially, LRU satisfies the stack inclusion property: at any point in a reference trace, the set of pages resident in a $k$-frame LRU cache is always a strict subset of the pages resident in a $(k+1)$-frame LRU cache. Consequently, LRU is mathematically immune to Bélády’s Anomaly.

Why Operating System Kernels Cannot Use Exact LRU

If exact LRU is so well-behaved, why don’t Linux, macOS, or Windows use it directly on hardware page tables?

Because the kernel is not invoked on TLB hits! A CPU executes billions of load and store instructions per second entirely in hardware. Maintaining an exact LRU ordering would require the hardware MMU to update a 64-bit timestamp or manipulate a doubly-linked list in RAM on every single memory instruction.

Instead, hardware MMUs provide only a single 1-bit flag in each Page Table Entry: the accessed (or reference) bit, which the CPU hardware sets to 1 whenever a page is read or written.


3. The Clock (Second-Chance) Algorithm

The Clock algorithm (attributed to Fernando Corbató) bridges the gap between FIFO and LRU using only that 1-bit hardware referenced flag.

Physical frames are arranged logically around a circular dial with a sweeping pointer called the hand. Whenever a page is accessed, the MMU sets referenced = 1. When a page fault requires an eviction, the kernel sweeps hand clockwise:

  • If referenced == 1: The page was used recently. The kernel grants it a second chance by clearing referenced = 0, advancing hand to the next frame, and continuing the sweep.
  • If referenced == 0: The page has not been accessed since the last time the clock hand swept past it. The kernel selects this frame as the victim, replaces its resident page, sets referenced = 1, and advances hand.

(In the worst case where every frame has referenced == 1, the hand sweeps full circle, clearing all bits to 0, and evicts the starting frame—degrading gracefully to FIFO).


Implementing and Benchmarking All Three Policies in C

Let’s write a clean, unified C benchmark that implements FIFO, Exact LRU, and Clock, and runs all three against Bélády’s classic 12-access reference string for both 3 and 4 physical frames:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#define MAX_FRAMES 16

// 1. FIFO Eviction Simulation
size_t simulate_fifo(const uint32_t *trace, size_t len, size_t num_frames) {
    uint32_t frames[MAX_FRAMES] = {0};
    size_t   count  = 0;
    size_t   hand   = 0;
    size_t   faults = 0;

    for (size_t step = 0; step < len; ++step) {
        const uint32_t page = trace[step];
        bool hit = false;
        for (size_t i = 0; i < count; ++i) {
            if (frames[i] == page) {
                hit = true;
                break;
            }
        }
        if (hit) continue;

        faults++;
        if (count < num_frames) {
            frames[count++] = page;
        } else {
            frames[hand] = page;
            hand = (hand + 1) % num_frames;
        }
    }
    return faults;
}

// 2. Exact LRU Eviction Simulation
size_t simulate_lru(const uint32_t *trace, size_t len, size_t num_frames) {
    uint32_t frames[MAX_FRAMES]    = {0};
    uint64_t last_used[MAX_FRAMES] = {0};
    size_t   count  = 0;
    size_t   faults = 0;

    for (size_t step = 0; step < len; ++step) {
        const uint32_t page = trace[step];
        bool hit = false;
        for (size_t i = 0; i < count; ++i) {
            if (frames[i] == page) {
                last_used[i] = step; // Update logical timestamp on every hit
                hit = true;
                break;
            }
        }
        if (hit) continue;

        faults++;
        if (count < num_frames) {
            frames[count]    = page;
            last_used[count] = step;
            count++;
        } else {
            size_t victim = 0;
            for (size_t i = 1; i < num_frames; ++i) {
                if (last_used[i] < last_used[victim]) {
                    victim = i;
                }
            }
            frames[victim]    = page;
            last_used[victim] = step;
        }
    }
    return faults;
}

// 3. Clock (Second-Chance) Eviction Simulation
size_t simulate_clock(const uint32_t *trace, size_t len, size_t num_frames) {
    uint32_t frames[MAX_FRAMES]     = {0};
    bool     referenced[MAX_FRAMES] = {false};
    size_t   count  = 0;
    size_t   hand   = 0;
    size_t   faults = 0;

    for (size_t step = 0; step < len; ++step) {
        const uint32_t page = trace[step];
        bool hit = false;
        for (size_t i = 0; i < count; ++i) {
            if (frames[i] == page) {
                referenced[i] = true; // MMU sets hardware accessed bit
                hit = true;
                break;
            }
        }
        if (hit) continue;

        faults++;
        if (count < num_frames) {
            frames[count]     = page;
            referenced[count] = true;
            count++;
        } else {
            while (referenced[hand]) {
                referenced[hand] = false; // Grant second chance
                hand = (hand + 1) % num_frames;
            }
            frames[hand]     = page;
            referenced[hand] = true;
            hand = (hand + 1) % num_frames;
        }
    }
    return faults;
}

int main(void) {
    // Bélády's classic anomaly reference sequence
    const uint32_t trace[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    const size_t   n       = sizeof(trace) / sizeof(trace[0]);

    for (size_t k = 3; k <= 4; ++k) {
        printf("Frames = %zu  |  FIFO faults: %2zu  |  Clock faults: %2zu  |  LRU faults: %2zu\n",
               k,
               simulate_fifo(trace, n, k),
               simulate_clock(trace, n, k),
               simulate_lru(trace, n, k));
    }
    return 0;
}

Benchmark Output and Architectural Summary

Compiling and running the simulation produces:

1
2
Frames = 3  |  FIFO faults:  9  |  Clock faults:  9  |  LRU faults: 10
Frames = 4  |  FIFO faults: 10  |  Clock faults: 10  |  LRU faults:  8

Notice how adding a 4th frame reduces Exact LRU faults from 10 down to 8, whereas FIFO and single-hand Clock exhibit Bélády’s anomaly (9 $\to$ 10 on this specific adversarial sequence).

In production kernels such as Linux, the page reclaimer refines the Clock concept into a Two-Handed / Two-List LRU (active and inactive lists, or Multi-Generational LRU MGLRU), combining the hardware accessed and dirty bits to protect frequently used working-set pages from one-off sequential scans while keeping memory-access overhead near zero.