Virtual Memory

1. It is easiest to test the VM algorithms by running only a single process and have it page against itself. It's a lot easier to see what is happening this way. Add debug print statements using the DEBUG() routine; I used "p" for paging to turn it on. I found it immensely useful to add debugging statements at the following points:
   • when a page is reclaimed (e.g., taken away from a process and made available to another one), indicate which process (address space) was forced to give up a page, which virtual page number it gave up, and the corresponding page frame number in physical memory.

     In order to print the name of the address space that was forced to give up a page, add a "char *name" field to the AddrSpace object and initialize it to the name of the Nachos binary when the space is initially created.

   • Whenever a process has a page fault, print the address space that caused the fault, which virtual page number the fault was for, and the physical page frame that was used to satisfy the fault.
2. Reduce the amount of available physical memory to insure lots of page faults. I got good results with 25 pages of real memory. Also, the matmult program in the test subdirectory uses quite a lot of memory. It is a good program to run with the "-x ../test/matmult" option to nachos.

   Another good test is to use a modified shell (the one that allows you to run a process in background by putting a '&' character before the file name). Run the matmult program in background, and then also run the console1 and console2 programs at the same time. You should be seeing alternating A's and B's as before (if using the "-rs" Nachos option).

3. You will need to maintain a data structure called a core map. The core map is a table containing an entry for every physical page frame in the system. For each page frame, a core map entry keeps track of:
   • Is the page frame allocated or free?
   • Which address space is using this page?
   • which virtual page number within space?
   • Plus possibly other flags, such as whether the page is currently locked in memory for I/O purposes

   When the system needs to find a free page, but none are available, the memory manager inspects the core map to find good candidate replacement pages. Of course, the memory manager looks at the page table entry for that frame (via the ``space'' pointer) to determine if a page has been used recently, is modified, etc.

   Start with a simple page replacement policy. I simply reclaimed frames in sequential order starting with frame 0. That is, first reclaim 0, than 1, etc., wrapping around when you get to the end of the list. This is obviously NOT an ideal policy, but it works for the purposes of testing your implementation (in fact, by being a ``bad'' policy, it tests your code surprisingly well). Once the rest of your code is debugged, then worry about implementing a better policy.

4. You need to think very carefully about mutual exclusion. For example, the page replacement process may select frame 13, but find that it needs to write it to backing store before it can be reclaimed. This will take a long time (I/O is slow), and in the meantime the process that was using that frame may be selected by the scheduler and start running again. What happens when it tries to reference that frame? It will surely notice that the page is gone, and try to reload it from backing store. Will it get the proper copy? Will it read the page only after the page replacement object has written it? There are all sorts of race conditions like that can potentially mess things up. So be sure to use appropriate mutual exclusion in the paging routines.
5. You will need to maintain a "shadow" page table for each address space. The existing page table defined by Nachos has a specific format dictated by the address translation hardware. You will need to keep additional information about each page, thus the shadow table. The shadow table keeps track of such things as the current state of the page (e.g., loaded in memory, needs to be loaded from the text or swap file, etc.)

   Moreover, when you do away with the hardware page table and use the TLB, the shadow table contains everything the standard table contains (e.g., reference bit, dirty bit, etc.). That is, when a program traps due to a TLB miss, the page fault handler will look in the shadow table to find the appropriate mapping (loading it from backing store first, if necessary), update the TLB and then restart the faulting instruction.

   In order to simplify the migration to the TLB part of this assignment, you may want to have your paging algorithms access only the shadow page tables (rather than the hardware page tables) when deciding which pages to reclaim, etc. That way, when the hardware table goes away, none of the routines need to be changed. One consequence of this approach, however, is that some information (e.g., dirty and reference bits) will be duplicated in both tables at the same time. Since the hardware automatically updates its page table, but not the shadow table, you will need to synchronize the two tables at key points before inspecting the shadow table. For example, before checking the dirty bit for an entry in the shadow page table, make sure that the shadow table has the must recent value for that bit. You may find it useful to have a routine SyncPageTableEntry() that synchronizes a shadow entry with its corresponding hardware value. Note: you will probably need such a routine anyway later when doing the TLB part of the assignment, since the Nachos hardware only updates its TLB entries.

6. You will need to allocate backing store (swap space) for each address space. One approach is to create a file (e.g., swap.PID) when the address space is created, open it, and then use it while the process is running. The file should be closed and removed when the process terminates.

   When a page fault takes place, there are three scenarios:

   1. The page belongs to the stack or heap section, and should be initialized to 0. This is the easiest case to handle, because you only have to find a free page and zero it out. There is no need for disk I/O.
   2. The page should be loaded from the swap file. This simply involves reading the page in the swap file at the offset corresponding to the page being accessed. For example, page number 7 would correspond to an offset of 7*PageSize = 7*128 = 896.
   3. The page contains instructions or initialized data and should be loaded from the original binary file.

      This is the most difficult case. You will need to figure out what offset within the text file the desired page begins at. To simplify matters, assume that the text and initialized data segments are laid out contiguously in the Nachos binary file (they are). That way, you only need to keep track of where the text segment begins (it doesn't start at offset 0, the NOFF header resides there) and the combined length of the text and data segments are.

   To handle the three above cases, you will need to keep two OpenFile objects with the AddrSpace object. One for the text file, the other for the swap file. In addition, for each page in an address space's shadow page table, maintain a state variable that indicates what state the page is in. For example, LOADFROMTEXT, LOADFROMSWAP and ZEROFILL. The state of a page is initialized when a process is created, and changes only if the memory manager reclaims the page, finds it modified, and writes it to backing store.

7. You will need routines that lock a range of addresses into memory (and unlock them later). For example, when a program does a system call to read data from a file, it provides a pointer to the buffer where it wants the file contents placed. The Read system call first reads the desired data into its own buffer, and then copies the data into the user buffer using the machine::WriteMem() operations. In order for this operation to succeed, the pages holding the buffer must be in memory. Thus, you will want to lock the pages associated with the buffer into memory before attempting to place data in the buffer. Once the data has been copied to the buffer, the pages can be unlocked again. For example, the routine LockMemory() might take a virtual address and length, insure that all pages corresponding to the specified addresses indicated are loaded and present in physical memory and lock them into place. While locked in memory, the memory manager would not reclaim them.

   What you must do for full credit. Please note that I will grade these in order. If part 1 doesn't work, I won't even look at 2 or 3. Don't waste your time working on any parts before completing the previous parts.

1. (40% of total grade) Get demand loading to work. That is, rather than load the program into memory during "exec", load individual pages as they are first referenced. If a page is never referenced, it is never loaded into memory. Assume that there is enough physical memory so that no pages ever need to be reclaimed.
2. (70% of total grade) In addition to 1), get full blown paging with backing store implemented. That is, when the system runs out of physical memory, grab any page, write it to backing store if necessary, and then reuse the page frame. Use a simple policy (like the one described above). The focus is on getting the mechanics of page replacement/backing store to work.
3. (85% of total grade) In addition to the previous steps, implement a better page replacement policy, such as LRU.
4. (100% of total grade) In addition to the previous steps, use the TLB rather than hardware page tables. (E.g., compile with the -DUSE_TLB option).