Project 6: Page Replacement with the Clock Algorithm

In this project you will extend your work on Project 5 to include page replacement, so MCryptFiles can be larger than the available physical memory. The goal of this project is to for you to learn about page replacement in general, and about the Clock Algorithm in particular.

Project Notes

• The APIs for MCryptFile will not change for this project, but you may no longer assume that there are enough physical pages to accommodate all of the pages in all of the open MCryptFiles. If a page fault occurs when all of the available physical pages are in use, then the Clock Algorithm must be used to choose a page to evict from memory.

• For this project you will need to keep track of physical pages as well as virtual pages, so that you can cycle through the physical pages in order when running the Clock Algorithm. PhysMem::npages returns the total number of pages in the pool, and you can assume that all of the PPages are adjacent in virtual address space. PhysMem::pool_base returns the first PPage; you can compute PPages for other pages by adding multiples of the page size to the this value.

• The Clock Algorithm described in lecture assumes the availability of “reference” bits for each page, set in hardware. For this project, no such bits are available. However, you can use page protection to compute this information, using an approach similar to the way you tracked dirty pages in Project 5.

• You do not need to consider whether a page is dirty when deciding whether to evict it (i.e., don’t give “extra chances” to dirty pages), but you must write dirty pages back to the encrypted file before evicting them from memory.

• You should implement global replacement: all pages from all MCrypteFiles are in a single pool. Thus, a page fault on one MCryptFile could evict a page from another MCryptFile.

• Mechanisms like the one you are implementing might well be useful in realistic settings (e.g. when caching some data in memory and keeping the rest on disk, it might be valuable from a security standpoint to store information in encrypted form on disk).

Developing and Testing

To get started on this project, make a copy of your work for Project 5 by typing the following command in the parent directory of Project 5:

cp -r cs111_p5 cs111_p6

This will create a directory cs111_p6. Do your work for the project in this directory.

The directory also contains a Makefile; if you type make, it will compile your code along with a test program, creating an executable test. You can then invoke ./run_tests clock_tests, which will run a simple set of tests on your code. You can also invoke test with an argument specifying a particular test name; this will run a single test and print out its results. Invoke test with a bogus test name to print out all of the available test names.

As usual, we do not guarantee that the tests we have provided are exhaustive, so passing all of the tests is not necessarily sufficient to ensure a perfect score (CAs may discover other problems in reading through your code).

Submitting Your Work

To submit your solution, cd to the directory containing your work and invoke the command

./submit

If you discover problems or improvements after you have submitted, you may resubmit; only the latest submit will be graded.