Programming assignment #4 - Supporting Multiple User Programs

Due by 11:59pm, Thursday, March 22.

The managing TA for this assignment is Daniel Mullowney. All email inquiries about this assignment should be addressed to the TA and the instructor.

This is a group assignment. You should form a group of two (or three under rare circumstances) to complete this assignment. You can form the same group as in assignment #3. Note that we will not distinguish grades within a group. You are advised to use CVS or other version control software to manage your source code. Discuss with your group members early to establish safe and flexible policies for managing your code. Again, you are encouraged to help (and seek help from) people in other groups (except sharing code, of course).

Assignment background

All the code you wrote in assignment #3 is part of the Nachos operating system kernel. In a real operating system, the kernel not only uses its procedures internally, but allows user programs to access some of its routines via "system calls".

The goal of this assignment is to extend Nachos with basic process management primitives to support multiple processes executing user programs on the simulated machine, using system calls to request services from the kernel. Since your kernel does not trust user programs to execute safely, the kernel and the simulated hardware will work together to protect the system from damage by malicious or buggy user programs. To this end, you will implement simple versions of key mechanisms found in real operating system kernels: virtual addressing, protected system calls, exception handling, and preemptive time-slicing. Virtual addressing prevents user processes from accessing kernel data structures or the memory of other programs; your kernel will use process page tables to safely allow multiple processes to reside in memory at the same time.

Most of the basic infrastructure for supporting multiple user programs is already in place. In particular: (1) the thread system and timer device already support preemptive time-slicing of multiple threads; (2) the thread context switch code already saves and restores MIPS machine registers and the process page table; and (3) the Nachos distribution (StartProcess in userprog/progtest.cc) includes skeletal code to set up a new user process context, load it from an executable file, and start a thread running in it. Most of the new files to look at are in the userprog/ subdirectory. For this assignment, you will build your Nachos executable in the userprog/ subdirectory instead of in threads/: be sure that you build and run the "right" nachos. The Nachos system call interface is defined in userprog/syscall.h. Also, be sure to read the material in the Nachos introduction page and machine/machine.h that defines your kernel's interface to the simulated machine.

User programs for the Nachos kernel

From this assignment forward, we start to deal with user programs. You can find some example user programs in the test/ subdirectory. Although user programs for a Nachos kernel can be written in C, they must be compiled into executables for the MIPS R2000 architecture in order to run on the simulated machine in Nachos. In case you wonder why, running user programs on a simulated machine gives Nachos complete control over how many instructions are executed, how address spaces work, and how interrupts and exceptions (including system calls) are handled.

Because the user programs are compiled for the MIPS architecture, they will not run directly on the x86 host that you run Nachos on. In fact, since they use Nachos system calls rather than UNIX system calls, they cannot even execute correctly on a real MIPS CPU running a real operating system such as SGI IRIX or DEC Ultrix. They are built specifically to execute under Nachos. The bizarre nature of these executables introduces some special considerations for building them. The Makefile in the test/ subdirectory takes care of the details of producing the Nachos user program executables. User programs are compiled using a gcc cross-compiler that runs on Linux/x86 but generates code for the MIPS processor. The compiled code is then linked with the MIPS assembly language routines in start.s. Finally, the programs are converted into a MIPS executable file format called NOFF, using the supplied program coff2noff.

The Nachos distribution includes several sample test programs. For example, look at test/halt.c, which simply asks the operating system to shut the "machine" down using the Nachos Halt system call. Run the halt program with the command nachos -x ../test/halt in the userprog/ subdirectory. (Check the comments in threads/main.cc for the semantics of the "-x" flag.) It may be useful to trace the execution of the halt program using the debug flag. The test/ subdirectory includes a few other simple user programs to test your kernels. However, none of them will work until you complete certain part of this assignment. We also expect you to extend these tests and add some of your own.

Troubleshooting user programs:
Some students have difficulty building and running new test programs, and may even spend lots of good sleeping time trying to track down "Nachos bugs" that were actually bugs in their test programs. The following guidelines will help you to avoid trouble.

Assignment requirements in detail

This assignment contains four parts: (1) address space management; (2) process management; (3) exception handling; (4) testing your kernel. There is no additional CSC456 part in this assignment.

Part I: address space management.
You will need basic facilities to load processes into the memory of the simulated machine. Spend a few minutes studying the AddrSpace class and the StartProcess procedure in userprog/progtest.cc. The current code works OK, but it assumes that there is only one program/process running at a time (started via the nachos -x option), and that all of the machine's memory is allocated to that process. Your job is to generalize this code for multiple simultaneous processes:

Note: What should your kernel do if there are not enough free page frames to back the address space for a new process? In a later assignment ("virtual memory") you will add support for "juggling" to allocate physical page frames on demand. For now it is acceptable to fail the Exec. Note that "failing Exec" doesn't mean "crashing the kernel", so having an ASSERT statement (as it is right now) is not acceptable. Make sure that your AddrSpace code releases any frames allocated to the process when Exec fails.

Part II: process management.
Implement the Exec, Exit, and Join system calls. If an executing user process requests a system call, the machine will transfer control to your kernel by calling ExceptionHandler in usrprog/exception.cc. Your kernel code must extract the system call identifier and the arguments from the machine registers, decode them, and call internal procedures that implement the system call. Here are some issues to attend to for implementing system calls in Nachos.

Note on returning errors from system calls: One of the broken things about Nachos is that it does not provide a clean way to return system call errors to a user process. For example, UNIX kernels return system call error codes in a designated register, and the system call stubs (e.g., in the standard C library or in start.s) move them into a program variable, e.g., the global variable errno for C programs. We are not bothering with this in Nachos. What is important is that you detect the error and reject the request with no bad side effects and without crashing the kernel. One suggestion is that you report errors by returning a 0 or -1 value where possible, instead of returning a value that could be interpreted as a valid result. If there is no clean way to notify the user process of a system call error it is acceptable to simply return from the call and just let the user process struggle forward.

Part III: exception handling.
The operating system kernel should be "bullet-proof"-ed from user program (or compiler) errors. There should be nothing that a user program can do to crash the operating system. Implement the Nachos kernel code to handle user program exceptions that are not system calls. The simulated MIPS machine raises an exception whenever it is unable to execute the next user instruction, e.g., because of an attempt to reference an illegal address, a privileged or illegal instruction or operand, or an arithmetic underflow or overflow condition. The kernel's role is to handle these exceptions in a reasonable way, i.e., by printing an error message and killing the process rather than crashing the whole system. Note: an ASSERT that crashes Nachos is a reasonable response to a bug within your Nachos kernel, but it not an acceptable response to a user program exception.

Part IV: testing your kernel.
Test your code by exercising the new system calls from user programs. To test your kernel, you will create some simple user programs.

Create more test programs if possible. We may award you extra credits when we see good test programs.

Administrative policies

Turn-in:
You are asked to electronically turn in a copy of the complete Nachos source tree. Include the test user programs you created for testing. Do not turn in any executables, object files, or things like that. Add enough comments in your code to make your changes easy to understand. Attach a README file describing the files you changed/added and anything else special you want us to know. The README file should be in plain text format. Instructions for electronic turn-ins can be found on the class Web page.

Grading guideline:
Below is a tentative grading guideline. Note that we will actually read your code. Your turn-in will be graded not only on its correctness, but also on the completeness and clarity of your comments.

Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.