Question

P3 – Page Replacement Algorithms
CS3310 Operating Systems

Page Replacement:

Complete the program that implements the FIFO and LRU algorithms presented in the chapter and calculates the number of page faults generated given a particular reference string. Implement the replacement algorithms such that the number of page frames can vary. Assume that demand paging is used.

Required Modifications:

• Implement LRU and FIFO algorithms
  • Add appropriate data structures and private helper methods to LRU.h and FIFO.h
  • Implement the insert() method in LRU.cpp and FIFO.cpp as well as any helper functions you specify in the header files.
• ReplacementAlgorithm.h should not be modified.
• testPR.cpp may be modified to facilitate testing and/or analysis. Comment appropriately.
  • You may want to modify the number of pages MAX_PAGE_NUMBER.
• reference_string.txt is given as an example reference string that can be opened via the command line arguments. You must create at least one more interesting and representative reference string and use one of them in your testing and analysis. If an input file is not specified, a random sequence of page numbers is generated.

Extra Credit (+30%)

• Create the OPT (optimal) replacement algorithm and compare its results with LRU & FIFO in your analysis. The implementation will have to be slightly different than the LRU & FIFO algorithm classes. If you make any changes to ReplacementAlgorithm.h or substantial changes to testPR.cpp, please be sure to document them appropriately

Project Code:

LRU.h:

#ifndef _LRU_H
#define _LRU_H

#include <iostream>
#include "ReplacementAlgorithm.h"

class LRU : public ReplacementAlgorithm {
public:
LRU(int numPageFrames);
void insert(int pageNumber) override;

private:
  
// data structure to store the int page frame list
//<data type> frameList;
};

#endif

LRU.cpp:

#include "LRU.h"

LRU::LRU(int numPageFrames) : ReplacementAlgorithm(numPageFrames) {
pageFaultCount = 0;
}

void LRU::insert(int pageNumber)
{
// Implement LRU page replacement algorithm
// Increment pageFaultCount if a page fault occurs

}

FIFO.h:

#ifndef _FIFO_H
#define _FIFO_H

#include <iostream>
#include "ReplacementAlgorithm.h"

class FIFO : public ReplacementAlgorithm {
public:
FIFO(int numPageFrames);
void insert(int pageNumber) override;

private:
// data structure to store the int page frame list
//<data type> frameList;
};

#endif

FIFO.cpp:

#include "FIFO.h"

FIFO::FIFO(int numPageFrames) : ReplacementAlgorithm(numPageFrames) {
pageFaultCount = 0;
}

void FIFO::insert(int pageNumber)
{
// Implement FIFO page replacement algorithm
// Increment pageFaultCount if a page fault occurs

}

reference_string.txt = 0 1 2 3 1 4 5 6 1 3 4 5 6 3 4 6 3 5 7 3 7 8 9 8 3 9

ReplacementAlgorithm.h:

#ifndef _REPLACEMENTALGORITHM_H
#define _REPLACEMENTALGORITHM_H

class ReplacementAlgorithm
{
public:
// numPageFrames - the number of physical page frames
ReplacementAlgorithm(int numPageFrames): pageFrameCount(numPageFrames) {};

// returns the number of page faults that occured
int getPageFaultCount() { return pageFaultCount; }

// pageNumber - the page number to be inserted
virtual void insert(int pageNumber) {};

protected:
int pageFaultCount;
int pageFrameCount;
};

testPR.cpp:
// Testing program for the page replacement algorithms.
//

#include <cstdlib>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <fstream>

#include "ReplacementAlgorithm.h"
#include "LRU.h"
#include "FIFO.h"
// #include "OPT.h"

std::vector<int> referenceString;

const int MAX_PAGE_NUMBER = 100;

// testPR <reference string size> <number of page frames> [fileName]
// The "reference string size" parameter is ignored if a filename is provided.
int main(int argc, char **argv)
{
int count;
int numPageFrames;
bool useRefFile = false;
std::string fileName = "";
std::ifstream in;

srand((unsigned int)time(0));

if (argc < 3 || argc > 4){
std::cerr << "Usage: " << argv[0]
<< " <reference string size> <number of page frames> "
<< "[reference string filename]"
<< std::endl;
exit(1);
}

count = atoi(argv[1]);
numPageFrames = atoi(argv[2]);

// input reference string from file or just randomly generate
if (argc == 4){
useRefFile = true;

//open the input file
in.open(argv[3]);
if (!in.is_open()){
std::cerr << "Error opening file " << fileName
<< ". Exiting..." << std::endl;
exit(1);
}

int n;
while (!in.eof())
{
in >> n;
if (n >= 0 && n < MAX_PAGE_NUMBER){
referenceString.push_back(n);
}
}
in.close();
}
else {
for (int i = 0; i < count; i++){
referenceString.push_back(rand() % MAX_PAGE_NUMBER);
}
}

ReplacementAlgorithm * lru = new LRU(numPageFrames);
ReplacementAlgorithm * fifo = new FIFO(numPageFrames);

for (int i : referenceString) {
lru->insert(i);
fifo->insert(i);
}

std::cout << "LRU faults = " << lru->getPageFaultCount() << std::endl;
std::cout << "FIFO faults = " << fifo->getPageFaultCount() << std::endl;
return 0;
}

#endif // !PPD_REPLACEMENTALGORITHM_H

Answer 1

//C++ implementation of above algorithm

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

}