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

[table id=372 /]

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription