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).
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 (
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
subdirectory. For this assignment, you will build your Nachos executable in the
userprog/ subdirectory instead of in
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
machine/machine.h that defines your kernel's interface to
the simulated machine.
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
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.
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
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.
test/subdirectory. In particular, do not remove the file called
scriptor any other files used by the build process.
int z=x+y; return z;" instead of "
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
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
BitMapclass if it helps. Also use synchronization primitives you built in assignment #3 when needed.
AddrSpaceto allow multiple processes to be resident in the machine memory at the same time. The existing
AddrSpaceconstructor code assumes that all of the machine memory is free, and it loads the new process contiguously starting at page frame 0. You must modify this scheme to use your memory manager to allocate page frames for the new process, and load the process code and data into those allocated page frames, which may not be contiguous. This step is a bit tricky. It might be helpful to take a look at the routine at
userprog/loadpage.hint. Although this piece of code is part of a working solution I developed, it might not be suitable for you. Use at your own risk.
AddrSpaceto call the memory manager to release the pages allocated to a process when the process is destroyed (see below).
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
Part II: process management.
Join system calls. If an executing user process requests a
system call, the machine will transfer control to your kernel by calling
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
Execcall returns, your kernel should have created a new process and started a new thread executing within it to run the specified program. Note that this semantics equals to combined
exec()system calls on Linux. You do not need to concern yourself with I/O until the next assignment. For now, you will be able to run user programs, but they will not be able to read any input or write any output.
Exec, you must copy the filename argument from user memory into kernel memory safely, so that a malicious or buggy user process cannot crash your kernel or violate security. The filename string address (char*) passed into the kernel as an argument is a process virtual address; in order for the kernel to access the filename it must locate the characters in the kernel address space (i.e., in the machine's physical "main memory" array) by examining the page table for the process. In particular, your kernel must handle the case where the filename string crosses user page boundaries and resides in noncontiguous physical memory. You must also detect an illegal string address or a string that runs off the end of the user's address space without a terminating null character. You may impose a reasonable limit on the maximum size of a file name.
Execmust return a unique process identifier (SpaceId), which can be used as an argument to
Join. Your kernel will need to keep a table of the active processes. Use synchronization primitives you built in assignment #3 when needed.
Exitshould not return back to the user program. Instead, it should destroy the calling thread (e.g.,
Exitsystem call handler, rather than calling the lower-level procedures directly from
ExceptionHandler. This will make it easier to kill a process from inside the kernel (e.g., if the process has some kind of fatal error), by calling the internal exit primitive from another kernel procedure (e.g.,
ExceptionHandler) in the target process context. In general, this kind of careful internal decomposition will save you from reinventing and redebugging wheels, and it is always good practice.
Joinsystem call correctly. The kernel
Joinprimitive must validate any SpaceId passed to it by a user process. It must also validate that the calling process has privilege to join; in this case, the caller must be the parent of the target process. Finally, your
Joinimplementation must correctly return the exit status code of the target process.
Joincorrectly and efficiently, you will need to keep a list of all children of each process. This list should be maintained in temporal order, so that you can always determine the most recently created child process. This will be necessary when you implement pipes in a future assignment.
Exitis tricky. Be sure you handle the case where the joinee exits before the joiner executes the
Join. Your kernel should also clean up any unneeded process state if
Joinis never called on some process. Try to devise the simplest possible synchronization scheme for the code and data structures that manage process relationships and
Exit/Join, even if your scheme is inefficient. One possibility might be to use broadcasts on a single condition variable shared by all processes in the system.
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
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.
ExecN times from each parent process, and join on all children before exiting. Since
Execas defined provides no way to pass arguments into the new process, you may hard-code M and N into your test programs as constants, and you may use multiple versions of the programs with different constants encoded within them.
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.
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.