Assignment #3
TLB and Virtual Memory

First, you will use a software-managed translation lookaside buffer (TLB) as a cache for page tables to provide the illusion of fast access to virtual page translation over a large address space.  Page tables were used in assignment 2 to simplify memory allocation and to isolate failures from one address space from affecting other programs. For this assignment, the hardware knows nothing about page tables. Instead it only deals with a software-loaded cache of page table entries, called the TLB. On almost all modern processor architectures, a TLB is used to speed address translation. 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 virtual page to physical page is already known. If so (a TLB hit), the translation can be done quickly. But if the mapping is not in the TLB (a TLB miss), page tables and/or segment tables are used to determine the correct translation. On several architectures, including Nachos, the DEC MIPS and the HP Snakes, a TLB miss simply causes a trap to the OS kernel, which does the translation, loads the mapping into the the TLB and re-starts the program. This allows the OS kernel to choose whatever combination of page table, segment table, inverted page table, etc., it needs to do the translation. On systems without software-managed TLB's, the hardware does the same thing as the software, but in this case, the hardware must specify the exact format for page and segment tables. Thus, software managed TLB's are more flexible, at a cost of being somewhat slower for handling TLB misses. If TLB misses are very infrequent, the performance impact of software managed TLB's can be minimal.

Second, you will need to use memory as a cache for disk, to provide the abstraction of an (almost) unlimited virtual memory size, with performance close to that provided by physical memory. For this assignment, page translation allows us the flexibility to get pages from disk as they are needed. Each entry in the TLB has a valid bit: if the valid bit is set, the virtual page is in memory. If the valid bit is clear or if the virtual page is not found in the TLB, software translation is needed to tell whether the the page is in memory (with the TLB to be loaded with the translation), or the page must be brought in from disk. In addition, the hardware sets the use bit in the TLB entry whenever a page is referenced and the dirty bit whenever the page is modified.

When a program references a page that is not in the TLB, the hardware generates a TLB exception, trapping to the kernel. The operating system kernel then checks its own page table. If the page is not in memory, it reads the page in from disk, sets the page table entry to point to the new page, and then resumes 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.

As with any caching system, performance depends on the policy used to decide which things are kept in memory and which are only 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 pages in memory that are soon to be referenced. Another consideration is that if the replaced page has been modified, the page must be first saved to disk before the needed page can be brought in; many virtual memory systems (such as UNIX) avoid this extra overhead by writing modified pages to disk in advance, so that any subsequent page faults can be completed more quickly.

It is important to note that this assignment is an open ended design problem.  Your instructor will expect you to come up with a design that makes sense in a real system, and to defend your choices in the design presentation.  For example, you will have the freedom to choose how to do software 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 presentation 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.  Note that the default loading of memory packs all segments one after the other.  For some virtual memory schemes this may not be satisfactory.  You can change the packing by modifying the script file in the test directory.  This file defines how the GNU ld program loads program and data segments into the final noff file that is loaded by Nachos. 

You have no new virtual memory code for this assignment (the only change is that you need to compile with the -DVM -DUSE_TLB flags); you can continue to use the "stub" version of the file system.

1. Implement software-management of the TLB, with software translation via an inverted page table. For this, you will need to implement some kind of software page translation for handling TLB misses.  Note that with the compile time flag -DUSE_TLB, the hardware no longer deals with page tables; instead, the hardware traps to the OS on a TLB miss. This provides the flexibility to implement inverted page tables without changing anything about the hardware. You will also need to do something about making sure the TLB state is set up properly on a context switch. Most systems simply invalidate all the TLB entries on a context switch; the entries get re-loaded as the pages are referenced.  For item 2, your page translation scheme should keep track of the dirty and use flags for each page set by hardware in the TLB entry.
   
2. Implement 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 file system as backing store--this way, when you implement the file system in assignment 4, you will be able to use the virtual memory system as a test case.  In order to find unreferenced pages to throw out on page faults, you will need to keep track of all of the pages in the system that are currently in use. (Hint: Traditional UNIX uses something called a "core map" that maps physical page numbers to the virtual pages that are stored there.)
   
3. Demonstrate the value of your paging algorithm.  Cache misses (TLB misses and page faults) can be divided into three categories:
   
• Compulsory (cold) misses are those due to the first reference to a cached item; no matter what, you have to pull each referenced page off disk and put it into memory and into the TLB.
  
• Capacity misses are those due to the size of the cache; if the working set of the program is larger than main memory or the number of TLB entries, the program will incur misses.  Capacity misses are those that would not occur in an infinite sized cache.
  
• Conflict misses are those due to the replacement policy of the cache.  These would not occur if the cache used an optimal replacement policy, for the same program running on the same size cache.
  
Instrument your implementation to keep track of these misses and when a program terminates display the number of misses associated with that application.  Misses are associated with the address space so misses from all threads in a multi-threaded program will accumulate together.  The result should be displayed when the last thread terminates.

Controlling the placement of segments in memory

The penultimate stage in building an executable program is to link the different types of regions (code, data, heap) together and then stack them up into a reloceatable load module.  The final step is assigning each region a specific (virtual) memory address at load/execute time.  The load module may specify where in virtual memory different regions should be located.  It might also require that a region start on, for example, a page boundary.

These details of the link process are controlled by the script file contained in the test directory.  The script file provided to you will start locating regions at address 0 and pack them one right after another.  This may or may not be satisfactory for your particular virtual memory arrangement.  For instance, if you want to protect against writes to the code region.  These type of page faults are at the resolution of a page unit.  For complete protection of all the code segments you would have to ensure that the last code page is not shared by the first piece of the data memory region.  Writes to the data memory should be allowed, whereas writes to code should be faulted.  If you have a mixed page you could not do this.  For some virtual memory organizations you need to scatter pages widely through the virtual memory space.  This again is something that would be controlled at link time via information in the script file.

You can find details of the syntax for the script file in the manual for GNU ld that you use for linking of your test programs.

Submitting your code

For the code submission you must provide:

• Current copies of Makefile, C++ source and include from the vm, threads, and userprog directories.
• Makefile.common and Makefile.dep from the nachos directory
• TESTCASES from the vm directory
• From the test directory
  • Makefile
  • C source files for applicable test files
  • script

These should be tar'ed into a single file that is submitted.   The tar file should maintain the directory structure.  The top-level make target vmtar should do what is needed to create the tar file.

From the team account make your submission using the following command:

submit 544-grd vm vmsubmit.tar

Submit paper copies of the final design documentation to your instructor on the day that the code submission is due.  Refer to the general assignment page for information on the required design documentation.  For this virtual memory assignment the documentation should include a description of your virtual memory architecture and the page and TLB replacement policies you selected.