In this assignment, you will implement a page table and analyze different page replacement algorithms, assuming a single running process and a fixed$-$size physical memory.

pagetable.h and $.$cpp: It defines a "PageTable" class, which is just an array of Page Entries. Each page entry has a frame number, valid bit and dirty bit $($not used in this assignment$).$ Remember the virtual page number is the index to the array. You need to complete the implementation of the PageTable in the pagetable.cpp file.

replacement.h and $.$cpp: It defines a "Replacement" class, the base class of the classes that implement specific replacement algorithms. You will need to add additional member variables to keep track of the statistics, such as number$-$of$-$page$-$faults and number$-$of$-$page$-$replacements, etc. Then complete the replacement.cpp file, especially the access$\_($p$)$age function. The access$\_($p$)$age function simulates the access by a single page number. If the page is found to be in memory, i$.$e$.$ the corresponding page entry is valid, it calls the touch$\_($p$)$age function; if the page isn't in memory but there are still free frames available, it would call the load$\_($p$)$age function; if the page isn't in memory and there isn't any free frame, it then calls the replace$\_($p$)$age function. The touch$\_($p$)$age$,$ load$\_($p$)$age and replace$\_($p$)$age are virtual functions that can be overridden for different replacement algorithms in the subclasses.

fifo$\_($r$)$eplacement$.$h and $.$cpp: FIFOReplacement is a subclass of the Replacement, and implements the FIFO page replacement algorithm. You will need to complete its constructor and destructor, and override the functions load$\_($p$)$age and replace$\_($p$)$age$.$

lifo$\_($r$)$eplacement$.$h and $.$cpp: LIFOReplacement is a subclass of the Replacement, and implements the LIFO$($Last in first out$)$ page replacement algorithm. It replaces a page that was last loaded into the memory. It isn't a good replacement algorithm and Let's see how bad it is$.$ You will need to complete its constructor and destructor, and override the functions load$\_($p$)$age and replace$\_($p$)$age$.$

lru$\_($r$)$eplacement$.$h and $.$cpp: LRUReplacement is a subclass of the Replacement, and implements the LRU page replacement algorithm. You will need to complete its constructor and destructor, and override the functions touch$\_($p$)$age$,$ load$\_($p$)$age and replace$\_($p$)$age$.$

main.cpp: The driver program tests the implementation of the page table and replacement algorithms. Test $1$ using a "small$\_($r$)$efs$.$txt$"$ file has been written. You need to complete test $2$ for the three replacement algorithms using a "large$\_($r$)$efs$.$txt$"$ file. See below for more info about the tests. The results of tests should match example outputs in the "example$\_($o$)$ut$.$txt$".$

Your program should support at least three page$-$replacement policies: FIFO, LIFO, and LRU. Assume that when it starts, the physical memory is empty, i$.$e$.$ all page table entries are invalid. As they are brought in$,$ the program should ensure that the total number of pages in memory should never exceed the physical memory size.

Your program should keep track of pages in the memory and free frames. Therefore, you need to maintain a page$-$table data structure, which can be easily implemented as an array of page entries. The size of the array equals the number of pages in the logical memory. The page entry data structure may contain the mapped frame number of the page, valid bit, and dirty bit, etc. For each memory reference, calculate its page number and check whether this page is in the main memory by looking up the page table. If this page is not in the main memory, a page fault is generated, the missing page is loaded into the main memory, and the page table is updated. However, if the main memory is full, i$.$e$.,$ no more free frames, a victim page must be selected and evicted according to a page replacement algorithm. Your program compares different page replacement algorithms in terms of the total number of page faults. Notice you will need to keep track of additional information in the implementations, such as the last page access time for the LRU $($least recently used$)$ algorithm.

The program should accept the page size and physical memory size $($# of address bits$)$ as command$-$line arguments. The page size must be a power of $2$ between $256(2^(8))$ and $8192(2^(13))$ bytes inclusively. The physical memory size is also a power of $2$ between $4(2^(22))$ and $64(2^(26))$ MB$.$ Using the provided Makefile, you just type "make" to build the executable "prog$5".$ Then run "prog$5"$ with command$-$line arguments, for example

$(.)/($p$)$rog$5102432$

simulates a system with page size $=1024$ bytes and $32$ MB physical memory. You should thoroughly test your program with multiple configurations of different page sizes $(256-8192$ bytes$)$ and physical memory sizes $($e$.$g$.4$ MB$,16$ MB$,32$ MB$,64$ MB$),$ and then present and analyze the data results in the report.