Bélády's anomaly
= Bélády's anomaly
{c}
{wiki}
= Belady anomaly
{c}
{synonym}
Increasing the number of <page frames> can increase misses under a given <page replacement> policy on the same <page-reference trace>. For <FIFO page replacement> on the displayed twelve-reference <sequence>, an empty start with three <page frames> gives nine misses, while an empty start with four gives ten. The larger run hits only at indices 5 and 6; it misses at 1–4 and 7–12. These are miss counts, not observed running times.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Belady's Anomaly aside, p. 5: the reference sequence and increasing capacity from three to four]{ref}
\Image[/fifo-belady-anomaly-frame-comparison.png]
{title=<FIFO page replacement> queue states and cumulative misses: four <page frames> give ten misses versus nine with three}
The explanation is visible before the final count. After access 6, the three-<page frame> queue is $(4,1,2)$ and the four-<page frame> queue is $(1,2,3,4)$, both oldest first. Loading <memory page> 5 at access 7 removes <memory page> 4 in the smaller run but <memory page> 1 in the larger. Their resulting <resident sets> are $\{1,2,5\}$ and $\{2,3,4,5\}$. The smaller <resident set> is not a <subset> of the larger: its next access to <memory page> 1 hits while the larger run misses. Different earlier evictions create different histories; an extra <page frame> is not simply an extra unchanged slot. <FIFO page replacement> can improve on other <sequences>; the anomaly is an existence claim, not a claim that more <page frames> usually hurt.