CMPSC 473 project to create a virtual memory manager. In this project, you will learn about virtual/physical memory and signals. This project requires you to implement a virtual memory manager which performs paging.
You will manage virtual memory on limited physical memory by implementing an access control mechanism and two page replacement policies. The virtual address space (size) and the number of physical pages is given to you via the mm_init() function. Based on the input file, the program will access (read/write) the virtual address space. When accesses are made, (i) you need to figure out whether they the corresponding memory is in physical memory, (ii) if it is, allow the access to go through, (iii) else, allocate a frame for this virtual page in physical memory (and consequently evict some other page as per the page replacement policy if the physical memory is full). You need to fault the access if the page is not in physical memory and handle the page faults properly. You will log your actions using the API explained below.
This machine is a single CPU system. Only one thread will read/write to the virtual memory.
If the physical frames are full, you need to evict and replace a physical frame. As discussed in class, there are multiple ways to do this. In this project, you will implement two replacement policies, explained below.
FIFO (First-In-First-Out) Replacement:
- Evict the oldest virtual page (among the currently resident pages in physical memory) brought in to the physical memory. You will have to protect the pages that are NOT in physical memory to catch accesses to these page and record page faults.
Third Chance Replacement:
- Maintain a circular linked list, with the head pointer pointing to the next potential candidate page for eviction (as discussed in class)
- Maintain a reference bit and a modified bit for each page in physical memory
- When looking for the next candidate page for eviction, if by any chance, the page pointed by the head pointer has its reference bit on (=1), the head pointer resets this bit (=0), and moves to the next element in the circular list and retries. When the head finds a candidate with a zero reference bit, it becomes a candidate for replacement as per the second chance page replacement algorithm.
- However, in our third chance algorithm, you will need to give such a page a third chance if it has been modified (modified bit=1) since we assume pages requiring write-back will incur higher overheads for replacement.
- Example: A physical page under the clock head could be in one of the following 3 states: (a) R=0, M=0; (b) R=1, M=0; or (c) R=1, M=1
- In case (a), the page can be immediately evicted.
- In case (b), you should give it a second chance, i.e. reset the R bit, and if the next time the clock head comes to that page its bits indicate state (a), then replace it.
- In case (c), you should give it a third chance, i.e. reset the R bit in the 1st pass, and even in the 2nd pass that the head comes to that page, you should skip it. Caution! You may be tempted to reset the M bit. However, if you do that, note that you will not know whether this page needs to be written back to disk (write_back parameter) later on at the time of replacement. Only the third time, should it be replaced (and written back). However, note it is possible that between the 2nd pass and the 3rd pass, the R bit could again change to 1 in which case it will again get skipped in the 3rd and 4th pass and would get evicted only in the 5th pass (as long as there is no further reference before then).
- You cannot use additional libraries.
- You cannot modify main.c and Makefile file.
- The page size will be the page size of the machine/operating system, which is 4096 bytes (check main.c file to learn how it is obtained).
- You should minimize the number of SIGSEGVs raised/handled inside your memory manager. Therefore, you can NOT simply set mprotect(..., PROT_NONE) for every virtual page and raise a SIGSEGV every access, which will execute your signal handler on every access. Instead, set the correct mprotect() of the pages so the SIGSEGVs are minimized for the page replacement algorithm.
- Write a brief report (pdf of around 2 pages) explaining the design of your memory allocator, any implementation choices/restrictions, any functions not implemented, things learned, distribution of the workload within the team, etc. Commit and push the report with the code into your repo before the deadline.