CREATE OWN LIBRARY

FIFO page replacement algorithm

The simplest page replacement algorithm is First in First out (FIFO) algorithm. This policy replaces the page that was loaded into memory earlier (oldest page) than any other page references of the process.

Implementation:

To implement FIFO page replacement we can create a queue to hold all pages in the main memory.

Every time we replace the page which is at the head of the queue i.e. the oldest one. When a new page is loaded into memory, we insert it at the tail of the queue.

We can implement this queue by a linked list where every page and its corresponding page entry maintain by a node of the linked list. So, a process can maintain by this whole linked list.

Suppose a new page 7 is required to load into main memory. So, as per FIFO policy page 7 is replaced by page 1 because it is the oldest one. 

But as per FIFO implementation by queue using a linked list, we insert page 7 at the last position of the linked list (tail) and delete the first node (head) which is page 1. 

Example

# Now we consider a reference string and evaluates the FIFO page replacement algorithm.

Page references: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 and we have 4 frames in main memory.

As per the concept of demand paging no pages will load until any request arises.

So, initially, frames are empty, now because our 4 frames are empty, we can load the first different 4 page references into frames.

Note: Here unlike Optimal and LRU, in FIFOwe use a queue to track which page comes earlier. It is important to use because for long page references it has the chance to trace the earlier one.

Step 1: Now, we can load the first 4 page references 6, 0, 1, 2. 

Next Request of page reference: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Step 2: Now, after loaded page reference 2, the next requirement of page reference is 0. But page reference 0 already loaded in the frame so, there is no page replacement that will not require. 

Next page requirement is 3, but no frames are available; one loaded page should be replaced as per FIFO policy. 

Now if we see the queue which is used to track the earliest page, the first loaded page is 6

So, we loaded new page 3 and replace page reference 6.

Next Request of page reference: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.

Step 3: Now, after loaded page reference 3, the next requirement of page reference is 0. But not considered because already loaded in the frame i.e. no page fault.

# Next requirement of page reference is 4, new page. But all frames are full, so we have replaced one page from the frame as per FIFO policy.

Now, again if we see the queue, the oldest page (first come) is 0.

So, we replace the oldest page reference 0 by the new page reference 4.

Next Request of page reference: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.

Step 4: After insert page reference 4 into the frame, the next requirement of page reference is 2, not considered because already in the frame, so, no page fault. 

Next request for page reference is 3 which also present in the frame, so, no page fault.

Next requirement of page reference is 0, new page. But all frames are full, so we have replaced one page from the frame as per FIFO policy.

Now, again if we see the queue, the oldest page (first come) is 1.

So, we replace page reference 1 by new page reference 0.

Next Request of page reference: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.

Step 5: After insert page reference 0 into the frame, the next requirement of page reference is 3 again, which also present in the frame, so, no page fault.

Next request for page reference is 2 which also present in the frame, so, no page fault.

Page reference request is ended.

Final picture of how page references working with frames:

Page References: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.

So, the number of page faults = 7.

And page fault rate = number of page faults / number page references

So, page fault rate = 7 / 13 = 0.53

Shortcut method:

But in examination it is not possible to solve it by this elaborative way we can do it by a single frame like below:

Page references: 6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Number of page faults = 7.