JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Who Gets Evicted? The Replacement Problem

Demand paging promised to run programs bigger than your RAM. But when every frame is full and a new page is needed, someone must move out. This guide frames that eviction problem, shows why a dirty page costs more to evict than a clean one, and introduces the yardstick — the page-fault rate — by which every replacement policy is judged.

The day the frames run out

By now you have met demand paging: a process starts with almost nothing in RAM, and the OS pulls in a page only when the program actually touches it, signalled by a page fault. This is what makes virtual memory feel like magic — a program with a huge address space runs while only a handful of its pages are resident in physical frames. For a while this works beautifully, because each fault simply finds a free frame and loads the page into it.

But physical memory is finite, and the whole point of virtual memory is to let the total demand of running programs exceed the RAM you own. So inevitably the day comes when a page fault arrives and there is no free frame left: every frame is already holding some page belonging to some process. The OS cannot just refuse — the faulting instruction needs that page to continue. It must make room. It has to pick a frame that is currently in use, evict whatever page lives there, and reuse that frame for the page being brought in. This is the replacement problem, and choosing the victim is the job of a page-replacement policy.

Eviction, step by step

Let us slow down and watch a single page fault when memory is full, because the steps reveal where the cost hides. Recall that the act of choosing which frame to free is called victim-page selection — the chosen page is the victim. What happens to the victim is more interesting than it first looks, and it depends entirely on one tiny piece of bookkeeping we will meet in the next section.

  1. A process touches a page that is not resident; the hardware raises a page fault and traps into the kernel.
  2. The OS looks for a free frame and finds none — every frame is occupied. So it runs its replacement policy to pick a victim frame.
  3. If the victim page was modified since it was loaded, the OS must first write it back out to disk (a page-out); if it was untouched, this step is skipped entirely.
  4. The OS marks the victim's page-table entry as invalid (no longer resident), so any future access to it will itself fault.
  5. The OS reads the wanted page from disk into the now-free frame, updates the faulting process's page table to point there, and restarts the instruction that faulted.

Notice that a worst-case fault now involves two disk transfers, not one: writing the victim out, then reading the new page in. Disk (or even an SSD) is staggeringly slower than RAM — a memory access takes nanoseconds, a disk access takes milliseconds, a gap of roughly a hundred thousand times. So the difference between one disk transfer and two is enormous, and it falls out of a single yes-or-no question about the victim: was it modified? That question is answered by a single bit.

The dirty bit: cheap evictions and costly ones

For each resident page the hardware keeps a dirty bit (also called the modify bit) inside the page-table entry. It starts at zero when the page is loaded. The very first time the program writes to that page, the hardware flips the bit to one, automatically, with no help from the OS. So the dirty bit answers exactly one question: has this page changed since it came in from disk?

Why does this matter so much? If the dirty bit is zero, the page is clean: the copy in RAM is byte-for-byte identical to the copy still sitting on disk. So when a clean page is chosen as the victim, the OS can simply overwrite its frame — the disk copy is already correct, nothing needs saving. That is a cheap eviction: one disk transfer, only the read of the incoming page. But if the dirty bit is one, the page is dirty: it holds changes that exist nowhere else. Evicting it forces a page-out first — write the page to disk so the changes survive — and only then can the frame be reused. That is a costly eviction: two disk transfers.

Reference strings and the score we keep

To compare replacement policies fairly we need a common test, and the standard one is a reference string: simply the sequence of page numbers a process touches, in order, with consecutive repeats usually collapsed (touching page 7 three times in a row counts once, since the second and third touches never fault). A reference string is the script of a process's memory life, stripped down to the only thing replacement cares about — which page, in what order. Feed the same string and the same number of frames to two policies and you can count, exactly, how many faults each one causes.

Reference string (page numbers touched, in order):
   7  0  1  2  0  3  0  4  2  3

With 3 frames, walk it left to right:
   - a page already resident  -> HIT  (no fault)
   - a page not resident      -> FAULT (must load it; maybe evict)

The score we keep:
   page-fault rate = (number of faults) / (number of references)

Lower fault rate = better policy on this string.
A reference string plus a frame count is the whole experiment. Every policy in this rung is scored by how few faults it produces on strings like this one.

The score itself is the page-fault rate: faults divided by total references, a number between 0 and 1. It is the single most important quantity in this whole rung, because it ties directly to speed. The effective time of a memory access is roughly the fast RAM time most of the time, plus the brutal disk time on the rare fault — so even a tiny fault rate can dominate. If a memory access is about 100 nanoseconds and a fault costs about 8 milliseconds (80,000 times more), then a fault rate of just one in a thousand already makes the average access many times slower than RAM alone. Shaving the fault rate is the entire game.

More frames, more choices, and the road ahead

There are really two knobs that decide how many faults a process suffers. The first is the policy — which victim to choose — and that is what guides 2 and 3 dig into: FIFO, the optimal benchmark that cheats by knowing the future, LRU and its buildable cousins like aging and the clock. The second knob is how many frames the process gets in the first place. Give a process more frames and, intuitively, it should fault less — and you would expect that always to hold.

Be careful: that intuition has a famous exception. For some policies — FIFO in particular — adding a frame can make the fault count go up, an unsettling result called Belady's anomaly. It feels impossible, yet it is real, and it is one of the reasons FIFO is not trusted in practice. Reassuringly, the well-behaved policies (OPT and LRU among them) provably never suffer it: with them, more frames can only help or stay equal. That contrast is a major theme of the next two guides, so file it away now.

Finally, the frame knob is not just per-process — it is a system-wide budget. When many processes compete, the OS must decide how to split a fixed pool of frames among them (frame allocation: equal shares, or proportional to size; chosen globally across all processes or locally within each), and that decision interacts with everything above. Allocate too few frames to too many processes and the whole machine can tip into thrashing — every process faulting constantly, the disk thrashing back and forth, throughput collapsing. So the chain of this rung is: which page to evict (policy), how many frames to give (allocation), and what happens when there are not enough (thrashing). It all starts with the single question we opened with — who gets evicted?