FIFO Page Replacement Algorithm

Last Updated on June 23, 2023 by Mayank Dham

In this article, we will learn about the FIFO Page Replacement Algorithm in OS. We will discuss the Working of FIFO in OS along with its advantages and disadvantages. We will also look at the implementation of the FIFO Page Replacement Algorithm in a programming language.

Introduction to Memory Management

Memory management is an essential subject in an operating system. It offers strategies for dynamically directing and organizing computer memory. When software requests it, memory management enables allocating a piece of memory. Additionally, it automatically releases memory from programs when they are no longer using it.

There are several methods for managing memory. Paging is one such approach. Page replacement algorithms are crucial in paging because they choose which page to stay in the main memory when a new page is received.

The simplest page replacement method is the first-in, first-out (FIFO) Algorithm.

Page Replacement Algorithms in OS

Page replacement algorithms in operating systems are used to manage the memory of a computer system. They are used to decide which page in memory should be replaced when a page fault occurs and a page needs to be loaded from disk into memory.

There are several page replacement algorithms that are used in operating systems, some of the most common ones include:

• FIFO (First-In-First-Out): This algorithm replaces the oldest page in memory when a page fault occurs. It keeps track of all pages in memory in a queue and when a page fault occurs, the page at the front of the queue is removed and a new page is added to the back of the queue.
• LRU (Least Recently Used): This algorithm replaces the page that has not been used for the longest period of time. It keeps track of the last access time of each page and when a page fault occurs, the page with the oldest access time is replaced.
• LFU (Least Frequently Used): This algorithm replaces the page that has been used the least number of times. It keeps track of the number of times each page has been accessed and when a page fault occurs, the page with the lowest access count is replaced.
• Optimal: This algorithm replaces the page that will not be used for the longest period of time in the future. It uses future knowledge of the memory access pattern to determine which page to replace.
• 2Q algorithm: This algorithm is a hybrid of LRU and LFU algorithms that tries to overcome the limitations of both algorithms by maintaining two queues.

The choice of the page replacement algorithm depends on the system’s needs and the characteristics of the workload. Some algorithms may perform well for certain types of workloads, but poorly for others.

Here we will discuss FIFO Algorithm in detail.

What is FIFO Algorithm

The term FIFO is an acronym for “First In, First Out”.The FIFO page replacement algorithm is a simple algorithm that replaces the oldest page in memory when a page fault occurs. The algorithm keeps track of all pages in memory in a queue and when a page fault occurs, the page at the front of the queue (the oldest page) is removed and the new page is added to the back of the queue.

Real Life Example to understand FIFO in OS:
A real-life example of the FIFO page replacement algorithm can be found in a restaurant kitchen. Imagine that a restaurant kitchen has a limited number of plates and the plates are used to serve food to customers. The kitchen staff washes the plates and puts them in a rack in the order they were washed. When a customer orders food, the kitchen staff takes the plate from the front of the rack (the oldest plate) and uses it to serve the food. If the kitchen runs out of plates and a customer orders more food, the kitchen staff takes the plate from the front of the rack (the oldest plate) and washes it before using it to serve the food.

In this example, the plates represent pages in memory and the rack represents the queue used by the FIFO page replacement algorithm. The kitchen staff, who takes the plate from the front of the rack and uses it to serve food, represents the page replacement algorithm that selects the oldest page in memory and replaces it with a new page when a page fault occurs.

Working of FIFO Algorithm

A page replacement algorithm determines which page to replace in order to allocate memory for the new page. A flowchart can be used to summarise the phases of a page replacement:

The FIFO page replacement algorithm follows these steps:

• Step 1: Initialize a queue to keep track of the pages in memory.
• Step 2: When a page fault occurs and a page needs to be replaced, the page at the front of the queue is selected for replacement.
• Step 3: The page that is being replaced is removed from memory and the new page is added to the back of the queue.
• Step 4: This process continues each time a page fault occurs and a page needs to be replaced.

The algorithm uses a simple data structure like a queue to keep track of the pages in memory, and the page that was brought in first will be the first one to be replaced. The algorithm does not consider how often or recently a page has been used, it simply replaces the oldest page in memory.

Implementation of the FIFO Page Replacement Algorithm

The code implementation for the FIFO Page Replacement Algorithm in Java is given below:

import java.util.*;

class Main{
    public static void main(String args[]){
        int pages[] = {1, 3, 0, 3, 5, 6, 3};
        int capacity = 3;
        int n = pages.length;
        
        // Set containing current pages
        HashSet<Integer> s = new HashSet<>(capacity);
    
        // Queue to store the pages in FIFO manner
        Queue<Integer> indexes = new LinkedList<>() ;

        int page_faults = 0;
        
        for (int i=0; i<n; i++){
            // Check if the set can hold more pages or not
            if (s.size() < capacity){
                // Insert it into set if not present
                // already which represents page fault
                if (!s.contains(pages[i])){
                    s.add(pages[i]);
    
                    // increment page fault
                    page_faults++;
    
                    // Push the current page into the queue
                    indexes.add(pages[i]);
                }
            }
    
            // If the set is full then need to perform FIFO
            // i.e. remove the first page of the queue from
            // set and queue both and insert the current page
            else
            {
                // Check if current page is not already
                // present in the set
                if (!s.contains(pages[i]))
                {
                    //Pop the first page from the queue
                    int val = indexes.peek();
    
                    indexes.poll();
    
                    // Remove the indexes page
                    s.remove(val);
    
                    // insert the current page
                    s.add(pages[i]);
    
                    // push the current page into
                    // the queue
                    indexes.add(pages[i]);
    
                    // Increment page faults
                    page_faults++;
                }
            }
        }
        System.out.println(page_faults);
        
    }
}

Output:

6

Explanation: Above we have implemented the FIFO Algorithm in OS in Java. Here, we have declared a HashSet which stores the current pages and a queue to maintain the “first in first out” order. Then we traversed the whole “pages” array. There can be two following situations on basis of the size of the set and the capacity specified.

1. If the set can hold more pages, insert the current page in the set if not already present and increase the page fault.
2. If the size of set exceeds capacity and the current page is not in set, then pop the topmost page from the queue and replace it with the current page, and the count of page_fault is increased

After that the total number of Page Faults have been printed.

Advantages of the FIFO Algorithm

The advantages of the FIFO page replacement algorithm in operating systems are listed below:

• Simple to implement: FIFO is a very simple algorithm to implement, as it only requires a basic data structure like a queue to keep track of the items.
• Low overhead: Since FIFO only requires a simple data structure and does not require any additional information to be stored, it has low overhead.
• Easy to understand: FIFO is easy to understand, as it only uses a first-in, first-out approach, and does not require any complex calculations.
• Predictable: FIFO is predictable, as the item that was brought in first will be the first one to be replaced.
• Predictable behavior: The algorithm has a predictable behavior, so it can be easily used in systems where predictability is important.
• Low complexity: FIFO is a low-complexity algorithm and requires minimal computational power.
• Suitable for workloads with temporal locality: FIFO is suitable for workloads where items are accessed in a temporal order, as the algorithm will keep the most recently accessed items in memory.

Drawbacks of the FIFO Algorithm

The disadvantages of the FIFO page replacement algorithm in operating systems include:

• Belady’s Anomaly: FIFO can lead to Belady’s Anomaly, where the number of page faults can increase as the number of frames increases, under certain circumstances.
• Not effective for workloads with a spatial locality: If a workload has a spatial locality, where pages that are used together are likely to be used again soon, FIFO does not perform well, as it does not take into account how recently or frequently a page has been used.
• Poor performance for workloads with a non-uniform access pattern: If a workload has a non-uniform access pattern, where pages are accessed at different rates, FIFO does not perform well as it does not take into account how recently or frequently a page has been used.
• Does not take into account the usage of the page and can lead to swapping out frequently used pages for less frequently used pages.
• This can lead to a high number of page faults when there is a large number of pages that are used in a non-sequential order.

Conclusion
In summary, FIFO (First-In, First-Out) is a page replacement algorithm used in operating systems to manage memory. It replaces the oldest page in memory with a new one when a page fault occurs. The algorithm is simple to implement, has low overhead, and performs well for workloads with a temporal locality, where recently used pages are likely to be used again soon. However, it can lead to Belady’s anomaly, where the number of page faults can increase as the number of frames increases, and it is not effective for workloads with a spatial locality or non-uniform access pattern where pages are accessed at different rates.

Frequently Asked Questions (FAQs)

Q1. What is the purpose of memory management in an operating system?
Memory management in an operating system is responsible for dynamically allocating and organizing computer memory. It ensures that memory is efficiently utilized by allocating memory to programs when requested and automatically releasing memory when it is no longer in use.

Q2. What are page replacement algorithms in operating systems?
Page replacement algorithms are used in operating systems to manage memory. They determine which page in memory should be replaced when a page fault occurs and a new page needs to be loaded from disk into memory.

Q3. How does the First-In, First-Out (FIFO) algorithm work?
The FIFO algorithm replaces the oldest page in memory when a page fault occurs. It uses a queue to keep track of the pages in memory, and the page at the front of the queue (the oldest page) is selected for replacement. The new page is then added to the back of the queue.

Q4. What are the advantages of the FIFO algorithm?
The advantages of the FIFO algorithm include its simplicity, low overhead, predictable behavior, and suitability for workloads with temporal locality where recently used pages are likely to be used again soon. It is also easy to understand and requires minimal computational power.

Q5. What are the drawbacks of the FIFO algorithm?
The drawbacks of the FIFO algorithm include the potential for Belady’s Anomaly, where increasing the number of frames can result in more page faults. Additionally, FIFO does not perform well for workloads with spatial locality or non-uniform access patterns, as it does not consider how recently or frequently a page has been used. This can lead to a higher number of page faults in such scenarios.