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 (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.
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.
test/
subdirectory.
In particular, do not remove the file called script
or any
other files used by the build process.int z=x+y; return z;
" instead of
"return (x+y);
".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:
BitMap
class if it helps. Also use synchronization primitives
you built in assignment #3 when needed.AddrSpace
to allow multiple processes to be resident
in the machine memory at the same time. The existing AddrSpace
constructor 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.AddrSpace
to 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 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.
Exec
call 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
fork()
and 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.
Exec
must 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.Exit
should not return back to the user program. Instead,
it should destroy the calling thread (e.g.,
currentThread->Finish()
).Exit
system 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.Join
system
call correctly. The kernel Join
primitive 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 Join
implementation must correctly
return the exit status code of the target process.Join
correctly 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.Join
and Exit
is
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 Join
is 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
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.
Exec
N times from each parent process, and join on all children
before exiting. Since Exec
as 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.
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.