Question

Simulator of Page Replace Management

Visualizing page replacement algorithms includes (1) Least Recently Used (LRU) (2) Optimal (OPT) (3) First in and First out (FIFO) (4) Clocks (2) Second Chance. Development Language: c .

Answer 1

// Java implementation of FIFO page replacement

// in Operating Systems.

  

import java.util.HashSet;

import java.util.LinkedList;

import java.util.Queue;

  

  

class Test

{

    // Method to find page faults using FIFO

    static int pageFaults(int pages[], int n, int capacity)

    {

        // To represent set of current pages. We use

        // an unordered_set so that we quickly check

        // if a page is present in set or not

        HashSet<Integer> s = new HashSet<>(capacity);

       

        // To store the pages in FIFO manner

        Queue<Integer> indexes = new LinkedList<>() ;

       

        // Start from initial page

        int page_faults = 0;

        for (int i=0; i<n; i++)

        {

            // Check if the set can hold more pages

            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++;

                }

            }

        }

       

        return page_faults;

    }

      

    // Driver method

    public static void main(String args[])

    {

        int pages[] = {7, 0, 1, 2, 0, 3, 0, 4,

                        2, 3, 0, 3, 2};

   

        int capacity = 4;

        System.out.println(pageFaults(pages, pages.length, capacity));

    }

}

// Java implementation of LRU algorithm

  

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

  

class Test

{

    // Method to find page faults using indexes

    static int pageFaults(int pages[], int n, int capacity)

    {

        // To represent set of current pages. We use

        // an unordered_set so that we quickly check

        // if a page is present in set or not

        HashSet<Integer> s = new HashSet<>(capacity);

       

        // To store least recently used indexes

        // of pages.

        HashMap<Integer, Integer> indexes = new HashMap<>();

       

        // Start from initial page

        int page_faults = 0;

        for (int i=0; i<n; i++)

        {

            // Check if the set can hold more pages

            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++;

                }

       

                // Store the recently used index of

                // each page

                indexes.put(pages[i], i);

            }

       

            // If the set is full then need to perform lru

            // i.e. remove the least recently used page

            // and insert the current page

            else

            {

                // Check if current page is not already

                // present in the set

                if (!s.contains(pages[i]))

                {

                    // Find the least recently used pages

                    // that is present in the set

                    int lru = Integer.MAX_VALUE, val=Integer.MIN_VALUE;

                      

                    Iterator<Integer> itr = s.iterator();

                      

                    while (itr.hasNext()) {

                        int temp = itr.next();

                        if (indexes.get(temp) < lru)

                        {

                            lru = indexes.get(temp);

                            val = temp;

                        }

                    }

                  

                    // Remove the indexes page

                    s.remove(val);

                   //remove lru from hashmap

                   indexes.remove(val);

                    // insert the current page

                    s.add(pages[i]);

       

                    // Increment page faults

                    page_faults++;

                }

       

                // Update the current page index

                indexes.put(pages[i], i);

            }

        }

       

        return page_faults;

    }

      

    // Driver method

    public static void main(String args[])

    {

        int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};

         

        int capacity = 4;

          

        System.out.println(pageFaults(pages, pages.length, capacity));

    }

}

// Java program Clock Algorithm


import java.util.*;
import java.io.*;
class secondChance
{
   public static void main(String args[])throws IOException
   {
       String reference_string = "";
       int frames = 0;

       //Test 1:
       reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4";
       frames = 3;
      
       //Output is 9
       printHitsAndFaults(reference_string,frames);
      
       //Test 2:
       reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1";
       frames = 4;
      
       //Output is 11
       printHitsAndFaults(reference_string,frames);
      
   }
  
   //If page found, updates the second chance bit to true
   static boolean findAndUpdate(int x,int arr[],
                   boolean second_chance[],int frames)
  
   {
       int i;
      
       for(i = 0; i < frames; i++)
       {
          
           if(arr[i] == x)
           {
               //Mark that the page deserves a second chance
               second_chance[i] = true;
              
               //Return 'true', that is there was a hit
               //and so there's no need to replace any page
               return true;
           }
       }
      
       //Return 'false' so that a page for replacement is selected
       //as he reuested page doesn't exist in memory
       return false;
      
   }
  
  
   //Updates the page in memory and returns the pointer
   static int replaceAndUpdate(int x,int arr[],
               boolean second_chance[],int frames,int pointer)
   {
       while(true)
       {
          
           //We found the page to replace
           if(!second_chance[pointer])
           {
               //Replace with new page
               arr[pointer] = x;
              
               //Return updated pointer
               return (pointer+1)%frames;
           }
          
           //Mark it 'false' as it got one chance
           // and will be replaced next time unless accessed again
           second_chance[pointer] = false;
          
           //Pointer is updated in round robin manner
           pointer = (pointer+1)%frames;
       }
   }
  
   static void printHitsAndFaults(String reference_string,
                                               int frames)
   {
       int pointer,i,l,x,pf;
      
       //initially we consider frame 0 is to be replaced
       pointer = 0;
      
       //number of page faults
       pf = 0;
      
       //Create a array to hold page numbers
       int arr[] = new int[frames];
      
       //No pages initially in frame,
       //which is indicated by -1
       Arrays.fill(arr,-1);
      
       //Create second chance array.
       //Can also be a byte array for optimizing memory
       boolean second_chance[] = new boolean[frames];
      
       //Split the string into tokens,
       //that is page numbers, based on space
       String str[] = reference_string.split(" ");
      
       //get the length of array
       l = str.length;
      
       for(i = 0; i<l; i++)
       {
          
           x = Integer.parseInt(str[i]);
          
           //Finds if there exists a need to replace
           //any page at all
           if(!findAndUpdate(x,arr,second_chance,frames))
           {
               //Selects and updates a victim page
               pointer = replaceAndUpdate(x,arr,
                       second_chance,frames,pointer);
              
               //Update page faults
               pf++;
           }
       }
      
       System.out.println("Total page faults were "+pf);
   }
}

// CPP program to demonstrate optimal page
// replacement algorithm.
#include <bits/stdc++.h>
using namespace std;

// Function to check whether a page exists
// in a frame or not
bool search(int key, vector<int>& fr)
{
   for (int i = 0; i < fr.size(); i++)
       if (fr[i] == key)
           return true;
   return false;
}

// Function to find the frame that will not be used
// recently in future after given index in pg[0..pn-1]
int predict(int pg[], vector<int>& fr, int pn, int index)
{
   // Store the index of pages which are going
   // to be used recently in future
   int res = -1, farthest = index;
   for (int i = 0; i < fr.size(); i++) {
       int j;
       for (j = index; j < pn; j++) {
           if (fr[i] == pg[j]) {
               if (j > farthest) {
                   farthest = j;
                   res = i;
               }
               break;
           }
       }

       // If a page is never referenced in future,
       // return it.
       if (j == pn)
           return i;
   }

   // If all of the frames were not in future,
   // return any of them, we return 0. Otherwise
   // we return res.
   return (res == -1) ? 0 : res;
}

void optimalPage(int pg[], int pn, int fn)
{
   // Create an array for given number of
   // frames and initialize it as empty.
   vector<int> fr;

   // Traverse through page reference array
   // and check for miss and hit.
   int hit = 0;
   for (int i = 0; i < pn; i++) {

       // Page found in a frame : HIT
       if (search(pg[i], fr)) {
           hit++;
           continue;
       }

       // Page not found in a frame : MISS

       // If there is space available in frames.
       if (fr.size() < fn)
           fr.push_back(pg[i]);

       // Find the page to be replaced.
       else {
           int j = predict(pg, fr, pn, i + 1);
           fr[j] = pg[i];
       }
   }
   cout << "No. of hits = " << hit << endl;
   cout << "No. of misses = " << pn - hit << endl;
}

// Driver Function
int main()
{
   int pg[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 };
   int pn = sizeof(pg) / sizeof(pg[0]);
   int fn = 4;
   optimalPage(pg, pn, fn);
   return 0;
}