17.1. FIFO Page Replacement

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

In the FIFO (First In, First Out) page replacement algorithm, pages are added to memory until the capacity is full. In our example, the reference string consists of a sequence of page requests. We start with 4 empty page frames. When the first four unique page requests (0, 2, 1, and 6) arrive, since the memory is initially empty, these requests lead to page faults, termed 'compulsory misses' because the pages have never been in memory before.

Imagine you have a cupboard with only four slots for your favorite books. The first four books you try to put in the cupboard will fill up those slots, and if you try to put in a fifth book, you will have to remove one of the books you initially placed in the cupboard to make space.

Now, 4 comes in whom will 4 replace? 0 was the first one to come into memory. So, the 0 is the oldest. So, 0 is replaced with 4. Now, 0 is accessed again; it leads to another page fault. 0 will replace 2, who is now the oldest one.

When page 4 is requested, it replaces the oldest page, which is page 0 since it arrived first. The FIFO algorithm does not take into account the future requests; it simply replaces the page that has been in memory the longest. After replacing 0 with 4, if page 0 is requested again, it results in a page fault since 0 is no longer in memory, leading to page 0 replacing page 2, which is now the oldest.

Think of a queue of customers waiting for service. The first customer is served first and leaves. If the next customer comes, and the first customer (who is now gone) is called back, it cannot be done - they would have to take the place of a customer that arrived later.

So, what is the fault rate? I had 12 memory references out of 12 references nine resulted in a fault. So, the fault rate is 9 by 12 or 0.75.

The page fault rate is the ratio of the number of page faults to the total number of memory references. In this case, there were 12 references made, 9 of which resulted in page faults. Therefore, the fault rate is calculated as 9/12, which simplifies to 0.75, indicating that three-quarters of the time, a page fault occurs upon a memory request.

Imagine you are in a class and you have 12 questions that require you to turn in papers. If you turn in the wrong papers 9 out of those 12 times, it shows you have a high error rate of 75%, meaning on average, you are making mistakes in a majority of your submissions.

FIFO although is very simple, it is 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 FIFO replacement policy has a significant limitation: it may evict pages that are frequently used simply because they were loaded first. This can lead to an inefficient use of memory, especially if an older page has become crucial for ongoing processes. Because FIFO does not consider how often or when pages are accessed, it can often lead to a suboptimal page replacement strategy.

Consider a vending machine that only allows you to remove the oldest snacks. If a brand-new snack becomes the favorite choice of everyone but was loaded after several older options, that favorite will end up remaining on the shelves until all older snacks are sold out, regardless of popularity or demand.

Before proceeding to the next actual algorithm we will go into a hypothetical actual algorithm, which actually cannot exist in practice, but is used as a measure of comparison for all other algorithms called the optimal page replacement algorithm.

The optimal page replacement algorithm serves as a theoretical benchmark, which proposes to replace the page that will not be used for the longest time in the future. Although it provides the lowest possible page fault rate, it is impractical because it requires knowledge about future requests, which is not possible. Therefore, this algorithm helps compare the effectiveness of other replacement policies.

Imagine a bus schedule where you know the exact times of your future trips. Using the optimal algorithm would mean you would plan your seats based on not just who is there now but who is expected to leave later, which is not possible in real life. In reality, you have to make decisions on the fly.

--