Project 3: Demand Paging1 OverviewIn project 2, each process had a page table which nachos knew about: memory accesses in userspace used the tableto map virtual addresses to physical addresses.Project 3 deals purely with implementing a more sophisticated memory management system. The memoryhierarchy of the simulated architecture is as follows:1. TLB. Userspace can only access memory through the TLB. When a (valid) mapping is not present, a fault isgenerated and the kernel is entered.2. Physical Memory. The TLB entries, as usual, specify physical page numbers. Recall that userspace innachos is run inside a MIPS simulator; in this project, that userspace can only see what the TLB can see. Butin your kernel, you can access all of memory. This may seem confusing at first, but it is simply an artifact ofthe nature of nachos (as configured for project 3). When a TLB miss occurs, it is the kernel’s responsibility toobtain a page with the correct contents, and place the mapping in the TLB.3. Disk. The demands of the system’s processes may exceed physical memory, in which case modified memorymust be copied to disk. Nearly1analogously, requests for (some) memory pages not currently present aresatisfied by reading from disk.Notice how this differs from memory systems we have discussed. Typically, there is a hardware MMU, which firstrefers to the TLB, automatically checking page tables if an entry is not found. If a mapping is not found in the pagetables, the kernel is entered. Here, however, the hardware only refers to the TLB, faulting into the kernel when thedesired mapping is not present—the hardware does not see any page tables.Your implementation will have the following properties:1. Demand Paging. Mappings will enter the TLB only strictly as needed. This mechanism will depend uponservicing TLB misses, and divide into a number of cases which will be detailed later. For the time being,consider the differing initial contents of stack/argument pages and coff pages, as well as the treatment of read-only and read/write coff pages. When no physical pages are free, it is necessary to free pages, possibly writingback to swap.2. Lazy Loading. To fulfill the spirit of demand paging, processes should load no pages when started, anddepend on demand paging to provide even the first instruction they execute. To be clear, this means thatloadSections() won’t allocate a single page!3. Page Pinning. At times it will be necessary to “pin” a page in memory, making it temporarily impossible toevict.For this project, we provide no new code—running inside the proj3 subdirectory will cause nachos to use the newmemory configuration. Your new implementation should reside in the vm subdirectory, in the files VMKernel.javaand VMProcess.java.You will notice that these classes inherit from UserKernel and UserProcess. You are advised to depend on theimplementation of your base classes as much as possible2. Note that, thanks to the existence of readVirtualMemory()1The situation is not perfectly symmetric for two reasons. First, unmodified pages need not be written back. Second, some pages donot originate on disk (for instance stack and arguments).2Anecdotally, Matus worked through project 2 with no knowledge of project 3, and found that by changing about 6 lines of UserProcess,he could have nearly no duplication of logic between project 2 and project 3 code, and both worked correctly from their own directories.1and writeVirtualMemory(), very little code needed to know the details of virtual addressing; for example, you shouldnot have to change any of the primary code which serviced the read() syscall.You should not change the base classes in any way which depends on project 3. That is to say, it should still bepossible to run nachos from the proj2 subdirectory, and achieve proper results.Note that even though userspace is no longer reading your per-process page tables directly, you may still findthem useful for your own memory management (notice that pageTable was protected, not private).2 Illustrative ExampleThe following scenario demonstrates many aspects of both the simulated memory hierarchy, and of the kernel youmust write. It is perhaps most useful to read this example twice—once now, and again after finishing the document.1. Process A is executing in userspace, which invokes the read() syscall.2. Process A enters the kernel, and is part way through writing to user memory.3. A timer interrupt triggers context switch, entering process B.4. Process B immediately generates numerous TLB misses, which in turn cause pages to be evictedfrom other processes, including some used by process A.5. Eventually, process A is scheduled to run again, and continues handling the read() syscall as before.This example demonstrates the necessity of page pinning—the page which A is writing to should be pinned inmemory. Imagine if otherwise process B evicted the page, and when process A was rescheduled, it accidentally wroteover, say, B’s code pages.Notice also that this example exposes the userspace/kernel disconnect of memory management—userspace passedthrough the TLB to access its memory, but when process A was servicing the read() request, it did not care whetherthe mapping was in the TLB.3 Design AspectsAlthough the implementation details are heretofore vague, it is useful to begin considering the following two designproblems, which end up being central to this project.In many places in this project, there will be clear, simple solutions which are reasonably efficient. Prefer suchsolutions.1. Swap File. To manage swapped out pages on disk, use the StubFileSystem (via ThreadedKernel.fileSystem)as in project 2. There are many design choices, however we suggest using a single, global swap file across allprocesses. This file should last the lifetime of your kernel, and be properly deleted upon nachos termination.Be sure to choose a reasonably unique file name.When designing the swap space, the central point is that the units of swap are pages. Thus you should try toconserve disk space using the same techniques applied in virtual memory: if you end up having gaps in yourswap space (which will necessarily occur with a global swap file upon program termination), try to fill them.As with physical memory in project 2, a global free list provides an adequate solution.It is safe to assume that the swap file can grow arbitrarily, and that any read/write errors are fatal, meaninga process depending on the problematic
View Full Document
Unlocking...