Disclaimer: This document is adapted from the Nachos Project Guide authored by Dr. Jeff Chase.
The remaining four assignments (#3, #4, #5, and #6) of this course will be based on an instructional operating system called Nachos. Nachos was originally developed by Dr. Tom Anderson and his associates (then at UC Berkeley). I made some modifications for use in this course. Compared with production operating systems such as Linux, Nachos is small enough for you to understand in a few months. The base system we give you runs, but it lacks many essential operating system mechanisms. Your job in the next four assignments is to put in those missing pieces. In the end, you should finish in building a fully functional operating system kernel (well, sort-of :).
While we try to minimize the orientation time for you, the assignments demand that you invest some efforts to learn the internals of an operating system (Nachos) that you will never need to use in practice. However, the goal is that through these efforts, you will learn about building operating systems and software systems in general, not just Nachos. Make sure you understand the given base system before making any changes/additions. Be warned that the preliminary step of understanding the base system may take a lot of time, especially for the first assignment. So start early! This document provides some basic information about Nachos that can jump start your learning. Most of your familiarity with Nachos is expected to come from reading the code and working on the assignments!
This document only describes general information about all Nachos assignments. Information specific to each assignment will be introduced within the corresponding assignment.
You will develop your code on URCS lab machines (Linux on x86 machines).
A copy of Nachos can be found at
/u/cs256/nachos/nachos-3.4-urv3.1.tar
if you are in the CSUG network; or
at /u/cs456/nachos/nachos-3.4-urv3.1.tar
if you are in the
research (graduate students and faculty) network.
Copy the file to your own directory, unpack it using
tar xf nachos-3.4-urv3.1.tar
, and you will
find the Nachos source in a directory nachos-3.4-urv3.1/
.
The Nachos code directory includes several subdirectories for different
pieces of the Nachos. You should build Nachos in a department machine since
the building process requires a cross-compiler (for Nachos user programs)
that we have installed for you on both department networks.
Do make
in each of these subdirectories
to build an OS kernel (called nachos
) with the right
components for specific assignments:
threads/
for an OS kernel supporting threads and
synchronization (assignment #3).userprog/
for an OS kernel supporting multiple
concurrent user programs (assignment #4).vm/
for an OS kernel supporting virtual memory
(assignment #5).filesys/
for an OS kernel supporting a native file
system (assignment #6).network/
for an OS kernel supporting basic networking
(we do not cover it in this course).machine/
contains a simulated MIPS machine for running
user programs. You are not allowed to change anything here, just like
an OS developer is not allowed to change the hardware machine.
However, you might want to know how this simulated machine works to assist
your development of the Nachos kernel. (more on this shortly)test/
contains some example user programs for Nachos
kernels. (more on this in later assignments)coff2noff/
contains a tool for building user programs
for the simulated MIPS machine. You will not need to understand this for
completing the assignments, but curiosity for looking into it is
encouraged.make
in the root source directory to build all
supporting components and all versions of the Nachos kernel. You should study
the Makefiles to understand how dependency identification and recompilation
work. The dependence information determines which .cc
files
are rebuilt when a given .h
file changes. The dependency
lines in each subdirectory Makefile are created automatically using
make depend
.
It is important to avoid build problems, which can consume a lot of frustrating
debugging time chasing bugs that do not really exist. Always be sure that you
run make depend
any time the header file dependencies change
(e.g., you cp
or move
the source tree
from one directory to another). Always make sure you are running the right copy
of the nachos
executable (all versions of the Nachos kernel
built in different subdirectories have the same executable name). Whenever you
are in doubt with build problems, do make clean; make depend; make
instead of a plain make
.
In the beginning, you may find the nature of the Nachos projects confusing, because there is a significant amount of code already written and it is not always clear what to change or where to make additions. Nachos is designed so that the changes for each assignment are reasonably localized. In most cases, you will be adding new code to the existing framework, mostly in new procedures or classes that you define and create. In a few cases you will be extending or "filling in" C++ classes or methods that are already defined. Very rarely will it be necessary to delete or rewrite code that already exists, or to add code in areas outside of the main focus of each assignment.
In general, we do not prohibit you from modifying any part of Nachos that you
feel is necessary to modify. However, we are telling you now that the simplest
and most direct solutions for each assignment do not require you to modify code
outside of the primary area of focus for each assignment. Also, under no
circumstances should you modify the behavior of the "hardware" as defined by
the machine simulation software in the machine/
subdirectory.
It is acceptable to change #define
directives that determine
the machine or system parameters (e.g., size of physical memory or size of the
default stack), but any code that implements the machine itself is strictly off
limits. If you are unsure about this, then please ask.
In this course you will be using C/C++ to do "systems programming", which requires you to be more directly in touch with the representation of data structures in the machine memory. For example, systems programmers often need to set up data structures interpreted directly by hardware, which expects everything to be just exactly perfect. Examples that will come up during the semester include thread stack frames, page tables, and saved register contexts. Also, to understand concurrency behaviors you must understand how lists and other data structures are represented in memory.
One risk of learning about nice clean object-oriented programming abstractions in introductory courses is that it is easy to lose sight of how data structures are really laid out in machine memory. In particular, be sure that you understand the relationship between character strings, pointers, and arrays in "raw" C and C++, and that you understand how memory for your data structure is allocated. If you use array indexing and/or string functions to address storage that you did not allocate properly, it almost always leads to unexpected errors that are difficult to trace back to the source.
In general, we recommend you to stick with the basic C and use C++ only for
structural modularity. We discourage the use of prepackaged classes and
C++ features not already present in the Nachos release. You can do everything
you need to do in this course cleanly and directly using simple constructs such
as arrays together with the List
class already included in
Nachos. Experience has shown that use of fancier features for these assignments
rarely if ever results in cleaner code, occasionally leads to build problems, and
very often leads to tedious debugging marathons. Templates, vectors, and overuse
of inheritance can be particularly dangerous.
There are at least three ways to trace execution: (1) add printf
(or fprintf
) statements to the code, (2) use the
gdb
debugger or another debugger of your choosing, and
(3) insert calls to the DEBUG
function that Nachos provides.
It takes a few hours to learn to use a debugger. However, investing those few
hours will save you many more hours when debugging. Printfs can be useful, but be
aware that they do not always work right, because data is not always printed
synchronously with the call to printf. Rather, printf buffers ("saves up")
printed characters in memory, and writes the output only when it has accumulated
enough to justify the cost of invoking the operating system's
write
system call to put the output on your screen. If your
program crashes while characters are still in the buffer, then you may never see
those messages print. If you use printf, it is good practice to follow every
printf with a call to fflush
to avoid this problem.
One of most important concepts in this course is the idea of a thread. Your
Nachos programs will execute as multiple independent threads of control, each
with a separate execution stack. When you trace the execution path of your
program, it is helpful to keep track of the state of each thread and which
procedures are on each thread's stack. You will notice that when one thread
calls SWITCH
, another thread starts running (this is called
a context switch), and the first thing the new thread does is to return from
SWITCH. Because gdb and other debuggers are not aware of the Nachos thread
library, tracing across a call to SWITCH might be confusing sometimes.
The DEBUG
primitive:
If you want to debug with printf statements, the Nachos DEBUG function (declared
in threads/utility.h
) is your best bet. In fact, the
Nachos code is already peppered with calls to the DEBUG function. You can see
some of them by doing an
fgrep DEBUG *.h *.cc
in the threads/
subdirectory. These are basically printf statements that keep quiet unless you
want to hear what they have to say. By default, these statements have no effect
at runtime. To see what is happening, you need to invoke Nachos with a special
command-line argument that activates the DEBUG statements you want to see.
See threads/main.cc
for a specification of the flags
arguments for Nachos. The relevant one for DEBUG is -d. The -d flag followed
by a space and a list of single-character debug flags (e.g.,
nachos -d ti
), enabling the nachos DEBUG statements matching
any of the specified flags. For example, the t debug flag activates DEBUG
statements relating to thread events. See threads/utility.h
for a description of the meanings of the current debug flags.
ASSERT early and often:
The ASSERT macro, also declared in threads/utility.h
, is
extremely useful in debugging, particularly for concurrent code. Use ASSERT
to indicate that certain conditions should be true at runtime. If the
condition is not true (i.e., the expression evaluates to 0), then your program
will print a message and crash right there before things get messed up further.
ASSERT early and often! ASSERTs help exposing bugs early.
This section contains information that you may not be able to completely understand in the beginning of this course. Understand as much as you can and check back later when needed!
In these assignments you will implement key pieces of an operating system supporting user programs and a protected kernel. In principle, this requires that we give each of you your own machine because your kernel will need complete control over how memory is managed and how interrupts and exceptions (including system calls) are handled. Since we cannot afford to give you a real machine, we will give you a simulated machine that models a MIPS CPU. (MIPS processors were used in some workstations when Nachos was first written; they are still around, but now they are mostly used for embedded systems applications, such as inside network switches.) You will use the simulated MIPS machine to execute user-level programs above your operating system. Your nachos executable will contain a MIPS simulator that reads the user-level program executables as data and interprets them, simulating their execution on a real MIPS machine booted with your Nachos kernel. "It's like a ship in a bottle."
The MIPS CPU simulator:
The simulated MIPS machine is really just a big procedure that is part of the
Nachos distribution. This procedure understands the format of MIPS
instructions and the expected behavior of those instructions as defined by the
MIPS architecture. When the MIPS simulator is executing a "user program", it
simulates the behavior of a real MIPS CPU by executing a tight loop, fetching
MIPS instructions from a simulated machine memory and "executing" them by
transforming the state of the simulated memory and simulated machine registers
according to the defined meaning of the instructions in the MIPS architecture
specification. The simulated machine's physical memory and registers are data
structures in your nachos program.
Interactions between the kernel and the machine:
Your Nachos kernel can control the simulated machine in the same way that a
real kernel controls a real machine. Like a real kernel on a real machine,
your kernel can direct the simulated machine to begin executing code in user
mode at a specific memory address. The machine will return control to the
kernel (by calling the Nachos kernel procedure
ExceptionHandler
) if the user program executes a system
call trap instruction, or if an interrupt or other machine exception occurs.
Like a real kernel, your Nachos kernel must examine and modify the machine
registers and other machine state in order to service exceptions and run user
programs. For example, system call arguments and results are passed between
user programs and the kernel through the machine's registers. Your kernel
will also examine and modify page table data structures that are used by the
simulated machine to translate virtual addresses in the current user program.
From the perspective of the Nachos kernel, all of the machine state -
registers, memory, and page tables - are simply arrays in the kernel address
space, accessible through the Machine object. See the definitions in
machine/machine.h
.
Note: in these projects, the page table format is defined by the machine architecture, not by the operating system. When your kernel examines or modifies page tables - or any other machine state - you should be certain to "give the machine what it wants", carefully adhering to the defined interface between the machine and the operating system. Do not attempt to change the architecture! In the real world, the operating system and the hardware architecture are often defined by different companies (e.g., Microsoft and Intel respectively); in this case, the software designers cannot dictate the hardware architecture, and they must respect the defined hardware interface or else their software will not work.
I/O devices, interrupts, and the console:
The Nachos distribution extends the MIPS CPU simulator to simulate some
devices, e.g., disks, a timer, and a console. Nachos maintains a queue of
interrupts that are scheduled to occur (e.g., completion of a pending disk
operation), and simulates delivery of these interrupts by calling kernel
interrupt handler procedures at the appropriate times.
Why does Nachos hang when I enable the console? Nachos has an
annoying "feature": the Nachos kernel will not shut down if there are
pending I/O operations, even if there are no threads or processes ready to
run. This is the behavior you would expect, but Nachos simulates a console
by using the interrupt queue to repeatedly poll for characters typed on the
console - thus there is always a pending I/O operation on the console.
This means that if you create a Console
object as
required for the later assignments, then Nachos will never shut down when it
is done running your test programs. Instead it will idle just like a real
kernel, waiting for console input. Feel free to kill it with
Ctrl-C
.
Don't leave hanging Nachos processes after you leave the lab.
They chew up a lot of CPU time.