P3 – Page Replacement Algorithms
CS3310 Operating Systems

Page Replacement:

Complete the program that implements the FIFO and LRU algorithmspresented in the chapter and calculates the number of page faultsgenerated given a particular reference string. Implement thereplacement algorithms such that the number of page frames canvary. Assume that demand paging is used.

Required Modifications:

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

Extra Credit (+30%)

• Create the OPT (optimal) replacement algorithm and compare itsresults with LRU & FIFO in your analysis. The implementationwill have to be slightly different than the LRU & FIFOalgorithm classes. If you make any changes toReplacementAlgorithm.h or substantial changes to testPR.cpp, pleasebe sure to document them appropriately

Project Code:

LRU.h:

#ifndef _LRU_H
#define _LRU_H

#include
#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
// 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
#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
// 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 78 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
#include
#include
#include
#include
#include

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

std::vector referenceString;

const int MAX_PAGE_NUMBER = 100;

// testPR [fileName]
// The \"reference string size\" parameter is ignored if a filenameis 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 filename]\"
<< std::endl;
exit(1);
}

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

// input reference string from file or just randomlygenerate
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 = \" <getPageFaultCount() << std::endl;
std::cout << \"FIFO faults = \" <getPageFaultCount() << std::endl;
return 0;
}

#endif // !PPD_REPLACEMENTALGORITHM_H