Page replacement: LRU, Belady's anomaly and thrashing
Cost of page faults with an example, FIFO, optimal and LRU, Belady's anomaly, the stack property of LRU proved, the clock algorithm, working set and thrashing.
Virtual memory (Computer Systems lesson on virtual memory) gives each process a private address space, divided into pages that the operating system loads into memory only when needed. When physical memory is full and a new page is needed, one must be chosen for removal: this is the page replacement problem, and the choice matters enormously, because a page fault costs millions of times a normal access. In this lesson we look at the cost of page faults with an example, the FIFO, optimal and LRU algorithms, Belady’s anomaly with the proof that LRU does not suffer from it, the clock algorithm, the working set and thrashing.
The cost of a page fault
If the requested page is not in memory, the processor raises a page fault: the operating system finds a free frame (or frees one), reads the page from disk, updates the page table and makes the instruction repeat. With fault probability 
, memory access time 
and fault service time 
, the effective access time is
![\[ t_{eff} = (1 - p)\,t_m + p\,t_f \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-52eb4f342be4df4ca24588c9dfd88abf_l3.png "Rendered by QuickLaTeX.com")
Example. With 
ns and 
ms (a magnetic disk), to slow down by no more than 10 % we need 
ns, i.e. 
ns roughly, 
: less than one fault every 800,000 accesses. With an SSD (
µs) the limit relaxes eighty-fold, but remains strict.
Replacement algorithms
- FIFO: remove the page loaded longest ago. Simple, but it also removes heavily used pages, such as those of the main code.
- Optimal (OPT, Belady): remove the page that will be used furthest in the future. It is the best possible, but requires knowing the future; it serves as a benchmark in simulations.
- LRU (least recently used): remove the page unused for the longest time. It uses the recent past as a prediction of the near future, exploiting locality (lesson on cache memory).
Belady’s anomaly
One would expect faults always to decrease with more frames. With FIFO this is not so.
With the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO makes 9 faults with 3 frames and 10 with 4: adding memory makes things worse. LRU and OPT do not have this anomaly, because of a structural property.
Theorem. With LRU, at every instant, the set of pages in memory with 
frames is contained in the set of pages in memory with 
frames. Consequently the number of faults with frames does not exceed that with frames.
Proof. With LRU, after the initial warm-up, memory with frames contains exactly the distinct pages used most recently; before that, it contains all those used so far. In both cases it is the set of the “first ” pages in order of recent use, and the first are contained in the first . Every reference that is a hit with frames (page present) is also a hit with , so the faults with frames are at most those with . ∎
Algorithms with this property are called stack algorithms. FIFO is not one: the set in memory depends on the loading order, not only on recent use.
The clock algorithm
Exact LRU would require recording the time of every memory access, which is too expensive. The hardware offers a reference bit per page, which the processor sets to 1 on every access. The clock (second chance) algorithm arranges the frames in a circle with a hand: when a frame is needed, it looks at the page the hand points to; if the bit is 1 it clears it and moves on (giving it a second chance), if it is 0 it chooses it. Recently used pages survive one sweep of the hand. It is an approximation of LRU used, with variants, in real systems. Clean (unmodified) pages are also preferred for removal, since they need not be written back to disk.
Working set and thrashing
The working set of a process is the set of pages used in the last window of 
references: it represents its current locality. If the sum of the working sets of all processes exceeds physical memory, each process removes pages needed by the others, faults multiply and the CPU spends its time waiting for the disk. This is thrashing: adding processes makes throughput collapse instead of increasing it. The cure is to reduce the number of active processes (suspending some) until the working sets fit in memory, or to add memory.
Other uses of virtual memory
- Copy-on-write after a fork (lesson on processes).
- Memory-mapped files: a file becomes an area of the address space, and reading it means accessing memory; the system loads pages on demand.
- Shared libraries: the code of a library used by a hundred processes is in memory only once, mapped into all of them.
- Huge pages (2 MB or 1 GB instead of 4 KB) for programs using a lot of memory, which reduce TLB misses.
