In this lab you will extend Nachos to support virtual memory. The new functionality gives processes the illusion of a virtual memory that may be larger than the available machine memory.
Virtual memory should be implemented and debugged in two steps. First, you will implement demand paging using page faults to dynamically load process virtual pages on demand, rather than initializing page frames for each process in advance at Exec time as you did in Labs 4 and 5. Next, you will 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 would 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.
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. You used page tables in Labs 4 and 5 to allow your kernel to assign any free page frame to any process page, while preserving the illusion of a contiguous memory for the process. The indirect memory addressing through page tables also isolates each process from bugs in other processes that are running concurrently. In Lab 6, you will extend your kernel's handling of the page tables to use three special bits in each page table entry (PTE):
In the first phase, you should preallocate a page frame for each virtual page of each newly created process at Exec time, just as in Labs 4 and 5. As before, return an error from the Exec system call if there are not enough free page frames to hold the process new address space. But now, Exec should initialize all the PTEs as invalid .
When the process references an invalid page, the machine will raise a page fault exception. Modify your exception handler to catch this exception and handle it by preparing the requested page on demand. This will likely require a restructuring of your AddrSpace initialization 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 unitialized data frame should zero-fill the frame. However you initialize the frame, clear the exception by marking the PTE as valid, then restarting execution of the user program at the faulting instruction. When you return from the exception, be sure to leave the PC in a state that reexecutes the faulting instruction. If you set up the page and page table correctly, then the instruction will execute correctly and the process will continue on its way, none the wiser.
Test your demand paging implementation before moving on to page replacement. See the notes on testing below.
In the second phase, your kernel delays allocation of physical page frames until a process actually references a virtual page that is not already loaded in memory.
First, complete the gutting of your code to create an address space: remove the code to allocate page frames and preinstall virtual-physical translations when setting up the page table. Instead, merely mark all the PTEs as invalid.
Next, extend your page fault exception handler to allocate a page frame on-the-fly when a page fault occurs. If memory is full, it will be necessary to free up a frame by selecting a victim page to evict from memory. To evict a page, the kernel marks the corresponding PTE(s) invalid, then frees the page frame and/or reallocates it to another virtual page. The system must be able to recreate the victim page contents if the victim page is referenced at a later time; if the page is dirty, the system must save the page contents in backing store or swap space on local disk or out on the network. An important part of this lab is to use the Nachos file system interface to allocate and manage the backing store. You will need routines to allocate space on backing store, locate pages on backing store, push pages from memory to backing store (for pageout), and pull from backing store to memory (for pagein). Be sure to clear the dirty bit when you mark a PTE for the victim page as invalid.
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. As you know, we are not especially concerned about the performance of your Nachos implementations (simplicity and correctness are paramount), but in this case we want you to experiment with one of the page replacement policies discussed in class. Use FIFO or random replacement if you are short on time, but we will be more impressed if you implement an LRU approximation, examining and clearing the use bit in each PTE in order to gather information to drive the policy. We would like to see you implement a policy with an asynchronous paging daemon that responds to memory conditions, but we recognize that time may be short and we will not penalize you heavily if you do not. In any case, choose your policy carefully based on your group's design criteria (e.g. simplicity, performance, simplicity, correctness, fun) and be able to explain your choices.
Another important design question is the handling of dirty pages. Some rather poor kernels allow processes to fill memory with dirty pages. Consider what can happen when memory is full of dirty pages. If a page fault occurs, the kernel must find a victim frame to hold the incoming page, but every potential victim must be written to disk before its frame may be seized. Cleaning pages is an expensive operation, and it could even lead to deadlock in extreme cases, if for example a page is needed for buffering during the disk write. For these reasons, "real" operating systems retain a reserve of clean pages that can be grabbed quickly in a pinch. Maintaining such a reserve generally requires a paging daemon to aggressively clean dirty pages by pushing them to disk if the reserve begins to drain down. This makes correct management of the dirty bits more interesting. Again, implement the best scheme you can in the available time. This will make the experience (and the demos) more interesting and rewarding.
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.
Lab 6 builds directly on Labs 4 and 5, so you will mostly be working with the same set of files. A useful test case is available in test/matmult.c . This program exercises the virtual memory system by multiplying two matrices. Of course, it is cheating to increase the size of main memory in the Nachos machine emulation, although you may want to decrease this number to stress your system for debugging (this counts as "reconfiguring" rather than "modifying" the hardware). You may find it useful 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.
Devising useful test programs is crucial in all of these assignments. Give thought to how you plan to debug and demo your kernels. Initial testing with only a single user process may be a good idea so that you can trace what is going on in a simpler environment. In later testing, you want to stress things more and run multiple programs.
Lab 6 implies that pages are brought into memory only if they are actually referenced by the user program. To show this, 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.
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.
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.