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
This assignment contains three parts: (1) page faults and demand paging;
(2) page replacement; and (3) testing your VM system.
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):
validbit in each PTE to tell the machine which virtual pages are resident in memory (a valid translation) and which are not resident (an invalid translation). If a user process references an address for which the PTE is marked invalid, then the machine raises a page fault exception and transfers control to your kernel's exception handler.
usebit (reference bit) in the PTE to pass information to the kernel about page access patterns. If a virtual page is referenced by a process, the machine sets the corresponding PTE reference bit to inform the kernel that the page is active. Once set, the reference bit remains set until the kernel clears it.
dirtybit in the PTE whenever a process executes a store (write) to the corresponding virtual page. This informs the kernel that the page is dirty; if the kernel evicts the page from memory, then it must first "clean" the page by preserving its contents on disk. Once set, the dirty bit remains set until the kernel clears it.
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:
Exectime as you did earlier,
Execshould instead initialize all the PTEs as invalid.
AddrSpaceinitialization code. Faults on different address space segments are handled in different ways. For example, a fault on a text page should read the text from the executable file, and a fault on a stack or uninitialized data frame should zero-fill the frame.
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.
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
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.
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.
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.