Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › Operating Systems

Page Replacement Algorithms

With virtual memory, a process's pages don't all have to be in RAM (Memory Management, Paging and Virtual Memory). When a needed page is missing, a page fault happens: the OS loads it from disk. If RAM (the set of frames) is full, it must evict a page — the page replacement algorithm decides which one.

Goal: as few page faults as possible (disk is ~100,000× slower than RAM).

We use the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames for every example.

FIFO — evict the oldest page loaded

Ref 7 0 1 2 0 3 0 4 2 3 0 3 2
F1 7 7 7 2 2 2 2 4 4 4 0 0 0
F2 0 0 0 0 3 3 3 2 2 2 2 2
F3 1 1 1 1 0 0 0 3 3 3 3
Fault ✱ ✱ ✱ ✱ ✱ ✱ ✱ ✱ ✱ ✱
10 page faults. Simple, but it can evict a page that is used all the time.

Belady's anomaly

With FIFO, adding more frames can increase page faults for some reference strings (classic example: 1 2 3 4 1 2 5 1 2 3 4 5 → 9 faults with 3 frames, 10 with 4). LRU and Optimal never show this (they are stack algorithms).

Optimal (OPT / MIN) — evict the page used farthest in the future

Ref 7 0 1 2 0 3 0 4 2 3 0 3 2
F1 7 7 7 2 2 2 2 2 2 2 2 2 2
F2 0 0 0 0 0 0 4 4 4 0 0 0
F3 1 1 1 3 3 3 3 3 3 3 3
Fault ✱ ✱ ✱ ✱ ✱ ✱ ✱
7 page faults — the minimum possible. It needs to know the future, so it is not implementable; it is used as a benchmark.

LRU — evict the least recently used page

Ref 7 0 1 2 0 3 0 4 2 3 0 3 2
F1 7 7 7 2 2 2 2 4 4 4 0 0 0
F2 0 0 0 0 0 0 0 0 3 3 3 3
F3 1 1 1 3 3 3 2 2 2 2 2
Fault ✱ ✱ ✱ ✱ ✱ ✱ ✱ ✱ ✱
9 page faults. Uses the past to guess the future — usually close to optimal.

Implementing exact LRU needs a timestamp or a stack on every memory access — too costly in hardware, so OSes use approximations:

(The same LRU idea is the famous LRU cache coding question: hash map + doubly linked list, O(1) get and put.)

Comparison

Algorithm Faults (example) Implementable Belady's anomaly
FIFO 10 ✅ easy ✅ possible
Optimal 7 ❌ ❌
LRU 9 ✅ costly (approximated) ❌

Thrashing

When processes don't have enough frames for the pages they actively use, the CPU spends most of its time handling page faults instead of real work. CPU utilisation drops as more processes are added.

Fixes: the working-set model (give each process the frames for the pages it used in the last Δ references), page-fault-frequency control, reduce the number of processes, add RAM.

Formula

Effective access time = (1 − p) × memory access time + p × page-fault service time, where p = page-fault rate. Even p = 0.001 slows memory down massively because a fault costs milliseconds.

Interview one-liners

More Operating Systems notes