HomeworkPageReplacement < CS385

CS385 Web>WebLeftBar>LectureRecordings>Syllabus>Homeworks>HomeworkPageReplacement (2016-09-27, Main.jakob) (raw view)EditAttach
---++ 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

<verbatim>
$ page_replacement
Exiting process. System free pages is 1, replacement count is 34040
</verbatim>

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

<verbatim>
$ page_replacement
Exiting process. System free pages is 1, replacement count is 2807
</verbatim>

_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._
Topic revision: r2 - 2016-09-27 - 03:51:33 - Main.jakob
CS385.HomeworkPageReplacement moved from CS385.Homework5 on 2016-09-27 - 03:51 by Main.jakob -
CS385
WISEST
Helping Women Faculty Advance
Funded by NSF