In this project, you will design and implement a simulated and simplified virtual memory management system and a number of page replacement algorithms in C/C++. This project does not use MIPS or SPIM, so it is completely independent of your other homework/exam assignments.

Since this is a simulation, we will use an integer C array for your physical memory as in Fig 3-9 in your textbook. As expected, your virtual memory may be much larger as shown in the same figure. You will keep your data that does not fit in your physical memory on a disk file.

Your simplified system will do simple integer array sorting with 2 different sorting algorithms (Bubble sort, quick sort) and 2 different search algorithms (linear search and binary search). The main steps of your program will be as follows

1. Fill the entire virtual memory with random integers using C/C++ function rand. Before you start filling, call srand(1000) to use the same random numbers for all runs of your program.
2. Create 2 C/C++ threads, one for each sorting algorithm. Each thread will sort half of the virtual memory in increasing order. Each thread will work on a different part of the virtual array.
3. When both of them done sorting, another thread will merge the results of both.
4. Create 2 C/C++ threads for the two search algorithms. These threads will wait until the all the sorting is done and they will make search operations on the main sorted array. Search 5 numbers 2 of which are not in the array.

The above steps will access your virtual integer memory using only the following C/C++ functions

void set(unsigned int index, int value, char * tName); int get(unsigned int index, char * tName);

where index is the virtual address of the integer, value is the value of the integer to put at that index, tName is the String that defines the thread (fill, quick, bubble, merge, linear, binary, etc.) The above functions will be implemented by you to get/set the desired data.

If the data is available in the physical memory, it is handled immediately. If the data is not available, then the page replacement algorithm has to be executed. The page replacement statistics can be easily calculated in these functions. Part 1

Design a page table structure that makes it possible to implement Second-Chance (SC), Least-Recently-Used (LRU), Working set clock (WSClock) algorithms. Note that since we are simulating the hardware, we can add any features as we like to the page table including updating the table at every array reference for LRU.

In your project report, draw figures and explain each field of the page table entries like Fig 3-11. Your report should include references to your implementation code (line numbers, C files, etc.) in your report.

Part 2

Write a C/C++ program that follows above steps. Your program will be named sortArrays and it will have the following command line structure

sortArrays frameSize numPhysical numVirtual pageReplacement tableType pageTablePrintInt diskFileName.dat

frameSize is the size of the page frames, numPhysical is the total number of page frames in the physical memory,

numVirtual is the total number of frames in the virtual address space, pageReplacement is the page replacement algorithm (NRU, FIFO, SC, LRU, WSClock), tableType is regular or inverted page table, pageTablePrintInt is the interval of memory accesses after which the page table is printed on screen, diskFileName.dat is the name of the file that keeps the out of memory frames. For example,

sortArrays 12 5 10 LRU inverted 10000 diskFileName.dat

defines a frame size of 2¹² (4096) integers, 2⁵ (32) physical frames, 2¹⁰ (1024) virtual frames, uses LRU as page replacement algorithm, inverted page table, and diskFileName.dat as the disk file name. In other words, this system has a physical memory that can hold 4096*32=131.072 integers and has a virtual memory that can hold 4096*1024= 4.194.304 integers. This command prints the page table on the screen at every 10000 memory accesses.

At the end of the program run, your statistics will include the following for each thread of the program

• Number of reads
• Number of writes
• Number of page misses
• Number of page replacements
• Number of disk page writes
• Number of disk page reads
• Estimated working set function w for each thread as a table

In this part, you will implement all necessary functions including get/set, page replacement, and all program phases. Note that you will use the virtual memory only for array storage. For other temporary sorting data (such as indexes), you will use C variables.

Write your report for this part that discusses how you implemented the get/set methods, your page replacement algorithms, and allocation policy issues. Do not forget to include a discussion about your backing store (Section 3.6.5 of the textbook) Part 3

For this part, physical memory can hold 16K integers and the virtual memory can hold 128K integers. Include a detailed discussion about each of these tasks in your report and list all the data for the graphs in your report. You may use tools like MS Excel to draw the graphs.

• Write a program that changes the page frame size in a loop for the given system to find the optimal page size for each sorting algorithm. The best frame size is the one that causes the smallest number of page replacements.
• (Bonus) Write another program that finds the best page replacement algorithm for each sort method. You should run many different configurations to make a decision. Notes

1. Always be careful about the errors, such as inconsistent memory configurations 2. Run experiments that tests end cases such as same size virtual and physical memory 3. Do not use any code from any other source even a single line!

General Homework Guidelines

1. No cheating, No copying, No peaking to other people homework
2. Follow the instructions very carefully.

3. Send required files only. Do not share your whole file system with us.
4. If you fail to implement one of the requirements, leave it be. Do not send an empty file
5. Respect the file names! Our HW grading is case-sensitive.
6. Failing to comply any of the warnings above will result in getting a 0 for your current homework.

Homework Instructions

1. Download and Install Vmware Player from Official site.
2. Download and install our virtual machine from https://drive.google.com/open?

id=1YppX3lNkyTsHV_lvA4w9TomNCUkpLeEg