Out: Friday, May 22, 1998
Intermediate turn in: May 29, by midnight
Due: June 5, by midnight
This assignment is due by midnight on June 5. The intermediate turn-in is due by midnight May 29. By default you will work in the same groups as for Assignment #3, unless you have made other arrangements with the TA.
Intermediate Turn in
Note that there is an intermediate due date on May 29. For this you
will submit a snapshot of your assignment and include a file called STATUS
that describes the status of your assignment. For this turn-in you should
aim to be done with part 1 of the assignment, as well as the write-up describing
the design of your virtual memory system.
Using Assignment #3 Solutions
If you are not confident in your implementation of minithreads, you
may use our Assignment #3 solutions. The Assignment #4 distribution comes
with the minithread solution already installed, and you may replace it
with your own or use it as is. Note that you will have to make minor changes
if you do not use the stock Assignment #4 distribution. See the Appendix
to this assignment for more details.
The assignment is divided into three parts. The first two parts can be done in parallel, while the third part is dependent on the previous parts.
mv Assignment.xyz Assignment4.tar.gz
gunzip Assignment4.tar.gz
tar xvf Assignment4.tar
This will create the directory tree Assignment4 in the current directory
with the required files.
You will want to check out the Appendix
to Assignment #4 for lots of helpful hints and explanations.
We've modified the underlying simulator so that it also provides an interface to your minithreads package and support to plug in a VM system. We have provided two versions of mipsi. mipsi-orig has a functioning memory system with no support for virtual memory and mipsi will make use of the VM system you write. Use mipsi-orig for parts 1 and 2 and mipsi for part 3. The sources for these versions are in mipsi-orig-src and mipsi-src, respectively.
We've modified mipsi-orig and mipsi to route system calls and TLB-related exceptions to your operating system code, which we will refer to as mt_os. More details on mipsi can be found in the Appendix to this assignment. You will also want to read the source code for mipsi to understand how virtual memory exceptions and system call dispatch work in this simulator.
mipsi allows your operating system code (minithread and synchronization stuff) to execute in a protected fashion from all user code (e.g., MIPS programs like boundbuf in the USER subdirectory). The simulator executes all user programs one instruction at a time. All memory references are satisfied from a simulated physical memory, which is implemented with a large char array. For instructions that interact with the operating system, the simulator generates an exception, which is forwarded on to your operating system trap handler (look at mt_syscall() in mt-os/mt_os.c). Your trap handler inspects the event, and then routes the trap to the appropriate service routine, whether it be for system calls, interrupts, or virtual memory TLB misses or page faults.
Because your operating system code is now protected, user programs will not be able to call your system functions directly. Instead, they will take a trap, and the machine state will be available to the operating system. From this machine state, the operating system will need to figure out which function is being called (passed in a register) and the arguments (also passed in registers). See the Appendix to this assignment and surf the code for more details.
Another implication of this organization is that user programs and the operating system can no longer share memory directly. Thus, in your minithread and synchronization code where you were passing back pointers to memory, you will need to modify these interfaces to pass back handles. In addition, you will need to maintain a data structure internal to the operating system that maps between handles (what user programs see) and object references/pointers (what you deal with directly).
Clarification: You will need to have some way of distinguishing between handles to threads, semaphores, mutextes, etc. This is so that a user program can't crash your OS by, say, passing in a handle to a semaphore where a handle to a mutex is expected. Since most of the mt-os calls have no way of returning errors, when you detect that this has happened you may return from the system call immediately, or terminate the program cleanly, printing out an error message (much as with an access to an illegal address).
Incidentally, though using handles is usually a prudent safety measure, in the context of mipsi running on Alphas, it is absolutely essential for correctness. This is because DEC MIPS programs use 32-bit integers and pointers, whereas the Alpha architecture uses 64-bit pointers. Thus if you passed back pointers to user programs, the upper 32 bits would be discarded, and when the object reference was passed back to the kernel, it would be garbage (because the top 32 bits would be missing). This mismatch is the source of the compiler warnings you will see if you try to compile mt_thread.c without putting in place the handle/pointer conversion code.
You will use mipsi-orig for this part of the assignment. You need to modify mt_thread.c so that instead of returning and accepting addresses, the mt_os returns handles. This will require that you change some of the interfaces where types, such as semaphore_t, are described. See the Appendix to this assignment for more hints on handles.
For an example of how UNIX uses handles ("file descriptors" in UNIX), see p. 655-658, 677/678 in the Dinosaur Book.
Your mission: Add support for condition variables and mutexes to your basic thread package.
You need to add support for condition variables and mutexes to the thread package of Assignment #3. Your implementation should conform to the interface provided in the assignment distribution in include/mutex.h. Develop your implementation in the Assignment #3 setup (which you should be quite familiar with by now). Copy mutex.h into your Assignment #3 include directory and put your implementation of the interface in src/mutex.c. When you have finished, rewrite your applications from Assignment #3 (boundbuf and cigarette) to use the condition variables and mutexes instead of semaphores. You may want to browse "An Introduction to Programming with Threads" by Andrew Birrell. This paper describes the use of mutexes and condition variables (and programming with threads in general).
After completing this part, you will need to integrate the functionality provided in mutex.c into the mipsi environment. To do this, copy mutex.c to your Assignment #4 minithread directory and add the appropriate system calls to user_minithread.c, mt_os.h, mt_os.c and mt_thread.c. Hint: Look at how we added the semaphore routines to mipsi. Then you will need to test your mutex and condition variable facilities again in the mipsi environment. Put boundbuff and rain in the USER directory, add them to the Makefile, and compile them. This will produce MIPS executables which you can execute with your new and improved version of mipsi. Remember, for this part of the assignment you will probably want to use the original (pre-VM) version of MIPSI: mipsi-orig-src/mipsi-orig.
The MIPS architecture uses a software-managed TLB. That is, the OS is responsible for handing TLB misses, as well as page faults. For the last part of the assignment, we've provided you with another version of mipsi, where the simple memory system of mipsi-orig has been replaced with one that uses a translation lookaside buffer (TLB), much as in real MIPS processors. You will provide a virtual memory system.
As far as the user application is concerned, nothing has changed. Applications will continue to use the malloc function to allocate memory. Whenever the application accesses a piece of memory (using a virtual address), mipsi translates the virtual address into a physical address referring to a piece of simulated physical memory. The simulated physical memory is simply a two megabyte array: the char array Phys_Memory[] in mipsi-include/mem.h. Physical memory addresses are offsets into this array.
When the TLB is consulted to map a virtual address to a physical address, if the mapping is in the TLB (a TLB hit), an offset into the simulated physical memory is returned. Otherwise a MT_TLB_TRANSLATION_FAULT occurs.
When a MT_TLB_TRANSLATION_FAULT occurs, mipsi invokes mt_syscall(). We have arranged for mt_syscall() to read the offending virtual page number from a register and call mt_tlb_translate_fault() with this virtual page number as its argument. This function should return a TLB entry containing the the physical page number and protection flags for the given virtual page. Since you will write the body for this function, you may implement any sort of page-based virtual memory system you wish. mt_tlb_translate_fault() returns an entry that will be placed in the TLB, so that the TLB contains only entries for pages that are currently in memory.
The TLB also implements a write protect flag. An MT_TLB_WRITE_FAULT occurs whenever the application program attempts to write to a page that has this write protect flag set. When a MT_TLB_WRITE_FAULT occurs, mipsi invokes mt_syscall(), where we have arranged to call mt_tlb_write_fault() with the offending virtual page number as its argument. The return value for mt_tlb_write_fault() is the new value for the TLB protection flags. This facility can be used to keep track of which pages are "dirty" (modified), since mipsi provides no dirty bit in TLB entries.
You will need to define your own data structures for managing virtual to physical translations, as well as keeping track of where on disk pages can be found. You will need to write the code that translates virtual addresses (which have not been found in the TLB) into their associated page table entries. Note that this code may have to deal with the more complex case of an actual page fault (which implies that the page you require is not in physical memory). In this case, you'll need to determine which page to throw out of physical memory (remembering to save it to disk if it's been modified) and then bring in the new page. We are providing you with the interface and implementation for a simulated disk that let's you read and write blocks (see include/disk.h). You should use this disk as your backing store.
One thing you should keep in mind as you are implementing your virtual memory subsystem is that there are, in general, several threads executing in the user program concurrently, and thus each may suffer TLB misses and page faults concurrently.
Since a virtual memory system is a complicated thing, to help yourselves as you implement, and the TA as he grades, you should create a text file called README-VM inside the mt-os directory documenting the design of your virtual memory subsystem. Be sure to include an explanation of your data structures, an outline of what happens in the common cases (TLB miss, page fault, and write-protection violation), and brief description of your page replacement algorithm, how you deal with the possibility of concurrent virtual memory events, and any optimizations you implement involving dirty/clean pages or free and dirty page lists. This does not have to be long (think a paragraph or two for each of the above categories), but to encourage you to think before you code, this design document will count for around 20% of the assignment grade. Make sure you have a draft of README-VM for the intermediate turn-in.
Again, see the Appendix for more details.
turnin-hw mipsi-ito turn in the intermediate submission and use
turnin-hw mipsito turn in the final submission.