UCSD Main WebsiteUCSD Jacobs SchoolDepartment of Computer Science and Engineering
spacer gif
spacer gif
CSE 120
spacer gifspacer gif
spacer gif
spacer gifCourse Overview
spacer gifspacer gifStructure
spacer gifspacer gifGrading
spacer gifspacer gifCollaboration
spacer gifspacer gifUseful books
spacer gif
spacer gifspacer gifSchedule
spacer gif
spacer gifProjects
spacer gif
spacer gif Homeworks
spacer gif
spacer gifWebBoard
spacer gif
spacer gif
spacer gif
Search
spacer gifspacer gifspacer gif
Advanced search  arrows gif

spacer gif
spacer gifspacer gif
spacer gif
spacer gif
spacer gif
spacer gif
spacer gifspacer gifspacer gif
spacer gif

Nachos Project 3: Virtual Memory

Informal Design Document Due: Never
Project 2 Autograder Rerun: May 30 at 14:00 PDT (See webboard for details!)
Early Submit Checkpoints: June 1 and 3 and 4, at 21:00 PDT
Project Code Due: Thursday, June 5, at 23:59 PDT

Announcement: If you are out of free pages and you try to exec(), you may just return -1. However, for 5% extra credit, you may sleep it and wake it up when there is a free page available for it.

The third phase of Nachos is to investigate the interaction between the TLB, the virtual memory system, and the file system. We don't provide any new virtual memory code for this assignment. You will continue to use the stub file system and your per process page tables. For this phase, you should run make and nachos in the proj3 directory.

To help you to organize your code better, we provide you with a new package, nachos.vm, with two new classes, VMKernel and VMProcess. VMKernel extends UserKernel, and VMProcess extends UserProcess. VMKernel and VMProcess are the only classes you should have to modify for this project phase.

This phase of the project involves open-ended design problems. We will expect you to come up with a design that would make sense in a real system. For example, you will have some freedom to choose how to do software address translation on TLB misses, how to represent the swap partition, how to implement paging, etc. There is no single "right" answer.

The first design aspect to consider is the software-managed translation lookaside buffer (TLB). Page tables were used in phase 2 to simplify memory allocation and to isolate failures from one address space from affecting other programs. For this phase, the processor knows nothing about page tables. Instead, the processor only deals with a software-managed cache of page table entries, called the TLB. 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 the virtual page to a physical page is already known. If the translation is in the TLB, the processor uses it directly. If the translation is not in the TLB (a "TLB miss"), the processor causes a trap to the OS kernel. Then it is the kernel's responsibility to load the mapping into the TLB. In other words, the Nachos MIPS simulator does not have direct access to your page tables; it only knows about the TLB. It is your job to write the code that manages a TLB miss. It is important to note that a TLB miss may not necessarily result in a page fault.

The second design aspect of this project is paging, which allows physical memory pages to be transferred to and from disk to provide the illusion of an (almost) unlimited physical memory. A TLB miss may require a page to be brought in from disk to satisfy the translation. That is, when a TLB miss fault occurs, the process should check its own page table. If the page is not in memory, it should read the page in from disk, set the page table entry to point to the new page, install the page table entry, and resume the execution of the user program. Of course, the process must first find space in memory for the incoming page, potentially writing some other page back to disk, if it has been modified. Note that this is a local page replacement policy. For this assignment, each process will have 4 physical pages (i.e. at most 4 entries in your page table are valid), which are taken from your free list. We do this so one process doesn't take up all the physical memory. To implement this you may need a data structure to keep track of which of your pages are actually in physical memory

Performance of this mechanism depends greatly on the policy used to decide which pages are kept in memory and which are 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 in memory those pages may be referenced soon. Another consideration is that if the replaced page has been modified, the page must first be saved to disk before the needed page can be brought in. (Of course, if the page has not been modified, it is not necessary to write it back to disk.)

To help you implement demand paging, each TranslationEntry contains three status bits: valid, used, and dirty. If the valid bit is set, the virtual page is in memory and the translation can be used directly by the processor. If the valid bit is clear, or if the page translation is not found in the page table, then the processor traps to the OS to perform the translation. You will need to set the used bit in the TLB entry whenever a page is referenced and sets the the dirty bit whenever the page is modified. Also, keep in mind that you will be using a local page replacement algorithm. That is, processes can only evict their own pages.

  1. (33%) Implement software-management of the TLB, with per-process page tables similar to what you did in Project 2.

    • 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 project phase 2.

    • When you run Nachos from the proj3 directory, the processor no longer deals with page tables (as it did in phase 2); instead, the processor traps to the OS on a TLB miss.

    • You will need to 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).

    • 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.

  2. (34%) 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; this will make Part 3 (see below) a lot easier.

    • 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.

    • 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). Thus, you will be required to keep pages around in swap even if they have been moved to physical memory.

    • 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. Don't forget to flush pages from the swap file when a process exits or is killed.

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

    • 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.

  3. (33%) Implement lazy loading of the code and data pages from user programs. That is, rather than reading all of the code and data from a user program at startup time, set up page table entries so that when page faults occur, the pages from the executable will be read into memory on demand.

    • You must ensure that changes to the memory image of the executable are not written back to the executable file. Code pages are always read-only, so there is no danger that the user process can modify them during execution. However, the data pages from the executable (representing global variables and the like) may be modified by the process. Ensure that these changes are not written back to the executable file.

    • In addition to lazy-loading pages from the executable file, you should allocate stack pages on demand as well. So, you should not allocate the full set of stack pages to the process when it is initialized; rather, when a page fault occurs on a stack page, you should allocate a new stack page at that time.

    • As with project phase 2, the maximum number of stack pages needed by a process is 8.


spacer gif
spacer gif
spacer gifback to top ^
spacer gif
spacer gif
spacer gif
spacer gif
9500 Gilman Drive, La Jolla, CA 92093-0114
spacer gif
About CSE | CSE People | Faculty & Research | Graduate Education | Undergraduate Education
Department Administration | Contact CSE | Help | Search | Site map | Home
snoeren@cs.ucsd.edu
Official web page of the University of California, San Diego
Copyright © 2002 Regents of the University of California. All rights reserved.
spacer gif