= FIFO page replacement
{c}
Evict the <memory page> loaded earliest among currently resident <memory pages>, without refreshing its position on access. It is simple but ignores <temporal locality> and can evict a frequently accessed <memory page>.
Implement this ranking with a <FIFO queue> of resident <memory pages>: append on loading, remove the oldest on eviction, and leave the queue unchanged on a hit. <Belady anomaly> shows why preserving arrival order can give more misses with more <page frames>. The comparison uses the same <page-reference trace> and empty initial <resident sets> in both runs.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Section 22.3, pp. 4–5: FIFO ordering; Belady's Anomaly aside, p. 5: the twelve-reference counterexample and contrast with stack policies]{ref}
Back to article page
