FIFO Page Replacement Algorithm

What is the FIFO Page Replacement Algorithm?

FIFO which is also known as First In First Out is one of the types of page replacement algorithm. The FIFO algorithm is used in the paging method for memory management in an operating system that decides which existing page needs to be replaced in the queue.

FIFO algorithm replaces the oldest (First) page which has been present for the longest time in the main memory.

In simple words, When a new page comes in from secondary memory to main memory, It selects the front of the queue which is the oldest page present, and removes it.

Why do we need to swap the pages?: Since we have a fixed number of frames and all the processes cannot be stored in the main memory at a single time we use page replacement algorithms to store pages of a process instead of the whole process.

How Does FIFO Page Replacement Work?

FIFO is implemented in the operating system by keeping track of all the pages in a queue. The newest page is at the head of the queue and the oldest (first) page is in the tail.

"To illustrate how the FIFO page replacement algorithm works in a real-life, Consider you are the owner of a supermarket which has N number of shelves to put exactly N different products.

One day, A company launches a new convenience powdered milk, organic food, and glass noodles that can be reconstituted in a microwave oven. So in order to sell the new products, you need to get rid of one old product. Now you have to find out which product you should eliminate from your store, So you need to find the product the supermarket has been stocking the longest. After finding the product, Just like the FIFO algorithm, the one at the front of the list is removed whereas the new one goes on the back of the list i.e. the reconstituted products.”

1. The OS maintains a list of all pages which are residing in the memory.
2. When a new page is brought from the secondary memory.
3. The new page requests the main memory.
4. On a page fault, the head of the list i.e. the oldest will be removed.
5. The new page will be added at the tail of the list.

Page Fault: A page fault occurs when a page requested by a program running in the CPU is not present in the main memory, but in the address page of that program. A page fault generally creates an alert for the OS.

FIFO Pseudocode

Here,

• 'P' is used to represent pages.
• 'N' is the number of pages.
• 'C' is the Capacity.

Implementation of FIFO Page Replacement Algorithm Using A Programming Language

Step 1. Start to traverse the pages. Step 2. If the memory has less pages than capacity; else goes to step 6. Step 3. ==Push== the pages in set one at a time until the size of the set does not overflow or all page requests are fulfilled. Step 4. Increment the PF (page fault) and ==return==. Step 5. If that current page is already available in the memory, do nothing. Step 6. Else, ==Pop== and Replace the topmost page in the queue which is inserted first with the page (current) from the string. Step 7. Increase the PF(page faults) and ==stop==.

Output:

The total number of page faults are: 6

Example of FIFO Page Replacement Algorithm

Q. Consider a page reference string 1, 3, 0, 3, 5, 6 with 3-page frames. To find the number of page faults?

Total Page Fault = 6.

Consider the steps below,

1. • Initially, Since all the slots are empty, therefore, the first 3 elements 0, 3, 1 are allocated to the empty slots due to which the Page faults become 3.
2. • After the 0, 3, and 1 element 3 comes, But now 3 is already present. So the Page faults become 0.
3. • Now when 5 comes which is not available in the memory the oldest page slot 1 will be replaced. So the Page faults become 1.
4. • After that 6 comes, 6 is also not present so it also gets replaced with the oldest page i.e. 3. The Page faults becomes 1.
5. • At last, element 3 arrives which is not present, Hence it is replaced by element 0. So the page faults become 1.

Advantages of FIFO Page Replacement Algorithm

• The FIFO page replacement algorithm is commonly known for its simplicity.
• The FIFO algorithm is much easier to implement as well as understand.
• Small systems can use the FIFO algorithm efficiently.

Disadvantages of FIFO Page Replacement Algorithm

• FIFO algorithm in os uses an additional ==Queue== data structure.
• It suffers from ==Belady's anomaly== problem i.e when the number of page frames increases, more memory is given to processes, but instead of decreasing, the number of page faults increases.