Phase 3: Caching and Virtual Memory

LAST MODIFIED: 5 Apr 2001 by mdw

The third phase of Nachos is to investigate the interaction between the TLB, the virtual memory system, and the file system. We don't provide any new virtual memory code for this assignment. You will continue to use the stub file system. For this phase, you should run gmake and nachos in the proj3 directory.

To help you to organize your code better, we provide you with a new package, nachos.vm, with two new classes, VMKernel and VMProcess. VMKernel extends UserKernel, and VMProcess extends UserProcess. VMKernel and VMProcess are the only classes you should have to modify for this project phase.

This phase and the next phase of the project involve open-ended design problems. We will expect you to come up with a design that would make sense in a real system, and to defend your choices in the design review. For example, you will have some freedom to choose how to do software address translation on TLB misses, how to represent the swap partition, how to implement paging, etc. In each case, we will expect you to come to the design review armed with a defensible justification as to why your choices are reasonable. You should evaluate your design on all the available criteria: speed of handling a TLB miss, space overhead in memory, minimizing the number of page faults, simplicity, etc. There is no single "right" answer.

The first design aspect to consider is the software-managed translation lookaside buffer (TLB). Page tables were used in phase 2 to simplify memory allocation and to isolate failures from one address space from affecting other programs. For this phase, the processor knows nothing about page tables. Instead, the processor only deals with a software-managed cache of page table entries, called the TLB. Given a memory address (an instruction to fetch, or data to load or store), the processor first looks in the TLB to determine if the mapping of the virtual page to a physical page is already known. If the translation is in the TLB, the processor uses it directly. If the translation is not in the TLB (a "TLB miss"), the processor causes a trap to the OS kernel. Then it is the kernel's responsibility to load the mapping into the TLB, using page tables, segments, inverted page tables, or whatever other mechanism might be appropriate. In other words, the Nachos MIPS simulator does not have direct access to your page tables; it only knows about the TLB. It is your job to write the code that manages a TLB miss.

The second design aspect of this project is paging, which allows physical memory pages to be transferred to and from disk to provide the illusion of an (almost) unlimited physical memory. A TLB miss may require a page to be brought in from disk to satisfy the translation. That is, when a TLB miss fault occurs, the kernel should check its own page table. If the page is not in memory, it should read the page in from disk, set the page table entry to point to the new page, install the page table entry, and resume the execution of the user program. Of course, the kernel must first find space in memory for the incoming page, potentially writing some other page back to disk, if it has been modified.

Performance of this mechanism depends greatly on the policy used to decide which pages are kept in memory and which are stored on disk. On a page fault, the kernel must decide which page to replace; ideally, it will throw out a page that will not be referenced for a long time, keeping in memory those pages may be referenced soon. Another consideration is that if the replaced page has been modified, the page must first be saved to disk before the needed page can be brought in. (Of course, if the page has not been modified, it is not necessary to write it back to disk.)

To help you implement virtual memory, each TLB entry contains three status bits: valid, used, and dirty. If the valid bit is set, the virtual page is in memory and the translation can be used directly by the processor. If the valid bit is clear, or if the page translation is not found in the TLB, then the processor traps to the OS to perform the translation. The processor sets the used bit in the TLB entry whenever a page is referenced and sets the the dirty bit whenever the page is modified.

  1. (30%) Implement software-management of the TLB, with software translation via an inverted page table.

  2. (40%) Implement demand paging of virtual memory. For this, you will need routines to move a page from disk to memory and from memory to disk. You should use the Nachos stub file system as backing store; this will make Part 3 (see below) a lot easier.

  3. (30%) Implement lazy loading of the code and data pages from user programs. That is, rather than reading all of the code and data from a user program at startup time, set up page table entries so that when page faults occur, the pages from the executable will be read into memory on demand.