These are the notes for CS Fundamentals for Placements, episode 34. In episode 33 a missing page caused a page fault, and the OS always found a free frame for it. But RAM fills up. Today the fault arrives when no frame is free, so some page must leave. We invent page replacement: the reference string, counting page hits and page faults, FIFO, Belady's anomaly, Optimal (OPT), LRU (counter and stack implementations), stack algorithms, LRU approximation with the reference bit, second chance (clock), enhanced second chance, and the counting-based LFU and MFU, with numericals solved by hand and checked by real simulators. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 6 November 2026.
Quick recap: pages, frames, page faults, the dirty bit
- A page is a fixed-size piece of a process's memory, usually 4 KB. A frame is a page-sized slot in RAM.
- A page fault happens when a program touches a page that is not in RAM; the OS loads it from disk and restarts the instruction.
- The dirty bit (also called the modify bit) of a page is 1 if the page was changed while it was in RAM. A dirty page must be written back to disk before its frame can be reused; a clean page can simply be dropped.
- A page fault costs milliseconds; a memory access costs nanoseconds. From episode 33: with 200 ns memory and an 8 ms fault, one fault in 1000 accesses makes memory 41 times slower. So every extra fault matters.
The problem: RAM is full
The story: a study desk with room for three books
In exam week your desk holds three books; the rest are in a cupboard across the room. You need a fourth book and the desk is full, so one book must go back. Pick badly (the maths book you'll need in five minutes) and you walk to the cupboard again. Each walk is a page fault.
Page replacement
When a page fault happens and no frame is free, the OS:
- runs a page replacement algorithm to pick a victim page (the page that will leave RAM);
- if the victim is dirty, writes it to disk (swap space or its file);
- reads the new page into the freed frame;
- updates both page-table entries (victim: valid bit 0; new page: frame number, valid bit 1) and restarts the instruction.
Removing a page from its frame is called evicting it. Every algorithm answers one question, which page to evict, and the goal is always the fewest page faults.
Measuring algorithms: the reference string
A reference string is the list of page numbers a program touches, in order. All algorithms are compared on the same string. The classic textbook string (20 references, 6 distinct pages):
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
- Page hit: the referenced page is already in a frame. No disk access.
- Page fault (miss): it isn't; it must be loaded (and maybe a victim evicted).
- Hit ratio = hits / references. Miss ratio (page fault rate) = faults / references = 1 - hit ratio.
- Compulsory miss (cold miss): the first use of every page always faults, whatever the algorithm. So faults ≥ number of distinct pages. For the classic string, at least 6.
Real reference strings come from tracing a program's memory addresses and keeping only the page number (address / page size). Consecutive references to the same page are merged, since the second can't fault.
FIFO (first in, first out)
The story: a queue at the ticket counter
The first person to join the queue is the first to leave. FIFO page replacement evicts the page that was loaded earliest. It needs only a queue of frames (or a pointer that moves round the frames in a circle), so it is the simplest algorithm to build.
Live: FIFO on the classic string, 3 frames
#include <stdio.h>
// FIFO: when RAM is full, throw out the page that came in first
int main(void) {
int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = 20, F = 3, fr[3] = {-1, -1, -1}, oldest = 0, faults = 0;
int grid[3][20]; char mark[20];
for (int t = 0; t < n; t++) {
int hit = 0;
for (int i = 0; i < F; i++) if (fr[i] == ref[t]) hit = 1;
if (!hit) { // page fault
fr[oldest] = ref[t]; // replace the oldest page
oldest = (oldest + 1) % F; faults++;
}
for (int i = 0; i < F; i++) grid[i][t] = fr[i];
mark[t] = hit ? '.' : 'F';
}
printf("ref "); for (int t = 0; t < n; t++) printf("%2d", ref[t]);
for (int i = 0; i < F; i++) {
printf("\nframe%d ", i);
for (int t = 0; t < n; t++) printf(grid[i][t] < 0 ? " -" : "%2d", grid[i][t]);
}
printf("\nresult "); for (int t = 0; t < n; t++) printf(" %c", mark[t]);
printf("\nFIFO, %d frames: %d page faults, %d hits\n", F, faults, n - faults);
}
ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
frame1 - 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
frame2 - - 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
result F F F F . F F F F F F . . F F . . F F F
FIFO, 3 frames: 15 page faults, 5 hits
- Each column is one moment in time;
Fmarks a fault and.a hit. 15 faults, 5 hits (hit ratio 25%). oldestalways points at the frame that was filled earliest, so the victim is replaced in a circle: frame 0, 1, 2, 0, ...- Look at page 0: it is used again and again, yet FIFO evicts it at the sixth reference (when 3 arrives) and needs it straight back at the seventh. FIFO only asks how long a page has been in RAM, never whether it is still being used.
FIFO by hand: the exam method
- Draw one column per reference and one row per frame.
- Fill empty frames first (each is a compulsory miss).
- After that, on each fault, replace in a circle: top, middle, bottom, top again. A hit changes nothing.
- Count the
Fs. Check: the answer must be ≥ the number of distinct pages.
ref: 7 0 1 2 0 3 0 4 ...
7 7 7 2 2 2 2 4
0 0 0 0 3 3 3
1 1 1 1 0 0
F F F F . F F F
Belady's anomaly
Common sense says more frames can only help. Try FIFO on 1 2 3 4 1 2 5 1 2 3 4 5 with 1 to 5 frames:
#include <stdio.h>
// Count FIFO page faults for one reference string, with F frames
int fifo(int *ref, int n, int F) {
int fr[10], used = 0, oldest = 0, faults = 0;
for (int t = 0; t < n; t++) {
int hit = 0;
for (int i = 0; i < used; i++) if (fr[i] == ref[t]) hit = 1;
if (hit) continue;
faults++;
if (used < F) fr[used++] = ref[t]; // a free frame
else { fr[oldest] = ref[t]; oldest = (oldest + 1) % F; }
}
return faults;
}
int main(void) {
int ref[] = {1,2,3,4,1,2,5,1,2,3,4,5};
for (int F = 1; F <= 5; F++)
printf("FIFO, frames = %d: %2d page faults\n", F, fifo(ref, 12, F));
}
FIFO, frames = 1: 12 page faults
FIFO, frames = 2: 12 page faults
FIFO, frames = 3: 9 page faults
FIFO, frames = 4: 10 page faults
FIFO, frames = 5: 5 page faults
3 frames: 9 faults. 4 frames: 10 faults. Adding memory made FIFO worse. This is Belady's anomaly: for some reference strings, giving FIFO more frames causes more page faults.
It was published by Laszlo A. Belady, Robert A. Nelson and Gerald S. Shedler in Communications of the ACM, volume 12, issue 6 (1969), pages 349-353, "An anomaly in space-time characteristics of certain programs running in a paging machine". The abstract notes that running time "generally increases" as memory shrinks, but experiments found cases where "a decrease in the size of the store is accompanied by a decrease in running time", and gives a formal treatment "for the case of the FIFO replacement algorithm". Belady worked at IBM's Thomas J. Watson Research Center from 1961 to 1981.
The two FIFO tables, by hand:
3 frames 4 frames
ref 1 2 3 4 1 2 5 1 2 3 4 5 ref 1 2 3 4 1 2 5 1 2 3 4 5
f0 1 1 1 4 4 4 5 5 5 5 5 5 f0 1 1 1 1 1 1 5 5 5 5 4 4
f1 - 2 2 2 1 1 1 1 1 3 3 3 f1 - 2 2 2 2 2 2 1 1 1 1 5
f2 - - 3 3 3 2 2 2 2 2 4 4 f2 - - 3 3 3 3 3 3 2 2 2 2
res F F F F F F F . . F F . = 9 f3 - - - 4 4 4 4 4 4 3 3 3
res F F F F . . F F F F F F = 10
Why it happens: with 4 frames, FIFO's queue evicts pages in a different order, so at some moments the 4-frame RAM does not contain a page that the 3-frame RAM still has (after reference 7, page 5: 3 frames hold {5, 1, 2}, 4 frames hold {5, 2, 3, 4}; the next references are 1 and 2). An algorithm whose memory with n frames is always a subset of its memory with n + 1 frames can't do this (see stack algorithms below).
Exam answer: FIFO (and FIFO-based rules such as second chance) can suffer from Belady's anomaly; LRU and OPT never do.
Optimal page replacement (OPT, also called MIN)
The story: if you had tomorrow's timetable
If you knew every exam date, you'd put back the book you need last (or never again). OPT evicts the page whose next use is farthest in the future; a page that is never used again is the perfect victim.
Live: OPT on the classic string, 3 frames
#include <stdio.h>
// OPT: throw out the page that will not be used for the longest time
int main(void) {
int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = 20, F = 3, fr[3] = {-1, -1, -1}, faults = 0;
char mark[20];
for (int t = 0; t < n; t++) {
int hit = 0, victim = 0, farthest = -1;
for (int i = 0; i < F; i++) if (fr[i] == ref[t]) hit = 1;
mark[t] = hit ? '.' : 'F'; if (hit) continue;
faults++;
for (int i = 0; i < F; i++) { // look into the FUTURE
int next = n; // n = never used again
if (fr[i] < 0) next = n + 1; // an empty frame wins
else for (int k = t + 1; k < n; k++)
if (ref[k] == fr[i]) { next = k; break; }
if (next > farthest) { farthest = next; victim = i; }
}
fr[victim] = ref[t];
}
printf("ref "); for (int t = 0; t < n; t++) printf("%2d", ref[t]);
printf("\nresult "); for (int t = 0; t < n; t++) printf(" %c", mark[t]);
printf("\nOPT, %d frames: %d page faults\n", F, faults);
}
ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
result F F F F . F . F . . F . . F . . . F . .
OPT, 3 frames: 9 page faults
- 9 faults, against FIFO's 15. OPT gives the lowest possible number of faults for any reference string and number of frames; no algorithm can beat it.
- The inner loop (lines 15-16) reads
ref[k]fork > t: it looks into the future. A real OS cannot know which pages a program will touch next, so OPT can't be built. - Its job is to be a yardstick: record a program's reference string, run OPT on it, and see how close a real algorithm gets.
- Belady described this rule, MIN, in "A Study of Replacement Algorithms for a Virtual-Storage Computer", IBM Systems Journal, vol. 5, no. 2, June 1966, while working at IBM Research.
- OPT never shows Belady's anomaly.
OPT by hand: at each fault, look right along the string from the current position. Among the pages in the frames, evict the one that appears last (or doesn't appear at all). Ties (two pages never used again): evict either; the fault count is the same.
LRU (least recently used)
The story: your phone's recent apps
We can't see the future, but the recent past is a good guess of the near future (this is locality, from episode 33). An app you used a minute ago, you'll probably open again; an app untouched for a week can be closed. LRU evicts the page whose last use is farthest in the past. LRU is OPT looking backwards.
Live: LRU with a counter, 3 frames
#include <stdio.h>
// LRU: throw out the page that was used least recently
int main(void) {
int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = 20, F = 3, fr[3] = {-1, -1, -1}, last[3] = {0}, faults = 0;
char mark[20];
for (int t = 0; t < n; t++) {
int at = -1;
for (int i = 0; i < F; i++) if (fr[i] == ref[t]) at = i;
mark[t] = at >= 0 ? '.' : 'F';
if (at < 0) { // page fault
faults++; at = 0;
for (int i = 0; i < F; i++) { // empty frame, or the oldest use
if (fr[i] < 0) { at = i; break; }
if (last[i] < last[at]) at = i;
}
fr[at] = ref[t];
}
last[at] = t + 1; // counter: time of last use
}
printf("ref "); for (int t = 0; t < n; t++) printf("%2d", ref[t]);
printf("\nresult "); for (int t = 0; t < n; t++) printf(" %c", mark[t]);
printf("\nLRU, %d frames: %d page faults\n", F, faults);
}
ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
result F F F F . F . F F F F . . F . F . F . .
LRU, 3 frames: 12 page faults
- 12 faults: better than FIFO (15), not as good as OPT (9). That's the usual picture; on real programs LRU is close to optimal.
- Page 0 is used almost every other step and stays in RAM: LRU respects locality.
- The empty frames are taken first (line 14); after that, the frame with the smallest "last used" time is the victim (line 15).
Two ways to build LRU
- Counter (timestamp) implementation: on every memory access, copy a global clock into the page's "time of last use" field (in the page-table entry). To evict, search all pages for the smallest time. Cost: a write on every access, and a search on every replacement.
- Stack implementation: keep the page numbers in a list ordered by use, most recent on top. When a page is referenced, move it to the top. The bottom is always the least recently used, so no search is needed. Usually a doubly linked list (each node points to the one before and the one after) so a page can be unlinked and moved to the top with a few pointer changes.
after using 7, 0, 1, 2, then 0 again:
top → 0 2 1 7 ← bottom = least recently used = the next victim
The catch: both versions must update something on every single memory access, billions per second. Doing that in software is far too slow, and full LRU hardware is expensive. So real systems approximate LRU (below).
Stack algorithms: why LRU has no anomaly
Live: FIFO vs LRU, 1 to 5 frames
#include <stdio.h>
// FIFO vs LRU on the same string, with 1 to 5 frames
int faults(int *ref, int n, int F, int lru) {
int fr[10], when[10], used = 0, count = 0;
for (int t = 0; t < n; t++) {
int at = -1;
for (int i = 0; i < used; i++) if (fr[i] == ref[t]) at = i;
if (at >= 0) { if (lru) when[at] = t; continue; } // hit
count++; // fault
if (used < F) at = used++;
else { // victim: smallest time
at = 0;
for (int i = 1; i < F; i++) if (when[i] < when[at]) at = i;
}
fr[at] = ref[t]; when[at] = t; // FIFO: load time, LRU: last use
}
return count;
}
int main(void) {
int ref[] = {1,2,3,4,1,2,5,1,2,3,4,5};
printf("frames FIFO LRU\n");
for (int F = 1; F <= 5; F++)
printf(" %d %2d %2d\n", F, faults(ref, 12, F, 0), faults(ref, 12, F, 1));
}
frames FIFO LRU
1 12 12
2 12 12
3 9 10
4 10 8
5 5 5
The only difference between the two rules is line 8: on a hit, LRU refreshes the page's time; FIFO doesn't (so FIFO's time is the load time and LRU's is the last-use time). FIFO goes 9 → 10; LRU only goes down: 10 → 8 → 5.
A stack algorithm is one for which, at every moment, the set of pages in memory with n frames is a subset of the set with n + 1 frames. This is the inclusion property: a bigger desk always holds everything the smaller desk holds, plus more. So adding a frame can never add a fault. LRU and OPT are stack algorithms; FIFO is not. That is the real reason only FIFO-like rules suffer Belady's anomaly.
LRU approximation
The reference bit
Each page-table entry has a reference bit (also called the use bit or accessed bit). The hardware sets it to 1 whenever the page is read or written, almost for free. The OS clears the bits now and then, so 0 means "not used since the last clearing". Algorithms that use these bits instead of exact times are called LRU approximation algorithms.
Additional reference bits (aging)
Keep an 8-bit history byte per page. At every timer tick (for example every 100 ms), the OS shifts each page's history right by one and copies the reference bit into the top bit, then clears the reference bit. Read the byte as an unsigned number: bigger = used more recently. The page with the smallest number is (roughly) the least recently used.
page A: 11000100 = 196 used in the last two ticks
page B: 01110111 = 119
page C: 00000011 = 3 ← smallest: the victim
Second chance (the clock algorithm)
The story: the librarian's round
A librarian walks along a circular shelf looking for a book to remove. A book with a bookmark in it was read recently: she takes the bookmark out and moves on (a second chance). The first book without a bookmark is removed.
Second chance is FIFO plus the reference bit. The frames are arranged in a circle, and a pointer, the clock hand, points at the next candidate. On a fault:
- If the page under the hand has reference bit 1: clear it to 0 and move the hand on (the page gets a second chance).
- If it has reference bit 0: evict it, put the new page there (with bit 1), and move the hand on.
On a hit, only the page's bit is set to 1; the hand doesn't move.
Live: the clock, 3 frames
#include <stdio.h>
// Clock (second chance): a hand goes round; bit 1 = "used recently"
int main(void) {
int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = 20, F = 3, fr[3] = {-1, -1, -1}, bit[3] = {0}, hand = 0;
int faults = 0;
char mark[20];
for (int t = 0; t < n; t++) {
int at = -1;
for (int i = 0; i < F; i++) if (fr[i] == ref[t]) at = i;
if (at >= 0) { bit[at] = 1; mark[t] = '.'; continue; } // hit
mark[t] = 'F'; faults++;
while (fr[hand] >= 0 && bit[hand] == 1) { // second chance:
bit[hand] = 0; // clear the bit,
hand = (hand + 1) % F; // move on
}
fr[hand] = ref[t]; bit[hand] = 1; // replace here
hand = (hand + 1) % F;
}
printf("ref "); for (int t = 0; t < n; t++) printf("%2d", ref[t]);
printf("\nresult "); for (int t = 0; t < n; t++) printf(" %c", mark[t]);
printf("\nClock, %d frames: %d page faults\n", F, faults);
}
ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
result F F F F . F . F F . F F . F F F . F . F
Clock, 3 frames: 14 page faults
- 14 faults: between FIFO (15) and LRU (12), using only one bit per page and a pointer.
- If every bit is 1, the hand clears them all, comes back to where it started and evicts that page: the clock then behaves exactly like FIFO. Because it is FIFO-based, the clock can also show Belady's anomaly.
- Here a new page starts with its bit set to 1 (it was just used). Some textbooks start it at 0; check which convention a question uses, since the counts can differ.
Enhanced second chance (the reference and dirty bits)
Use the pair (reference bit, dirty bit) to put every page in one of four classes:
| Class | (ref, dirty) | Meaning | As a victim |
|---|---|---|---|
| 1 | (0, 0) | not used recently, clean | best: just drop it |
| 2 | (0, 1) | not used recently, dirty | must be written to disk first |
| 3 | (1, 0) | used recently, clean | probably needed again soon |
| 4 | (1, 1) | used recently, dirty | worst |
The hand goes round looking for the lowest non-empty class (it may need several passes). Evicting a clean page saves a whole disk write.
Counting-based: LFU and MFU
Keep a counter of how many times each page has been referenced.
- LFU (least frequently used): evict the page with the smallest count. Idea: a page used often is important. Problem: a page used heavily at start-up keeps a big count and never leaves, even when no longer needed. Fix: periodically shift the counts right (halve them), so old use fades (exponential decay).
- MFU (most frequently used): evict the page with the largest count. Idea: a page with a small count has probably just arrived and hasn't been used yet.
- Ties are usually broken by FIFO order (the page loaded earliest goes).
counts: A = 9 B = 2 C = 5
LFU evicts B MFU evicts A
Neither approximates OPT well and both are costly to keep exact, so they are rare in real kernels; both appear in exams.
A full numerical: one string, three algorithms
String 1 2 3 4 1 2 5 1 2 3 4 5, 3 frames:
FIFO LRU OPT
ref 1 2 3 4 1 2 5 1 2 3 4 5 ref 1 2 3 4 1 2 5 1 2 3 4 5 ref 1 2 3 4 1 2 5 1 2 3 4 5
f0 1 1 1 4 4 4 5 5 5 5 5 5 f0 1 1 1 4 4 4 5 5 5 3 3 3 f0 1 1 1 1 1 1 1 1 1 3 4 4
f1 - 2 2 2 1 1 1 1 1 3 3 3 f1 - 2 2 2 1 1 1 1 1 1 4 4 f1 - 2 2 2 2 2 2 2 2 2 2 2
f2 - - 3 3 3 2 2 2 2 2 4 4 f2 - - 3 3 3 2 2 2 2 2 2 5 f2 - - 3 4 4 4 5 5 5 5 5 5
F F F F F F F . . F F . F F F F F F F . . F F F F F F F . . F . . F F .
9 faults 10 faults 7 faults
OPT step by step: 1, 2, 3 fill the frames (3 faults). 4 faults: looking right, 1 and 2 come next and 3 is farthest, so evict 3. 1, 2 hit. 5 faults: 1 and 2 come next again, 4 is farthest, evict 4. 1, 2 hit. 3 faults: 1 and 2 are never used again, evict 1. 4 faults: evict 2 (never used again) or 3. 5 hits. Total 7.
Quick checks that catch most mistakes:
- OPT's answer must be the smallest of all.
- Every answer must be ≥ the number of distinct pages (here 5).
- When hits are rare, count hits instead: faults = references - hits.
- FIFO: a hit changes nothing. LRU: a hit moves the page to "most recent".
The whole chain
| Problem | Invention |
|---|---|
| RAM is full and a fault arrives | page replacement, victim page, reference string |
| The simplest rule | FIFO: 15 faults on the classic string |
| More frames made it worse | Belady's anomaly (1969) |
| What's the best possible? | OPT / MIN: 9 faults, needs the future (1966) |
| Use the past instead | LRU: 12 faults; counter and stack implementations |
| Why LRU has no anomaly | stack algorithms, the inclusion property |
| Exact LRU is too expensive | reference bit, additional reference bits |
| A cheap, good-enough LRU | second chance / clock: 14 faults; enhanced second chance |
| Another idea: count uses | LFU and MFU |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int fr[3] = {-1}; in a simulator |
14 faults instead of 15 (a fake hit on page 0) | Only fr[0] becomes -1; the rest become 0, which looks like page 0 |
{-1, -1, -1}, or fill the array with a loop |
| Moving a page on a hit in FIFO | your FIFO answer equals LRU's | FIFO looks only at load time | In FIFO, a hit changes nothing |
| "LRU suffers from Belady's anomaly" | wrong theory answer | LRU is a stack algorithm | Only FIFO-like rules (FIFO, second chance) do |
| Not counting the first loads | fault count too low | Compulsory misses count | faults ≥ distinct pages |
| OPT: looking left instead of right | OPT answer worse than LRU | OPT uses the future | At a fault, scan to the right |
| Forgetting the dirty victim in time questions | time too small | A dirty victim costs a disk write too | fault time = write-back + read |
The first row is a real bug, run in the video. The only change from the FIFO program is line 5:
#include <stdio.h>
// FIFO: when RAM is full, throw out the page that came in first
int main(void) {
int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = 20, F = 3, fr[3] = {-1}, oldest = 0, faults = 0;
int grid[3][20]; char mark[20];
for (int t = 0; t < n; t++) {
int hit = 0;
for (int i = 0; i < F; i++) if (fr[i] == ref[t]) hit = 1;
if (!hit) { // page fault
fr[oldest] = ref[t]; // replace the oldest page
oldest = (oldest + 1) % F; faults++;
}
for (int i = 0; i < F; i++) grid[i][t] = fr[i];
mark[t] = hit ? '.' : 'F';
}
printf("ref "); for (int t = 0; t < n; t++) printf("%2d", ref[t]);
for (int i = 0; i < F; i++) {
printf("\nframe%d ", i);
for (int t = 0; t < n; t++) printf(grid[i][t] < 0 ? " -" : "%2d", grid[i][t]);
}
printf("\nresult "); for (int t = 0; t < n; t++) printf(" %c", mark[t]);
printf("\nFIFO, %d frames: %d page faults, %d hits\n", F, faults, n - faults);
}
ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 7 0 0 0 0 2 2 2 2 2 1 1 1 1 7 7 7
frame1 0 0 1 1 1 3 3 3 3 3 0 0 0 0 2 2 2 2 2 1
frame2 0 0 0 2 2 2 2 4 4 4 4 3 3 3 3 0 0 0 0 0
result F . F F F F . F F . F F . F F F . F . F
FIFO, 3 frames: 14 page faults, 6 hits
In C, an initialiser with fewer values than the array fills the rest with 0. So frames 1 and 2 started as "page 0", and the second reference (page 0) was counted as a hit although page 0 was never loaded.
Mini project: a page replacement lab
Write one C program that reads a reference string and a number of frames from the input, and prints, for FIFO, OPT, LRU and Clock:
- the full frame table (one column per reference) with F/. marks;
- the number of faults and the hit ratio;
- a line saying which algorithm did best and how far each is from OPT (in faults and percent).
Then add: a --belady mode that tries 1 to 10 frames with FIFO and prints every frame count where adding a frame increased the faults; and LFU and MFU with FIFO tie-breaking. Test with the classic string and 1 2 3 4 1 2 5 1 2 3 4 5.
Practice
1. FIFO, LRU and OPT for 7 0 1 2 0 3 0 4 2 3 0 3 2 with 4 frames.
Solution
FIFO, 4 frames: 7 faults, 6 hits
ref 7 0 1 2 0 3 0 4 2 3 0 3 2
f0 7 7 7 7 7 3 3 3 3 3 3 3 3
f1 - 0 0 0 0 0 0 4 4 4 4 4 4
f2 - - 1 1 1 1 1 1 1 1 0 0 0
f3 - - - 2 2 2 2 2 2 2 2 2 2
res F F F F . F . F . . F . .
LRU, 4 frames: 6 faults, 7 hits (OPT gives the same table: 6 faults)
ref 7 0 1 2 0 3 0 4 2 3 0 3 2
f0 7 7 7 7 7 3 3 3 3 3 3 3 3
f1 - 0 0 0 0 0 0 0 0 0 0 0 0
f2 - - 1 1 1 1 1 4 4 4 4 4 4
f3 - - - 2 2 2 2 2 2 2 2 2 2
res F F F F . F . F . . . . .
FIFO evicts 0 when 4 arrives (0 was loaded first among the frames), so 0 faults again later. LRU evicts 1 instead (least recently used). Here LRU happens to match OPT.
2. Show Belady's anomaly for 1 2 3 4 1 2 5 1 2 3 4 5 by hand.
Solution
See the two FIFO tables in the Belady section: 3 frames give 9 faults and 4 frames give 10. The key moment is after the seventh reference (page 5): with 3 frames, RAM holds {5, 1, 2}; with 4 frames it holds {5, 2, 3, 4}. The next references are 1 and 2: hits for 3 frames, but page 1 faults for 4 frames, and the 4-frame run keeps evicting exactly the page it needs next.
3. Clock (second chance) with 3 frames for 1 2 3 1 4 1 5 2 (a new page starts with its bit set to 1).
Solution
ref 1 2 3 1 4 1 5 2
f0 1 1 1 1 4 4 4 2
f1 - 2 2 2 2 1 1 1
f2 - - 3 3 3 3 5 5
res F F F . F F F F = 7 faults
At reference 4 all three bits are 1 (page 1's hit set it again), so the hand clears all three, comes back to frame 0 and evicts page 1, the page that was just used. Then 1 faults straight back. This shows why the clock is only an approximation of LRU.
4. Why is exact LRU hard to build?
Solution
LRU must record the order of use on every memory access (a timestamp write, or moving a node to the top of a list), which is billions of updates per second, and with timestamps it also needs a search on every replacement. Software can't do that per access, and full hardware support is costly, so systems approximate LRU with the hardware reference bit (additional-reference-bits, second chance / clock).
5. A process has 4 frames and the string 1 2 3 4 5 1 2 3 4 5 (repeated). Compare FIFO, LRU and OPT.
Solution
The loop uses 5 pages and only 4 fit. With FIFO and LRU, the page needed next is always the one just evicted: every reference faults (10 of 10).
OPT, 4 frames: 6 faults
ref 1 2 3 4 5 1 2 3 4 5
f0 1 1 1 1 1 1 1 1 4 4
f1 - 2 2 2 2 2 2 2 2 2
f2 - - 3 3 3 3 3 3 3 3
f3 - - - 4 5 5 5 5 5 5
res F F F F F . . . F .
OPT: 1-4 fault (4). 5 faults: looking right, 1, 2, 3 come before 4, so evict 4. Then 1, 2, 3 hit. 4 faults: 1 is never used again, evict it. 5 hits. 6 faults. With FIFO/LRU this is thrashing from episode 33: a process needs frames for its whole locality.
6. Hit ratio: FIFO on the classic string with 3 frames.
Solution
5 hits out of 20 references: hit ratio = 5/20 = 0.25, miss ratio = 15/20 = 0.75.
Quick quiz
reference string: 1 2 3 2 1 4 2 1
frames: 3
algorithm: LRU
// how many page faults?
A. 4 B. 5 C. 6 D. 3
Answer
A. 4. 1, 2, 3 fault (3). 2 and 1 hit. 4 faults; the least recently used of {1, 2, 3} is 3 (last used at the third reference), so 3 is evicted (4 faults). 2 and 1 hit. With FIFO the answer would be 5 (FIFO evicts 1, the first loaded, and 1 faults at the end).
Interview questions
- What is page replacement and when does it run? On a page fault with no free frame: the OS picks a victim page, writes it back if dirty, and loads the new page into its frame.
- Explain FIFO page replacement and its weakness. Evict the page loaded earliest. Simple (a queue), but it ignores use, so a busy page can be evicted; it can suffer Belady's anomaly.
- What is Belady's anomaly? Give an example. More frames causing more page faults under FIFO.
1 2 3 4 1 2 5 1 2 3 4 5: 9 faults with 3 frames, 10 with 4 (Belady, Nelson and Shedler, CACM 1969). - What is the optimal algorithm and why can't it be used? Evict the page whose next use is farthest in the future; gives the minimum faults but needs future knowledge, so it's a benchmark only.
- Explain LRU and two ways to implement it. Evict the page unused for the longest time. Counters (timestamp per page, search for the smallest) or a stack/doubly linked list (move to top on use, evict the bottom).
- What is a stack algorithm? One where the pages held with n frames are always a subset of those with n + 1 frames; such algorithms (LRU, OPT) cannot show Belady's anomaly.
- How does the clock (second chance) algorithm work? FIFO in a circle with a reference bit: bit 1 → clear and skip; bit 0 → evict. Degenerates to FIFO when all bits are 1.
- What is enhanced second chance? Clock using (reference, dirty) classes; prefers (0,0) victims to avoid write-backs.
- LFU vs MFU? LFU evicts the smallest use count; MFU evicts the largest (assuming small counts are new pages). Both are rare in practice.
- Which algorithms suffer from Belady's anomaly? FIFO and FIFO-based ones like second chance; not LRU or OPT.
- What is the minimum number of page faults for any algorithm? At least the number of distinct pages in the string (compulsory misses); OPT achieves the true minimum.
- Where else are these algorithms used? Any cache: CPU caches (episode 10), database buffer pools, web and CDN caches all choose victims with LRU-like rules.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Page | A fixed-size piece of a process's memory | 4 KB |
| Frame | A page-sized slot in RAM | frame 2 |
| Page fault (miss) | The page touched isn't in RAM, so it must be loaded | first use of page 7 |
| Page hit | The page touched is already in a frame | page 0 at reference 5 |
| Page replacement | Choosing a page to remove from RAM when no frame is free | evict 7 to load 2 |
| Page replacement algorithm | The rule that picks the victim | FIFO, LRU, OPT |
| Victim page | The page chosen to leave RAM | page 7 |
| Evict | Remove a page from its frame | 2 replaces 7 |
| Dirty (modify) bit | 1 if the page was changed in RAM; must be written back before eviction | edited page |
| Reference string | The page numbers a program uses, in order | 7 0 1 2 0 3 ... |
| Hit ratio | hits / references | 5/20 = 0.25 |
| Miss ratio (page fault rate) | faults / references = 1 - hit ratio | 15/20 |
| Compulsory (cold) miss | The unavoidable fault on a page's first use | 6 for the classic string |
| FIFO (first in, first out) | Evict the page loaded earliest | 15 faults |
| Queue | A line where the first in is the first out | ticket counter |
| Belady's anomaly | More frames giving more faults (FIFO) | 3 frames 9, 4 frames 10 |
| OPT / MIN (optimal) | Evict the page whose next use is farthest in the future | 9 faults |
| Yardstick (benchmark) | A standard to compare others against | OPT's fault count |
| LRU (least recently used) | Evict the page whose last use is farthest in the past | 12 faults |
| Counter (timestamp) implementation | Each page stores its time of last use | last[i] = t + 1 |
| Stack implementation | A list ordered by use, most recent on top, victim at the bottom | top → 0 2 1 7 |
| Doubly linked list | A list whose nodes point both forward and back | quick move-to-top |
| Stack algorithm | Pages held with n frames ⊆ pages held with n + 1 frames | LRU, OPT |
| Inclusion property | That subset rule, true at every moment | bigger desk ⊇ smaller desk |
| Reference (use, accessed) bit | Set to 1 by hardware when the page is used | bit = 1 after a read |
| LRU approximation | Algorithms that estimate LRU from reference bits | clock |
| Additional reference bits (aging) | An 8-bit history per page, shifted each tick | 11000100 |
| Second chance algorithm | FIFO that skips (and clears) pages with reference bit 1 | bookmark removed |
| Clock algorithm | Second chance with frames in a circle and a moving hand | 14 faults |
| Clock hand | The pointer to the next candidate frame | hand |
| Enhanced second chance | Clock using (reference, dirty) classes | prefer (0,0) |
| LFU (least frequently used) | Evict the page with the smallest use count | evicts B (2) |
| MFU (most frequently used) | Evict the page with the largest use count | evicts A (9) |
| Locality | Programs keep reusing a small set of pages | page 0 in the classic string |
| Thrashing | Too few frames: the process spends its time faulting | 5-page loop in 4 frames |
| Initialiser (C) | The {...} values given to an array when declared; missing ones become 0 |
{-1} |
Summary
- When RAM is full, a page replacement algorithm picks a victim; a dirty victim is written back first. Algorithms are compared by counting faults on a reference string (faults ≥ distinct pages).
- FIFO evicts the oldest page (live: 15 faults on the classic string) and can show Belady's anomaly (live: 3 frames 9 faults, 4 frames 10; Belady, Nelson and Shedler, CACM 1969).
- OPT / MIN evicts the page used farthest in the future: the minimum (live: 9), but it needs the future (Belady, IBM Systems Journal, 1966).
- LRU evicts the page used farthest in the past (live: 12); built with counters or a stack; it's a stack algorithm, so no anomaly (live: 10 → 8 → 5).
- Exact LRU is too costly, so systems use the reference bit: additional reference bits, second chance / clock (live: 14) and enhanced second chance with the dirty bit.
- LFU and MFU count uses; rare in practice, common in exams.
Next episode: File systems 1: files, file descriptors, access methods, directory structures, paths, links and permissions.