Question

Write Algoritm , code and output.

In Operating Systems ,

. Implement a program for page replacement using the following

a.FIFO

b.LRU

c.OPTIMAL

Answer 1

a) Algorithm =>

1- Start traversing the pages.
 i) If set holds less pages than capacity.
   a) Insert page into the set one by one until 
      the size  of set reaches capacity or all
      page requests are processed.
   b) Simultaneously maintain the pages in the
      queue to perform FIFO.
   c) Increment page fault
 ii) Else 
   If current page is present in set, do nothing.
   Else 
     a) Remove the first page from the queue
        as it was the first to be entered in
        the memory
     b) Replace the first page in the queue with 
        the current page in the string.
     c) Store current page in the queue.
     d) Increment page faults.

2. Return page faults.

Code =>

#include<bits/stdc++.h> 
using namespace std; 
  
// Function to find page faults using FIFO 
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 
    unordered_set<int> s; 
  
    // To store the pages in FIFO manner 
    queue<int> indexes; 
  
    // 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.find(pages[i])==s.end()) 
            { 
                // Insert the current page into the set 
                s.insert(pages[i]); 
  
                // increment page fault 
                page_faults++; 
  
                // Push the current page into the queue 
                indexes.push(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.find(pages[i]) == s.end()) 
            { 
                // Store the first page in the  
                // queue to be used to find and 
                // erase the page from the set 
                int val = indexes.front(); 
                  
                // Pop the first page from the queue 
                indexes.pop(); 
  
                // Remove the indexes page from the set 
                s.erase(val); 
  
                // insert the current page in the set 
                s.insert(pages[i]); 
  
                // push the current page into 
                // the queue 
                indexes.push(pages[i]); 
  
                // Increment page faults 
                page_faults++; 
            } 
        } 
    } 
  
    return page_faults; 
} 
  
// Driver code 
int main() 
{ 
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 
                   2, 3, 0, 3, 2}; 
    int n = sizeof(pages)/sizeof(pages[0]); 
    int capacity = 4; 
    cout << pageFaults(pages, n, capacity); 
    return 0; 
} 

Output => 7

b) LRU

Algorithm =>

Let capacity be the number of pages that
memory can hold.  Let set be the current
set of pages in memory.

1- Start traversing the pages.
 i) If set holds less pages than capacity.
   a) Insert page into the set one by one until 
      the size  of set reaches capacity or all
      page requests are processed.
   b) Simultaneously maintain the recent occurred
      index of each page in a map called indexes.
   c) Increment page fault
 ii) Else 
   If current page is present in set, do nothing.
   Else 
     a) Find the page in the set that was least 
     recently used. We find it using index array.
     We basically need to replace the page with
     minimum index.
     b) Replace the found page with current page.
     c) Increment page faults.
     d) Update index of current page.

2. Return page faults.

Code=>

#include<bits/stdc++.h> 
using namespace std; 
  
// Function to find page faults using indexes 
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 
    unordered_set<int> s; 
  
    // To store least recently used indexes 
    // of pages. 
    unordered_map<int, int> indexes; 
  
    // 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.find(pages[i])==s.end()) 
            { 
                s.insert(pages[i]); 
  
                // increment page fault 
                page_faults++; 
            } 
  
            // Store the recently used index of 
            // each page 
            indexes[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.find(pages[i]) == s.end()) 
            { 
                // Find the least recently used pages 
                // that is present in the set 
                int lru = INT_MAX, val; 
                for (auto it=s.begin(); it!=s.end(); it++) 
                { 
                    if (indexes[*it] < lru) 
                    { 
                        lru = indexes[*it]; 
                        val = *it; 
                    } 
                } 
  
                // Remove the indexes page 
                s.erase(val); 
  
                // insert the current page 
                s.insert(pages[i]); 
  
                // Increment page faults 
                page_faults++; 
            } 
  
            // Update the current page index 
            indexes[pages[i]] = i; 
        } 
    } 
  
    return page_faults; 
} 
  
// Driver code 
int main() 
{ 
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2}; 
    int n = sizeof(pages)/sizeof(pages[0]); 
    int capacity = 4; 
    cout << pageFaults(pages, n, capacity); 
    return 0; 
} 

Output => 6

c) Optimal

Algorithm=>

1. If referred page is already present, increment hit count.
2. If not present, find if a page that is never referenced in future. If such a page exists, replace this page with new page. If no such page exists, find a page that is referenced farthest in future. Replace this page with new page.

Code=>

#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; 
} 

Output =>

No. of hits = 7
No. of misses = 6