17.1.1. Compulsory Misses

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.

Compulsory misses occur when a program tries to access data that has never been loaded into memory. In this scenario, the memory can only hold 4 page frames, and the reference string is a set of memory accesses. For the first four accesses (which are 2, 0, 1, 6), since nothing is in memory, all these accesses will result in misses. Thus, the first four page faults are considered compulsory because they represent the initial loading of the pages into memory.

Imagine you are attending a class for the first time without having any of the textbooks. When you arrive and check for your textbooks, you won't find any, leading to multiple previous visits to the library being necessary (compulsory misses). Each time you reference a textbook, it will be a miss until you have checked out all the necessary books.

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 come into memory. So, the 0 is the oldest.

As new pages are referenced, page replacement comes into play when the memory is full, leading to a page fault. In this case, when the reference 4 arrives, the system needs to decide which of the current pages (0, 2, 1, 6) to evict. It will choose the oldest page in memory, which in this case is 0, because it was the first page loaded. Thus, 0 is replaced with 4, leading to an updated memory state.

Think of a crowded classroom where only four students can sit at a table. If a fifth student wants to sit down, the teacher must decide which student to ask to leave. The teacher will typically choose the student who has been sitting there the longest—this is similar to how the page replacement works in 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.

The page fault rate is calculated by taking the number of page faults and dividing it by the total number of memory accesses. In this case, there were 12 memory references, and 9 of those resulted in page faults. Thus, the page fault rate is computed as 9/12, resulting in a rate of 0.75, indicating that 75% of memory accesses resulted in a fault, leading to inefficiency.

Imagine if you were allowed to check out 12 books from the library but found that 9 of them were never available because they were already checked out. This would indicate that you have a 75% failure rate in accessing the books you want, demonstrating a similar situation to a high page fault rate.

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.

The First-In-First-Out (FIFO) page replacement policy operates by removing the oldest page, regardless of how frequently it may have been accessed recently. This can lead to inefficiencies because a frequently used page can be evicted simply because it has been in memory the longest—missing the opportunity to keep useful data in memory and resulting in higher page faults.

To visualize this, think of a vending machine that only dispenses the first snack placed inside, regardless of how many times the other snacks have been sold. If a customer needs a snack that is still popular but was the first one placed in, they may not get it when they need it, leading to disappointment (analogous to missing frequently accessed pages).

--