Skip to main content

Replacement Policies: FIFO, LRU, Approximations

What This Concept Is​

When physical memory is full and the kernel needs to install a new page, it must evict an old one. A replacement policy is the rule for choosing the victim.

Key policies:

  • OPT (Belady's optimal): evict the page that will not be used for the longest time in the future. Unimplementable (requires seeing the future), used only as the theoretical lower bound on fault count.
  • FIFO: evict the page that has been resident longest. Simple, but ignores usage. Can exhibit Belady's anomaly: more frames can sometimes cause more faults.
  • LRU (least recently used): evict the page touched longest ago. Approximates OPT under temporal locality. Exact LRU requires updating a timestamp or list on every access, which is too expensive for real hardware.
  • Clock (second-chance): pages sit in a circular list with a reference bit that the MMU sets on access. A pointer sweeps the clock; when a page is examined, if the reference bit is 1 the bit is cleared and the pointer advances, if it is 0 the page is evicted. Cheap, robust, a good LRU approximation.
  • LRU-K, 2Q, CAR, ARC: refinements that distinguish frequency from recency, avoid scan-resistance failures, or separate hot from cold pages.

Linux's page reclaim uses a two-list variant (active/inactive LRU) plus reference-bit sweeps, closer to the clock family than to pure LRU.

Why It Matters Here​

Replacement is where virtual memory's performance story gets decided. A policy that evicts the wrong page costs you major faults; a policy that is too expensive to run costs you CPU. The reason textbooks spend so much time on OPT/FIFO/LRU is that the gap between them on real reference strings predicts how sensitive a workload is to memory pressure.

Understanding replacement also explains why cache-friendly workloads tolerate low RAM well (good locality means LRU-like policies keep the hot set resident) and why streaming scan workloads are toxic (every page is recent once and then useless, overwhelming LRU and requiring scan-resistant policies).

Concrete Example​

Reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames:

PolicyFault traceFaults
OPThit/miss pattern optimized by seeing the future7
FIFO1,2,3 fill; 4 evicts 1; 1 evicts 2; 2 evicts 3; 5 evicts 4; ...9
LRU1,2,3 fill; 4 evicts 1; 1 evicts 2; 2 evicts 3; 5 evicts 4; ...10

(Exact counts depend on tie-breaking; the point is that OPT is a lower bound, and FIFO and LRU are close but not identical.)

Belady's anomaly. Reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames under FIFO: 9 faults. With 4 frames under FIFO: 10 faults. More memory, more faults, because FIFO makes evictions ignoring usage.

Clock in practice. A thread allocates and walks a 2 GiB array on a 1 GiB machine. Linux keeps hot pages on the active list, scans the inactive list looking for pages with cleared reference bits, and evicts those first. Pages with locality survive multiple sweeps.

Common Confusion / Misconception​

"Linux uses LRU." Linux uses an active/inactive two-list scheme with reference-bit-based promotion, not true LRU. Exact LRU per page on every access is too expensive on modern hardware.

"FIFO is just bad, nobody uses it." FIFO-like policies are fine for workloads with uniform or streaming access. What is toxic is pure FIFO under high-locality workloads, where it throws away the very pages you are about to reuse.

"OPT is achievable with prediction." Prediction can approach OPT for specific workloads with known patterns, but for general workloads OPT is a reference, not an implementation target.

How To Use It​

For a new workload:

  1. Characterize access pattern: highly recurring (locality wins), streaming (scan hurts LRU), random (all policies behave similarly).
  2. If the workload scans huge arrays, suspect that the default LRU-like reclaim will evict hot pages under pressure. Consider MADV_SEQUENTIAL, posix_fadvise(POSIX_FADV_SEQUENTIAL), or moving the scan to direct I/O to bypass the page cache.
  3. Measure fault rate, not just throughput. A policy mismatch shows up as inflated major-fault counts.

For interview-style thinking: always compare any proposed policy against OPT on a small reference string before claiming it is good.

Check Yourself​

  1. Define Belady's anomaly in one sentence and give a reference string that exhibits it under FIFO.
  2. Why does exact LRU require updates on every memory access, and why is that not viable?
  3. What does the "reference bit" in a PTE let the kernel approximate without that cost?
  4. Why does a pure LRU policy perform badly on a workload that scans a dataset larger than RAM?

Mini Drill or Application​

Simulate the following reference strings on 4 frames. Give the fault count for OPT, FIFO, LRU, and clock (assume reference bits start 0 and are set on each access).

  1. A B C D A B E A B C D E -> OPT faults? FIFO? LRU?
  2. 1 2 3 4 5 1 2 3 4 5 1 2 -> LRU fault count, then FIFO on 3 frames vs 4 frames (note Belady).
  3. Construct your own reference string where LRU produces strictly more faults than FIFO. (Hint: hard, but possible with carefully chosen recent-but-useless accesses.)
  4. A database scans a table twice as large as RAM. Sketch the fault trajectory under LRU and argue why scan-resistant policies like 2Q or ARC help.

Read This Only If Stuck​