Page Replacement

Page replacement is the operating system's policy for choosing which resident page to evict when a program faults and physical memory is already full. FIFO evicts the page that arrived first, LRU the page used least recently, and Clock approximates LRU with a single reference bit per frame.

Reading the tags to make that choice costs a few comparisons; keeping the tags current costs work on every memory access; getting the choice wrong costs a page fault, which is roughly a million cycles. Those three numbers are why there is more than one policy.

Here is the thing worth holding onto before anything else. Give each frame of RAM one sticky note. FIFO writes a number on the note when the page arrives and never touches it again. LRU rewrites the note every single time the page is used. Clock does not write a number at all — it writes one bit, and a slowly rotating hand keeps wiping it. That sticky note is the entire difference between the three policies. Same hardware, same fault mechanism, same code around it; different scrap of paper, and on the run this page animates, two fewer trips to storage.

How Page Replacement Works

Virtual memory gives every process more address space than the machine has RAM. That works right up until the moment it does not: a program touches a page that is not resident, the kernel traps, and there is no free frame to put it in. Something already in memory has to leave.

Every policy answers the same question — which one — and they all have the same three moves. Check whether the wanted page is resident. If it is, that is a hit, and the page never leaves RAM. If it is not, that is a fault, and the page must come in from storage: into a free frame if one exists, otherwise into a frame you take from somebody else.

Only the last case is a policy decision, and it is made by reading the tags:

• FIFO keeps arrived, the access number at which the page was loaded, and evicts the smallest. It is a queue: first in, first out. The tag is written once, on load, and a hit does not touch it.
• LRU keeps last_used, the access number at which the page was last touched, and evicts the smallest. Every hit rewrites the tag. That single extra write is what separates it from FIFO.
• Clock keeps R, one bit, set to 1 by a hit. A hand sweeps the frames in a ring; at each frame, if R is 1 the page is spared and the bit is cleared, and the hand moves on. The first frame it finds with R already 0 is the victim. The hand stops at the victim while it is chosen, then advances past that frame after the new page is loaded. The next fault resumes there rather than restarting at frame zero.

Notice what LRU is buying. A hit is the only information a replacement policy ever gets for free — the program has told you, at no cost, which pages it still cares about. FIFO throws that information away. That is not an implementation detail; it is the reason FIFO is bad, and you can watch it happen.

Notice also what Clock is buying. Real LRU needs to maintain a total order over the resident pages on every memory access, and no hardware will do that for you. What hardware does give you is one bit per page-table entry that it sets on reference. Clock is the policy you get when you accept that bit as your whole budget: it cannot rank pages, but it can separate "used since I last looked" from "not used at all", and it turns out that is most of what you needed.

Page Replacement Step by Step

The default run gives the machine three frames and issues twelve accesses under FIFO: 0 1 2 · 0 1 3 · 0 1 4 · 0 1 2. Read it as a program with a hot pair — it keeps coming back to P0 and P1 — that touches one cold page in between each time.

Accesses 1, 2, 3 — P0, P1, P2. Three faults, and no decision in any of them. Nothing is resident, so each page goes into a free frame and gets a tag: P0 in F0 with arrived @1, P1 in F1 with @2, P2 in F2 with @3. These are compulsory faults. No policy can avoid them; you cannot keep a page you have never seen.

Accesses 4 and 5 — P0, P1. Both resident, both hits, no disk. This is the beat the whole lesson turns on. The animation stops here to point at a tag that does not move: F0 still reads arrived @1. The program has just announced that P0 is hot, and FIFO wrote it down nowhere.

Access 6 — P3. Not resident, and RAM is full. FIFO reads the three tags — @1, @2, @3 — and takes the smallest. That is P0, the page hit two accesses ago, at access 4. Its clean resident copy is discarded; P3 lands in F0 with arrived @6. Fault 4.

Access 7 — P0. The page FIFO just threw out. Fault. The tags are now @6, @2, @3, so the victim is P1 — the other hot page. P0 comes back into F1 with @7. Fault 5.

Access 8 — P1. Same story: fault, evict P2 (@3), load into F2 with @8. Fault 6.

Three accesses, three faults, and the two pages the program actually uses have both been evicted and refetched. FIFO's queue rotated straight through the working set.

Access 9 — P4. Fault. Smallest tag is @6, so P3 goes. Fault 7.

Accesses 10 and 11 — P0, P1. Hits at last: both happen to still be resident. Their tags stay at @7 and @8.

Access 12 — P2. Fault. Tags are @9, @7, @8; the smallest is @7, so P0 is evicted again. Fault 8.

The run ends at 8 faults and 4 hits. Then the first of two closing beats draws the same twelve accesses through the same three frames under all three policies — FIFO 8, LRU 6, Clock 6 — beside the choice that produced each count. At the first eviction FIFO gave up P0 on arrived @1, LRU gave up P2 on last used @3, and Clock gave up P2 because its bit was still 0. Three policies, one access, two different victims and three selection rules: that line is the whole lesson in one row.

FIFO vs LRU vs Clock on the Same Input

Switch the policy selector to LRU and replay. The first three faults are identical — compulsory misses do not care about policy. Accesses 4 and 5 are hits again, but now the tags move: F0 becomes last used @4, F1 becomes @5.

So when P3 faults at access 6, the tags read @4, @5, @3, and the victim is P2 — the cold page nobody has touched since it arrived. P0 and P1 stay. Accesses 7 and 8 are hits instead of faults, and the same thing happens again at access 9 (P3 goes) and access 12 (P4 goes). LRU evicts a cold page every single time, and finishes at 6 faults.

Two fewer faults out of twelve. At roughly a million cycles a fault, that is about two million cycles of disk that better bookkeeping avoided — and the only thing that changed was one line in the hit branch.

Now switch to Clock. It faults on exactly the same six accesses, and evicts exactly the same three pages. With this much locality, one bit is as good as a timestamp: by the time the hand reaches P2, P0 and P1 have had their bits set by hits, so they are spared and cleared while P2, whose bit was never set, is taken. Clock is not a compromise here. It is LRU's answer at a fraction of the cost, which is why it and its descendants are what real kernels ship.

Clock's honest worst case is worth seeing too. Load the Clock's full sweep preset: every resident page has been hit, so every bit is 1, and the hand has to clear the entire ring and come back round to where it started. It ends up taking the oldest frame — the same page FIFO would have taken. When every page looks equally used, one bit cannot tell them apart, and Clock degenerates into FIFO. That is the price of the approximation, and it is a good deal, because it happens rarely and costs one extra pass over a handful of frames.

When More Memory Makes Page Replacement Worse

Every instinct says more RAM means fewer faults. For FIFO, that instinct is provably wrong.

Load the Bélády: 3 frames preset. FIFO runs 0 1 2 3 · 0 1 4 · 0 1 2 3 4 and takes 9 faults. Now load Bélády: 4 frames — identical string, identical policy, one more frame. It takes 10. This is Bélády's anomaly, and it is not a rounding artifact; you can watch every eviction that causes it.

The reason is a property FIFO does not have. LRU is a stack algorithm: the set of pages LRU keeps resident with k frames is always a subset of the set it keeps with k+1 frames. Adding memory can only ever turn a fault into a hit, never the reverse. FIFO's resident set is not nested that way — the extra frame changes the eviction order, so a bigger machine can throw out a page the smaller machine would have kept, and pay for it two accesses later. Switch the same pair of presets to LRU and the anomaly disappears, because it cannot happen.

The second closing beat draws the whole series: this policy on this string at two, three, four and five frames, with a marker on any step where the count went up. On the Bélády string under FIFO, that marker is the picture.

When LRU Falls Off a Cliff

LRU's guarantee is about monotonicity, not about being good. Its actual bet is that recent use predicts future use, and a loop is where that bet loses.

Load A loop that thrashes: four pages cycled three times through three frames, under LRU. The hit count is zero. Every page is evicted exactly one access before the program asks for it again, because "least recently used" is precisely "next one needed" when you are walking a ring. Twelve accesses, twelve faults, which is what a policy looks like when its assumption is inverted.

Then load A loop that fits — same loop, one more frame. Four compulsory faults and eight hits. The cliff is one frame wide. This is the shape of real thrashing: performance does not degrade smoothly as the working set grows past physical memory, it falls off an edge, and the fix is almost never a cleverer policy.

Edge Cases

• A cold fault is not a policy decision. While a free frame exists, the fault costs a disk trip and nothing is evicted. A run starts with one per frame — fewer if it touches fewer distinct pages — and no policy can do better. When you compare policies, compare what they do after memory fills.
• A reference string with no reuse defeats everything. Load Nothing to reuse — six pages touched once each. All three policies tie at six faults, because a replacement policy can only exploit reuse the program actually has. If your profile shows a high fault rate with no reuse in sight, the lever is the access pattern, not the kernel.
• Loaded once is not the same as still resident. Access 7 of the default run asks for P0, which was loaded at access 1 and hit at access 4. It faults, because access 6 evicted it. This is the single most common mistake in tracing these by hand.
• A hit on the frame the Clock hand is pointing at sets R to 1 without moving the hand. The hand moves only on a fault: one step past each page it clears, and one more after installing the new page. A bit is cleared only when the hand reaches it, so hits in between just keep it at 1.
• Two frames is the smallest machine that has a policy at all. With one frame every fault evicts the only resident page and all three policies are identical. The slider stops at two for that reason.
• The animation caps the reference string at 15 accesses and pages at P0–P5. That is a visualization limit — six identity colors, one ribbon that fits on screen — not an algorithmic one.

Common Mistakes

• Equating exact LRU with every operating system's reclaim policy. Exact ordering on every memory reference is expensive, so kernels use sampled recency and other approximations. Linux policies vary by configuration and include Multi-Gen LRU. Buffer pools also choose among LRU variants and clock-style policies. Exact LRU remains a useful baseline, not a universal description of kernel reclaim.
• Assuming the anomaly is a FIFO curiosity you can ignore. The useful takeaway is not "FIFO is weird" but "not every policy is a stack algorithm". Second-chance and Clock are also non-stack, and any eviction policy you invent yourself — for a cache, a connection pool, a CDN tier — is non-stack until you prove otherwise. If you cannot prove it, do not promise users that more capacity means fewer misses.
• Confusing a page fault with a page-table miss. They are different failures. A translation missing from the TLB costs a page-table walk; a page missing from RAM costs a disk trip, four orders of magnitude worse. This page is entirely about the second one. The virtual memory lesson pulls the two apart.
• Tuning the policy when the working set does not fit. The loop presets are the demonstration: at three frames these three displayed policies all fault on every access, and at four every policy is fine. When the resident set is too small for the program's working set, the answer is more memory, a smaller working set, or different I/O — and a victim heuristic alone cannot make a too-large active set fit, even though another policy may reduce some faults.
• Reading "evicted" as "lost". The modeled clean page already has a backing copy, so its resident copy can be discarded without a write. Nothing is destroyed. Getting it back costs a fault, which is expensive, but it is a latency cost and not a correctness one — which is exactly why the kernel is free to guess wrong.
• Assuming eviction is free. This page counts faults and stops there. A real eviction also has to check whether the page is dirty, and a dirty page must be written back before its frame can be reused, which doubles the disk traffic for that eviction. That is why real policies prefer clean victims when they can find one.

A Note on Simplification

This is a teaching model. One process, demand paging only, six pages, at most five frames — real systems juggle thousands of processes over millions of 4 KB frames, and the reference string is a program's whole memory access history rather than twelve numbers.

Three simplifications are worth naming because they change what you would conclude. First, no dirty bit: every eviction here costs the same, when in reality writing back a modified page costs a second disk trip. Second, Clock loads a page with R = 0, on the reasoning that a new page must earn its bit; some textbooks load with R = 1 instead, and on the default string that convention would let the first full sweep clear every bit and collapse Clock's behavior into FIFO's. Third, LRU is shown as a linear scan of the frames, which is honest for five frames and absurd for five million — the real O(1) construction is a hash map over a doubly linked list, which is its own LeetCode problem.

The fault cost of ~1,000,000 cycles is the order of magnitude carried over from virtual memory. An NVMe SSD is closer to 100,000; a spinning disk is worse than a million. Treat it as a scale, not a measurement — the argument here only needs it to be enormous compared to the cost of reading three tags.

There is one policy this page deliberately leaves out: OPT, which evicts the page that will not be needed for the longest time. It is optimal, it is unimplementable (it requires knowing the future), and its only real use is as a lower bound you measure your actual policy against. If you ever have a trace on disk, running OPT over it offline gives the minimum fault count for that trace and capacity. The excess above it is avoidable under that offline benchmark; its own faults can include both compulsory and capacity-related faults. That number is usually the one that ends the argument.