Implementing Page Replacement Algorithm for LRU and Modified 2nd Chance Algorithm in C++

Page Replacement Algorithm

The goal of this homework is to implement page replacement algorithm. You are given a program that implement a version of FIFO page replacement policy. The program consists of 3 parts:

 

Class PRDS_FIFO: a class that store the data structure that is used by the page replacement algorithm. In this case this is a just a simple deque

int Page_Replacement(vector& pages, int nextpage, PRDS_FIFO* p). Implementation of the page replacement algorithm.

? pages: a vector storing the set of pages that is currently in main memory

? nextpage: the next page to be accessed (nextpage is a non-negative number, between 0 and MAXINT).

? p : a pointer to the data structure that is used for the page replacement

? 1: if no page replacement is needed

? any other number: the index in the pages vector that is to be replaced

• The main program, who generate a list of page references and execute the page replacement algorithm. For each page request, it will print a line o The first number is the page that is requested

 

o The second number is the value returned by the page replacement function.

o The rest of the numbers denote the pages in the pages vector (i.e. those who are “in memory”)

 

The code has comments that should help you understand the it.

 

Task (Base case) (90 points) You need to implement 2 page replacement algorithms:

 

Case 1: LRU You will need to define a class (PRDS_LRU) that store the data structure that will be used to implement the algorithm. It must have a constructor that take an integer as a parameter, which denotes the number of pages available in main memory. Notice that you are NOT required to use that number if you do not want to. You can define any other methods that you need. You also need to implement an function: int Page_Replacement_LRU(vector& pages, int nextpage, PRDS_LRU* p), that implement the LRU algorithm. The three parameters are the same as the three parameters in the Page_Replacement function provided in the code. You should put the code for these two parts in a file name “prog4_lru.h”.

 

Case 2: modified 2nd chance algorithm. You should implement the following modification of the 2nd chance algorithm.

• Each page in main memory has a reference number (between 0 and 3 inclusive) associated with it. When a page is read in, its reference number is initialized to 0

• Once a page is in memory, if it is reference again, its reference number is incremented by 1 (but it will never be larger than 3)

• A FIFO queue is maintained, whenever a new page is brought into memory, it is inserted at the end of the queue

• When a victim for replacement is needed, we apply the following algorithm to select it

o If the page a the front of the FIFO queue is 0, then this page is selected and removed from the queue

o Otherwise, it is moved to the back of the queue, and its reference number is decreased by 1

o Repeat until you find a victim

 

(Notice that you do NOT have to implement this algorithm as stated, as long as you achieve the same effect).

 

You will need to define a class (PRDS_2nd) that store the data structure that will be used to implement the algorithm. It must have a constructor that take an integer as a parameter, which denotes the number of pages available in main memory. Notice that you are NOT required to use that number if you do not want to. You can define any other methods that you need.

 

You also need to implement an function: int Page_Replacement_2nd(vector& pages, int nextpage, PRDS_LRU* p), that implement the LRU algorithm. The three parameters are the same as the three parameters in the Page_Replacement function provided in the code. You should put the code for these two parts in a file name “prog4_2nd.h