Project Assignment #3: Caching and Virtual Memory

The third phase of Nachos is to investigate the interaction between the TLB, the virtual memory system, and the file system. We are not providing new virtual memory code for this assignment. The only change is that you need to compile with the flag "-DVM -DUSE_TLB" flags. You can use the "stub" version of the file system. (This flag is already set for you.)

It is important for you to note that in addition to getting virtual memory working, this assignment is also meant to be an open-ended design problem. Thus, I would like to meet with each group on the 22nd, 23rd, or 24th of May to discuss your design. I 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 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, I 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 of the available criteria: speed of handling a TLB miss, space overhead in memory, minimizing the number of page faults, simplicity, etc. There is no "right" answer, but there are plenty of wrong ones. The design review is not intended for you to ask me how to implement things.

The first part to consider is the software-managed translation lookaside buffer (TLB); the TLB is a cache of translations to provide the illusion of fast access to 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 (though this is not the case in the typical CPU). Instead, it only deals with a software-loaded cache of page table entries (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 a 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 and most modern architectures designed for Unix, a TLB "miss" simply causes a trap to the OS kernel, which does the translation, loads the mapping into the TLB, and starts the program again. 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 TLBs, the hardware does the same thing as the software, but, in this case, the hardware must specify the exact format for the page and segment tables. Thus, software managed TLBs 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 TLBs 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 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.

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 those pages in memory that will soon 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.

For this assignment, you will need three data structures:

1. Some way of translating in software from virtual page frames to physical page frames. (hint: consider using a hash table -- we will provide an implementation: hash.cc hash.h list.h - I may give a better hash implementation since this one sucks.)
2. Some way of translating from physical page frames back to virtual page frames, so that when you replace a page, you can invalidate its translation.
3. Some way of finding a page on disk if it is not in memory.

1. Implement software-management of the TLB, with software translation via an inverted page table. An inverted page table is one which has one entry for each physical page, and the entry contains the virtual address and owning address space identifier. You shouldn't worry about paging the page table, or about putting the page table itself in virtual memory. Note that with the compile 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 hardware. You will also need to do something about making sure the TLB is set up properly on a context switch. Most systems simply invalidate all the TLB entries on a context switch, and the entries get reloaded as pages are referenced. Some systems associate a process id with the entries in the TLB. Performance considerations for the TLB handler include the amount of code executed and the number of memory references required.
2. Implement system calls to allow an address space to allocate and free additional virtual memory, using the following system calls.
   void * AllocVm(int NumPages);
   void * ReallocVm(void * Address, int OldPages, int NewPages);
   void FreeVm(void * Address, int NumPages);
   void ProtectVm(void * Address, int NumPages, int Protection);

   Where protection can be:
   #define MEM_READONLY 1
   #define MEM_READWRITE 2

   The AllocVm() call should allocate the specified number of pages and set the protection to be read/write. The ReallocVm() call should allocate a new chunk of address space NewPages long, and move OldPages number of pages from the old chunk of address space to the new chunk of address space. This shouldn't require any data copying. FreeVm() should de-allocate the memory, and ProtectVm() should update the protection bits for the specified pages.

3. Implement demand-paged 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 a backing store - this will make part 4 a lot easier, if you choose to do it. In order to find unreferenced pages to throw out on page faults, you will need to keep track of all pages in the system which are currently in use (Hint: traditional Unix machines use something called a "core map" or "inverted page table" that maps physical page numbers to the virtual pages that are stored there.)

   The Nachos TLB sets and clears dirty and use bits, which you can use to implement the clock algorithm, or you can use TLB misses to implement the FIFO second-chance algorithm.

   Demonstrate the value of your paging algorithm by writing some programs that page, but page less frequently under your approach than using random replacement.

4. Extra Credit: implement memory mapped files for executables, so that data from an executable is paged back to the file from which it was loaded, rather than to the page file. This will require you to keep track of from where pages were loaded, but is simplified by the fact that you can mark the code pages as read-only and thus never have to write them back.

• Think about how you will measure the performance of the system, in terms of the number of page faults, TLB misses, and the cost of a page fault or TLB miss in cycles. Nachos already has some support for maintaining statistics that you can use.
• You may want to have a "segment" data structure that keeps track of a contiguous set of virtual pages stored in a particular backing store. Thus, you could have one segment data structure per mapped file, and one for the data, code and stack segments.
• You shouldn't use linear searches to find free physical pages.

Similar to the last two programs, we will be using the turnin program. In addition, you will be expected to write a paper describing the design of your system and a justification for the design, including benefits, drawbacks, and assumptions. You should try to cover cases where it will perform well, and the conditions under which it will perform badly. And again, please list what parts of the project each team member did. In addition, I would like each team member to separately send me e-mail representing what percentage of the overall project work that each team member did.