Trusted by 2+ million users, 1000+ happy students everyday
Showing pages 1 to 3 of 6 pages
1 Overview This machine problem involves implementation of part of a virtual memory subsystem for Nachos. The code for the test case is a set of array operations that span large portions of the virtual memory space. This virtual memory space is mapped into 20 physical frames of memory. Address translation and page table structures are given by the machine implementation (in machine directory). The purpose of this MP is to implement the routines that handle page faults. This will involve swapping pages to and from the backing store when appropriate. In an effort to minimize the number of page faults and I/O swaps from memory to disk, you will be implementing a page buffering scheme and three page replacement algorithms, First In First Out (FIFO), Least Recently Used (LRU - Approximation using Additional-Reference bits), and Enhanced Second Chance (ESC). 2 Preparation Materials: The given code for this MP can be extracted with the usual tar command with the appropri- ate command line arguments as in the previous projects. Once you unzip and untar the archive the source code will be in the “mp3given” directory. For this MP, you will be working in the “userprog” subdirec- tory. Look at the files filesys/OpenFile.java, filesys/OpenFileStub.java, machine/TranslationEntry.java, ma- chine/Timer.java, userprog/NoffHeader.java, and userprog/BitMap.java. It will be helpful to understand the additional functions added to the List class in threads/List.java as well (note that these functions are not optimized but are given for your convenience in programming). In this assignment you will need to modify only MemManager.java (in userprog directory). Structures: As you know, each address space has a page table associated withit. Each entry in the page table is an instance of a TranslationEntry. The three primary fields that we will be working with in this MP are the USE, DIRTY, and VALID fields. These are described thoroughly in machine/TranslationEntry.java. The structure AddrSpace consists of all the information about the address
space of a nachos process - the page table, its length, etc, and functions to manipulate the address space. When a new process is created this structure is instantiated, initialized and associated with the process. The code supplied implements demand paging. In this paging scheme a page is read into the physical memory from the source (executable) file only if the process accesses it during its execution. So initially when the process is created all the entries in the page table are initialized to invalid (the valid bit of the all page table entries is set to false). However, in general, it may not be legal to access certain pages (the ones that do not belong to any program segment). While initializing the table a note is made about which pages are legal to access and which are not (the legal field). Every executable file starts with a header which specifies the virtual address range of all the segments of the program. Read AddrSpace.AddrSpace() and the comments in NoffHeader.java for further details. Beginnings: The AddrSpace.readSourcePage() function is called to read a single page from the exe- cutable file into the physical memory. Note that this function is called only when a virtual page is accessed for the first time by the process. For subsequent accesses, if the page is not in physical memory the swap file rather than the source file is searched. The swap file is a single file, consisting of frames of memory just like MainMemory, except that they are stored on a disk. An array of TranslationEntry pointers named CSCI 40300/ECE 40800 1 Project 3 “swapOwners” is used to keep track of the page table entries that refer to the page stored there in the swap file. A similar structure, “coreOwners”, exists for pages in main memory. Read AddrSpace.readSourcePage() and MemManager.pageIn() for further details. Execution: During execution, the machine emulation will handle setting the appropriate bits in the Trans- lationEntry such as DIRTY=TRUE when a write occurs or USE=TRUE when a read or write occurs. If the machine emulator processes a memory request on a TranslationEntry that has a LEGAL=TRUE, but VALID=FALSE, it will trap to MemManager.faultIn(). This is the entry point for your implementation. Given the faulting TranslationEntry, use pageIn(), pageOut(), and methods that you will
implement to clear the exception by loading the appropriate buffer into a frame of memory, updating the TranslationEntry and returning control to the virtual machine. Read the code for MemManager.pageFaultExceptionHandler(). This is calledby Nachos.exceptionHandler() when it receives a page fault exception. The details about how to implement MemManager.faultIn along witha few hints are given as comments in MemManager.pageFaultExceptionHandler(). Note that you should not increment the program counter in this function. After the exception is handled and the control is returned back to the faulting process the instruction which caused the page fault should be re-executed. Anatomy: While “faultIn” is the “handler”, various other methods encapsulate important functionality. pageOut is responsible for writing a pageto the backing store. It is assumed that only dirty pages are given to pageOut because the others can be overwritten, since they are already on the backing store or are unchanged from their original state. pageIn is responsible for reading a page into a specified frame. If the page is not in the backing store, itis loaded from the original file. MemManager.makeFreeFrame is responsible for choosing a victim with the appropriate page replacement algorithm when no free frames are available. MemManager.recordHistory is a timer interrupt handler that updates history information from the appropriate bits in the TranslationEntry. 3 Reading Guide Read this handout, then read userprog/AddrSpace.java, userprog/MemManager.java, and threads/Nachos.java (method exceptionHandler). Look in machine/TranslationEntry.java for the declaration of class Translatio- nEntry. You may also want to look at userprog/Bitmap.java. Look at MemManager.pageIn and MemMan- ager.pageOut also. Make a paper design before starting to code. 4 Problem: Various Page Replacement Algorithms. 4.1 Prerequisite: RecordHistory Implement the Interrupt Service Routing ( MemManager.recordHistory ) to record the state of the USE bit from each TranslationEntry that has a frame
Found this document preview useful?
You are reading a preview Upload your documents to download or Become a Desklib member to get accesss