| CPSC 431 | Operating Systems | Fall 2009 |
In this (final) lab, you will implement a memory manager for the Larc operating system. Your memory manager will allow multiple processes to efficiently share physical memory, which will greatly improve the overall performance of the system. Your memory manager will use paging to place processes non-contiguously in memory, as well as to provide each process with a virtual address space that is disconnected from the size of physical memory.
This lab is due in three weeks and it has a weight of 3. The final version is due at the start time of the final exam, on Tuesday, December 15th at 8:30AM. However, a portion of this assignment will be due in lab in two weeks (December 8th, note: there is no checkpoint next week due to break). Important: like the file system and process manager lab assignments, this assignment is challenging so make sure you plan on spending a significant amount of time on it. In particular, this assignment will probably require more time testing than any of the previous assignments (although the amount of code you will have to write is not all that large).
Here are some details concerning various aspects of the lab assignment.
General. You will be implementing a memory manager, which will allow processes to efficiently share physical memory. Your memory manager will use paging to provide non-contiguous memory storage of processes. It also provides a virtual address space, which is not tied to physical memory.
The logical address space of each process will start at 0x0000 and end at 0x7C00. Obviously, since we are using paging, the address space will be broken up into several pages. To keep the page table small, we will use a page size (and frame size) of 1024 words. In a commercial system, we would use the entire addressable range (216 in our case), but limiting it to 0x7C00 allows us to save a process's address space on disk using the file system. Because the seek pointer in our file system must be non-negatative, this limits the maximum size to 0x7FFF and 0x7C00 is the largest address that is less than 0x7FFF but falls at a page boundary (divisible by 1024).
To simplify our implementation, only the user space in physical memory will be paged and not the kernel or I/O spaces. Here is the layout of memory:
|
|
User memory consists of 15 frames (a small number but then again our system is small), which can hold 15 pages from various processes. We will use an inverted page table (i.e., a page table with an entry per frame rather than per page) to store the translation from virtual addresses to physical addresses. Because the number of frames that are paged is small, we can store the entire inverted page table in a hardware cache rather than in memory (or worse, on disk). The page table will be stored in the translation lookaside buffer (TLB), which the CPU will use to translate virtual addresses used by the program into physical addresses. If the page is not in memory, then the CPU will trap to the operating system and the trap handler will invoke your memory manager to handle the page fault. The TLB is loaded via sofware, i.e., the OS updates it on a trap using memory-mapped I/O.
On a page fault, your memory manager will need to select a frame for holding the requested page. In this case, you may need to evict a page from some frame if none of the frames are empty. You will use the not recently used (NRU) page replacement policy to select a page to evict. Although this algorithm is not generally a good approximation of least recently used (LRU), it is simple to represent and has only two bits of state per page table entry: a bit indicating whether the page has been read and a bit indicating whether the page has been written. These bits are housed in the TLB and automatically updated by the CPU on a memory load, memory store, or control transfer.
You will be given a working version of the trap handler, I/O handler, file system manager, and process manager. They have been augmented to integrate with the memory manager, to provide support for page fault traps, and in other ways. Although you will not have source code for these modules, you can view the header (or interface) files (i.e., proc.h, fs.h, io.h). Note: there is no interface file for the trap handler as you won't need access to any of its functions.
Page table. The page table in our memory manager is a logical data structure, meaning we don't actually keep track of all of it in hardware, memory, and/or disk. Instead, we keep track of the pages that are just in physical memory, which can be viewed as an inverted page table. Because the amount of physical memory dedicated to user programs is small, this inverted page table is small and can be housed entirely in hardware (in a TLB as discussed below).
Process image files. Of course, when a page is not in the inverted page table, we need some way to find it on disk. For this, we will use a similar approach as in the last lab. Each process will have a process image file containing the logical address space of that process. When a page is on disk, your memory manager will go to this image file to find the page. Because the image file contains the entire logical address space, your memory manager can seek to the virtual address of the start of the requested page, and then read a page into memory from the file. Likewise, when writing an evicted page from physical memory to disk, we can write the image file by seeking to the virtual address of the start of the evicted page, and writing a page from memory to the image file.
The process image files will be named similarly as in the previous lab: /proc/<pid> where <pid> is replaced with the PID of the process. These are automatically created and removed by the process manager (similar to what you did in the previous lab although a few optimizations have been added). You just need to make sure you update them on a page fault or on a page save (which occurs on a fork).
TLB. The inverted page table will be stored entirely in the translation lookaside buffer (TLB) in hardware. The TLB has an entry per frame in user space and is ordered by frame number. As a result, the frame number does not have to be stored in an entry (TLB entry 0 houses the translation information for user frame 0, and so forth). Of course, because the TLB is ordered by frame number and not by page number the CPU must search all of its contents to find a match (i.e., it is fully associative). If the requested page is found, then the translation is performed (the upper bits of the physical address are implicit in the matched TLB entry). If a page is not found, the CPU traps to the operating system, which uses your memory management module to service the miss in software. Because there is a TLB entry per physical user frame, a miss in the TLB implies a page fault. So your memory manager will need to bring the page in from disk as well as update the TLB.
The TLB is read and written using memory-mapped I/O. To manipulate a particular TLB entry, one can read or write the following memory addresses:
| tlbv0 | TLB entry 0 | 0xFE0F |
| tlbv1 | TLB entry 1 | 0xFE10 |
| tlbv2 | TLB entry 2 | 0xFE11 |
| ... | ... | ... |
| tlbv14 | TLB entry 14 | 0xFE1E |
In the operating system I/O module header file (io.h), there are macros for accessing these entries. The macro TLB_START_ADDR holds the memory-mapped address of the first TLB entry and TLB_END_ADDR holds one more than the address of the last TLB entry.
Each TLB entry is a 16-bit word made up of the following:
| V? | Page number | PID | W? | R? |
| 1 | 7 | 6 | 1 | 1 |
On the far left, the highest order bit, is a valid flag (V?), which indicates whether this TLB entry contains a valid page table entry. After that is the page number (in 7 bits although the high order bit is always 0) of the page housed in the corresponding frame (assuming the TLB entry is valid). After that is the PID of the owner process (in 6 bits). Finally, on the far right, are two bits, which indicate whether the page referred to by this TLB entry has been read and/or written.
Memory protection. Each TLB entry contains the PID of the owning process. This is to protect pages owned by one process from being read or written by a different process as all the processes are now sharing physical memory. Whenever the TLB is searched for a page, the PID of the currently running process must match the PID in the TLB entry. The CPU searches the TLB for an entry with the corresponding page number, valid bit set to 1, and PID equal to the current PID.
Page faults. As mentioned above, a page fault occurs when the CPU is unable to find a match in the TLB. In this case, the CPU performs a trap into the operating system. The CPU writes the virtual address to a memory-mapped register called pfault_addr (0xFE1F) where it can be retrieved by the trap handler. The trap handler gets this address and then passes it along to the memory manager, which can service the page fault, bringing in the requested page, and, potentially, evicting another page.
NRU page replacement. To select a page to evict, you will use the not recently used (NRU) page replacement policy. In particular, the CPU keeps track of whether a page in physical memory has been read or written by setting some bits in the corresponding TLB entry. Your memory manager will use these bits to determine if a page was read or written between the last page fault and the current one. In picking a page to replace it will use the following priorities:
Unused frames. If there are any unused frames (i.e., TLB entries that are marked invalid), these should be filled before evicting a frame with a valid page in it.
Untouched frames. Frames that have not been read or written since the last page fault should be selected next.
Read but unmodified frames. Frames that have been read but not written since the last page fault should be selected next.
Modified but unread frames. Frames that have been modified but not read since the last page fault should be selected next. If a modified page is selected, it will need to be written back to disk.
Read and modified frames. Finally, a frame that is read and modified should be selected if there are no other frames in the classes above. If a modified page is selected, it will need to be written back to disk.
At every page fault, your memory manager will reset the read and write bits in the page table entry in the TLB so that you can perform the same analysis at the next page fault. You will need to remember any modified frames that you reset so that you can write them back to disk if they are evicted later on. For example, a page that is written between page fault 1 and page fault 2 but then not accessed between page fault 2 and page fault 3 might be selected for replacement during page fault 3 as its read and write bits will be 0. But it must be written back to disk since it was modified between page fault 1 and page fault 2.
If there are ties when performing NRU, you can arbitrarily select a frame, however, when applicable, you should select a page that will not need to be written back to disk. For example, if considering evicting page A and B, which were both read but not written between the last two page faults, you should look at whether either page has ever been written. If A was written at some point in the past but B was not, then you should select B for replacement.
Memory functions. Your memory manager will need to support several functions, which will be called by other parts of the operating system. These include:
minit: a function for initializing the memory manager. This function is called by the trap handler at boot time. It will need to set up all of the page table entries in the TLB. Initially, each page table entry should be valid, unwritten, unread, and belong to the core application (PID 0), which starts in physical memory. Each page table entry will also need to contain the correct page number (you will need to figure out what that is).
mget_real_addr: a function for converting virtual addresses into physical addresses. It takes the virtual address and PID of the current process as parameters and returns the corresponding physical address or -1 if the page containing the address is not in physical memory.
This function is called by the trap handler so that it can pass other OS modules (e.g., the file system) physical addresses rather than virtual addresses. In addition, the trap handler can also use this function to determine when a page fault has occurred due to an address specified within a system call. (If the address wasn't actually loaded or stored, but rather provided in a system call, such as fread, it would not necessarily have caused a page fault trap.)
mfault: a function for servicing page faults. This function is called by the trap handler whenever a page fault trap occurs. This function takes as a parameter the the faulting virtual address and the PID of the current process. It should bring the requested page into memory from the process image file on disk, evicting another page using the NRU page replacement policy. If the evicted page has been modified then it will need to be written back to the process image file on disk.
This function should also clear the read and write bits of the page table entry in the TLB so that the NRU page replacement policy is always considering only the most recent window of memory references. However, because of this, your function will need to keep track of modified pages so that if any are later evicted they will be written back to disk.
msaveall: a function for saving all of the modified pages of a process to disk. This function takes as a parameter the PID of some process and saves all the valid, modified pages of that process to the corresponding process image file on disk.
This function is called by the process manager on a fork to synchronize the parent process's image file with memory. This is necessary because on a fork the parent's image file must be copied to the child's image file and physical memory cannot be used as in the previous lab since some of the parent's address space might be on disk rather than physical memory.
mevictall: a function for evicting (and not saving to disk) all of the pages of a specified process. This function takes the PID of the process as a parameter and invalidates any valid page table entry in the TLB belonging to this process. It should not write back modified pages to disk.
This function is called by the process manager whenever a process is terminated or an exec occurs. Because the process is either completed or will no longer need this memory any more (on an exec), the modified pages do not have to be written back to disk.
mswitch_pid: a function for switching the PID stored in a TLB entry. This function takes an old PID, a new PID, and a page number. It should check to see if the specified page is in the TLB, is a valid entry, and contains the old PID. If such an entry is found, then this function switches the PID to the new PID leaving all other parts of the TLB entry alone. In this case, the function returns true indicating it was successful. Otherwise, it returns false indicating failure.
This function is used by the process manager to allow for page sharing between processes. Currently, this feature is only used for implementing copy on write (for optimizing fork) when enabled. Although copy on write is currently disabled we may enable it later on (you will need a lib.s patch to enable it), which will greatly improve the performance of fork. However, this function is still required even if copy on write is left disabled.
As in the last two labs, this lab will require a significant amount of coding and design (as well as a substantial amount of testing). Make sure you take some time to carefully plan out your implementation. As in the last three assignments, we will be writing our memory manager using C--. See lab 4 for details on C--.
The operating system consists of several modules. We implemented four in the last three labs: trap.c, io.c, fs.c, and proc.c. You will not need to modify these in this lab. In fact, you will not have access to the implementation of these modules (the .c files), just the header files (the .h files -- there is no header file for the trap handler module although there is a system-wide header file os.h). Note: trap.c and proc.c have been extended to integrate with your new memory manager.
There are also two auxiliary modules: util.c, which contain some utility code and strings.c, which contains code for manipulating strings. You should not need to modify these modules either, although you could potentially add functions to them if needed. Both the .c files and .h files are provided.
The last module is the most critical for this lab: mem.c. This module contains the code implementing the memory manager. It is largely incomplete. You will complete it in this lab (note: until this code is more or less completed, the OS will not work correctly). At the very least, you will need to implement the functions listed above under the heading "Memory manager functions" in the section titled Lab Details. You will probably also want to write some additional functions to avoid code redundancy and complexity. For example, you might find it helpful to create the functions for doing the following:
Note: this list is by no means exhaustive. Feel free to organize your code in any way you see fit so long as it is readable by others.
One thing that makes this lab more challenging than any of the prior labs is that it is difficult to do incrementally. With some cleverness, you may be able to test aspects of it incrementally, but for the most part you will find this infeasible. So make sure you design and implement your code more carefully than in previous labs, and that you allocate even more time for testing. Be prepared to spend a significant amount of time testing your implementation.
Create a lab07 directory within your ~/cs431 directory (which you created in lab 1) for use in this lab assignment. Change to the newly-created lab07 directory. Then execute the following command:
bash$ make -f /classes/f09/cs431/labs/lab07/Makefile start
This command creates several files and directories you will need. In particular, it creates a Makefile for building your OS and for handing in the lab assignment; several C files for the OS, one of which must be completed in this lab; an assembly file containing some pre-compiled portions of the operating system (the trap handler, I/O handler, file system, and process manager); and a directory tests with several test programs.
To compile your operating system, you can execute the following command from your lab07 directory:
bash$ make
Note: you can also compile it without the Makefile. It's somewhat complicated but look in the Makefile for details on doing this.
Inside the directory tests are several test programs including a process test program, a (multi-processed) interactive shell program, and a non-interactive shell program. These are basically the same test programs that were included in the test programs from the previous lab (although there are a few small differences). See lab 6 for more details on these test programs.
During the course of testing your operating system, you may find that your file system and disk get corrupted (after all there is no journaling in our file system). If that occurs, then you can reload the original disk file by doing the following (this will take several seconds to complete):
bash$ make disk
One nice aspect of testing in this lab is that the memory manager will significantly speed up the test programs (although programs will still take a few seconds to execute). For instance, the context switch time has been reduced from 10 seconds to 1 second. So your test programs should run a lot faster.
Answer the following non-technical questions regarding your thoughts on this assignment. These are required so make sure you do them. Put them in a file called answers.txt within your lab07 directory.
As mentioned in the syllabus, multi-week projects will have checkpoints. Although this is a three-week lab, a portion of the lab will be due in lab in two weeks (there is no checkpoint next week due to break) to ensure that you are keeping up with the workload. In particular, you must finish writing all of the functions listed above for the checkpoint, although they need not be 100% correct. This will leave you with an entire week in which to test (and fix) your implementation, as well as complete anything that wasn't done in the first two weeks.
When you have completed the checkpoint, you should submit it, by following the procedure outlined below underneath the handin header (i.e., "make submit"). You can resubmit a checkpoint at any point before the due date, however, you cannot turn in a checkpoint late (although one checkpoint will be dropped at the end of the semester).
For this project, each checkpoint will be worth 5% of your total grade for this lab (for a total of 10%).
This lab assignment is due in 3 weeks, at the start of the final exam on Tuesday, December 15th at 8:30AM, although part of your solution is due in two weeks (see the Section on checkpoints above). In particular, you need to complete the file mem.c. When you are ready to submit your solution, verify that your lab07 folder contains all of the files you created or modified for this assignment, then move to your lab07 directory, and execute the following command:
bash$ make submit
This command will copy all of the files in your lab07 directory to your handin folder, which is located at /classes/f09/cs431/handin/<username>/lab07) where <username> is replaced with your username.
Note: you can do this more than once, however, be aware that it will overwrite your previously submitted files, each time you issue this command.