Project Assignment #2: Multiprogramming

CSE 451

Due Friday, May 12, 2000, at 11:59 pm

Note - Here is the new Makefile for the test directory.

The second phase of Nachos is to support multiprogramming. As in the first assignment, we give you some of the code you need and 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 also allows user-level programs to access some of its routines via “system calls”.

 The first step is to read and understand the part of the system we have written for you. The new code is spread over several directories. There are some new kernel files in “userprog”, there are a few additional machine simulation files in “machine”, and a stub file system in “filesys”. The user programs are in “test”, and utilities to generate a Nachos loadable executable are in “bin”. Since Nachos executes MIPS instructions (and there aren’t very many MIPS machines left!), we also provide you a cross-compiler. The cross-compiler runs on Linux and compiles user programs into MIPS format.

The code we provide can run a single user-level “ C” program at a time. As a test case, we’ve provided you with a trivial user program, “halt”. All “halt” does is to turn around and ask the operating system to shut the machine down. To run the “halt” program, make and then run Nachos in the “userprog” directory. Trace what happens as the user program gets loaded, runs, and invokes a system call.

You may find the road map to Nachos helpful. Also, it is OK to change the constants in “machine.h” if it helps you design better test cases. For example, you can change the amount of physical memory. The code for this part of the project is enabled by the USER_PROGRAM compiler macro. The files for this assignment include:

In this assignment we are giving you a simulated CPU that models a real CPU. In fact, the simulated CPU is the same as the real CPU (a MIPS chip), but we cannot just run user programs as regular UNIX processes, because we want complete control over how many instructions are executed at a time, how the address spaces work, and how interrupts and exceptions (including system calls) are handled.

Our simulator can run normal programs compiled from C -- see the Makefile in the `test' subdirectory for an example.  The compiled programs must be linked with some special flags, and then converted into Nachos format, using the program ``coff2noff'' (which we supply). The only caveat is that floating-point operations are not supported.

  1. Implement system call and exception handling.  You must support some of the system calls defined in syscall.h: halt, exit, exec, join, read, and write. You can also implement thread fork and yield for extra credit.  Additionally, you are only required to implement Read and Write for console reads and writes, not for file reads and writes.  We have provided you an assembly-language routine, ``syscall'', to provide a way of invoking a system call from a C routine (UNIX has something similar -- try `man syscall'). You'll need to do part 2 of this assignment in order to test out the `exec' and `wait' system calls.

    You will also need to implement a detach system call for this project. You may imagine that if a process is forked and is never joined, we won't know when to clean up its state. It is the forking thread's responsibility to make the detach system call to ensure that when the forked thread finishes, the OS can clean up all the state if the forked thread is not to be joined. This detach system call can be implemented by passing the process ID of the forked thread as the argument, which the OS will then use to adjust the forked threads PCB appropriately. To implement this reasonably, only the forking thread should be allowed to make a detach system call that affects a forked thread.

    Note that you will need to ``bullet-proof'' the Nachos kernel from user program errors -- there should be nothing a user program can do to crash the operating system (with the exception of explicitly asking the system to halt).  (We will provide more details on how to bullet-proof the kernel soon). Also, to support the system calls that access the console device, you will probably find it helpful to use the ``SynchConsole'' class that provides the abstraction of synchronous access to the console.  This may need updating for your needs.

  2. Implement multiprogramming.  The code we have given you is restricted to running one user program at a time. You will need to: (a) come up with a way of allocating physical memory frames so that multiple programs can be loaded into the nachos machine's memory at once (cf. bitmap.h), (b) provide a way of copying data to/from the kernel from/to the user's virtual address space (now that the addresses the user program sees are not the same as the ones the kernel sees), and (c) add synchronization to the routines that create and initialize address spaces so that they can be accessed concurrently by multiple programs. Note that scheduler.cc now saves and restores user machine state on context switches.  You will need to make sure that user programs can't disrupt either the kernel or other user programs. You will probably want to write some test programs beyond those provided in the test directory and to use the “shell” provided in the “test” subdirectory to verify that the system call handling and multiprogramming are working properly. (The shell may need enhancing, if I recall correctly.)

  3. The current version of the “exec” system call does not provide any way for the user program to pass parameters or arguments to the newly created address space. UNIX™ does allow this, for instance, to pass in command line arguments to the new address space. Implement this feature.

  4. Implement interprocess communication using pipes. This will redirect the output of one process to the input of another. Since you are not required to implement file reads and writes, this will be the only way to pass information to a process, aside from command line arguments. An example of a unix pipe would be "program1 | program2" In this example, program1 would normally output text to the standard output, but the pipe will redirect this output to the input of program2. program2 would normally take its input from a file. This problem will require some imagination since files do not exist, but shouldn't be too difficult to implement.

  5. (Extra Credit) Implement multithreaded user programs. Implement the thread fork() and yield() system calls to allow a user program to fork a thread to call a routine in the same address space, and then ping-pong between threads.  (Hint: you will need to change the kernel to allocate memory in the user address space for each thread stack.)

 

All the code you write should be well commented so we can understand what you changed. To hand in code, one of the members of your project should use the turnin command:

To turnin a set of files or directories, run:

turnin –ccse451 –puserprog {list of files or directories to turnin)

For example, to turnin all the files in the “code” directory, you would run this command in the “nachos-4.0” directory:

turnin –ccse451 –puserprog code

To see which files were turned in, run: :

turnin –ccse451 -v

You should hand in all the code you changed, and test programs you wrote and their outputs, and a file named “readme” containing your group name and the members of the team. In addition, we would like a short paper write-up describing what changes you made, how well they worked, how you tested your changes, and how each group member contributed to the project. The write-up should be mailed to the TA by 11:59pm on May 13th, so that you won’t need to worry about working on it just before the code is due.