Phase 2: Multiprogramming

The second phase of Nachos is to support multiprogramming. As in the first assignment, we give you some of the code you need; your job is to complete the system and enhance it. Up to now, all the code you have written for Nachos has been part of the operating system kernel. In a real operating system, the kernel not only uses its procedures internally, but allows user-level programs to access some of its routines them via system calls.

The first step is to read and understand the part of the system we have written for you. The kernel files are in the nachos.userprog package, and there are a few additional machine simulation classes that get used:

The new kernel files for this assignment include:

In this assignment we are giving you a simulated CPU that models a real CPU (a MIPS R3000 chip). By simulating the execution, we have complete control over how many instructions are executed at a time, how the address translation works, and how interrupts and exceptions (including system calls) are handled. Our simulator can run normal programs compiled from C to the MIPS instruction set. The only caveat is that floating point operations are not supported.

The code we provide can run a single user-level MIPS program at a time, and supports just one system call: halt. All halt does is ask the operating system to shut the machine down. This test program is found in test/halt.c and represents the simplest supported MIPS program.

We have provided several other example MIPS programs in the test directory of the Nachos distribution. You can use these programs to test your implementation, or you can write new programs. Of course, you won't be able to run the programs which make use of features such as I/O until you implement the appropriate kernel support! That will be your task in this project.

The test directory includes C source files (.c files) and Nachos user program binaries (.coff files). The binaries can be built while in the test directory by running gmake, or from the proj2 directory by running gmake test.

To run the halt program, go to the test directory and gmake; then go to the proj2 directory, gmake, and run nachos -d ma. Trace what happens as the user program gets loaded, runs, and invokes a system call (the 'm' debug flag enables MIPS disassembly, and the 'a' debug flag prints process loading information).

In order to compile the test programs, you need a MIPS cross-compiler. This is already installed on the instructional machines as mips-gcc (see the Makefile in the test directory for details). If you are not using an instructional machine, you must download the appropriate cross-compiler and set the ARCHDIR environment variable accordingly.

There are multiple stages to building a Nachos-compatible MIPS binary (all of which are handled by the test Makefile):

  1. Source files (*.c) are compiled into object files (*.o) by mips-gcc.
  2. Some of the object files are linked into libnachos.a, the Nachos standard library.
  3. start.s is preprocessed and assembled into start.o. This file contains the assembly-language code to initialize a process. It also provides the system call "stub code" which allows system calls to be invoked. This makes use of the special MIPS instruction syscall which traps to the Nachos kernel to invoke a system call.
  4. An object file is linked with libnachos.a to produce a Nachos-compatible MIPS binary, which has the extension *.coff. (COFF stands for Common Object File Format and is an industry-standard binary format which the Nachos kernel understands.)
  5. Note that if you create a new test file (*.c), you will need to append your program name to the variable TARGETS in the Makefile inside test directory

You can run other test programs by running

  nachos -x PROGNAME.coff
where PROGNAME.coff is the name of the MIPS program binary in the test directory. Feel free to write your own C test programs -- in fact, you will need to do so for testing your own code!

As with Phase 1, you should submit and document your test cases (for both the Java and C components of your code) with the project. For this project most test cases will be implemented as C programs which test your system calls, but some "internal" testing in Java may be possible as well.

  1. (30%, 125 lines) Implement the file system calls (creat, open, read, write, close, and unlink, documented in syscall.h). You will see the code for halt in; it is best for you to place your new system calls here too. Note that you are not implementing a file system; rather, you are simply giving user processes the ability to access a file system that we have implemented for you.

  2. (25%, 100 lines) Implement support for multiprogramming. The code we have given you is restricted to running one user process at a time; your job is to make it work for multiple user processes.

  3. (30%, 125 lines) Implement the system calls (exec, join, and exit, also documented in syscall.h).

  4. (15%, 50 lines+existing priority scheduler) Implement a lottery scheduler (place it in threads/ Note that this class extends PriorityScheduler, you should be able to reuse most of the functionality of that class; the lottery scheduler should not be a large amount of additional code. The only major difference is the mechanism used to pick a thread from a queue: a lottery is held, instead of just picking the thread with the most priority. Your lottery scheduler should implement priority donation. (Note that since this is a lottery scheduler, priority inversion can't actually lead to starvation! However, your scheduler must do priority donation anyway.)