17.3.3. Stack-based Solution

(Refer Slide Time: 63:00) So, consider the reference string 2 0 1 6 4 2 0 1 6 4 0 1 0 3 1 2 1. Now here I have 4 page frames, let us say my physical memory only has 4 page frames available and these are the set of memory accesses. So, initially there is nothing in the physical memory. So, the first 4 misses are compulsory the first 4 misses are compulsory misses and. So, I bring in 0 2 1 6, 0 2 1 6 missed and then what happens 4 comes in whom will 4 replace 0 was the first one to; 0 was the first one to come into memory. So, the 0 is the oldest. So, 0 is replaced and with 4.

This chunk introduces a reference string of memory accesses and describes how it interacts with a limited number of page frames (4 in this case). Initially, the physical memory is empty, which causes the first four accesses (to pages 2, 0, 1, and 6) to result in page faults because those pages need to be loaded into memory. The chunk explains that when a new page (4) is accessed, the oldest page in memory (0) must be replaced due to the FIFO (First-In, First-Out) replacement policy.

Imagine a situation where you have a small filing cabinet that can only hold four folders at a time. When you get a new folder (like accessing page 4), you must remove the oldest folder (like page 0) to make space. Each time you try to access a folder that isn’t in the cabinet, you have to go get it, which takes time—just like the page faults.

Now, 0 is accessed again, now 0 is not there in the physical memory. So, 0 will again lead to another page fault and. So, whom will it replace 2 is now the oldest one who which came into memory. So, 0 replaces 2 then what happens one comes again one is referenced again this one does not result in a miss this one is already there in main memory. And this is not a miss, then 0 this also does not incur a miss 0 is already there in memory, it does not incur a miss. Then 3 is accessed when 3 is accessed 3 is not there in physical memory whom will it replace? It will replace the oldest one because 0 2 1 6 was the order 0 and 2 has already been replaced. So, now, the oldest is one now the oldest is to 1. So, 3 replaces 1.

In this chunk, we see the continued operation of the memory system as different pages are accessed. When page 0 is accessed again after being replaced, it leads to another page fault since it is not currently in memory. As per the FIFO policy, the page that gets replaced is based on which one was accessed the longest ago. This chain reaction highlights how frequently accessed pages remain in memory while others are swapped out.

Think of a library where patrons can only check out four books at a time. If a patron returns a book and later wants to borrow it back but has already returned it, they will have to find a different book to return as there are limited slots. The library follows the same idea as FIFO; the first person who checked out the oldest book has to return it to check out a new one.

Now, 1 is accessed again 1 is currently not there in physical memory 3 just replaced 1, 1 accessed again and then a one incurs a miss again whom does 1 replace will see 1 replaces 6? So, 1 replaces 6, now 2 is accessed 2 is accessed 2 is currently not there in physical memory. So, 2 replaces 4, 2 replaces 4 and because 4 is now the oldest and then 1 is now there again in physical memory. So, what is the fault rate? So, I had 12 the different string is of length 12. So, I have 12 mem references out of 12 references nine resulted in a fault 1 2 3 4 5 6 7 8 9; 9 resulted in a fault. So, the fault rate is 9 by 12 or 0.75.

This chunk discusses further accesses to pages and concludes with calculating the page fault rate. A series of substitutions occurs with the least recently used pages, leading to a count of how many accesses were misses or faults. Out of 12 total memory references, 9 resulted in faults, so the fault rate is calculated as 9/12, which simplifies to 0.75. This indicates a high rate of faults which is generally indicative of performance issues in the memory management system.

Continuing with the library example, if out of 12 visitors, 9 had trouble finding the books they wanted (because the books were either already checked out or had been returned), the library might consider adjusting its policies or acquiring more copies of popular titles to improve the experience.

So, FIFO although is very simple, I find out the oldest page in memory and replace it, this is the algorithm, it’s a poor replacement policy why it evicts the oldest page in the system and it does not take care whether this page is being heavily used currently or not, it does sees who has been brought at the earliest and it will replace that, it does not care as to which if this page is being frequently used.

Here, the discussion shifts to the limitations of the FIFO page replacement policy. While it is straightforward and easy to implement by simply replacing the oldest page in memory, this method does not account for how frequently or recently pages have been used. Consequently, it might evict an active page that is still needed, causing more page faults.

Think of a restaurant rotation system where the oldest orders are automatically removed after a certain time, regardless of whether those meals are still being enjoyed. Although it ensures old items are cleared out, diners may be left hungry if their favorite dish was removed just because it was ordered first without considering current popularity.

--