Page Replacement Algorithms

Here is the exact situation. Demand paging means a page is only brought into RAM when it is actually touched. A process runs, touches a page that is not resident, and faults. The kernel needs a free physical frame to load that page into. If the free list is empty — every frame is occupied — the kernel cannot proceed until it frees one. It runs the page replacement algorithm: pick a resident page (the victim), write it out to disk if it has been modified, mark its page-table entry as not-present, and hand the now-free frame to the faulting page. Only then does the faulting instruction get to retry.

Notice the stakes hidden in that paragraph. Every eviction is a bet about the future: you are betting the victim page will not be needed again soon. If you lose that bet, the very next reference to the victim faults, and you have paid two disk trips (writing it out, reading it back) to accomplish nothing. The goal of a replacement algorithm is therefore blunt: minimise the number of page faults over the life of the program. Fewer faults means fewer disk trips means the process spends its time computing instead of waiting.

To reason about this precisely we need a way to talk about a program’s memory behaviour without the noise of a whole address space. We use a reference string: the sequence of page numbers a process touches, in order. Real programs touch millions of pages, but the interesting behaviour of an algorithm shows up on a short string, so that is what we trace by hand. We fix the number of physical frames available, feed the reference string in one page at a time, and at each step ask: is this page already resident (a hit) or not (a fault)? On a fault with no free frame, the algorithm chooses a victim.

Reference string

The ordered sequence of page numbers a process accesses; the standard way to describe and compare replacement policies.

Frame

A fixed-size slot of physical RAM that holds exactly one page. The number of frames is what limits how much of the process fits in memory.

Page fault

A reference to a page that is not currently resident. It must be brought in from disk — expensive.

Victim / eviction

The resident page the algorithm chooses to remove to make room for the faulting page.

Fault rate

Faults divided by total references. The single number every replacement algorithm is trying to push down.

One convention before we start tracing. In every trace below, the frames begin empty. The first references therefore always fault simply because nothing is loaded yet — these are called cold or compulsory faults, and no algorithm can avoid them. The interesting differences between algorithms appear only once the frames fill up and real eviction choices begin. When you compare two algorithms, watch what happens after the frames are full; that is where the policy earns or loses its keep.

Start with the perfect algorithm, precisely because it is impossible. Belady’s optimal algorithm, usually written OPT or MIN, says: when you must evict, look at all the resident pages and throw out the one that will not be used for the longest time into the future. The intuition is airtight — the page you will need soonest is the worst one to evict, and the page you will need latest (or never again) is the best one to lose, because you get the most use out of the frame before you have to pay for it again.

It has been proven that no algorithm can produce fewer faults than OPT on a given reference string with a given number of frames. That is a strong statement: OPT is not just good, it is a provable lower bound on faults. Which is exactly why you cannot use it. To evict the page used farthest in the future, you must know the future — the entire remaining reference string — and a real OS servicing a live process has no idea what page it will touch next, let alone in ten thousand instructions. OPT is unrealizable.

So what is it for? It is the benchmark. When you invent or tune a real algorithm, you run it and OPT on the same reference string and compare fault counts. OPT tells you the best that was theoretically possible, so you learn not just that your algorithm caused 9 faults, but that the floor was 7 — you were 2 away from perfect. Without that yardstick, "9 faults" means nothing. Let us trace it on the string we will reuse for FIFO and LRU, so the three are directly comparable.

Reference:   7   0   1   2   0   3   0   4   2   3   0   3   2
-------------------------------------------------------------
Frame 0:     7   7   7   2   2   2   2   2   2   2   2   2   2
Frame 1:     .   0   0   0   0   0   0   4   4   4   0   0   0
Frame 2:     .   .   1   1   1   3   3   3   3   3   3   3   3
-------------------------------------------------------------
Fault?:      F   F   F   F   .   F   .   F   .   .   F   .   .

Step 4: load 2, evict 7 (7 is never used again).
Step 6: load 3, evict 1 (0 and 2 are used sooner; 1 never again).
Step 8: load 4, evict 0 (next uses: 2@9, 3@10, 0@11 -> 0 is farthest).
Step 11: load 0, evict 4 (4 is never used again).

Total faults = 7   (this is the provable minimum for this string)

Trace it yourself and watch the reasoning at step 8. The resident pages are {0, 2, 3}. Looking forward, 2 is used next (step 9), 3 after that (step 10), and 0 not until step 11 — so 0 is the victim, and we get to keep 2 and 3, which we are about to use. That is the kind of clairvoyant choice no real kernel can make, and it is why OPT’s 7 faults will be hard for anything realizable to match.

The simplest realizable policy is First-In, First-Out. Treat the resident pages as a queue in the order they were loaded. When you must evict, remove the page at the front — the one that has been in memory longest — and add the newcomer at the back. The appeal is that it is trivial to implement: keep a queue of frames, evict from the head, insert at the tail. No per-access bookkeeping, no timestamps, no hardware help. Just age.

The problem is that age is a poor proxy for usefulness. A page that was loaded early and is still being hammered on every iteration of a loop — think of a page holding a hot global table, or the top of the stack — is exactly the page FIFO throws out first, purely because it arrived first. FIFO cannot tell the difference between a page that was loaded long ago and abandoned versus one that was loaded long ago and is still central to the program. It evicts by seniority, not by value. Here is the same string, same three frames, under FIFO.

Reference:   7   0   1   2   0   3   0   4   2   3   0   3   2
-------------------------------------------------------------
Frame 0:     7   7   7   2   2   2   2   4   4   4   0   0   0
Frame 1:     .   0   0   0   0   3   3   3   2   2   2   2   2
Frame 2:     .   .   1   1   1   1   0   0   0   3   3   3   3
-------------------------------------------------------------
Fault?:      F   F   F   F   .   F   F   F   F   F   F   .   .

Load order (oldest first) drives every eviction:
Step 4: 2 in, evict 7 (oldest).   Step 8: 4 in, evict 2.
Step 6: 3 in, evict 0 (oldest).   Step 9: 2 in, evict 3.
Step 7: 0 in, evict 1 (oldest).   Step 10: 3 in, evict 0.
                                  Step 11: 0 in, evict 4.

Total faults = 10   (OPT needed only 7 on this same string)

Ten faults against OPT’s seven — FIFO leaves three on the table here, and on adversarial strings it does far worse. Look at page 0: it is referenced at steps 2, 5, 7, and 11, clearly a useful page, yet FIFO evicts it at step 6 (because it was old) and again at step 10, forcing reloads both times. It kept throwing out a page that kept coming back. That is the FIFO failure mode in one line: it is blind to how heavily a page is actually used.

Here is a result that offends intuition. You would expect that giving a process more frames can only help — more RAM means more pages fit, so faults should go down, or at worst stay the same. For most algorithms that is true. For FIFO it is not. In 1969 Laszlo Belady found reference strings where increasing the number of frames increases the number of page faults. Adding memory made the program slower. This is Belady’s anomaly, and it is a genuine defect of FIFO, not a rounding error.

The classic demonstration uses the reference string below. We run FIFO once with three frames and once with four, and count faults both times. Trace them side by side — this is worth doing slowly, because the surprise is only convincing when you have checked it yourself.

Reference:   1   2   3   4   1   2   5   1   2   3   4   5
---------------------------------------------------------
Frame 0:     1   1   1   4   4   4   5   5   5   5   5   5
Frame 1:     .   2   2   2   1   1   1   1   1   3   3   3
Frame 2:     .   .   3   3   3   2   2   2   2   2   4   4
---------------------------------------------------------
Fault?:      F   F   F   F   F   F   F   .   .   F   F   .

Total faults = 9

Reference:   1   2   3   4   1   2   5   1   2   3   4   5
---------------------------------------------------------
Frame 0:     1   1   1   1   1   1   5   5   5   5   4   4
Frame 1:     .   2   2   2   2   2   2   1   1   1   1   5
Frame 2:     .   .   3   3   3   3   3   3   2   2   2   2
Frame 3:     .   .   .   4   4   4   4   4   4   3   3   3
---------------------------------------------------------
Fault?:      F   F   F   F   .   .   F   F   F   F   F   F

Total faults = 10

Read the two fault rows. With three frames FIFO faults 9 times; with four frames — more memory — it faults 10 times. The extra frame did not just fail to help, it actively hurt. Why does this happen? Because FIFO’s eviction order depends on load order, and adding a frame changes which pages are resident when each eviction fires, which changes the load order downstream, which can line up evictions so that pages are thrown out just before they are reused. There is no guarantee that the set of pages FIFO keeps with N+1 frames is a superset of what it keeps with N frames — and without that "stack" property, weird things are allowed to happen.

This is not merely a curiosity for exams. It is the sharpest possible demonstration that FIFO’s notion of "which page to keep" is broken — an algorithm whose fault count can go the wrong way when you add resources is one you cannot reason about. Algorithms that avoid this are called stack algorithms, and their defining property is exactly that the pages resident with N frames are always a subset of those resident with N+1 frames. OPT and LRU are stack algorithms and therefore provably immune to Belady’s anomaly. FIFO is not.

OPT looks into the future; we cannot. But we have the next best thing — the past. Least Recently Used makes one assumption and rides it hard: pages used recently will probably be used again soon, and pages not touched in a long time probably will not be. So when it must evict, LRU throws out the page that has gone unused for the longest time. It is OPT with the arrow of time reversed: instead of "farthest in the future", it evicts "farthest in the past".

The reason LRU works so well in practice is that real programs have locality of reference. They spend most of their time in loops touching the same handful of pages (temporal locality) and walking through nearby data (spatial locality). A page touched a moment ago is very likely part of the current working set; a page untouched for a million instructions has almost certainly been left behind. LRU captures that instinct exactly, which is why it is the gold standard that cheaper real-world policies are all trying to imitate. Same string, same three frames.

Reference:   7   0   1   2   0   3   0   4   2   3   0   3   2
-------------------------------------------------------------
Frame 0:     7   7   7   2   2   2   2   4   4   4   0   0   0
Frame 1:     .   0   0   0   0   0   0   0   0   3   3   3   3
Frame 2:     .   .   1   1   1   3   3   3   2   2   2   2   2
-------------------------------------------------------------
Fault?:      F   F   F   F   .   F   .   F   F   F   F   .   .

Step 4: load 2, evict 7 (least recently used).
Step 6: load 3, evict 1 (0 was just used @5; 1 is oldest).
Step 8: load 4, evict 2 (0 used @7, 3 used @6; 2 is oldest).
Step 9: load 2, evict 3 (0 used @7, 4 used @8; 3 is oldest).
Step 10: load 3, evict 0 (4 used @8, 2 used @9; 0 is oldest).
Step 11: load 0, evict 4 (2 used @9, 3 used @10; 4 is oldest).

Total faults = 9   (OPT = 7, FIFO = 10 on this same string)

Nine faults — better than FIFO’s ten, and much closer to OPT’s seven. Contrast step 6 with FIFO: here LRU keeps page 0 because it was just referenced at step 5, whereas FIFO evicted it for being old. That one difference is LRU’s whole advantage — it protects hot pages regardless of when they were loaded. And because LRU is a stack algorithm, it is immune to Belady’s anomaly: give it more frames and its fault count can only stay the same or drop.

So why does no kernel implement exact LRU? Because "least recently used" requires knowing the order of every memory access, and memory accesses happen billions of times a second in hardware, far below where the OS can see them. To do it exactly you would need one of two things, and both are prohibitive. Option one: a hardware timestamp counter written into the page-table entry on every single access, plus a scan of all entries at eviction time to find the smallest — enormous memory-traffic overhead. Option two: a stack (or doubly linked list) of pages that you move-to-front on every access — which means extra bookkeeping work on every memory reference, again something no hardware does for free. Exact LRU is correct and expensive; the trick is to approximate it cheaply.

Temporal locality

A page used recently is likely to be used again soon. The core assumption LRU exploits.

Working set

The set of pages a process is actively using right now. LRU tries to keep the working set resident and evict everything else.

Stack algorithm

One where the pages resident with N frames are always a subset of those with N+1 frames. LRU and OPT qualify; FIFO does not — which is why they never suffer Belady’s anomaly.

Cost of exact LRU

Tracking a total order over accesses needs either a per-access hardware timestamp or a per-access list update — too expensive to do on every memory reference.

The bridge from ideal LRU to buildable LRU is one bit per page that the hardware maintains almost for free. It is called the reference bit (or accessed bit). The rule is simple: whenever a page is accessed — read or written — the MMU sets that page’s reference bit to 1. The OS can read the bit, and crucially it can clear it back to 0. This costs the hardware essentially nothing because it is a byproduct of the address translation it was doing anyway. From this one bit we can build surprisingly good LRU approximations.

The reference bit alone gives you a two-tier ranking: pages whose bit is 1 have been used since you last cleared it (recently used), pages whose bit is 0 have not (candidates for eviction). That is a crude two-bucket version of LRU — you cannot order pages within a bucket, but you can at least avoid evicting anything in the "used recently" bucket while an unused page is available. Second-chance turns this ranking into a working policy, and it is the direct ancestor of the Clock algorithm in the next section.

Reference bit (R)

A per-page bit the hardware sets to 1 on any access. The cheap raw material for every LRU approximation.

Second-chance

FIFO, but before evicting the oldest page you check its R bit. If R = 1, clear it to 0 and skip the page (a second chance); if R = 0, evict it. A used page survives one pass.

Additional reference bytes

Keep an 8-bit (or longer) history per page. Periodically shift right and insert the current R bit at the top, building a fuller recency record than one bit alone.

Aging

The additional-reference-bytes scheme read as an unsigned number: the page with the smallest value is the least recently used approximation, so evict it. Cheap, and close to true LRU.

Second-chance is the key idea, so make it concrete. You keep pages in FIFO order, but eviction is no longer automatic. To find a victim you look at the oldest page: if its reference bit is 0, it has not been touched since the last sweep, so evict it. If its bit is 1, it has been used recently — so you give it a second chance: clear its bit to 0, move it to the back as if freshly loaded, and move on to the next-oldest page. A page that keeps getting used keeps getting its bit re-set to 1 by the hardware and keeps surviving; a page that has gone quiet will eventually be found with a 0 bit and evicted. That is a decent approximation of "evict something not used recently" using nothing but one bit and a queue.

Aging refines this for cases where a single bit is too coarse. Instead of one bit, keep a byte of history per page. On a timer, the OS shifts every page’s byte right by one and slides the current reference bit into the top position, then clears the reference bit. A page used in the most recent period gets 10000000; a page used only several periods ago has drifted down to 00000010; a long-idle page is 00000000. Read as unsigned numbers, the smallest value is the best eviction candidate. Aging orders pages far more finely than second-chance while still touching only a few bits per page per timer tick — and it comes impressively close to true LRU.

Second-chance as described has an ugly implementation detail: giving a page a second chance means moving it to the back of a FIFO queue, and shuffling a queue is fiddly. The Clock algorithm is the elegant fix, and it is what real kernels actually run. Arrange all the frames in a circle — like numbers on a clock face — and keep a single pointer, the "hand", that sweeps around it. Each frame carries its reference bit. Nothing ever moves; only the hand advances.

When a page needs to be evicted, the hand starts sweeping from where it last stopped. At each frame it inspects the reference bit. If the bit is 1, the page was used recently, so the hand clears the bit to 0 and advances to the next frame — that is the page’s second chance. If the bit is 0, the page has not been touched since the hand last passed it, so it is the victim: evict it, load the new page in that frame with its reference bit set to 1, and leave the hand pointing at the next frame for the following eviction. On a plain hit (no fault), the hardware simply sets that page’s reference bit back to 1 and the hand does not move.

The beauty is that a heavily-used page keeps having its bit re-set to 1 by the hardware, so every time the hand reaches it the bit is 1 and it survives another lap — it is effectively protected as long as it stays hot. Only pages that have gone cold sit with a 0 bit long enough for the hand to catch and evict. And in the worst case, if every bit is 1, the hand makes one full sweep clearing all the bits, then comes back around and evicts the page it started on — degrading gracefully to FIFO, never looping forever. Let us walk a small clock.

Frames start empty; hand at slot 0.

Ref 1  fault  load into slot0, set bit.   [1*H]  -    -
Ref 2  fault  load into slot1, set bit.    1*  [2*H]  -
Ref 3  fault  load into slot2, set bit.    1*   2*  [3*H]
              (frames full; hand wraps to slot0)
Ref 1  HIT    set slot0 bit (already 1).  [1*H]  2*   3*

Ref 4  fault  sweep from slot0:
              slot0 1* -> clear to 1°, advance
              slot1 2* -> clear to 2°, advance
              slot2 3* -> clear to 3°, advance (wrap)
              slot0 1° -> bit 0, EVICT 1, load 4*.
              hand now at slot1.               4*  [2°H]  3°

Ref 2  HIT    set slot1 bit.                   4*  [2*H]  3°

Ref 5  fault  sweep from slot1:
              slot1 2* -> clear to 2°, advance
              slot2 3° -> bit 0, EVICT 3, load 5*.
              hand now at slot0.               4*   2°  5*  [H@slot0]

Faults: refs 1,2,3,4,5,7  -> 5 faults; hits at refs 4 and 6.

Follow the ref-4 eviction: page 1 had just been used (its bit was re-set at the hit), so the hand cleared its bit and gave it a chance — but pages 2 and 3 also had their bits set, so the hand cleared all three on the first lap and, coming back around, found page 1 now at 0 and evicted it. That is second-chance behaving correctly: recently-used pages are spared for one pass, and only a page that stays untouched through a full sweep is lost. Real Linux and BSD kernels have used variants of exactly this for decades.

One refinement worth naming: WSClock, the working-set clock. It augments each frame with a timestamp of its last use and combines the reference bit with a time threshold, so the hand evicts pages that are both unreferenced and older than the working-set window — and it also prefers to evict clean pages over dirty ones to avoid a disk write during the sweep. It is the practical marriage of the clock’s cheap sweep with the working-set model, and it is the shape of what production systems actually run.

Picking a victim is the core decision, but a handful of surrounding knobs shape how much that decision costs and whose pages are even in the running. The first is scope: global versus local replacement. Under global replacement, a faulting process can evict a frame belonging to any process — there is one shared pool and the algorithm ranges over everyone’s pages. Under local replacement, each process is given a fixed set of frames and can only evict its own. Global usually gives better overall throughput because memory flows to whoever needs it, but it means one greedy process can steal frames from its neighbours and hurt their fault rates — so isolation-sensitive systems lean toward local, or toward global with per-process limits.

The second knob is how many frames each process gets in the first place. Too few and the process faults constantly because its working set does not fit; too many and you are wasting RAM that another process could use to stop its own faulting. The target is to give each process roughly its working-set size — enough frames to hold the pages it is actively using. Allocation is often done proportionally to process size, but the working-set idea is the principle underneath, and when the sum of every process’s working set exceeds physical memory, no allocation scheme can save you — that is thrashing, and it is the whole subject of the next chapter.

The third knob directly changes eviction cost: the dirty bit. Just like the reference bit, the hardware sets a per-page modified (dirty) bit when a page is written to. When you evict a clean page — one not modified since it was loaded — you can simply drop it, because an identical copy still exists on disk; freeing the frame is instant. But evicting a dirty page means you must first write its contents back to disk, and that write is on the critical path of servicing the fault. This is why smart algorithms (and WSClock) prefer to evict clean pages when they can, and why kernels run background threads that proactively flush dirty pages to disk so that when eviction comes, more candidates are already clean.

Global vs local replacement

Global lets a fault evict any process’s page (better throughput, weaker isolation); local restricts each process to its own frames (stronger isolation, less flexible).

Clean vs dirty eviction

A clean page can be dropped for free (its copy is on disk); a dirty page must be written back first, adding a disk write to the fault’s cost.

Prefetching / prepaging

Bringing in pages before they fault, betting on spatial locality — e.g. reading ahead during a sequential scan so the next pages are resident before they are touched.

The last knob works the other direction from eviction: prefetching, or prepaging. Instead of waiting for each page to fault in one at a time, the OS predicts what you will need and loads it early. The classic case is a sequential scan — if a process just read page N and the access pattern looks linear, read N+1 and N+2 now, so their references become hits instead of faults. Prefetching amortises disk latency by reading in bulk, but it is a bet: prefetch pages that never get used and you have wasted both the disk bandwidth and the frames they occupy, possibly evicting something useful to make room. Good prefetchers watch the access pattern and back off when their guesses stop paying.

Pull it together with what production kernels actually ship. No mainstream OS runs exact LRU, exact OPT (impossible), or pure FIFO. They run tuned approximations built on the reference bit and clock-style sweeps. Linux, for instance, does not keep one list — it keeps two: an active list of pages judged to be in use and an inactive list of pages that have gone cold. Pages start on the inactive list; a second reference promotes them to active; pages on the active list that stop being referenced are demoted back to inactive; and reclaim evicts from the tail of the inactive list. It is a two-level, reference-bit-driven approximation of LRU that resists being fooled by a single access — a page has to prove sustained use to earn a spot on the active list. Under the hood it is the clock idea, scaled up and hardened.

When eviction pushes an anonymous (not file-backed) page out, it goes to swap — disk space standing in for RAM. And here the modern engineer’s attitude has hardened into a rule of thumb: for a latency-sensitive service, swapping is death. A page fault that hits swap can stall a request for milliseconds while a disk (or even an SSD) is read, and because that stall lands unpredictably, it does not raise your average latency so much as it wrecks your tail — the p99 and p999 that users and SLAs actually feel. This is why operators of low-latency services often disable swap entirely, or use tools like cgroups to cap memory and get a fast, predictable out-of-memory kill instead of a slow, invisible swap-death. "Add more swap" is exactly the wrong instinct when latency matters.

Now the payoff that makes this chapter worth your time as an engineer: this is not just kernel trivia, it is the identical problem you solve one layer up, constantly. Any cache is finite, so any cache must answer the eviction question. Redis exposes it directly — its maxmemory-policy setting lets you choose allkeys-lru (approximate LRU over all keys), allkeys-lfu (least-frequently-used, which favours frequency over recency), or others; Redis even implements approximate LRU by sampling a few keys and evicting the oldest, the exact "sample a cheap proxy" trick from the aging discussion. A CDN evicting cached objects, a browser cache, a database buffer pool deciding which disk pages to keep in memory, an ORM’s object cache — all of them are running a page-replacement algorithm under a different name. The OS just taught you the canonical version.

Linux active/inactive lists

A two-tier LRU approximation: pages must be referenced repeatedly to reach the active list; reclaim evicts from the tail of the inactive list. Clock-like, reference-bit-driven.

Swap

Disk space used to hold evicted anonymous pages. Necessary for memory flexibility, but a fault into swap is a disk-latency stall on the critical path.

Tail latency

The slow end of the latency distribution (p99, p999). Eviction-induced faults hurt the tail far more than the average — the metric that actually breaks SLAs.

LRU vs LFU in caches

The same eviction question at the application layer: evict by recency (LRU) or by access frequency (LFU). Redis, CDNs, and buffer pools all expose this choice.

Step back over the whole chapter. Every eviction is a bet about the future. OPT wins by cheating with perfect foresight and gives us the benchmark we can never beat. FIFO evicts by age, ignores usage, and can even fault more when given more memory — Belady’s anomaly. LRU bets that the recent past predicts the near future and wins in practice by tracking locality, but exact LRU is too expensive to build. So real systems approximate it with a reference bit, second-chance, aging, and above all the Clock sweep — near-LRU quality at almost no cost — surrounded by knobs for allocation, dirty-page writeback, and prefetching. That is the complete answer to "which page do we evict?"