This machine problem involves implementation of several page-replacement algorithms as part of the virtual memory subsystem of Nachos. This is the first time that the virtual machine of Nachos will be used. 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 (machine directory). The purpose of this MP is to implement the routines that handle page faults by selecting an appropriate page to replace. You will be implementing four page replacement algorithms: First In First Out (FIFO), Second Chance (SC), Least Recently Used, and Clock . All these are described in the Tanenbaum book (Pages 217 to 227)..
First, you should obtain the given code for this machine problem. The code can be downloaded from here or you can copy it from the CSIL file system. It is tarred and gzipped. Here is a short script to retrieve the file:
gunzip -c mp3.tar.gz | tar -xvf -
You will see tar listing out the files it's creating for you. Do not issue this command again from this directory unless you want to overwrite all changes you have made! If you wish to replace individual files, untar the mp3.tar.gz file in a different directory and copy the relevant files. Everything you need for this assignment will be put in the subdirectory userprog.
To compile your code, use the following commands: (from the userprog directory)
gmake depend
gmake
Note: you must use gmake to compile your programs.
The code you will be changing and writing for this MP will be placed in memmanager.cc and memmanager.h. Do not change any of the other files. You will also be required to write a report in which you explain your measurement studies for this MP.
Structures: As you know, each address space has a page table associated with it. 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. An additional TIMESTAMP field had been added for this MP for use with the WS and WSC algorithms. These are described thoroughly in machine/translate.h.
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 noff.h for further details.
Beginnings: The Addrspace::ReadSourcePage() function is called to read a single page from the executable 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 "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 TranslationEntrys 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 page into a frame of memory, updating the TranslationEntry and returning control to the virtual machine.
Read the code for MemManager::PageFaultExceptionHandler(). This is called by ExceptionHandler() when it receives a page fault exception. The details about how to implement MemManager::faultIn along with a 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 page to 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, it is loaded from the original file. makeFreeFrame is responsible for choosing a victim with the appropriate page replacement algorithm when no free frames are available.
Read this handout, then read exception.cc, addrspace.h, addrspace.cc, memmanager.h, and memmanager.cc. Look in translate.h for the declaration of class TranslationEntry. You may also want to look at bitmap.h, and bitmap.cc. Look at MemManager::pageIn and MemManager::pageOut also. Understand the flow of control before implementing the modules.
Select the frame to be replaced using the FIFO algorithm.
For this algorithm, you will maintain a FIFO list of pages to select the victim, as described in the text.
For this algorithm, you will maintain a pointer, or clock hand, that moves through the physical page frames sequentially. When a victim is selected, the clockhand is chosen to be the next frame in physical memory. These frames will not necesarrily be maintained in FIFO order.
See section 4.4.6 of the text.
Compare the performance of 4 algorithms -- FCFS, Second Chance, Clock and
LRU -- using your implementations. Write THREE task sets that are different
from the test cases provided to you, and measure metrics -- this should
include (but need not be limited to) page fault rates, turnaround times,
waiting times, throughput, and efficiency. Use the ticks made available by
Nachos. You can call the following two methods defined in Statistics class:
PrintElapsedTicks and GetElapsedTicks. Statistics class has been defined in
machine/stats.h and machines/stats.cc, and used to show various statistics.
You can take a look at, for example, threads/threadtest.cc, to see how to
call these methods.
Clearly, this measurement may not be authoritative since you are not
programming with a real scheduler (Nachos may be subject to scheduling
delays due to the REAL scheduler in Solaris). However, this will give you a
feel for what it is like to create test cases and compare different
algorithms.
Write a 2 page report on your results. The 2 page limit includes everything
-- describe the contents of your task sets and why you chose them, present
your results systematically (table or plot), and describe your
interpretation and conclusions from the data.
Write a paragraph describing how you split the work for the entire MP among the 2 group members, and anything else you want to say. Please submit only 1 report per group. Any report exceeding the limit will be given a zero. The 2 page report should be different from the README. You may use Word, latex or any other editor for the report. Remember -- clarity of presentation is as important as content.
In order to compile your code type: gmake depend followed by gmake from userprog directory. There are three test programs: test1, dump, and test2, but only one ( test2 ) really exercises the virtual memory space enough to use most of the above algorithms. The parameters of this test however are quite varied, because of the command line arguments. Test your program by typing:
nachos -M <policy> <num_bits> -x ../test/<testcase> from userprog directory where
<policy> ranges from 1 to 4 with
1: FIFO, 2: SC, 3: Clock, 4:LRU
<num_bits> determines the number of bits used to store history for the LRU algorithm and should be a positive number.
You can gauge the effectiveness of the various policies by the number of page faults and disk I/O transactions at the end of the output file.
A suggested testing sequence is:
nachos -M 1 0 -x ../test/test2 // Corresponds to test.1.std
nachos -M 2 0 -x ../test/test2 // test.2.std
nachos -M 3 0 -x ../test/test2 // test.3.std
nachos -M 4 0 -x ../test/test2 // test.4.std
You should hand in both your report and code. Report is due at the start of lecture, in class. Again, the report should be typed and printed out.
In the directory containing your modified files, type ~cs423ug/handin. Follow the instructions after you run handin: Type in MP number (for this MP, it is 3), and check whether your netid is correct or not. The handin program will automatically copy memmanager.cc, memmanager.h, and README.txt. README.txt should include you and your partner's netids, names, MP number, and any comments that you want to include. Please make sure you have all three files with exactly same filename (case-sensitive) in the directory. Before handin is completed, it will show the files that you submitted.
The following is an example of running handin.
dclsn4> ~cs423ug/handin /===================================================\ | CS 423 UG | | Fall 2005 | | Welcome to handin | \===================================================/ -> Type in the Machine Problem number (1, 2, 3, 4): 3 Handin currently believes that your are: kim28 Enter y if this is correct or anything else otherwise y ------------- THIS IS THE INFO WE HAVE --------------- | | login-id: kim28 | MPNumber: 3 | Current Time: Wed Oct 19 13:18:16 CDT 2005 ------------------------------------------------------ -> Your MP has been handed in successfully. These are the files that you submitted: .: total 36 -rw-r--r-- 1 kim28 stdt 19 Oct 19 13:18 README.txt -rw-r--r-- 1 kim28 stdt 12248 Oct 18 2004 memmanager.cc -rw-r--r-- 1 kim28 stdt 3909 Oct 18 2004 memmanager.h Handin successful
In summary, you will need to hand in memmanager.cc, memmanager.h, and README.txt online through command-line based handin. A printed-out 2-page report should be submitted at the start of lecture, in class. Please summarize in the report any test cases that you used, and do not submit them online.
Your grade will be based on the correctness of your code and largely based on your code's ability to produce correct output in the test cases (though there are errors and omissions which the test cases don't catch). Style and legibility will be a part of your score, but possibly be a major effect especially if the code is hard to grade: if we can't see that your code is correct, we can't give you points. Crashing or failing to compile is, of course, not a correct behavior.
FIFO - 15%
SC - 25%
Clock - 25%
LRU - 25%
Report - 5%
Comments and Style - 5%
Any revisions will be listed at the top of the page and announced in the course newsgroup. Please use the newsgroup or send an email to ta423ug@cs.uiuc.edu if you have any questions.