Interview Prep Zoneby CuriouserLabs

Question 4 of 5 · senior level

Page replacement (LRU, clock), the working set, and thrashing — how does a system die from memory pressure?

🎤 Say this first

When RAM is full, someone's page must go. True LRU is unaffordable per-access, so kernels approximate it: the clock algorithm sweeps a circular list clearing hardware 'referenced' bits, evicting pages nobody re-touched (Linux: two LRU lists, active/inactive, with the same spirit). It works because of locality — each process has a working set it re-touches constantly. When the sum of working sets exceeds RAM, eviction starts stealing pages that are about to be needed: fault → evict → fault → thrashing, where the system does I/O instead of work and CPU drops while everything is 'busy'. The only real cures: less demand or more RAM.

The full picture

  • Why not true LRU: perfect recency ordering means bookkeeping on every memory access — hardware gives you only a referenced bit per page; clock/second-chance is 'LRU with one bit of memory', and it's within a few percent of LRU on real workloads.
  • Belady's insights worth citing: the optimal algorithm (evict the page used furthest in the future) is unimplementable but benchmarkable; and FIFO can get worse with more memory (Belady's anomaly) — why stack-property algorithms like LRU matter.
  • Thrashing signatures: high majfl + high disk I/O + low user CPU + load average climbing — 'busy but nothing finishes'. Modern Linux adds PSI (pressure stall information, /proc/pressure/memory) as the direct 'time stalled on memory' metric — alert on it.
  • The cloud translation: in containers there's often no swap, so 'thrashing' appears as page-cache evict/reload storms (files re-read constantly) or as the OOM killer — same disease, different symptom. Working-set thinking survives: it's what K8s memory requests are supposed to be.

🔄 Likely follow-up questions

  • What is PSI and how would you alert on memory pressure with it?
  • How do active/inactive lists and refault distance work in modern Linux?
  • Why does adding RAM sometimes fix p99 more cheaply than any code change?