A Road Map Through Nachos
Thomas Narten
Department of Computer Sciences
Levine Science Research Center
Duke University
Box 90129
Durham, N.C. 27708-0129
narten@cs.duke.edu
January 4, 1995
Abstract
Nachos is instructional software that allows students to examine, mo dify and exe-
cute operating system software. Nachos provides a skeletal op erating system that sup-
p orts threads, user-level pro cesses, virtual memory and interrupt-driven input output
devices. Nachos is a complex piece of software and it is dicult for b eginning students
(and instructors) to easily gain on overall understanding of the various system pieces
and how they t together.
This document provides a road map to understanding the Nachos system. It gives
a high-level overview of the source code, fo cusing on the big picture rather than on the
details. It is not intended as a replacement for reading the source co de. Rather, it is
a companion that is intended to help students (and instructors) overcome the initial
learning curve encountered when learning and using the system.
Contents
1 Intro duction to Nachos 1
2 Nachos Machine 1
2.1 Machine Comp onents
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
2
2.2 Interrupt Management
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
4
2.3 Real-Time Clo ck Interrupts
: : : : : : : : : : : : : : : : : : : : : : : : : : :
5
2.4 Address Translation
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
5
2.4.1 Linear Page Tables
: : : : : : : : : : : : : : : : : : : : : : : : : : : :
6
2.4.2 Software Managed TLB
: : : : : : : : : : : : : : : : : : : : : : : : :
6
2.5 Console Device
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
6
2.6 Disk Device
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
7
3 Nachos Threads 9
3.1 Mechanics of Thread Switching
: : : : : : : : : : : : : : : : : : : : : : : : :
12
3.2 Threads & Scheduling
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
13
3.3 Synchronization and Mutual Exclusion
: : : : : : : : : : : : : : : : : : : : :
14
3.4 Sp ecial Notes
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
14
4 User-Level Pro cesses 15
4.1 Pro cess Creation
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
15
4.2 Creating a No Binary
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
16
4.3 System Calls and Exception Handling
: : : : : : : : : : : : : : : : : : : : : :
16
4.4 Execution Trace of User-Level Pro cess
: : : : : : : : : : : : : : : : : : : : :
17
5 Nachos Filesystem 19
5.1 SynchDisk
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
19
5.2 FileSystem Ob ject
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
21
5.3 Op enFile Ob ject
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
24
5.4 File System Physical Representation
: : : : : : : : : : : : : : : : : : : : : :
24
5.4.1 File Header
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
24
5.4.2 Directories
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
25
5.4.3 Putting It All Together
: : : : : : : : : : : : : : : : : : : : : : : : : :
26
6 Exp erience With Nachos Assignments 27
i
6.1 General Tips
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
27
6.2 Synchronization
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
28
6.3 Multiprogramming
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
29
6.4 Virtual Memory
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
30
6.5 File System
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
34
6.6 Common Errors
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
34
7 MIPS Architecture 35
ii
1 Intro duction to Nachos
Nachos is instructional software that allows students to study and mo dify a real op erating
system. The only dierence between Nachos and a \real" op erating system is that Nachos
runs as a single Unix pro cess, whereas real operating systems run on bare machines. However,
Nachos simulates the general low-level facilities of typical machines, including interrupts,
virtual memory and interrupt-driven device I/O.
The rest of this do cument attempts to provide a road map through Nachos. It is not
intended to replace the need for reading the source co de rather, it this do cument attempts
to sp eed up the learning pro cess by describing \the big picture."
Section 2 provides an overview of the underlying machine that Nachos simulates and
runs on top of. Section
??
describ es Nachos threads and the mechanics of scheduling,
synchronization and thread switching. Section 4 describ es how user-level programs execute
as separate pro cesses within their own private address spaces. Section 5 provides an overview
of the lesystem implementation. Section 6 rep orts on exp erience using Nachos to teach
op erating systems courses, and provides sp ecic suggestions on individual assignments.
2 Nachos Machine
Nachos simulates a machine that roughly approximates the MIPS architecture. The machine
has registers, memory and a cpu. In addition, an event-driven simulated clo ck provides a
mechanism to schedule interrupts and execute them at a later time. The simulated MIPS
machine can execute arbitrary programs. One simply loads instructions into the machine's
memory, initializes registers (including the program counter PCReg) and then tells the ma-
chine to start executing instructions. The machine then fetches the instruction PCReg p oints
at, decodes it, and executes it. The pro cess is rep eated indenitely,until an illegal op eration
is performed or a hardware interrupt is generated. Whenatraporinterrupt takes place, ex-
ecution of MIPS instructions is susp ended, and a Nachos interrupt service routine is invoked
to deal with the condition.
Conceptually, Nachos has two mo des of execution, one of which is the MIPS simulator.
Nachos executes user-level pro cesses by loading them into the simulator's memory, initializing
the simulator's registers and then running the simulator. User-programs can only access the
memory asso ciated with the simulated machine. The second mo de corresp onds to the Nachos
\kernel." The kernel executes when Nachos rst starts up, or when a user-program executes
an instruction that causes a hardware trap (e.g., illegal instruction, page fault, system call,
etc.). In \kernel mo de", Nachos executes the way normal Unix pro cesses execute. That
is, the statements corresp onding to the Nachos source co de are executed, and the memory
accessed corresp onds to the memory assigned to Nachos variables.
Nachos do es not have to execute user-level programs in order to p erform useful things.
Nachos supp orts kernel threads, allowing multiple threads to execute concurrently. In this
context, Nachos b ehaves in a manner analogous to other thread packages. Indeed, user-level
pro cesses are executed by having a kernel thread invoke the simulator. Thus, multipro-
1
gramming makesuseofmultiple threads each user-level pro cess has a Nachos kernel thread
asso ciated with it to provide a context for executing the MIPS simulator.
2.1 Machine Components
The Nachos/MIPS machine is implemented by the
Machine
ob ject, an instance of which is
created when Nachos rst starts up. The
Machine
ob ject exp orts a number of op erations
and public variables that the Nachos kernel accesses directly. In the following, we describ e
some of the imp ortant variables of the
Machine
ob ject describing their role helps explain
what the simulated hardware do es.
The Nachos
Machine
ob ject provides registers, physical memory, virtual memory supp ort
as well as op erations to run the machine or examine its current state. When Nachos rst
starts up, it creates an instance of the
Machine
ob ject and makes it available through the
global variable
machine
. The following public variables are accessible to the Nachos kernel:
registers:
An array of 40 registers, which include such special registers as a stack pointer, a
double register for multiplication results, a program counter, a next program counter
(for branchdelays), a register target for delayed loads, a value to b e loaded on a delayed
load, and the bad virtual address after a translation fault. The registers are number
0{39 see the le
machine.h
for symb olic names for the registers having sp ecial meaning
(e.g.,
PCReg
).
Although registers can be accessed directly via
machine-
>
registersx]
, the
Machine
ob ject provides sp ecial
ReadRegister()
and
WriteRegister()
routines for this purp ose
(describ ed in more detail b elow).
mainMemory:
Memory is byte-addressable and organized into 128-byte pages, the same
size as disk sectors. Memory corresponding to physical address
x
can be accessed
in Nachos at
machine-
>
mainMemoryx]
. By default, the Nachos MIPS machine has
31 pages of physical memory. The actual number of pages used is controlled by the
NumPhysPages
variable in
machine.h
.
Virtual Memory
Nachos supp orts VM through either a single linear page table or a
software-managed TLB (though not simultaneously). The choice of which is in eect
is controlled by initializing the
tlb
or
pageTable
variables of the
machine
class. When
executing instructions, the
Machine
ob ject uses whichever is dened, after verifying
that they are not b oth set simultaneously.
At this p oint, we know enough about the
Machine
ob ject to explain how it executes
arbitrary user programs. First, we load the program's instructions into the machine's physical
memory (e.g, the
machine-
>
mainMemory
variable). Next, we initialize the machine's page
tables and registers. Finally we invoke
machine-
>
Run()
, which begins the fetch-execute
cycle for the machine.
The
Machine
ob ject provides the following operations:
2
