20.2.3. Why These Algorithms Avoid Belady's Anomaly

Now we will try to see in more detail why this happens? Now the reason for Belady’s anomaly has been found to be this; pages in memory at any given time for the stipulated number of frames is not always a subset of the pages when the number of frames become higher.

Belady's anomaly refers to a situation in computer memory management where increasing the number of page frames allocated to a system results in a higher number of page faults rather than a lower one, which is counterintuitive. The basic reason is that the pages currently in memory, when fewer frames are available, do not necessarily correlate to pages that will remain in memory when more frames are added. This leads to a situation where, with more frames, certain patterns of memory reference can increase the page fault rate instead of decreasing it.

Imagine a classroom where there are limited desks (frames) for students (pages) to sit. If there are 3 desks and some students are seated but can’t sit by the window (most accessed pages), adding more desks (frames) doesn’t guarantee that all students will still be seated together comfortably. In fact, some students might still end up outside if their specific seating arrangement isn’t optimal.

So, when my number of frames are lower, if thus the pages that I am containing are not a subset when my number of pages are higher then Belady’s anomaly occurs.

When we have fewer frames, the pages that can be loaded may create a situation where those pages are repeatedly accessed, leading to fewer page faults. However, when we increase the frames and load different pages, the set of pages in memory at that moment no longer represent the optimal choices for minimizing faults. Consequently, this misalignment leads to more frequent page faults occurring with the larger number of frames.

Consider trying to fit a limited number of singers into a band (low frames); they may work well together because of their familiarity. However, adding more members (frames) might mix incompatible singers, leading to a cacophony instead of harmony due to less efficient music-making.

We will take an example we will take the example of this reference string and see why and how this happens. So, these are the set of memory references and these are the set of memory references shown here, 1 2 3 4 1 2 5 1 2 3 4 5.

To illustrate how page faults occur with different frame allocations, we analyze the reference string: 1, 2, 3, 4, 1, 2, 5, etc. With 3 frames and applying a FIFO (First-In-First-Out) policy, page faults are counted every time a new page access isn't already loaded into a frame. Starting with all frames empty, as pages are accessed, faults occur for each unique page until the frames are filled. Subsequent accesses may either result in a page fault or a hit depending on whether the requested page is already in one of the frames.

Think of a busy library with limited shelf space (frames) for books (pages). If popular titles continuously rotate in and out (access patterns) and new titles arrive before old ones can be checked out again, the library will often run out of space to accommodate readers wishing to find certain books – leading to frustration (page faults).

Now, the optimal algorithm and LRU both the optimal algorithm and the LRU do not exhibit Belady’s anomaly.

Both the Optimal algorithm and the Least Recently Used (LRU) algorithm manage page references effectively by keeping track of which pages are most frequently or recently accessed. The Optimal algorithm focuses on predicting and retaining the most useful pages that will be accessed next, while LRU tracks the least recently accessed pages and evicts them. Because both strategies prioritize relevant pages, they avoid situations that lead to increased page faults, thus preventing Belady’s anomaly.

Imagine a smart librarian who knows in advance which books students will need (Optimal) or the librarian who recalls which books were last borrowed and prioritizes those (LRU). Both strategies can prevent empty spaces on shelves where students can’t find their needed books. Instead of constantly returning to the storage closet (disk), they ensure the most relevant materials are always readily available.

--