20.3.1. Introduction to Page Buffering

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. 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 occur.

Belady's anomaly refers to a counterintuitive situation where increasing the number of page frames results in an increase in page faults. This occurs because, during any point in time when the number of frames is limited, the pages that are currently loaded into memory may not be a subset of the pages that would be loaded if there were more frames available. This indicates a flaw in some page replacement algorithms where more frames do not necessarily lead to better performance.

Imagine a library with a fixed number of bookshelves. If there are too few shelves, you can only display certain books at once, which might not include the ones most frequently needed. When you expand the number of shelves, it might lead to different books being accessible but not necessarily the right ones that readers want, thus causing confusion and 'misses' in what they wished to find.

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.

The example of memory references 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 is used to illustrate how pages are loaded into memory and the resulting page faults. Each memory reference is treated sequentially, and frames are filled based on a FIFO (First In, First Out) policy. When a page reference that is not currently in memory occurs, it's a page fault. This example demonstrates the relationship between the number of frames and the occurrence of page faults.

Think of it like a car parking scenario; if you have only a few parking spots (frames), only certain cars (pages) can park. If a certain car is not parked when you go to access it, you'll have to leave and come back later, which can be inconvenient if more suitable parking spots don’t mean more cars parked correctly.

Now, when I have 4 frames in memory these are the set of accesses. ... So, therefore, you have 10 page faults, here you have 9 faults and here you have 10 faults.

The analysis shows how the number of page frames directly affects the number of page faults. In the case where there are 3 frames, we see more hits (successful retrievals) but also a high number of page faults than with 4 frames. The key takeaway is that increasing frames doesn't always improve the situation, illustrating the anomaly further.

This can be likened to packing a suitcase. A smaller suitcase might force you to streamline your packing effectively, but suddenly increasing your luggage capacity doesn’t ensure that everything you want will fit perfectly without leaving something important behind.

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

The optimal page replacement algorithm is defined as always choosing the page that will not be used for the longest period of time in the future for replacement. LRU (Least Recently Used) keeps track of page usage and replaces the least recently used page. Both methods do not exhibit Belady's anomaly, as they ensure that the pages in memory maintain a continuity that avoids increasing faults with more frames.

Imagine a food buffet. If you know what dishes guests will pick next, you can ensure only the right dishes are left out. Similarly, LRU watches consumption patterns, avoiding wastage or repeated misses by staying effectively 'in tune' with guest choices over time.

Now, page buffering it is expensive to wait for a dirty page to be written out. ... So, this is how buffering will work.

Page buffering is a technique that reduces wait times by keeping a pool of free frames. During a page fault when a dirty page (a page that has been modified) needs to be replaced, instead of waiting for the page to be written to disk, the system uses a free frame from the pool. This helps to streamline the replacement process and maintain efficient operation.

Imagine you’re in a busy kitchen replacing dishes. Instead of letting everyone wait for one dish to be cleaned, you keep a spare set of clean dishes ready to serve immediately. You clean and refill the spare set later without holding up service, allowing for a smooth operation.

Now, one more important aspect ... I can keep a pointer that this page is still there although it is there in the free frame pool.

An enhancement in page buffering allows the content of replaced pages to remain intact in the free frame pool. If needed later, that unchanged page can still be accessed quickly rather than fetching it from disk. This significantly reduces access time and improves efficiency.

Consider a store that has returned but unsold items in the back storage but readily available for purchase. If a customer decides they want something, rather than waiting for it to be re-stocked from the wholesaler, having it on hand makes serving the customer quicker and more efficient.

--