Introduction

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.

Try the Algorithms

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.

<!-- Page replacement demo — reference string + frame state visualization -->
<div class="controls">
  <label>Frames (RAM slots): <input type="number" id="frameCount" min="1" max="6" value="3"></label>
  <label>Algorithm:
    <select id="algoSelect">
      <option value="OPT">OPT (clairvoyant)</option>
      <option value="LRU" selected>LRU (least recently used)</option>
      <option value="Clock">Clock (second chance)</option>
    </select>
  </label>
  <button id="btnStep" type="button">Step</button>
  <button id="btnRun" type="button">Run all</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="ref-row" id="refRow" aria-label="Page reference string"></div>
<div class="frames-area" id="framesArea" aria-label="RAM frame state"></div>
<div class="stats" id="stats"></div>
<div class="legend">
  <span class="dot hit"></span> Hit (page already in RAM)
  <span class="dot miss"></span> Miss (page fault)
</div>

/* Styles for the page replacement demo */
* { 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; }
/* Reference string row */
.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; }
/* Frame state area */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Page replacement algorithms: OPT (clairvoyant), LRU (evict oldest use), Clock (circular second-chance)
const REF_STRING = [3,1,4,1,5,9,2,6,5,3,5,3,5,8,9,7,9,3,2,3];
let frameCount = 3;
let algo = 'LRU';
let step = 0;
// Simulation state
// frames: array of page numbers (-1 = empty)
// useBits: for Clock algorithm
// lastUsed: for LRU timestamps
let frames = [], useBits = [], lastUsed = [], clockPtr = 0;
let history = []; // one entry per step

function resetState() {
  frameCount = parseInt(document.getElementById('frameCount').value, 10);
  algo = document.getElementById('algoSelect').value;
  step = 0;
  frames = new Array(frameCount).fill(-1);
  useBits = new Array(frameCount).fill(0);
  lastUsed = new Array(frameCount).fill(-1);
  clockPtr = 0;
  history = [];
  render();
  document.getElementById('stats').textContent = '';
}

// OPT: evict the frame whose page is needed farthest in the future
function optEvict(futureStart) {
  let farthest = -1, victim = 0;
  for (let i = 0; i < frames.length; i++) {
    if (frames[i] === -1) return i; // empty slot — use it first
    const next = REF_STRING.slice(futureStart).indexOf(frames[i]);
    if (next === -1) return i; // page never needed again — perfect victim
    if (next > farthest) { farthest = next; victim = i; }
  }
  return victim;
}

// LRU: evict the frame least recently used
function lruEvict() {
  let oldest = Infinity, victim = 0;
  for (let i = 0; i < frames.length; i++) {
    if (frames[i] === -1) return i;
    if (lastUsed[i] < oldest) { oldest = lastUsed[i]; victim = i; }
  }
  return victim;
}

// Clock: walk the pointer; give each page a second chance via use-bit
function clockEvict() {
  while (true) {
    if (frames[clockPtr] === -1) { const p = clockPtr; clockPtr = (clockPtr + 1) % frameCount; return p; }
    if (useBits[clockPtr] === 0) { const p = clockPtr; clockPtr = (clockPtr + 1) % frameCount; return p; }
    useBits[clockPtr] = 0; // clear use-bit (second chance expired)
    clockPtr = (clockPtr + 1) % frameCount;
  }
}

function doStep() {
  if (step >= REF_STRING.length) return;
  const page = REF_STRING[step];
  const hitIdx = frames.indexOf(page);
  let evicted = -1, evictSlot = -1;
  let isHit = hitIdx !== -1;

  if (isHit) {
    // page is already in RAM — update recency tracking
    if (algo === 'LRU') lastUsed[hitIdx] = step;
    if (algo === 'Clock') useBits[hitIdx] = 1;
  } else {
    // page fault — choose a victim frame and load the page
    if (algo === 'OPT') evictSlot = optEvict(step + 1);
    else if (algo === 'LRU') evictSlot = lruEvict();
    else evictSlot = clockEvict();
    evicted = frames[evictSlot];
    frames[evictSlot] = page;
    useBits[evictSlot] = 1;
    lastUsed[evictSlot] = step;
  }

  history.push({ page, isHit, evicted, evictSlot, frameSnap: [...frames], useBitsSnap: [...useBits], clockPtrSnap: clockPtr });
  step++;
  render();
  updateStats();
  if (step >= REF_STRING.length) {
    document.getElementById('btnStep').disabled = true;
    document.getElementById('btnRun').disabled = true;
  }
}

function render() {
  // Render the reference string row with hit/miss coloring
  const refRow = document.getElementById('refRow');
  refRow.innerHTML = '';
  REF_STRING.forEach((p, i) => {
    const d = document.createElement('div');
    d.className = 'ref-cell';
    d.textContent = p;
    if (i < history.length) d.classList.add(history[i].isHit ? 'hit' : 'miss');
    if (i === step - 1) d.classList.add('current');
    refRow.appendChild(d);
  });

  // Render the current frame state
  const area = document.getElementById('framesArea');
  area.innerHTML = '';
  const snap = history.length > 0 ? history[history.length - 1] : null;
  for (let fi = 0; fi < frameCount; fi++) {
    const col = document.createElement('div');
    col.className = 'frame-col';
    const lbl = document.createElement('div');
    lbl.className = 'frame-label';
    lbl.textContent = 'F' + fi;
    col.appendChild(lbl);
    const cell = document.createElement('div');
    const pg = snap ? snap.frameSnap[fi] : -1;
    cell.className = 'frame-cell' + (pg === -1 ? ' empty' : ' loaded');
    cell.textContent = pg === -1 ? '-' : pg;
    if (snap && fi === snap.evictSlot && !snap.isHit && snap.evicted !== -1) cell.classList.replace('loaded', 'evicted');
    if (algo === 'Clock' && snap && fi === snap.clockPtrSnap) cell.classList.add('clock-ptr');
    col.appendChild(cell);
    area.appendChild(col);
  }
}

function updateStats() {
  const hits = history.filter(h => h.isHit).length;
  const misses = history.filter(h => !h.isHit).length;
  const total = history.length;
  document.getElementById('stats').textContent = total > 0
    ? i18nFmt('%algo% — %hits% hits + %misses% misses out of %total% references', { hits, misses, total, algo })
    : '';
}

document.getElementById('btnStep').addEventListener('click', doStep);
document.getElementById('btnRun').addEventListener('click', () => {
  const interval = setInterval(() => {
    if (step >= REF_STRING.length) { clearInterval(interval); return; }
    doStep();
  }, 200);
});
document.getElementById('btnReset').addEventListener('click', resetState);
document.getElementById('frameCount').addEventListener('change', resetState);
document.getElementById('algoSelect').addEventListener('change', resetState);
resetState();
Result
Console

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 Real Complexity

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 kk frames, LRU's fault count is at most kk 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 kk is always a subset of the pages in a cache of size k+1k+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.

Where It Matters

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 KK 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/page-replacement/Content licensed under CC BY-NC 4.0.