FIFO Page Replacement Algorithm in Java

FIFO Page Replacement Algorithm in Java

The approach of First in First Out (FIFO) states that the element which entered the queue initially will leave the queue first. The order in which the elements are placed in a queue will be followed to remove them from the queue. 

FIFO in OS

How does it work?

In this algorithm, the page that came in first will go out first.

In other words, the page oldest page in the queue/memory will be replaced first.

  • Incoming page Steam – 7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1
  • Page Size/ Frame Size = 3
Incoming Page Stream ->70120304230321
Existing at position 177722244400
Existing at position 20003332221
Existing at position 3111000333
Page Faultxxxxxxxxxxx

Method 1

Program in Java

Run

// Code for FIFO page replacement algorithm in java

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;


class Main
{
    static int pageFaults(int incomingStream[], int n, int frames)
    {
        System.out.println("Incoming \t Pages");
        // Using Hashset to quickly check if a given
        // incoming stream item in set or not
        HashSet s = new HashSet<>(frames);

        // Queue created to store pages in FIFO manner
        // since set will not store order or entry
        // we will use queue to note order of entry of incoming page
        Queue queue = new LinkedList<>();

        int page_faults = 0;

        for (int i=0; i < n; i++)
        {
            // if set has lesser item than frames
            if (s.size() < frames)
            {
                // If incoming item is not present, add to set
                if (!s.contains(incomingStream[i]))
                {
                    s.add(incomingStream[i]);
                    page_faults++;

                    // Push the incoming page into the queue
                    queue.add(incomingStream[i]);


                }
            }

            // If the set is full then we need to do page replacement
            // in FIFO manner that is remove first item from both
            // set and queue then insert incoming page
            else
            {
                // If incoming item is not present
                if (!s.contains(incomingStream[i]))
                {
                    // remove the first page from the queue
                    int val = (int) queue.peek();

                    // remove from queue
                    queue.poll();

                    // Remove from set
                    s.remove(val);

                    // insert incoming page to set
                    s.add(incomingStream[i]);

                    // push incoming page to queue
                    queue.add(incomingStream[i]);
                    page_faults++;


                }
            }
            // printing happens here
            System.out.print(incomingStream[i] + "\t");
            System.out.print(queue + " \n");
        }


        return page_faults;
    }

    public static void main(String args[])
    {
        int incomingStream[] = {7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1};
        int frames = 3;

        int len = incomingStream.length;
        int pageFaults = pageFaults(incomingStream, len, frames);
        int hit = len - pageFaults;

        System.out.println("Page faults: " + pageFaults);
        System.out.println("Page fault Ratio: " + (double) pageFaults/len);
        System.out.println("Hits: " + hit);
        System.out.println("Hit Ratio : " + (double) hit/len);
    }

Output

Incoming 	 Pages
7	         [7] 
0	         [7, 0] 
1	         [7, 0, 1] 
2	         [0, 1, 2] 
3	         [1, 2, 3] 
0	         [2, 3, 0] 
4	         [3, 0, 4] 
2	         [0, 4, 2] 
3	         [4, 2, 3] 
0	         [2, 3, 0] 
1	         [3, 0, 1] 

Page faults: 11
Page fault Ratio: 0.7857142857142857
Hits: 3
Hit Ratio : 0.21428571428571427

Method 2

Program in Java

Run
package LinkedLists;
// Code for FIFO page replacement algorithm in java

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;


class Main
{

    public static void main(String args[])
    {
        int incomingStream[] = {7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1};
        int pageFaults = 0;
        int frames = 3;
        int m, n, s, pages;

        pages = incomingStream.length;

        System.out.println("Incoming \t Frame 1 \t Frame 2 \t Frame 3");
        int temp[] = new int[frames];
        for(m = 0; m < frames; m++)
        {
            temp[m] = -1;
        }

        for(m = 0; m < pages; m++)
        {
            s = 0;

            for(n = 0; n < frames; n++)
            {
                if(incomingStream[m] == temp[n])
                {
                    s++;
                    pageFaults--;
                }
            }
            pageFaults++;

            if((pageFaults <= frames) && (s == 0))
            {
                temp[m] = incomingStream[m];
            }
            else if(s == 0)
            {
                temp[(pageFaults - 1) % frames] = incomingStream[m];
            }

            System.out.println();
            System.out.print(incomingStream[m] + "\t\t\t");
            for(n = 0; n < frames; n++)
            {
                if(temp[n] != -1)
                    System.out.print(temp[n] + "\t\t\t");
                else
                    System.out.print(" - \t\t\t");
            }
        }

        System.out.println("\nTotal Page Faults:\t" + pageFaults);
    }
}

Output

Incoming 	 Frame 1 	 Frame 2 	 Frame 3

7		7		- 			- 			
0		7		0			- 			
1		7		0			1			
2		2		0			1			
0		2		0			1			
3		2		3			1			
0		2		3			0			
4		4		3			0			
2		4		2			0			
3		4		2			3			
0		0		2			3			
3		0		2			3			
2		0		2			3			
1		0		1			3			

Total Page Faults:	11

Other pages

  1. Page Replacement Algorithms
    1. LRU – C | C++ | Java | Python
    2. FIFO – C | C++ | Java | Python
    3. Optimal Page Replacement algorithm – C | C++ | Java | Python