CSE 120 Nachos Project 3: Virtual Memory

Fall 2000

Due: December 3, 2000 at Midnight

In this lab you will extend Nachos to support demand paged virtual memory. This new functionality gives processes the illusion of a virtual memory that is 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 Project 2. 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 Project 2 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 this project, you will extend your kernel's handling of the page tables to use three special bits in each page table entry (PTE):

This project has two parts:
  1. [35 pts] Implement demand paging. In the first part, you will continue to preallocate a page frame for each virtual page of each newly created process at Exec time, just as in Project 2. 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 for this project, you need to make the following changes to AddrSpace:

    When the process references an invalid page, the machine will raise a page fault exception (if a page is marked valid, no fault is generated). Modify your exception handler to catch this exception and handle it by preparing the requested page on demand. This will 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 code page should read the corresponding code from the executable file, a fault on a data page should read the corresponding data from the executale file, and a fault on a stack frame should zero-fill the frame.

    After initializing the frame, clear the exception by marking the PTE as valid, then restart 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 (note that this is different than when handling system calls where you increment the PC). If you set up the page (by initializing it) and page table (by setting the valid bit) correctly, then the instruction will execute correctly and the process will continue on its way, none the wiser.

    Testing: Start by testing with one process running at a time. During debugging, you will probably want to print out the arguments that you are giving to ReadAt or bzero when initializing a page during a page fault to make sure that you are loading the right parts of the executable file into the virtual page. Then test with multiple processes; this should work automatically since these changes are independent of the number of processes running.

  2. [65 pts] Implement demand paged virtual memory with page replacement. In this second part, not only do you delay initializing pages, but now you delay the allocation of physical page frames until a process actually references a virtual page that is not already loaded in memory.

    If physical memory is full, it will be necessary to free up a physical frame by selecting a victim page to evict from memory. To evict a page, the kernel first marks the corresponding PTE(s) invalid, then empties and frees the page frame.

    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 clean (i.e., not dirty), then the page can be overwritten. If the page is dirty, the system must save the page contents in backing store on disk. An important part of this project 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).

    In particular, add two new counters to the Statistics class in machine/stats.h, numPageOuts and numPageIns, and update the constructor and Print methods in stats.cc to initialize and report the values of those counters (ignore the top of the file where it says to not change the file). Increment the "PageOut" counter whenever you write a page to the backing store (e.g., "clean" pages should not cause a PageOut). Increment the "PageIn" counter whenever you read a page from (1) the original executable file and (2) your backing store. Print the values of those counters on the same line as the numPageFaults counter.

    With backing store implemented, 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. For this part, use a simple algorithm to implement such as FIFO or random replacement. For extra credit, you can implement LRU or an LRU approximation (see below). In any case, choose your policy carefully based on your group's design criteria (e.g., simplicity, performance, simplicity, correctness, fun) and explain your choices in the project writeup.

    In your project writeup, create a table that reports the values of the paging counters for all of the test programs that you used to test your page replacement algorithm. If you implemented more than one replacement algorithm, report the values for all of the algorithms that you implemented. Here is an example:

    Physical memory size: 32 pages.
    Page replacement policy: Random.
    Program		PageFaults	PageOuts	PageIns
    halt		3		0		2
    matmult		112		45		74
    sort		755		624		722

    Testing: In this project, programs can use more virtual memory than physical memory, and pages are brought into memory only if they are actually referenced by the user program. To show that virtual memory works, you can run sort or matmult (which require more pages than the default 32 pages in physical memory). To show demand references, 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.

  3. (Extra Credit) [10 pts] Implement LRU or an LRU approximation for your page replacement algorithm, examining and clearing the use bit in each PTE in order to gather information to drive the policy. Make it possible to run your nachos executable with your original algorithm as well your LRU algorithm (e.g., with a new command line switch to main.cc). Using the counters and experiments with test programs, demonstrate that LRU does a better job of replacing pages than your original (FIFO or random). Extend your page fault table in your writeup to include the values for your LRU algorithm. Design a test case where LRU does a worse job.

  4. (Extra Credit) [5 pts] 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.


As with projects 1 and 2, we would like a paper write-up describing what changes you made, how well they worked, how you tested your changes, and how each group member contributed to the project. For project 3, also include a discussion of the page replacement algorithm that you used, and a description of how well that page replacement algorithm worked on your test programs (e.g., the test program name, the number of pages it requires, and the faults it generated). Please include this writeup in your userprog directory.

To turn in project 3, I want you to create a tar file of your nachos code directory and email it to me. Please be sure and compress it using gzip. Assuming you are group 57, do the following:

% cd nachos-3.4/code
% gmake clean
% tar cvf group57.tar *
% gzip group57.tar
% [mail group57.tar.gz to voelker@cs.ucsd.edu using whatever method works
best for you]
Look on the project groups page if you do not remember your group number.