Design and Coding

Although the VM system we've provided is a huge advance on the previous one, there are some issues we should address.

• Page replacement is currently a simple FIFO algorithm.
• vm_object_setsize is not implemented, which means sbrk barely works.

In this assignment you will address these issues.

Task 1: TLB-aware Page Replacement

For relatively little effort, we can improve the basic FIFO algorithm. We just need to observe that if a page is in the TLB, it's not as good a candidate for replacement as a page that's not in the TLB.

Modify page_replace in kern/arch/mips/vm/coremap.c so that:

• There is a boolean, evict_tlb_pages which is initially set to false.
• We now skip a page if it is in the TLB and evict_tlb_pages is false.
• If we cycle through all pages in the coremap and find no candidates, we set evict_tlb_pages to true and continue cycling.

This will give us a simple TLB-aware page replacement algorithm.

Test your code! (Using the VM-CLOCK-RTLB configuration you built in the clone and build section.) Use the maze program to test your code. It's a memory-intensive program that exercises the VM system.

Task 2: Random Page Replacement

Above the code you've been working on for Task 1, there is an alternative version of page_replace that is compiled when OPTOPT_RANDPAGE is set. To set this option, use the VM-RAND-RTLB configuration (but following the same steps for setup as you used in the clone and build section).

This version should implement a simple random page replacement algorithm.

Note that you can call random() to get a random number.

Task 3: Implement vm_object_setsize

In the current system, sbrk seems to work, but only because of a hack in addrspace.c that hardwires a 2 MB heap. This is not a good solution, since it's more space than some programs need and less than some others might want.

You will need to implement vm_object_setsize, which is currently only a minimal stub. This function changes the size of a VM object by modifying its lpage array. This is the core functionality needed for:

• Growing the heap when sbrk is called with a positive increment
• Shrinking the heap when sbrk is called with a negative increment

Current Limitations

The provided implementation is a stub that:

• Returns success if new size <= current size
• Returns ENOMEM if trying to grow
• Doesn't actually modify the object

Key Requirements for Implementation

1. Handle Both Growth and Shrinkage
   • When growing: allocate new zero-filled pages
   • When shrinking: clean up existing pages
2. Manage Swap Space
   • Reserve space for new pages
   • Release space for removed pages
   • Use swap_reserve() and swap_unreserve()
3. Handle Memory Cleanup
   • Clean up pages properly when shrinking (you can use vm_object_zap as a reference)
4. Maintain TLB Consistency
   • Clear TLB entries for removed pages
   • Use mmu_unmap() when removing pages

More guidance can be found in the help page for VM objects.

Once you think you have a working implementation, look in addrspace.c for the code for as_sbrk. There is currently a hack at the top of the function that allocates a fixed 512 pages for the heap. You should remove this hack, allocating zero pages instead, allowing the later code to call vm_object_setsize to allocate the pages as needed.

The test program malloctest will exercise this code, but don't bother with the “whole memory” tests, as they take ages and aren't very informative.

There is also another test program, sbrktest that offers a variety of tests for sbrk. You can run it with sbrktest and experiment with the options from the menu. Tests 4, 11, 14, 16 and 19 are probably the most interesting.

Task 4: Implement the Clock Algorithm with Page Aging

In this part, you will move beyond the code you wrote in Task 1 and implement a more sophisticated page replacement algorithm, the Clock Algorithm with Page Aging.

You are actually free to implement any variant of the clock algorithm, but we recommend the aging variant as it is relatively simple and only needs one clock hand.

In this algorithm, pages have an age that increases on each clock pass until it hits a maximum value after which the page is evicted. Pages that are in use have an age of 0. We recommend a range of 0..3 for page ages, although you're free to experiment with other values.

You'll have to work out where to store the age information and how to update it.

Testing

The maze program is one way to test your page replacement algorithms. It's a memory-intensive program that exercises the VM system. You can run it with maze -s 271828 800 in and see how it performs with different page replacement algorithms.

(When logged in, completion status appears here.)

Previous Page Go to Parent Page