Question

Develop an algorithm and implement Optimal Page Replacement algorithm using C++. Determine the number of page faults and page hits by considering the Frame size=4, ReferenceString:2 4 6 7 8 2 4 9 13 9 2 7 2 6 1 4 9 2

Answer 1

• Below is the detailed implementation of the above problem in C++ with code and output shown.
• For better understanding please read the comments mentioned in the code.
• In optimal page replacement algorithm we do following steps for every page in reference string:

If current page is present in frame then we increase page hit and move to next page in reference string,

Otherwise we insert that page in the frame if frame size is less than it's capacity, if not then find if any page in the frame is not referenced in future if so then replace that page with the current one, and if this also is not the case then find the farthest referenced page and replace that with current one.

This algorithm is not practical as you can see we are taking action on the basis of future and in real life we can't predict future.

• CODE:

//include headers
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

//function to find page which is not referred in future or is referred farthest in future
int find(int reference_str[], vector<int>&frame, int tot, int index){
//to save index of resulting page
   int save=-1;
   //initialize farthest page to be index
   int farthest=index;
   //for all page in frame
   for(int i=0;i<frame.size();i++){
   //set found to false
   bool found=false;
   //for all pages in reference string starting from index
   for(int j=index;j<tot;j++){
//if current is matched then
           if(frame[i]==reference_str[j]){
//set found true
found=true;
//update farthest if possible
               if(j>farthest){
                   farthest=j;
                   save=i;
               }
               //and break
               break;
           }
       }
       //if the current page is not found then return index as it is not reference in future
       if (found==false)
           return i;
   }

   //if no farthest found return 0
   if(save==-1){
return 0;
   }
   //otherwise return farthest
   return save;
}

//function which uses optimal page replacement algorithm and prints page hits and page faults
void OptimalPageReplacement(int reference_str[], int tot, int frame_size){
//current frame
vector<int>frame;
//unordered map to store which pages are present in frame
unordered_map<int,bool>present;

//to store page hits
   int page_hits=0;
   //for all pages in reference string
   for(int i=0;i<tot;i++){
//if current page is in frame then it is a page hit
       if (present.find(reference_str[i])!=present.end()){
           page_hits++;
           continue;
       }
//otherwise
//if frame has some space then add this page to frame
       if(frame.size()<frame_size){
           frame.push_back(reference_str[i]);
           //and mark it in map also
           present[reference_str[i]]=true;
       }
       //otherwise
       else{
//find the farthest or not reference in future page
           int index=find(reference_str, frame, tot, i+1);
//erase this from map
           present.erase(frame[index]);
           //update frame
           frame[index] = reference_str[i];
           //mark this page in map
           present[frame[index]]=true;
       }
   }
   //print page hit and page faults
   cout<<"Number of page hits are: "<<page_hits<< endl;
   cout<<"Number of page faults: "<<tot-page_hits<< endl;
   return;
}

//driver function
int main(){
//reference string
   int reference_str[] = {2, 4, 6, 7, 8, 2, 4, 9, 13, 9, 2, 7, 2, 6, 1, 4, 9, 2};
   //size of reference string
   int sz=sizeof(reference_str)/sizeof(reference_str[0]);
   //frame size
   int frame_size=4;
   //call function
   OptimalPageReplacement(reference_str, sz, frame_size);
   return 0;
}

• OUTPUT:

Number of page hits are: 8
Number of page faults: 10

• Below are the screenshot attached for the code and output for better clarity and understanding.

CODE

OUTPUT

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.