Programming assignment #5 - Virtual Memory

Due by 11:59pm, Wednesday, April 11.

The managing TA for this assignment is Daniel Mullowney. All email inquiries about this assignment should be addressed to the TA and the instructor.

This is a group assignment. You should form a group of two (or three under rare circumstances) to complete this assignment. Remember that you can NOT form the same group for all four Nachos assignments and now it might be the good time to switch groups. In this assignment, you will build your Nachos executable in the vm/ subdirectory. This assignment contains three parts: (1) page faults and demand paging; (2) page replacement; and (3) testing your VM system.

Part I: Page Faults and Demand Paging

The operating system kernel works together with the machine's memory management unit (MMU) to support virtual memory. Coordination between the hardware and software centers on the page table structure for each process. To implement virtual memory, you will extend your kernel's handling of the page tables to use three special bits in each page table entry (PTE):

The first task is to extend your kernel to implement demand paging using page faults to dynamically load process virtual pages on demand. In this phase, continue to preallocate a page frame for each virtual page of each newly created process at Exec time. As before, return an error from the Exec system call if there are not enough free page frames to hold the new process address space. Here is a summary of changes for demand paging:

Part II: Page Replacement

Implement page replacement, enabling your kernel to evict any virtual page from memory in order to free up a physical page frame to satisfy a page fault. Demand paging and page replacement together allow your kernel to "overbook" memory by executing more processes than can fit in machine memory at any one time, using page faults to "juggle" the available physical page frames among the larger number of process virtual pages. If it is implemented correctly, virtual memory is undetectable to user programs unless they monitor their own performance.

For this assignment, your kernel delays allocation of physical page frames until a process actually references a virtual page that is not already loaded in memory.

In this way, your operating system will use main memory as a cache over a slower and cheaper backing store. As with any caching system performance depends largely on the policy used to decide which pages are kept in memory and which to evict. Choose a page replacement policy in your VM system. Use FIFO or random replacement if you are short on time. Implement a LRU-approximation policy will earn you more points.

Warning: The simulated MIPS machine provides enough functionality to implement a fully functional virtual memory system. Do not modify the "hardware". In particular, the simulator procedure Machine::Translate is off limits.

Part III: Testing Your VM System

Devising useful test programs is crucial in this lab. Give thought to how you plan to debug and demo your kernel. Your initial tests might use only a single user so that you can trace what is going on in a simpler environment, but conduct further tests to challenge your kernel. One could devise test cases for various scenarios, such as (1) the whole program is, in fact, referenced during the lifetime of the program; (2) only a small subset of the pages are referenced. Accessing an array selectively (e.g. all rows, some rows) can give different page reference behavior. We don't particularly care if the test programs do anything useful (like multiplying matrices), but they should generate memory reference patterns of interest.

Consider what tracing information might be useful for debugging and showing off what your kernel can do. You might print information about pagein and pageout events, which processes are affected (whose pages are victimized) or responsible (who is the faulting process) for each event, and how much of the virtual address space is actually loaded at any given time. It is useful to see both virtual and physical addresses. It may also be useful to print the name of the executable file that each process is running, as a way to identify the process.

A useful test case for virtual memory is available in test/matmult.c. This program exercises the virtual memory system by multiplying two matrices. You may want to adjust the size of main memory in the Nachos machine emulation to stress your system for debugging (this counts as "reconfiguring" rather than "modifying"the hardware). This can be done by modifying the constant NumPhysPages (defined in machine/machine.h). Further, you might want to devise your own test cases - they can be simpler patterns of access to a large array that might let you test and debug more effectively.

Your test programs should also demonstrate the page replacement policy and correct handling of dirty pages (e.g., allocating backing storage and preserving the correct contents for each page on backing store). The test cases can generate different kinds of locality (good and bad) to see how the paging system reacts. Can you get the system to thrash, for example? Have you built in the kinds of monitoring and debugging that lets you see if it is thrashing? Try reducing the amount of physical memory to ensure more page replacement activity.

Administrative policies

Turn-in:
You are asked to electronically turn in a copy of the complete Nachos source tree. Include the test user programs you created for testing. Do not turn in any executables, object files, or things like that. Add enough comments in your code to make your changes easy to understand. Attach a README file describing the files you changed/added and anything else special you want us to know. The README file should be in plain text format. The README file also needs to provide descriptions for all test programs you created.

Grading guideline:
Below is a tentative grading guideline. Note that we will actually read your code. Your turn-in will be graded not only on its correctness, but also on the completeness and clarity of your comments.

Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.