This project is a simulation program of virtual memory replacement algorithms written in C++. The algorithms are First in First Out (FIFO), Least Recently Used (LRU), and Optimal page replacement (OPT). This program runs simulations of each algorithm with a input file and reports on the their performance. These algorithms are run in comparison with each other and also with different frame sizes. The program is run 4 times with 4 different page sizes (128, 256, 512, and 1024). The main interest is in how many page faults are generated by each algorithm with each page size.
This program will run in a Unix CLI environment.
Download the project files, navigate to their root folder and unzip. The program requires 4 arguments including the program name
In the shell:
prompt> make
prompt> ./memsim <number of frames> <input file> <output file>
The shell script with test cases can be run using the command:
prompt> ./test.sh
The number of frames will dictate how many pages can be held in "memory" at a time. Memory is represented by a queue which is limited by this number.
The input file must be in .txt format and be integers delineated by new lines. Each integer is a page, with each unique integer representing a unique page. These are loaded into a queue. The queue has been made from a linked list.
This is the name of a .txt which the program can print the same output seen in the shell.
The output of the program will be in the form of this table:
============================================================================ Page Replacement Algorithm Simulation (frame size = 128)
Page fault rates
FIFO 9653 0.965 0.966 0.966 0.966 0.965 LRU 9651 0.966 0.966 0.965 0.966 0.965 Optimal 7773 0.826 0.795 0.785 0.782 0.777
It shows the frame size, each algorithm, the total page faults for each, and the page fault rate for the pages executed at multiples of 2000.
The FIFO algorithm is the simplest virtual memory algorithm. Its behavior is exactly like that of a FIFO queue when it comes to replacement.
When a page is referenced, it checks if that page is already in memory. If it is then it moves on to the next page in the queue.
If a page is not in memory, then it checks if there are any free frames. If so, it is added to memory. This is counted as a page fault.
If a page is not in memory and there are no free frames, then FIFO is put to work. The oldest page in memory is removed and then the new page is added. The oldest page is found at the head of the queue. This is counted as a page fault.
The LRU algorithm improves slightly upon FIFO by removing the page in memory which was used the farthest back in time. This is based on the idea that recent behavior may be a good predictor of future behavior.
When a page is referenced, it checks if that page is in memory. If it is, then it is moved to the tail of the queue. Because the frame queue is dequeued at the head, adding a recently used page to the tail creates a sort of priority queue by use times.
If a page is not in memory and there is a free frame, it is added to the tail. This is counted as a page fault.
If a page is not in memory and there are no free frames, the head is dequeued and the new page is enqueued at the tail. Also, a page fault.
This algorithm is only possible in a hypothetical environment such as this simulation. Future page references are used to tell the algorithm which pages to remove from memory. The page which is in memory but either used farthest in the future or not again is removed from memory.
When a page is referenced, it will check if it is in memory. If so it will move to the next page.
If the page is not in memory and there is a free frame, it is added to the tail. This is another page fault.
If a page is not in memory and there are no free frames, OPT iterates through each page in memory and through all future page references to assign each page in memory a priority number. The priority number is the soonest that page is referenced from the current page. If it is not referenced again, it receives a priority of -1. The first page to receive a priority of -1 is chosen as the victim. If there are no pages with a priority of -1, then the highest integer priority number is the victim. The page fault counter is incremented.
The files included are : main.cpp - Driver function with printing helper functions. Queue.h - Structs to build the nodes, queue and their helper functions PageReplace.h - All three page replacement algorithms output.txt pg-reference.txt - list of 10,000 pages makefile README.md test.sh - shell script to run 4 different page sizes