Page Replacement

Your computer runs more programs than can fit in RAM at once. The operating system creates an illusion of unlimited memory through virtual memory: it keeps pages of data on disk and loads them into physical RAM only when needed.

When a program touches a page that is not in RAM, a page fault occurs. The OS pauses the program, fetches the page from disk — which can take thousands of times longer than a RAM access — and then resumes. If RAM is already full, it must first evict one of the existing pages to make room.

Which page should it evict? Evict the wrong one and the processor stalls again moments later fetching it back. Evict the right one and the program barely notices. That choice is the page replacement problem, and the gap between a clever policy and a careless one is the difference between a snappy system and one that thrashes.

Below is a stream of page references — the sequence of pages a program accesses one by one. Each algorithm keeps a small frame buffer in RAM (capacity shown in the controls). When a needed page is missing it is a miss (page fault); when it is already loaded it is a hit.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_frames}} <input type="number" id="frameCount" min="1" max="6" value="3"></label>
  <label>{{lbl_algo}}
    <select id="algoSelect">
      <option value="OPT">OPT ({{lbl_opt_desc}})</option>
      <option value="LRU" selected>LRU ({{lbl_lru_desc}})</option>
      <option value="Clock">Clock ({{lbl_clock_desc}})</option>
    </select>
  </label>
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="ref-row" id="refRow" aria-label="{{aria_ref_row}}"></div>
<div class="frames-area" id="framesArea" aria-label="{{aria_frames}}"></div>
<div class="stats" id="stats"></div>
<div class="legend">
  <span class="dot hit"></span> {{lbl_hit}}
  <span class="dot miss"></span> {{lbl_miss}}
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .7rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .3rem; }
input[type=number] { width: 3rem; padding: .2rem .3rem; border: 1px solid #adb1b8; border-radius: 6px; }
select { padding: .2rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .85rem; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
/* {{c_css_ref}} */
.ref-row { display: flex; gap: 4px; margin-bottom: .5rem; flex-wrap: wrap; }
.ref-cell { width: 32px; height: 32px; display: flex; align-items: center; justify-content: center;
            font: 700 14px ui-monospace, monospace; border-radius: 6px;
            background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; transition: all .15s; }
.ref-cell.current { background: #1d3557; color: #fff; border-color: #1d3557; }
.ref-cell.hit { background: #d4edda; border-color: #7dc8a0; color: #0a5e2a; }
.ref-cell.miss { background: #fde8e8; border-color: #f2a0a0; color: #a31515; }
/* {{c_css_frames}} */
.frames-area { display: flex; gap: 6px; margin: .4rem 0 .6rem; min-height: 48px; }
.frame-col { display: flex; flex-direction: column; gap: 3px; }
.frame-label { font-size: .72rem; color: #666; text-align: center; }
.frame-cell { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
              font: 700 14px ui-monospace, monospace; border-radius: 7px;
              background: #c9ccd1; border: 1px solid #adb1b8; color: #333; transition: all .2s; }
.frame-cell.loaded { background: #d4edda; border-color: #7dc8a0; color: #0a5e2a; }
.frame-cell.evicted { background: #fde8e8; border-color: #f2a0a0; color: #a31515; }
.frame-cell.clock-ptr { outline: 2px solid #e67e22; outline-offset: 1px; }
.frame-cell.empty { background: #eee; border-color: #ccc; color: #aaa; }
.stats { font-size: .9rem; font-weight: 600; margin: .3rem 0; min-height: 1.3em; }
.legend { font-size: .8rem; color: #555; display: flex; gap: 1rem; align-items: center; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.hit { background: #7dc8a0; }
.dot.miss { background: #f2a0a0; }

// Code not found

OPT (Belady's optimal) always evicts the page that will be needed furthest in the future — a provably perfect strategy. The catch: you need a crystal ball. LRU (Least Recently Used) evicts the page that was used least recently, betting that the past predicts the future. Clock (Second Chance) approximates LRU with a single circular pointer and a use-bit per frame — cheap enough to run on every memory access.

Notice how OPT's miss count is always the lower bound: no algorithm can do better on the same reference string.

The page replacement problem has a remarkable theoretical structure.

Belady's OPT (1966). László Bélády proved that always evicting the page needed furthest in the future minimises total page faults. The proof is elegant: if any other algorithm makes a different choice, you can swap it for OPT's choice without increasing faults. OPT is provably optimal — but it is an offline algorithm. It needs the entire future reference sequence in advance, which is never available to a running OS.

LRU is the best online algorithm. Without knowledge of the future, LRU (evict the page unused for the longest time) achieves the best possible competitive ratio: on a cache of size $k$ frames, LRU's fault count is at most $k$ times OPT's. No deterministic online algorithm can beat this ratio.

The Belady anomaly. Surprisingly, FIFO (evict the oldest page) can produce more page faults with more frames — adding RAM makes things worse. LRU and OPT are immune to this anomaly. The anomaly arises because FIFO ignores recency; it is not a property of sensible replacement policies.

Stack algorithms. LRU belongs to the class of stack algorithms: the set of pages in a cache of size $k$ is always a subset of the pages in a cache of size $k+1$ on the same reference string. This monotonicity property is exactly what prevents the Belady anomaly.

Closely related is caching, and the problem shares structure with the online algorithm framework where decisions must be made without future knowledge.

The same eviction logic appears at every level of the memory hierarchy and beyond:

• OS virtual memory: the Linux kernel uses a variant of the Clock algorithm (active/inactive lists with reference bits) to manage page frames with minimal overhead.
• CPU caches: hardware designers implement pseudo-LRU in L1/L2/L3 caches because true LRU requires tracking every access — too slow for nanosecond-latency caches.
• Database buffer pools: PostgreSQL, MySQL and Oracle all maintain a buffer pool where pages of table data are kept in RAM. They use variants of Clock or LRU-K (track the last $K$ accesses) to decide which data pages to flush to disk.
• Content Delivery Networks: a CDN node evicts cached objects using policies like LRU, LFU (Least Frequently Used) or ARC (Adaptive Replacement Cache) — the trade-offs are identical to the OS problem, just at the scale of gigabytes of web content.
• Web browsers: browser caches for HTTP resources use Cache-Control headers to guide eviction, but still run an internal LRU-like policy when storage limits are hit.

Understand page replacement and you have the mental model for every finite-buffer resource manager: CDN, cache, buffer pool, or TLB.

Page replacement is a small decision made billions of times a day inside every operating system — and its theory is surprisingly deep. The optimal algorithm (OPT) is unimplementable because it requires the future. The best practical algorithm (LRU) matches it as closely as any online strategy can, and its stack property gives it a clean theoretical guarantee.

The next time your laptop feels sluggish, it may be thrashing: evicting and re-loading the same pages in a loop because the working set no longer fits in RAM. That is the page replacement problem in painful, audible form — the disk light blinking as the OS tries to conjure more memory than exists.

The lesson generalises: whenever you manage a finite resource against an unknown future request stream, you are solving page replacement. The same framework governs scheduling decisions and any online algorithm that must commit without hindsight.