Anomalies

The page replacement algorithm First-In First Out may be easy to program and to understand, but it does not always perform well. If a page named early in the reference string is just for initialization, replacing it first is logical. However, if a page is called early because it contains a frequently used variable, replacing it causes the extra work of reading it in again right away.

In fact, using FIFO some reference strings actually generate more page faults when more page frames are allotted. This truly unexpected result was first demonstrated by Belady in 1970 and is known as Belady's Anomaly.

This illustration uses a reference string similar to the sawtooth pattern observed in the reference string discussion. The order of the page frames now reflects when the page was read into memory. The newest page is on the top and the oldest migrates to the bottom like a queue. All of the page faults are indicated by red numeral and red framed boxes. Notice the expected improvement in the number of page faults when three page frames are used. But, most unexpectedly, see that adding a fourth page results in an INCREASE in the number of page faults.

The LEAST RECENTLY USED replacement policy does not suffer from Belady's Anomaly.

---