Paging and page replacement for xv6

In this homework, we implement another missing feature in xv6: paging, and page replacement. In xv6, when memory runs out, you're out of luck. Processes start dying, and probably the kernel too at some point.

Modern OS's, meanwhile, degrade more gracefully. When memory runs out, some pages get moved to disk (paged out) to make room for new allocations. When a process tries to access a page that has been paged out, it is moved back to RAM (paged in), potentially displacing another page. The algorithm by which a page is chosen for eviction (being paged out), is called a page replacement algorithm.

Getting started

As in previous homeworks, git fetch the latest updates from the class repository. Then git checkout hw5 -b hw5_solution to start working on your solution from the template provided.

Then, follow the below step-by-step guide to create a paging system for xv6.

evicting pages from mmap regions

The hw5 template is based on the hw4 solution, which means there is mmap() support in the kernel. There's also a temporarily added system call, sys_evict(), which is meant to take an address as argument and evict the page that includes that address. sys_evict() calls evict(), which is an unfinished function.

Implement evict() for addresses inside of mmap regions. The beauty of these regions is that they are file-backed. If you successfully evict a page, the standard page fault handling for mmap regions will read the page back into RAM when needed, making this part quite easy.

The program evict_mmap should run to completion, and the number of free pages reported on exit should be larger than the number of free pages for lazy_mmap, indicating that the pages were indeed freed up by evicting them.

write other pages to the swap space on disk

The hw5 template includes a 16 megabytes (4096 pages) of swap space in the xv6.img file, which is the first hard drive from xv6's perspective. The space comes directly after the boot sector (before the kernel), and is initialized to all zeros.

In this step, if evict() is called on a page that is not within an mmap region, write the contents of the page to the swap space. Use bread() and bwrite() to access raw disk sectors. Do not free the page in this step, start by verifying that writing to swap is working well. You can verify this by running hexdump on the image file. The program evict_swap evicts a page with recognizable contents, for this purpose.

For this to be useful in later steps, you need to also retain two things when you write to swap: (a) which virtual memory page (for this process) went where on disk? (b) which swap space pages are used, and which are available to accept page-outs (this is system-wide, not per-process)? For (a), consider using the just-cleared page table entry, just make sure to leave the "present" bit at 0.

evict() and page-in for all virtual memory pages

Now, when evict is called on a non-mmap page, make sure to kfree it after writing it to disk, to make it available for other allocations.

Then, update the page-fault handler to also support reading in pages from the swap space. The program evict_swap checks that memory actually gets freed when you evict a non-mmap page. pagein_swap tests that the paging functionality works correctly, by allocating memory, writing something familiar to it, evicting the page, then reading the page to make sure the contents are still there.

full-on page replacement

You've done all the hard work above, now there's only the question of deciding what page to replace to achieve good performance. The program page_replacement uses up all the available memory (this is artificially limited for hw5), and more. kalloc has been modified to evict() pages rather than return a null pointer when out of free pages.

If the steps above are working correctly, page_replacement will run to completion. However, you will see a large count of page replacement printed out at process exit. Implement a better page replacement method.

When running with the template victim selection, I get

$ page_replacement
Exiting process. System free pages is 1, replacement count is 34040

running with my random eviction solution, I get a much more reasonable

$ page_replacement
Exiting process. System free pages is 1, replacement count is 2807

For full points, get below 3500 replacements. For the bonus, implement an LRU-approximating method based on the "accessed" bit in the PTE's (i.e. not random or otherwise hard-coded order), and get below 2807.