How does page replacement work, and what causes thrashing?

Question

IT Interview Practice · Accepted Answer

When physical RAM fills up but processes need more pages, the OS must **evict** a resident page to make room — writing it to **swap** (disk) if it's dirty. Which page to evict is the **page replacement** decision, and getting it wrong wrecks performance.

## Replacement policies

The theoretical optimum is to evict the page used furthest in the future (**Bélády's OPT**) — impossible, since you can't see the future. So we approximate **LRU (least recently used)**: evict the page unused for the longest time. True LRU needs a timestamp on every access (too costly), so real kernels use the **clock (second-chance) algorithm**:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

Clock gives LRU-like results at O(1) cost. Linux refines it further with **active/inactive LRU lists**.

## Working set and thrashing

A process's **working set** is the set of pages it actively uses within a time window. Paging works fine *as long as the combined working sets fit in RAM*. When they don't:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

Thrashing is a cliff, not a slope: go a little over the limit and throughput collapses because nearly every access misses. Symptoms: CPU near idle but disk I/O saturated, and latency exploding.

## Fixing / avoiding it

- **Add RAM** or **reduce load** (fewer concurrent processes) so the working sets fit.
- The scheduler can **suspend and swap out** whole processes to shrink demand (medium-term scheduling).
- Linux's **OOM killer** is the last resort — kill a process rather than thrash forever.
- Improve **locality** so the working set itself is smaller.

## Why it matters

This ties the whole memory story together and is a favorite senior question because thrashing is a real production failure mode: a service that's fine at N users falls off a cliff at N+1 as its working set exceeds RAM. Recognizing the signature (heavy paging, saturated disk, stalled CPU) and knowing the levers (RAM, load shedding, locality — and that swap turns a memory shortage into a latency catastrophe) is the difference between diagnosing it in minutes and staring at a mysteriously frozen box.

Replacement policies

Working set and thrashing

Fixing / avoiding it

Why it matters

Related questions