Project 3: Memory management

Part I (25%) Implement support for multiprogramming. The code we have given you is restricted to running one user process at a time; your job is to make it work for multiple user processes.

• Come up with a way of allocating the machine's physical memory so that different processes do not overlap in their memory usage. Note that the user programs do not make use of malloc() or free(), meaning that user programs effectively have no dynamic memory allocation needs (and therefore, no heap). What this means is that you know the complete memory needs of a process when it is created. You can allocate a fixed number of pages for the processe's stack; 8 pages should be sufficient.

  We suggest maintaining a global linked list of free physical pages (perhaps as part of the UserKernel class). Be sure to use synchronization where necessary when accessing this list. Your solution must make efficient use of memory by allocating pages for the new process wherever possible. This means that it is not acceptable to only allocate pages in a contiguous block; your solution must be able to make use of "gaps" in the free memory pool.

  Also be sure that all of a process's memory is freed on exit (whether it exits normally, via the syscall exit(), or abnormally, due to an illegal operation).

• Modify UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory, which copy data between the kernel and the user's virtual address space, so that they work with multiple user processes.

  The physical memory of the MIPS machine is accessed through the method Machine.processor().getMemory(); the total number of physical pages is Machine.processor().getNumPhysPages(). You should maintain the pageTable for each user process, which maps the user's virtual addresses to physical addresses. The TranslationEntry class represents a single virtual-to-physical page translation.

  The field TranslationEntry.readOnly should be set to true if the page is coming from a COFF section which is marked as read-only. You can determine this using the method CoffSection.isReadOnly().

  Note that these methods should not throw exceptions when they fail; instead, they must always return the number of bytes transferred (even if that number is zero).

• Modify UserProcess.loadSections() so that it allocates the number of pages that it needs (that is, based on the size of the user program), using the allocation policy that you decided upon above. This method should also set up the pageTable structure for the process so that the process is loaded into the correct physical memory pages. If the new user process cannot fit into physical memory, exec() should return an error.

  Note that the user threads (see the UThread class) already save and restore user machine state, as well as process state, on context switches. So, you are not responsible for these details.

Part II (25%) Implement the system calls (exec, join, and exit, also documented in syscall.h).

• Again, all the addresses passed in registers to exec and join are virtual addresses. You should use readVirtualMemory and readVirtualMemoryString to transfer memory between the kernel and the user process.

• Again, you must bullet-proof these syscalls.

• Note that the state of the child process is entirely private to this process. This means that the parent and child do not directly share memory, file descriptors, or other state. Note that two processes can of course open the same file; for example, all processes should have file descriptors 0 and 1 mapped to the system console.

• Unlike KThread.join(), only a process's parent can join to it. For instance, if A executes B and B executes C, A is not allowed to join to C, but B is allowed to join to C.

• join takes a process ID as an argument, used to uniquely identify the child process which the parent wishes to join with. The process ID should be a globally unique positive integer, assigned to each process when it is created. (Although for this part the only use of the process ID is in join, for later parts it is important that the process ID is unique across all running processes in the system.) The easiest way of accomplishing this is to maintain a static counter which indicates the next process ID to assign. Since the process ID is an int, then it may be possible for this value to overflow if there are many processes in the system. For this project you are not expected to deal with this case; that is, assume that the process ID counter will not overflow.

• When a process calls exit(), its thread should be terminated immediately, and the process should clean up any state associated with it (i.e. free up memory, close open files, etc). Perform the same cleanup if a process exits abnormally.

• The exit status of the exiting process should be transferred to the parent, in case the parent calls the join system call. The exit status of a process that exits abnormally is up to you. For the purposes of join, a child process exits normally if it calls the exit syscall with any status, and abnormally if the kernel kills it (e.g. due to an unhandled exception).

• The last process to call exit() should cause the machine to halt by calling Kernel.kernel.terminate(). (Note that only the root process should be allowed to invoke the halt() system call, but the last exiting process should call Kernel.kernel.terminate() directly.)

Part III (25%): Implement software-management of the TLB, with software translation via an inverted page table.

• Since VMProcess extends UserProcess, you should not have to duplicate much code from UserProcess; that is, only override what's necessary and call methods in the superclass for everything else.

• The way to handle TLB misses is to add code to VMProcess.handleException which deals with the Processor.exceptionTLBMiss exception. The virtual address causing the TLB miss is obtained by calling Machine.processor().readRegister(Processor.regBadVaddr).

• Some methods you will need to use are: Machine.processor().getTLBSize() (obtains the size of the processor's TLB), Machine.processor().readTLBEntry() (reads a TLB entry), and Machine.processor().writeTLBEntry() (writes a TLB entry). Note that TLB entries are of type TranslationEntry, the same class used for page table entries in Part I.

• When you run Nachos from the proj3 directory, the processor no longer deals with page tables (as it did in Part I); instead, the processor traps to the OS on a TLB miss. This provides the flexibility to implement inverted page tables without changing anything about the processor simulation.

• You will need to do make sure that TLB state is set up properly on a context switch. Most systems simply invalidate all the TLB entries on a context switch, causing entries to be reloaded as the pages are referenced.

• Your TLB replacement policy can be random, if you wish. The only requirement is that your policy makes use of all TLB entries (that is, don't simply use a single TLB entry or something weird like that).

• You should use a single global inverted page table for all processes. (This is a departure from the use of per-process page tables from Part I) Because the inverted page table is global, each key used to look up an entry in the table will need to contain both the current process ID and the virtual page number. You may use the standard Java java.util.Hashtable class to implement the inverted page table, but do not depend upon the fact that this class is synchronized to avoid changes being made to it by multiple threads.

• Only invalidate TLB entries when it is necessary to do so (e.g. on context switches).

• Don't forget to set used and dirty bits where necessary in readVirtualMemory and writeVirtualMemory.

Part IV (25%) 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

• 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 which are currently in use. You should consider using a core map, an array that maps physical page numbers to the virtual pages that are stored there.

• The inverted page table must only contain entries for pages that are actually in physical memory. You will need to maintain a separate data structure for locating pages in swap.

• The Nachos TLB sets the dirty and used bits, which you can use to implement the clock algorithm for page replacement. Alternately, you may choose to implement the nth chance clock algorithm as described in the lecture notes (see the textbook for more details on these algorithms).

• Your page-replacement policy should not write any pages to the swap file which have not been modified (i.e. for which the dirty bit is not set). Also, do not unnecessarily increase the size of the swap file (by having unused space at the end or in the middle of the file). Thus, you will be required to keep pages around in swap even if they have been moved to physical memory.

• Now that pages are being moved to and from memory and disk, you need to ensure that one process won't try to move a page while another process is performing some other operation on it (e.g., a readVirtualMemory or writeVirtualMemory operation, or loading the contents of the page from a disk file). You should not use a separate Lock for every page -- this is highly inefficient.

• We recommend that you use a single global swap file shared by all processes. You may use any format you wish for this file, but it should be rather simple as long as you keep track of where different virtual pages are stored in the file. You may assume that it's safe to grow the swap file to an arbitrary size; that is, you don't need to be concerned about running out of disk space for this file. (If a read or write operation on the swap file returns fewer bytes than requested, this is a fatal error.) To conserve disk space, you should reuse unallocated swap file space; a simple list of free swap file pages is sufficient for this.

• The swap file should be closed and deleted when VMKernel.terminate() is called.

• If a process experiences an I/O error when accessing the swap file, you should kill the process.

• You should test the performance of your page-replacement algorithm by comparing it to a simpler algorithm, such as random replacement. A good way to test this is to write a MIPS C program which does a lot of paging; test/matmult.c is a good example. By counting the number of page faults, you can compare the performance of your algorithm with random replacement. We will grade your algorithm in part based on the page fault rate as compared to a simple replacement policy.

• Note that it is possible to experience indefinite thrashing when the system has only a single physical page of memory if a process attempts to perform a load/store operation (convince yourself why!). Your implementation need not deal with this case.