Lesson 2 · Memory management

Page Replacement Algorithms

When memory is full and a new page is needed, something resident must go. Which page you evict decides how many future faults you take, and the algorithms differ only in how they guess what will be needed next.

The Setup and the Metric

Page replacement is the act of choosing which resident page to evict when a page fault occurs and no free frame is available. When that happens the kernel must choose a victim to evict. Page replacement algorithms in OS design differ only in that choice, and they are compared by counting page faults on the same reference string — the sequence of pages a program touches.

The worked example on this page uses the reference string 7, 0, 1, 2, 0, 3 with three frames. The first three references fault trivially into empty frames. The interesting moment is page 2 arriving with all frames full, because from there the algorithms diverge.

Fault count is the metric because the cost gap is enormous. A memory access takes about 100 nanoseconds; a major fault that reads from SSD takes tens of microseconds, and from a spinning disk, milliseconds. A fault is between a hundred and a hundred thousand times more expensive than a hit, so shaving a few percent off the fault rate matters more than any constant-factor cleverness in the algorithm itself.

This also explains why an expensive algorithm can still be worth it — but only up to a point, since replacement decisions happen on the fault path with the process blocked.

The FIFO page replacement algorithm example below runs the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2 through three frames. These page replacement algorithms examples are worked end to end, so you can check every eviction against the frame table rather than taking the fault count on trust.

Choose a victim only when no free frame exists
Compare algorithms by faults on one reference string
A fault costs 100× to 100,000× a normal access
The decision runs on the fault path, so it must stay cheap

Optimal and FIFO

The optimal page replacement algorithm (OPT, or Belady's algorithm) is the policy that evicts the page whose next use lies furthest in the future. Optimal page replacement is the yardstick, not a candidate. It provably produces the minimum possible number of faults, and it is impossible to implement because it requires knowing the future.

It is still useful. Run it offline against a recorded trace and you get the floor — the best any algorithm could have done — which tells you whether your real algorithm has 5% or 50% left to gain. Without that baseline you cannot tell a good replacement policy from a bad one.

The FIFO page replacement algorithm evicts the page that has been resident longest, using a simple queue. It is trivial to implement and performs badly, because arrival time has almost nothing to do with future usefulness — a page loaded first may be the hottest page in the program.

FIFO also exhibits Belady's anomaly: adding more frames can increase the number of faults. This is deeply counter-intuitive and is a genuine property of FIFO, not a bug. Algorithms in the stack algorithm class — LRU and OPT among them — provably cannot suffer it, because the set of pages resident with N frames is always a subset of the set resident with N+1.

FIFO on 7,0,1,2,0,3,0,4,… with 3 frames — the frame-by-frame trace an exam expects
Reference	Frames after	Result	Evicted
7	7	Fault	—
0	7, 0	Fault	—
1	7, 0, 1	Fault	—
2	0, 1, 2	Fault	7 (oldest)
0	0, 1, 2	Hit	—
3	1, 2, 3	Fault	0 — just used
0	2, 3, 0	Fault	1
4	3, 0, 4	Fault	2
2	0, 4, 2	Fault	3

OPT needs the future; use it offline as the benchmark floor
FIFO evicts by age, which does not predict usefulness
Belady's anomaly: more frames, more faults
Stack algorithms like LRU and OPT are immune to it

Key reference

Terms, operations, and practical uses

The setup

VictimThe resident page evicted to free a frame.
Reference stringThe sequence of pages a program touches.
Cost gapA fault is 100x to 100,000x a normal memory access.

Algorithms

OPTEvicts the page used furthest ahead — the unreachable benchmark.
FIFOEvicts the oldest; age does not predict usefulness.
LRUEvicts least recently used; approximates OPT well.
ClockSecond chance via the free hardware reference bit.

Anomalies and bits

Belady's anomalyUnder FIFO, more frames can produce more faults.
Stack algorithmsLRU and OPT provably cannot suffer it.
Reference bitSet by the MMU on access, cleared by the sweeping hand.
Dirty bitA modified victim must be written back before reuse.

Code example

Three policies on one reference string

# One reference string, three frames, three policies. Count the faults.
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
FRAMES = 3

def fifo(refs, n):
    mem, order, faults = set(), [], 0
    for p in refs:
        if p in mem:
            continue
        faults += 1
        if len(mem) == n:
            victim = order.pop(0)        # oldest arrival, regardless of use
            mem.remove(victim)
        mem.add(p); order.append(p)
    return faults

def lru(refs, n):
    mem, recent, faults = set(), [], 0
    for p in refs:
        if p in mem:
            recent.remove(p); recent.append(p)   # touch: now most recent
            continue
        faults += 1
        if len(mem) == n:
            victim = recent.pop(0)       # least recently used
            mem.remove(victim)
        mem.add(p); recent.append(p)
    return faults

def opt(refs, n):
    mem, faults = [], 0
    for i, p in enumerate(refs):
        if p in mem:
            continue
        faults += 1
        if len(mem) == n:
            # evict whichever resident page is needed furthest in the future
            future = []
            for m in mem:
                future.append(refs.index(m, i) if m in refs[i:] else len(refs))
            mem.pop(future.index(max(future)))
        mem.append(p)
    return faults

print(f"FIFO {fifo(refs, FRAMES)} faults | LRU {lru(refs, FRAMES)} faults "
      f"| OPT {opt(refs, FRAMES)} faults on {','.join(map(str, refs))}")

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// One reference string, three frames, three policies. Count the faults.
int fifo(const vector<int>& refs, int n) {
    vector<int> mem;
    int faults = 0;
    for (int p : refs) {
        if (find(mem.begin(), mem.end(), p) != mem.end()) continue;
        faults++;
        if ((int)mem.size() == n) mem.erase(mem.begin()); // oldest arrival
        mem.push_back(p);
    }
    return faults;
}
int lru(const vector<int>& refs, int n) {
    vector<int> recent;
    int faults = 0;
    for (int p : refs) {
        auto it = find(recent.begin(), recent.end(), p);
        if (it != recent.end()) {
            recent.erase(it);
            recent.push_back(p);
            continue;
        }
        faults++;
        if ((int)recent.size() == n) recent.erase(recent.begin()); // least recent
        recent.push_back(p);
    }
    return faults;
}
int opt(const vector<int>& refs, int n) {
    vector<int> mem;
    int faults = 0;
    for (size_t i = 0; i < refs.size(); i++) {
        int p = refs[i];
        if (find(mem.begin(), mem.end(), p) != mem.end()) continue;
        faults++;
        if ((int)mem.size() == n) {
            int worst = -1, worstAt = -1;
            for (size_t m = 0; m < mem.size(); m++) {
                size_t nextUse = refs.size();
                for (size_t j = i + 1; j < refs.size(); j++)
                if (refs[j] == mem[m]) {
                    nextUse = j;
                    break;
                }
                if ((int)nextUse > worst) {
                    worst = nextUse;
                    worstAt = m;
                }
            }
            mem.erase(mem.begin() + worstAt); // needed furthest ahead
        }
        mem.push_back(p);
    }
    return faults;
}
int main() {
    vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    cout << "FIFO " << fifo(refs, 3) << " faults | LRU " << lru(refs, 3)
    << " faults | OPT " << opt(refs, 3) << " faults on ";
    for (size_t i = 0; i < refs.size(); i++) {
        if (i) cout << ',';
        cout << refs[i];
    }
    cout << "\n";
}

import java.util.ArrayList;
import java.util.List;
class Main {
    // One reference string, three frames, three policies. Count the faults.
    static int fifo(int[] refs, int n) {
        List<Integer> mem = new ArrayList<>();
        int faults = 0;
        for (int p : refs) {
            if (mem.contains(p)) continue;
            faults++;
            if (mem.size() == n) mem.remove(0); // oldest arrival
            mem.add(p);
        }
        return faults;
    }
    static int lru(int[] refs, int n) {
        List<Integer> recent = new ArrayList<>();
        int faults = 0;
        for (int p : refs) {
            if (recent.contains(p)) {
                recent.remove(Integer.valueOf(p));
                recent.add(p);
                continue;
            }
            faults++;
            if (recent.size() == n) recent.remove(0); // least recently used
            recent.add(p);
        }
        return faults;
    }
    static int opt(int[] refs, int n) {
        List<Integer> mem = new ArrayList<>();
        int faults = 0;
        for (int i = 0; i < refs.length; i++) {
            if (mem.contains(refs[i])) continue;
            faults++;
            if (mem.size() == n) {
                int worst = -1, worstAt = -1;
                for (int m = 0; m < mem.size(); m++) {
                    int nextUse = refs.length;
                    for (int j = i + 1; j < refs.length; j++)
                    if (refs[j] == mem.get(m)) {
                        nextUse = j;
                        break;
                    }
                    if (nextUse > worst) {
                        worst = nextUse;
                        worstAt = m;
                    }
                }
                mem.remove(worstAt); // needed furthest ahead
            }
            mem.add(refs[i]);
        }
        return faults;
    }
    public static void main(String[] args) {
        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < refs.length; i++) {
            if (i > 0) sb.append(',');
            sb.append(refs[i]);
        }
        System.out.println("FIFO " + fifo(refs, 3) + " faults | LRU " + lru(refs, 3)
        + " faults | OPT " + opt(refs, 3) + " faults on " + sb);
    }
}

Input7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames

OutputFIFO 10 faults | LRU 9 faults | OPT 7 faults on 7,0,1,2,0,3,0,4,2,3,0,3,2

Example

Run the example step by step

Output

LRU and Its Approximations

LRU (least recently used) is the policy that evicts the page unused for the longest time, betting on temporal locality — recently touched pages are likely to be touched again. That bet is right often enough that LRU comes close to OPT on real workloads.

Exact LRU is too expensive to implement in hardware. It needs the resident set kept in recency order and updated on every single memory access, either by timestamping each access or by moving an entry to the head of a list. Doing that work on every load and store would dominate the cost of memory access itself.

So real systems approximate. The clock (second-chance) algorithm arranges frames in a circle with a moving hand and uses the hardware reference bit that the MMU sets automatically on access. When the hand lands on a page: if the bit is set, clear it and move on — a second chance; if clear, evict. Pages touched since the last sweep survive, which is a decent approximation of recency for essentially zero cost.

Enhanced clock adds the dirty bit, preferring clean pages because a modified page must be written back before its frame can be reused. Linux refines this further into active and inactive LRU lists, promoting a page only on a second reference so a single large sequential scan cannot flush the working set — the exact behaviour that ruins naive LRU when you grep a huge file.

The four policies on the full reference string, 3 frames
Algorithm	Faults	Evicts	Implementable	Belady's anomaly
OPT	7	Page used furthest ahead	No — needs the future	No
LRU	9	Least recently used	Only approximately	No
Clock	≈ LRU	First page with a clear reference bit	Yes — nearly free	No
FIFO	10	Oldest arrival	Yes	Yes

LRU bets on temporal locality and approximates OPT well
Exact LRU needs work on every access — far too costly
Clock uses the free hardware reference bit as a recency proxy
Linux's two lists stop a sequential scan evicting the working set

Frame Allocation, Dirty Pages, and Thrashing

Choosing a victim is only half the problem; the other half is how many frames each process gets. Local replacement takes the victim from the faulting process's own frames, so a process cannot damage its neighbours but also cannot borrow when it genuinely needs more. Global replacement picks from anywhere, which adapts to demand but means one greedy process can degrade everything.

Allocation can be equal (frames divided evenly) or proportional (by process size), and priority can weight it further. Most systems use global replacement with a floor per process, because the flexibility is worth more than the isolation.

The dirty bit adds real asymmetry to the victim choice. A clean page can be dropped instantly because an identical copy exists on disk; a dirty page must be written out first, which means the fault now waits for a write and a read. Background writeback threads exist to keep the dirty population low precisely so replacement rarely hits this.

When the allocation is too small for the process's working set — the pages it actively needs — the result is thrashing: it faults, evicts a page it is about to need, faults again, and forward progress collapses while the disk saturates. The historical trap was systems reacting to the resulting low CPU utilisation by admitting more processes, which makes it worse. The fixes are to reduce multiprogramming, add memory, or use page-fault-frequency control to detect it early.

Local replacement isolates; global adapts and risks interference
Clean victims are free; dirty victims cost a writeback first
Thrashing means the working set does not fit the allocation
Admitting more processes during thrashing makes it worse