An Introduction to Nachos

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.

Acquiring and building Nachos

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:

The other subdirectories contain supporting components for Nachos kernels: Do 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.

What parts of Nachos should we modify?

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.

Systems programming in C/C++

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.

Tracing and debugging Nachos programs

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/ 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.

The Nachos MIPS simulator

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.