Belady's Anomaly in Page Replacement

Introduction

Belady's anomaly is an unusual behavior in page replacement where more memory frames can lead to more page faults. This goes against the normal expectation that extra frames should help the system keep more pages in RAM.

The anomaly is usually demonstrated using FIFO page replacement. With the same reference string and the same algorithm, increasing the frame count can sometimes increase the total number of faults.

Belady's Anomaly Meaning

Belady's anomaly occurs when increasing the number of available page frames causes more page faults for the same reference string and the same page replacement algorithm.

The important conditions are:

• Same reference string: The page access sequence must remain unchanged.

• Same algorithm: The replacement policy must be the same.

• More frames: The number of available page frames is increased.

• More faults: The larger frame count gives a higher page fault count.

This does not happen every time frames are increased. It means that for some reference strings and some algorithms, especially FIFO, this unexpected increase is possible.

Why the Result Feels Strange

The natural expectation is that more memory should help. If RAM has more frames, it should be able to hold more pages, so future references should have a better chance of becoming hits.

Belady's anomaly shows that this expectation is not always true for every replacement policy. In FIFO, increasing the frame count can change the sequence of hits, faults, and evictions. Once the eviction order changes, the later fault count can also change.

FIFO and Belady's Anomaly

FIFO stands for First-In, First-Out. It removes the page that entered memory earliest. FIFO treats memory like a queue:

• Front of queue: Oldest loaded page, selected first for replacement.

• Back of queue: Newest loaded page.

• Page fault with full memory: Remove the front page.

• Page hit: Do not change the queue order.

The last rule is very important. FIFO is based on arrival order, not recent use. Even if a page is accessed again, it does not become newer in the FIFO queue.

Worked Example Setup

Use this reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

We will compare FIFO in two cases:

• Case 1: FIFO with 3 frames

• Case 2: FIFO with 4 frames

If more frames always helped, 4 frames should give the same number of faults or fewer faults than 3 frames. Belady's anomaly is shown when 4 frames gives more page faults.

FIFO with 3 Frames

With 3 frames, FIFO gives 9 page faults and 3 page hits.

A useful observation is that pages 1 and 2 are reloaded before page 5 arrives. Because of this, they become newer in FIFO order, so later references to 1 and 2 become hits.

FIFO with 4 Frames

With 4 frames, FIFO gives 10 page faults and 2 page hits. This is Belady's anomaly. Increasing frames from 3 to 4 increases page faults from 9 to 10.

Why FIFO Shows This Anomaly

FIFO does not refresh a page on a hit. A page may be used again, but its position in the FIFO queue remains old.

With 4 frames, pages 1 and 2 are hits at steps 5 and 6. However, FIFO does not move them to the back. They remain old, so when page 5 comes, page 1 is evicted first. This starts a chain of faults for 1, 2, 3, 4, and 5.

With 3 frames, pages 1 and 2 were faulted back into memory earlier, so they became newer in FIFO order. That different queue history produces fewer total faults.

Subset Property and Stack Algorithms

In an ideal situation, pages present with fewer frames should also be present when more frames are available. For example, if 3 frames contain pages A, B, C, then 4 frames should contain A, B, C plus one extra page.

This is called the stack property or subset property. If an algorithm has this property, increasing frames cannot increase page faults because the larger memory never loses what the smaller memory already had.

FIFO does not guarantee this property. Different frame counts can create different FIFO queue histories, so the pages in the smaller-frame case may not be contained inside the larger-frame case.

Which Algorithms Avoid Belady's Anomaly

LRU and Optimal avoid Belady's anomaly because they are stack algorithms. Their page sets preserve the useful containment behavior as the number of frames increases.

LRU evicts the least recently used page, so a hit refreshes recency. Optimal evicts the page whose next use is farthest in the future. These rules prevent the kind of harmful queue-history shift seen in FIFO.

Summary

Belady's anomaly is the unexpected case where increasing the number of page frames increases page faults for the same reference string and the same page replacement algorithm. It is most commonly demonstrated using FIFO page replacement.

In the standard FIFO example, the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 gives 9 faults with 3 frames and 10 faults with 4 frames. LRU and Optimal avoid this anomaly because they are stack algorithms and preserve the subset property.