Project 2--EECS 482 (Winter 2003) Worth: 15 points Assigned: Tuesday, February 18, 2003 Due: 6:00 pm, Tuesday, March 18, 2003 1 Overview This project will help you understand address spaces and virtual memory management. In this project, you will implement an external pager, which is a process that handles virtual memory requests for application processes. The external pager ("pager" for short) is analogous to virtual-memory portion of a normal operating system. The pager will handle address space creation, read and write faults, address space destruction, and simple argument passing between spaces. For simplicity, your pager will only handle a special arena, or heap, of each application that uses it. Your pager will be single threaded, handling each request to completion before processing the next request. Your pager will manage a range of (simulated) physical memory that is to be used to provide the arena for each application backed by the pager. If the total number of pages in use by all of the applications using your pager exceeds the capacity of the physical memory, your pager will use a (simulated) disk as backing storage. In addition to handling page faults, your pager will handle two system calls: vm_extend and vm_syslog. An application uses vm_extend to ask the pager to add a new virtual page to the end of its arena. An application uses vm_syslog to ask the pager to print a message to its console. This handout is organized as follows. Section 2 describes how the infrastructure for this project performs the same tasks as the MMU and exception mechanism on normal computer systems. Section 3 describes the system calls that applications can use to communicate explicitly with the pager. Section 4 is the main section; it describes the functionality that you will implement in the external pager. Section 5 describes the functions your pager will use to maintain the emulated MMU and access physical memory and disk. Section 6 gives some hints for doing the project, and Sections 7-10 describe the test suite and project logistics/grading. 2 Infrastructure and System Structure In a normal computer system, the CPU's MMU (memory management unit) and exception mechanism perform several important tasks. The MMU is invoked on every virtual memory access. a. For non-resident memory accesses, the MMU triggers a page fault exception, transfers control to the kernel's fault handler, then retries the faulting instruction after the fault handler finishes. b. For resident memory accesses that have a protection violation, the MMU triggers an exception, calls the kernel's fault handler, then retries the faulting instruction after the fault handler finishes. c. For resident memory accesses that are allowed by the page's protection, the MMU translates the virtual address to a physical address and accesses that physical address. d. Some MMUs automatically maintain dirty and reference bits; other MMUs leave this task to be handled in software. The MMU in this project does NOT automatically maintain dirty or reference bits. On normal computer systems, system call instructions also invoke the exception mechanism. When a system call instruction is executed, the exception mechanism transfers control to the registered kernel handler for this exception. We provide software infrastructure to emulate the MMU and exception functionality of normal hardware. To use this infrastructure, each application that uses the external pager must include "vm_app.h" and link with "libvm_app.a", and your external pager must include "vm_pager.h" and link with "libvm_pager.a". You do not need to understand the mechanisms used to emulate this functionality (in case you're curious, the infrastructure uses mmap, mprotect, SEGV handlers, and remote procedure calls). Linking with these libraries enables application processes to communicate with the pager process in the same manner as on normal hardware. Applications issue normal load and store instructions (compiled from normal C++ variable accesses), and these are translated or faulted by the infrastructure exactly as in the above description of the MMU. The infrastructure will transfer control on faults and system calls to the pager, which receives control as the target of a normal function call. The following diagram shows how your pager will interact with applications that use the pager. An application makes a request to the pager via the function calls vm_create, vm_extend, and vm_syslog, or by trying to load or store an address that is non-resident or protected. vm_init (called by infrastructure when pager starts) vm_destroy (called by infrastructure when an application exits) vm_create --> vm_create vm_extend --> vm_extend vm_syslog --> vm_syslog faulting load --> vm_fault faulting store --> vm_fault +-----------+ +--------------+ |APPLICATION| |EXTERNAL PAGER| +-----------+ +--------------+ Note that there are two versions of vm_create, vm_extend, and vm_syslog: one for applications and one for the pager. The application-side vm_create/vm_extend/vm_syslog is implemented in libvm_app.a and is called by the application process. The pager-side vm_create/vm_extend/vm_syslog is implemented by you in your pager and has an additional parameter. Think of the vm_create/vm_extend/vm_syslog in libvm_app.a as a system call wrapper, and think of the vm_create/vm_extend/vm_syslog in your pager as the actual system call. When the application calls its vm_create/vm_extend/vm_syslog (the one in libvm_app.a), the infrastructure takes care of adding the extra parameter and invoking the system call vm_create/vm_extend/vm_syslog in your pager. See the header files vm_app.h and vm_pager.h for the actual function declarations. 3 System Calls Offered by External Pager Applications use three system calls to communicate explicitly with the external pager: vm_create, vm_extend, vm_syslog. The prototypes for these system calls are given in the file "vm_app.h": ------------------------------------------------------------------------------- /* * vm_app.h * * Public routines for clients of the external pager */ #ifndef _VM_APP_H_ #define _VM_APP_H_ /* * vm_create -- initialize arena and external pager support * * This should be called in the first statement in your main(). It is * going to install signal handlers for a wide range of signals to * ensure that exit() is called; since we aren't really writing a * kernel, we need to make sure that the process calls exit() whenever * it is going to quit. Otherwise, the external pager will never know * the process has died, and -- if it ever tries to evict a page that * had been made resident by that process -- will eventually keel over and * die. */ extern void vm_create(void); /* * vm_extend() -- ask that a new page be added to the end of the process' * arena. Returns the lowest-numbered byte of the newly allocated memory. * E.g. if the arena before calling vm_extend is 0x60000000-0x60003fff, * and the application calls vm_extend(), the return value will be 0x60004000, * and the resulting arena will be 0x60000000-0x60005fff. vm_extend will * return NULL if the disk is out of swap space. */ extern char *vm_extend(void); /* * vm_syslog() -- ask external pager to log a message (message data must * be in address space controlled by external pager). Logs message of length * len. Returns 0 on success, EINVAL on failure, */ extern int vm_syslog(char *message, unsigned int len); #define EX_PAGESIZE 8192 #endif /* _VM_APP_H_ */ ------------------------------------------------------------------------------- Applications make themselves known to the pager by calling vm_create. The arena is initialized as empty (no virtual pages) after vm_create returns. An application calls vm_extend to add a virtual page to its arena. vm_extend returns the lowest-numbered byte of the newly allocated memory. E.g. if the arena before calling vm_extend is 0x60000000-0x60003fff, and the application calls vm_extend(1), the return value will be 0x60004000, and the resulting arena will be 0x60000000-0x60005fff. Each byte of a newly extended virtual page is defined to be initialized with the ASCII character '0'. Applications can load or store to any address in the arena. Depending on the protections and residencies set by the pager, some of these loads and stores will result in calls to the pager's vm_fault routine; however these faults are serviced without the application's knowledge. An application calls vm_syslog to ask the pager to print a message (all message data should be in the arena). vm_syslog returns 0 on success and EINVAL (defined in ) on failure. FYI, the vm_extend interface is similar to the sbrk call provided by Solaris. The interface you are used to using to manage dynamic memory (new/malloc and delete/free) are user-level libraries built on top of sbrk. The following is a sample application program that uses the external pager. ------------------------------------------------------------------------------- #include #include "vm_app.h" using namespace std; main() { char *p; vm_create(); p = vm_extend(); p[0] = 'h'; p[1] = 'e'; p[2] = 'l'; p[3] = 'l'; p[4] = 'o'; vm_syslog(p, 5); } ------------------------------------------------------------------------------- 4 Pager Specification This section describes the functions you will implement in your external pager: vm_init, vm_create, vm_fault, vm_destroy, vm_extend, and vm_syslog. Note that you will not implement main(); instead, main() is included in libvm_pager.a. The infrastructure will invoke your pager functions as described below. 4.1 vm_init The infrastructure calls vm_init when the pager starts. Its parameters are the number of physical pages provided in physical memory and the number of disk blocks available on the disk. vm_init should set up whatever data structures you need to begin accepting vm_create and subsequent requests from processes. 4.2 vm_create The vm_create routine is called when a new process starts to use the external pager (viz. when an application calls vm_create). You should initialize whatever data structures you need to handle this process and its subsequent calls to the library. Its initial page table should be empty, since there are no pages in its arena until vm_extend is called. 4.3 vm_extend vm_extend is called when a process requests that a page be added to the end of its arena. The arena in each application's virtual memory is structured as a contiguous collection of pages (the size of each page is EX_PAGESIZE). Each application's arena starts at the virtual address EX_ARENA_BASEADDR. Virtual page numbers start at EX_ARENA_BASEPAGE (which is just EX_ARENA_BASEADDR divided by EX_PAGESIZE). These constants are defined in vm_pager.h. vm_extend should return the lowest-numbered byte of the newly allocated memory. E.g. if the arena before calling vm_extend is 0x60000000-0x60003fff, and the application calls vm_extend(), the return value will be 0x60004000, and the resulting arena will be 0x60000000-0x60005fff. This address is in the application's virtual address space. vm_extend should immediately assign a disk block to the new virtual page for later use as backing store. This disk block will be assigned to the virtual page until that application is destroyed. Choose the lowest-numbered free disk block when assigning a disk block to a virtual page. If there are no free disk blocks, vm_extend should return NULL. Remember that an application should see each byte of a newly extended virtual page as initialized with the ASCII character '0'. However, the actual data initialization needed to provide this abstraction should be deferred as long as possible. The application may not need the page immediately, so you should not instantiate it until absolutely necessary. 4.4 vm_fault The vm_fault routine is called in response to a read or write fault by the application. Faults can be generated when an application accesses a non-resident page, when an application accesses a page with protection PROT_NONE, or when an application writes a page with protection PROT_READ. The infrastructure ensures that vm_fault will only be called with addresses in the arena. Your pager determines which accesses will generate faults by controlling which pages are resident and by setting the page protections for resident pages. 4.4.1 Non-Resident Pages If a fault occurs on a virtual page that is not resident, you must find a physical page to associate with the virtual page. If there is a free physical page, you should choose the lowest-numbered one to hold the virtual page. If there are no free physical pages, you must create a free physical page by evicting a virtual page that is currently resident. Before making the newly assigned physical page resident, you should fill it with the data of the faulted-in virtual page. Use the "FIFO with second-chance" (clock) algorithm to select a victim. When a virtual page is assigned to a physical page, that physical page should be placed on the tail of the clock queue (and marked as referenced). To select a victim, remove and examine the physical page at the head of the queue. If it has been accessed in any way since it was last placed on the queue, it should be added to the tail of the queue (and its protection updated appropriately), and victim selection should proceed to the next page in the queue. If the page at the head has not been accessed since it was last enqueued, then its virtual page should be evicted. Dirty and clean pages are treated the same when selecting a victim page to evict; do not give either preference. To evict a virtual page, first call pm_nonresident (described in Section 5), then if needed, write the victim's data to disk (think about what race condition occurs if you write the data to disk before calling pm_nonresident). Hint: many pages, even those that are not zero-filled, do not need to be paged out. 4.4.2 Resident Pages Your pager controls the page protections for resident pages via pm_chprot (described in Section 5). Its goal in controlling protections is to maintain any state it needs to defer work and implement the clock replacement algorithm (e.g. dirty and reference bits). An access to a resident page will generate a page fault if the page's protection does not allow the access. On these faults, vm_fault should update state as needed, change the protections on the virtual page via pm_chprot, and continue. 4.5 vm_syslog vm_syslog is called with a process id, a pointer to an array of characters in that application process's virtual address space, and the length of that array. Your pager should first check that the entire message is in a valid portion of the arena (i.e. is on a page that has been created with vm_extend). Return EINVAL (defined in ) if any portion of the message is outside the valid arena (and don't print anything). Messages with zero length are legal and are never considered outside the valid arena. After checking for invalid addresses, your pager should next copy the entire array into a C++ string in the pager's address space, then print the C++ string to cout. You should use the following snippet of code for your print statement (this assumes the C++ string variable is named "s"): cout << "syslog\t\t(" << pid << ")\t" << s << endl; Most of the work in vm_syslog will be copying the array into the pager's C++ string. vm_syslog must handle virtual to physical address translation while copying the message from one address space to another. (Hint: you should treat vm_syslog's accesses to the application's data exactly as if they came from the application program for the purposes of protection, residence, and reference bits.) vm_syslog should copy the application's data starting at the lowest virtual address and proceeding toward the highest virtual address. 4.6 vm_destroy vm_destroy is called by the infrastructure when the corresponding application exits. This routine must deallocate all resources held by that process. This includes page tables, physical pages, and disk blocks. Physical pages that are released should be put back on the free list. vm_destroy need not (and should not) call pm_nonresident. 4.7 Deferring and Avoiding Work There are many points in this project where you have some freedom over when zero-fills, faults, and disk I/O happen. You must defer such work as far into the future as possible. Similarly, there are points in this project where careful state maintenance can help you avoid doing work. Whenever possible, avoid work. For example, if a page that is being evicted does not need to be written to disk, don't do so. (However, the victim selection algorithm in Section 4.4.1 must be used as specified; e.g. don't change the victim selection to avoid writing a page to disk). Note that you will need to maintain reference and dirty bits to defer work and to implement the clock algorithm. Since the MMU for this project does not maintain dirty or reference bits, your pager will maintain these bits by generating page faults on appropriate accesses. If you could possibly defer or avoid some action at the possible expense of making another necessary, keep in mind that incurring a fault (about 5 microseconds on current hardware) is cheaper than zero-filling a page (30 microseconds), which is in turn cheaper than a disk I/O (10 milliseconds). For instance, if you have a choice between taking an extra page fault and causing an extra disk I/O, you should prefer to take the extra fault. 5 Functions Used by External Pager This section describes the functions your external pager will use to carry out its tasks. Here is the file "vm_pager.h", which includes these utility functions and some constants you will need. ------------------------------------------------------------------------------- /* * vm_pager.h * * Combined header file for the external pager */ #ifndef _VM_PAGER_H_ #define _VM_PAGER_H_ #include /* * **************************************************** * * Interface for student portion of Project 2 pager * * **************************************************** */ /* * vm_init * * Called when the pager starts. It should set up any internal data structures * needed by the pager, e.g. physical page bookkeeping, process table, disk * usage table, etc. * * vm_init is passed both the number of physical memory pages and the number * of disk blocks in the raw disk. */ extern void vm_init(unsigned int memory_pages, unsigned int disk_blocks); /* * vm_create * * Called when a new process, with process identifier "pid", is added to the * system. It should create whatever new elements are required for each of * your data structures. */ extern void vm_create(pid_t pid); /* * vm_fault * * Called when process "pid" has a fault of type "type" at virtual address * "addr". Type is either EI_RDFAULT or EI_WRFAULT (defined below). */ extern void vm_fault(pid_t pid, char *addr, int type); /* * vm_destroy * * Called when process "pid" exits. It should deallocate all resources held by * process pid (page table, physical pages, disk blocks, etc.) */ extern void vm_destroy(pid_t pid); /* * vm_extend * * A request by process "pid" to add a new page of virtual memory to the * end of its arena. It should return the lowest-numbered byte of the newly * allocated memory. E.g. if the arena before calling vm_extend is * 0x60000000-0x60003fff, and the application calls vm_extend(), the return * value will be 0x60004000, and the resulting arena will be * 0x60000000-0x60005fff. vm_extend should return NULL if the disk is out * of swap space. */ extern char * vm_extend(pid_t pid); /* * vm_syslog * * A request by process "pid" to log a message that is stored in the process' * arena at address "message" and is of length "len". * * Should return 0 on success, EINVAL (defined in ) on failure. */ extern int vm_syslog(pid_t pid, char *message, unsigned int len); /* * ********************************************* * * Public interface for the disk abstraction * * ********************************************* * * Disk blocks are numbered from 0 to (disk_blocks-1), where disk_blocks * is the parameter passed in vm_init(). */ /* * disk_read * * read block "block" from the disk into physical memory page "ppage". */ extern void disk_read(unsigned int block, unsigned int ppage); /* * disk_write * * write the contents of physical memory page "ppage" onto disk block "block". */ extern void disk_write(unsigned int block, unsigned int ppage); /* * ******************************************************** * * Public interface for the physical memory abstraction * * ******************************************************** * * Physical memory pages are numbered from 0 to (memory_pages-1), where * memory_pages is the parameter passed in vm_init(). * * Your pager accesses the data in physical memory through the array * pm_physmem, e.g. pm_physmem[5] is byte 5 in physical memory. * Use pm_zerofill() to zero fill a page (rather than directly writing zeroes * to the pm_physmem array), so that these operations get logged properly. */ extern char * const pm_physmem; /* * Zero-fill a physical page */ extern void pm_zerofill(unsigned int ppage); /* * Mark the virtual page vpage in process pid's virtual address * space resident, associating it with physical page ppage. * * mode should be either PROT_READ (in which case the page will be * read-only) or PROT_READ | PROT_WRITE. These are defined in * . */ extern void pm_resident(pid_t pid, unsigned int vpage, unsigned int ppage, unsigned int mode); /* * Change permissions on process pid's virtual page vpage. * * mode should be either PROT_NONE (meaning leave the page resident, but * force a page fault on the next read or write), PROT_READ (in which * case the page will be read-only) or PROT_READ | PROT_WRITE. * These are defined in . */ extern void pm_chprot(pid_t pid, unsigned int vpage, unsigned int prot); /* * Make pid's virtual page vpage non-resident. */ extern void pm_nonresident(pid_t pid, unsigned int vpage); /* * ***************************** * * Miscellaneous definitions * * ***************************** */ /* codes for vm_fault()'s type parameter */ #define EI_RDFAULT 0x401 #define EI_WRFAULT 0x402 /* pagesize for the machine */ #define EX_PAGESIZE 8192 /* virtual address at which application's "arena" starts */ #define EX_ARENA_BASEADDR ((char *) 0x60000000) /* virtual page number at which application's "arena" starts */ #define EX_ARENA_BASEPAGE ((unsigned int) EX_ARENA_BASEADDR / EX_PAGESIZE) #endif /* _VM_PAGER_H_ */ ------------------------------------------------------------------------------- Physical memory is structured as a contiguous collection of N pages, numbered from 0 to N-1. It is settable through the -m option when you run the external pager (e.g. by running "pager -m 4"). The minimum number of physical pages is 2, the maximum is 128, and the default is 4. Your pager can read the data in physical memory via the array pm_physmem. Your pager can modify the data in physical memory only by calling pm_zerofill (and disk_read, described below); do not modify physical memory data via pm_physmem. Given a physical page number, pm_zerofill will initialize each the byte of the page with the ASCII character '0'. Your pager will communicate information about the virtual memory system to the infrastructure, just as a kernel communicates information about the virtual memory system to the hardware MMU. There are three functions your pager will use to communicate this information: pm_resident, pm_nonresident, and pm_chprot. pm_resident causes a physical page to be associated with a virtual page of some application process. It takes as arguments the process id (pid) of the application, the physical page that is being associated with this process, the virtual page in that process that this physical page is associated with, and the protection (read-only or read/write) that the page should be given. A read-only page allows loads but will fault on stores, while a read/write page allows both loads and stores to occur without faulting. A physical page can be associated with at most one virtual page in one process at any given time (no sharing). pm_nonresident disassociates the physical page currently associated with an application's virtual page. It takes as arguments the pid of the process from which to remove the association, and the virtual page number that is being made non-resident. Any access to an non-resident page (load or store) will generate a fault. pm_chprot is used to change the protections on a resident page (without making it non-resident). For example, if you want to make a page unreadable and unwritable so that the next load or store to it will generate a fault, you would call pm_chprot for that page with a protection argument of PROT_NONE. Likewise, if a page is protected as read-only, and you are handling a write fault on that page, you will eventually call pm_chprot for that page with a protection of (PROT_READ | PROT_WRITE). The pm_chprot operation takes the pid of the process with the virtual page in question, the virtual page number of the page to change, and the new protection for that page. The protection argument for pm_resident and pm_chprot should be PROT_READ if the page is being protected as read-only, (PROT_READ | PROT_WRITE) for pages that are both readable and writable, or PROT_NONE for pages that are neither readable nor writable (i.e. either loads or stores will generate faults). These constants are defined in the include file . The disk is modeled as a single device that is disk_blocks "blocks" long, where each disk block is the same size as a physical memory page. Your pager will use two functions: disk_read and disk_write. Arguments to each function are a disk block number and a physical page number. The disk_write function is used to write data from a physical page out to disk, and the disk_read function is used to read data from disk into a physical page. 6 Hints The first thing you should do is to write down a finite state machine for the life of a virtual page, from creation via vm_extend to destruction via vm_destroy. Ask yourself what events can happen to a page at each stage of its lifetime, and what state you will need to keep to represent each state. As you design the state machine, try to identify all of the places in the state machine where work can be deferred or avoided. A large portion of the credit in this project hinges on having this state machine correct. You may use any data structure you like to represent the page table of a process. Strive for a data structure that is efficient in time and space. E.g. it should allow fast lookups, and it should not take up much space for small processes. Use assertion statements copiously in your process library to check for unexpected conditions. These error checks are essential in debugging complex programs, because they help flag error conditions early. Read-faults should typically make the virtual page read-only, but NOT always. 7 Test Cases An integral (and graded) part of writing your pager will be to write a suite of test cases to validate any pager. This is common practice in the real world--software companies maintain a suite of test cases for their programs and use this suite to check the program's correctness after a change. Writing a comprehensive suite of test cases will deepen your understanding of virtual memory, and it will help you a lot as you debug your pager. To construct a good test suite, trace through different transition paths that a page can take through a pager's state machine, then write a short test case that causes a page to take each path. Each test case for the pager will be a short C++ application program that uses a pager via the interface described in Section 3 (e.g. the example program in Section 3). Each test case should be run without any arguments and should not use any input files. Your test suite may contain up to 20 test cases. Each test case may cause a correct pager to generate at most 64 KB of output and must take less than 60 seconds to run. These limits are much larger than needed for full credit. You will submit your suite of test cases together with your pager, and we will grade your test suite according to how thoroughly it exercises a pager. See Section 9 for how your test suite will be graded. Each test case will specify the number of physical memory pages to use when running the pager (the -m option) for the test case. This parameter will be communicated via the name of the test case file. Each test case should be of the following format: anyName.memoryPages.cc where memoryPages identifies the number of physical memory pages to use with the pager, and the parts are separated by periods. Remember that the minimum number of physical memory pages is 2 and the maximum is 128. You should test your pager with both single and multiple applications running. However, your submitted test suite need only be a single process; none of the buggy pagers used to evaluate your test suite require multi-process applications to be exposed. If you do want to try your hand at multi-process test cases, I suggest you run a parent process that then forks child processes to do the actual pager requests. The parent process can communicate with child processes by creating pipes before forking. We'll assume the entire set of application processes is done when the initial process exits, so it should exit after all the other application processes. Writing a correct multi-process test case is challenging (which is why we don't require multi-process test cases in the submitted test suite), but you'll learn some interesting things. 8 Project Logistics Write your pager in C++ on Solaris. Declare all global variables and functions "static" to prevent naming conflicts with other libraries. Use g++ (/usr/um/bin/g++) to compile your programs. You may use any functions included in the standard C++ library, including (and especially) the STL. You should not use any libraries other than the standard C++ library. To compile a pager "pager.cc", use the command "g++ pager.cc libvm_pager.a" (of course, you can add things like -g for debugging and -o to name the executable). You compile an application just like any other C++ program, except that you must link with libvm_app.a. E.g. "g++ app.cc libvm_app.a" Your pager must be in a single file and must be named "pager.cc". Here's how to run your pager and an application. First start the pager. It will print a message saying "Pager started with # physical memory pages", where "#" refers to the number of physical memory pages. After the pager starts, you can run one or more application processes which will interact with the pager via the infrastructure. The same user must run the pager and the applications that use the pager, and all processes must run on the same computer. We will place copies of vm_app.h, vm_pager.h, libvm_app.a, and libvm_pager.a in /afs/engin.umich.edu/class/perm/eecs482/proj2. You should make copies of these files and store them in your own directory so you can do "#include "vm_app.h" in your applications and "#include vm_pager.h" in your pager (without needing the -I flag to g++). 9 Grading, Auto-Grading, and Formatting To help you validate your programs, your submissions will be graded automatically, and the result will be mailed back to you. You may then continue to work on the project and re-submit. The results from the auto-grader will not be very illuminating; they won't tell you where your problem is or give you the test programs. The main purpose of the auto-grader is it helps you know to keep working on your project (rather than thinking it's perfect and ending up with a 0). The best way to debug your program is to generate your own test cases, figure out the correct answers, and compare your program's output to the correct answers. This is also one of the best ways to learn the concepts in the project. The student suite of test cases will be graded according to how thoroughly they test a pager. We will judge thoroughness of the test suite by how well it exposes potential bugs in a pager. The auto-grader will first run a test case with a correct pager and generate the correct output FROM THE PAGER (on stdout, i.e. the stream used by cout) for this test case. The auto-grader will then run the test case with a set of buggy pagers. A test case exposes a buggy pager by causing the buggy pager to generate output (on stdout) that differs from the correct output. The test suite is graded based on how many of the buggy pagers were exposed by at least one test case. This is known as "mutation testing" in the research literature on automated testing. You may submit your program as many times as you like. However, only the first submission of each day will be graded and mailed back to you. Later submissions on that day will be graded and cataloged, but the results will not be mailed back to you. In addition to this one-per-day policy, you will be given 3 bonus submissions that also provide feedback. These will be used automatically--any submission you make after the first one of that day will use one of your bonus submissions. After your 3 bonus submissions are used up, the system will continue to provide 1 feedback per day. Because your programs will be auto-graded, you must be careful to follow the exact rules in the project description: 1) Your code should not print any output other than that specified for vm_syslog. The pager infrastructure also prints messages to help you debug (and to allow the auto-grader to understand what the pager is doing); you can disable these messages by running the pager with the "-q" flag. 2) Do not modify the header files or libraries provided in the project directory. 3) Call the disk_ and pm_ routines rather than doing the work yourself; the auto-grader depends on statistics collected by these routines. 4) When allocating a physical page or disk block, your pager should use the lowest available free physical page or disk block. 5) Assign a disk block to a virtual page when it is created with vm_extend, then keep that disk block assigned to that virtual page until that application is destroyed. In addition to the auto-grader's evaluation of your programs' correctness, a human grader will evaluate your programs on issues such as the clarity and completeness of your documentation, coding style, the efficiency, brevity, and understandability of your code, etc.. Your pager documentation should give an overall picture of your solution, with enough detail that we can easily read and understand your code. You should present a list of all of the places in your solution that you deferred work; give both the event that you deferred, and the time at which you had to do the work. Your final score will be the the auto-grader score. Grader feedback is meant to help you write better code in the future, but is not graded due to its subjective nature. 10 Turning in the Project Use the submit482 program to submit your files. The full name is /afs/engin.umich.edu/class/perm/eecs482/bin/submit482, but you should add /afs/engin.umich.edu/class/perm/eecs482/bin/ to your path (see the FAQ) so you don't have to keep typing in the full name. submit482 submits the set of files associated with a project part, and is called as follows: submit482 ... Here are the files you should submit for each project part: 1) pager (project-part 2) a. C++ program for your pager (name should be "pager.cc") b. suite of test cases (each test case is a C++ program in a separate file). The name of each test case must follow the format described in Section 7. c. a file named "README", which contains a description of the contributions of each group member. example: submit482 2 pager.cc test1.4.cc test2.32.cc README The official time of submission for your project will be the time the last file is sent. If you send in anything after the due date, your project will be considered late (and will use up your late days or will receive a zero).