25/32 · 6 min

Choosing what to evict

Physical memory is full and a page is needed. Something has to go, and the choice decides how often the next fault happens.

Measuring

code

effective access time = (1 - p) x memory time + p x fault time

A memory access is about 100 nanoseconds and a page fault from disk about 8 milliseconds, a factor of 80,000. At a fault rate of one in a thousand, average access time is roughly 8 microseconds: eighty times slower than memory.

Which is why the fault rate has to be very small, and why the eviction policy matters at all.

The algorithms

Optimal: evict the page that will be needed furthest in the future. Unimplementable, because it requires knowing the future. It is the benchmark everything else is measured against.

FIFO: evict the oldest. Simple, and ignores whether a page is heavily used. It also suffers Belady's anomaly: adding more frames can produce *more* faults, which is deeply counterintuitive and is why FIFO is not used.

LRU: evict the least recently used. Close to optimal in practice, because recent use predicts near future use well. Exact LRU needs a timestamp or a list update on every memory access, which is far too expensive in hardware.

Clock: the practical approximation. Pages sit in a circle, each with a reference bit the hardware sets on access. A hand sweeps: if the bit is set, clear it and move on; if clear, evict. A page gets a second chance only if it was touched since the hand last passed.

code

    [A:1] -> [B:0] -> [C:1] -> [D:0]
      ^
    hand: A has the bit set, clear it and advance
          B is clear, evict B

Nearly LRU's quality for one bit per page and no work on a normal access.

Algorithm	Quality	Cost	Used
Optimal	best possible	impossible	as a benchmark
FIFO	poor, Belady's anomaly	trivial	no
LRU	very good	too high exactly	approximated
Clock	close to LRU	one bit	yes

The dirty bit

A page that has not been modified since being loaded can be dropped, because the copy on disk is still correct. A modified page must be written out first, which costs a disk write.

So a second bit is tracked, and the preference is to evict clean pages. A page that is clean and unreferenced is the cheapest possible eviction, and real implementations look for exactly that combination first.