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, modify and execute operating system software. Nachos provides a skeletal operating system that supports threads, user-level processes, virtual memory and interrupt-driven input output devices. Nachos is a complex piece of software and it is di cult for beginning 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, focusing on the big picture rather than on the details. It is not intended as a replacement for reading the source code. 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 Introduction to Nachos 2 Nachos Machine
2.1 2.2 2.3 2.4 Machine Components : : : : : : Interrupt Management : : : : : Real-Time Clock Interrupts : : Address Translation : : : : : : : 2.4.1 Linear Page Tables : : : 2.4.2 Software Managed TLB 2.5 Console Device : : : : : : : : : 2.6 Disk Device : : : : : : : : : : :

1
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

1

2 4 5 5 6 6 6 7

3 Nachos Threads
3.1 3.2 3.3 3.4

Mechanics of Thread Switching : : : : Threads & Scheduling : : : : : : : : : Synchronization and Mutual Exclusion Special Notes : : : : : : : : : : : : : : Process Creation : : : : : : : : : : : : Creating a No Binary : : : : : : : : : System Calls and Exception Handling : Execution Trace of User-Level Process

12 13 14 14

9

4 User-Level Processes
4.1 4.2 4.3 4.4

15

15 16 16 17

5 Nachos Filesystem
5.1 5.2 5.3 5.4

SynchDisk : : : : : : : : : : : : : : : FileSystem Object : : : : : : : : : : OpenFile Object : : : : : : : : : : : File System Physical Representation 5.4.1 File Header : : : : : : : : : : 5.4.2 Directories : : : : : : : : : : : 5.4.3 Putting It All Together : : : :

: : : : : : :

19
19 21 24 24 24 25 26

6 Experience With Nachos Assignments i 27

6.1 6.2 6.3 6.4 6.5 6.6

General Tips : : : Synchronization : : Multiprogramming Virtual Memory : : File System : : : : Common Errors : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

27 28 29 30 34 34

7 MIPS Architecture

35

ii

1 Introduction to Nachos
Nachos is instructional software that allows students to study and modify a real operating system. The only di erence between Nachos and a \real" operating system is that Nachos runs as a single Unix process, 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 document attempts to provide a road map through Nachos. It is not intended to replace the need for reading the source code rather, it this document attempts to speed up the learning process by describing \the big picture." Section 2 provides an overview of the underlying machine that Nachos simulates and runs on top of. Section ?? describes Nachos threads and the mechanics of scheduling, synchronization and thread switching. Section 4 describes how user-level programs execute as separate processes within their own private address spaces. Section 5 provides an overview of the lesystem implementation. Section 6 reports on experience using Nachos to teach operating systems courses, and provides speci c 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 clock 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 machine to start executing instructions. The machine then fetches the instruction PCReg points at, decodes it, and executes it. The process is repeated inde nitely, until an illegal operation is performed or a hardware interrupt is generated. When a trap or interrupt takes place, execution of MIPS instructions is suspended, and a Nachos interrupt service routine is invoked to deal with the condition. Conceptually, Nachos has two modes of execution, one of which is the MIPS simulator. Nachos executes user-level processes 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 associated with the simulated machine. The second mode corresponds 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 mode", Nachos executes the way normal Unix processes execute. That is, the statements corresponding to the Nachos source code are executed, and the memory accessed corresponds to the memory assigned to Nachos variables. Nachos does not have to execute user-level programs in order to perform useful things. Nachos supports kernel threads, allowing multiple threads to execute concurrently. In this context, Nachos behaves in a manner analogous to other thread packages. Indeed, user-level processes are executed by having a kernel thread invoke the simulator. Thus, multipro1

gramming makes use of multiple threads each user-level process has a Nachos kernel thread associated with it to provide a context for executing the MIPS simulator.

2.1 Machine Components
The Nachos/MIPS machine is implemented by the Machine object, an instance of which is created when Nachos rst starts up. The Machine object exports a number of operations and public variables that the Nachos kernel accesses directly. In the following, we describe some of the important variables of the Machine object describing their role helps explain what the simulated hardware does. The Nachos Machine object provides registers, physical memory, virtual memory support as well as operations to run the machine or examine its current state. When Nachos rst starts up, it creates an instance of the Machine object and makes it available through the global variable machine . The following public variables are accessible to the Nachos kernel: double register for multiplication results, a program counter, a next program counter (for branch delays), a register target for delayed loads, a value to be 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 symbolic names for the registers having special meaning (e.g., PCReg ). Although registers can be accessed directly via machine->registers x] , the Machine object provides special ReadRegister() and WriteRegister() routines for this purpose (described in more detail below). 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->mainMemory x] . 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 supports VM through either a single linear page table or a software-managed TLB (though not simultaneously). The choice of which is in e ect is controlled by initializing the tlb or pageTable variables of the machine class. When executing instructions, the Machine object uses whichever is de ned, after verifying that they are not both set simultaneously. At this point, we know enough about the Machine object 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 object provides the following operations: 2

registers: An array of 40 registers, which include such special registers as a stack pointer, a

Machine(bool debug) The Machine constructor takes a single argument debug . When

debug is TRUE, the MIPS simulator executes instructions in single step mode, invoking the debugger after each instruction is executed. The debugger allows one to interactively examine machine state to verify (for instance) that registers or memory contain expected values. By default, single-stepping is disabled. It is enabled by specifying the \-s" command line option when starting Nachos up.

virtual address virtAddr into its corresponding physical address physAddr . Translate examines the machine's translation tables (described in detail in Section 2.4) in order to perform the translation. When successful, Translate returns the corresponding physical address in physAddr . Otherwise, it returns a code indicating the reason for the failure (e.g., page fault, protection violation, etc.) Whenever a translation fails, the MIPS simulator invokes the Nachos routine RaiseException to deal with the problem. RaiseException is responsible for handling all hardware trap conditions. When RaiseException returns, the Nachos Machine assumes that the condition has been corrected an resumes its fetch-execute cycle. Note that from a user-level process's perspective, traps take place in the same way as if the program were executing on a bare machine a trap handler is invoked to deal with the problem. However, from the Nachos perspective, RaiseException is called via a normal procedure call by the MIPS simulator. OneInstruction() does the actual work of executing an instruction. It fetches the current instruction address from the PC register, fetches it from memory, decodes it, and nally executes it. Any addresses referenced as part of the fetch/execute cycle (including the instruction address given by PCReg) are translated into physical addresses via the Translate() routine before physical memory is actually accessed. Run() \turns on" the MIPS machine, initiating the fetch-execute cycle. This routine should only be called after machine registers and memory have been properly initialized. It simply enters an in nite fetch-execute loop. The main loop in Run does three things: 1) it invokes OneInstruction to actually execute one instruction, 2) it invokes the debugger, if the user has requested singlestep mode on the command line, and 3) it increments a simulated clock after each instruction. The clock, which is used to simulate interrupts, is discussed in the following section. int ReadRegister(int num) fetches the value stored in register num . void WriteRegister(int num, int value) places value into register num . bool ReadMem(int addr, int size, int* value) Retrieves 1, 2, or 4 bytes of memory at virtual address addr . Note that addr is the virtual address of the currently executing user-level program ReadMem invokes Translate before it accesses physical memory. 3

ExceptionType Translate(int virtAddr, int* physAddr, int size, bool writing) converts

One point that should be noted is that ReadMem fails (returning FALSE), if the address translation fails (for whatever reason). Thus, if the page is not present in physical memory, ReadMem fails. ReadMem does not distinguish temporary failures (e.g., page not in memory) from hard errors (e.g., invalid virtual address)1 . ReadMem is used (for instance) when dereferencing arguments to system calls. bool WriteMem(int addr, int size, int value) writes 1, 2, or 4 bytes of value into memory at virtual address addr. The same warnings given for ReadMem apply here as well.

2.2 Interrupt Management
Nachos simulates interrupts by maintaining an event queue together with a simulated clock. As the clock ticks, the event queue is examined to nd events scheduled to take place now. The clock is maintained entirely in software and ticks under the following conditions: 1. Every time interrupts are restored (and the restored interrupt mask has interrupts enabled), the clock advances one tick. Nachos code frequently disables and restores interrupts for mutual exclusion purposes by making explicit calls to interrupt::SetLevel(). 2. Whenever the MIPS simulator executes one instruction, the clock advances one tick. 3. Whenever the ready list is empty, the clock advances however many ticks are needed to fast-forward the current time to that of the next scheduled event. Whenever the clock advances, the event queue is examined and any pending interrupt events are serviced by invoking the procedure associated with the timer event (e.g., the interrupt service routine). All interrupt service routines are run with interrupts disabled, and the interrupt service routine may not re-enable them. Warning: in interrupt handler may not call any routines that lead to a context switch of the current thread (e.g., scheduler::Run() or SWITCH() ). Doing so may lead to deadlock. This restriction is an artifact of the way interrupts are simulated under Nachos, and should not be taken as an indication of the way things are done on real machines. Speci cally, consider the case where multiple events happen to be scheduled at exactly the same time. If the handler for the rst event invokes sleep (which calls SWITCH ), the others won't be serviced at the right time. In fact, the thread that called sleep may actually be waiting for one of the other events that is supposed to take place now, but is delayed because of the SWITCH . We now have a deadlock2 . All routines related to interrupt management are provided by the Interrupt object. The main routines of interest include:
See Section 1 for a description of one common problem students encounter due to this. To correctly implement preemption, the interrupt handler invoked when a running threads quantum expires needs to switch to another thread. This is handled by having the interrupt service routine invoke Thread::YieldOnReturn() , which delays the actual preemption until it is safe to do so.
1 2

4

a future event to take place at time when . When it is time for the scheduled event to take place, Nachos calls the routine handler with the single argument arg . IntStatus SetLevel(IntStatus level) Change the interrupt mask to level , returning the previous value. This routine is used to temporarily disable and re-enable interrupts for mutual exclusion purposes. Only two interrupt levels are supported: IntOn and IntO . OneTick() advances the clock one tick and services any pending requests (by calling CheckIfDue ). It is called from machine::Run() after each user-level instruction is executed, as well as by SetLevel when the interrupts are restored. bool CheckIfDue(bool advanceClock) examines the event queue for events that need servicing now. If it nds any, it services them. It is invoked in such places as OneTick . Idle() \advances" to the clock to the time of the next scheduled event. It is called by the scheduler (actually Sleep()) when there are no more threads on the ready list and we want to \fast-forward" the time.

void Schedule(VoidFunctionPtr handler, int arg, int when, IntType type) schedules

2.3 Real-Time Clock Interrupts
Nachos provides a Timer object that simulates a real time clock, generating interrupts at regular intervals. It is implemented using the same event driven interrupt mechanism described above. Timer supports the following operations:

Timer(VoidFunctionPtr timerHandler, int callArg, bool doRandom) The Timer constructor creates a real-time clock that interrupts every TimerTicks (100) time units. When the timer goes o , the Nachos simulator invokes procedure timerHandler , passing it callArg as an argument. To add a bit of non-determinism to the system, argument doRandom speci es that the time between interrupts should be taken from a uniform interval between 1 and 2 TimerTicks. The real-time clock can be used to provide preemption.

Note that starting Nachos with the \-rs" option creates a timer object that interrupts at random intervals and preempts the currently running thread.

2.4 Address Translation
Nachos supports two types of VM architectures: linear page tables, or a software managed TLB. While the former is simpler to program, the latter more closely corresponds to what current machines support. Nachos supports one or the other, but not both (simultaneously). 5

2.4.1 Linear Page Tables
With linear tables, the MMU splits a virtual address into page number and page o set components. The page number is used to index into an array of page table entries. The actual physical address is the concatenation of the page frame number in the page table entry and the page o set of the virtual address. To use linear page tables, one simply initializes variable machine->pageTable to point to the page table used to perform translations. In general, each user process will have its own private page table. Thus, a process switch requires updating the pageTable variable. In a real machine, pageTable would correspond to a special register that would be saved and restored as part of the SWITCH() operation. The machine variable pageTableSize indicates the actual size of the page table. Page table entries consist of the physical page frame number for the corresponding virtual page, a ag indicating whether the entry is currently valid (set by the OS, inspected by hardware), a ag indicating whether the page may be written (set by OS, inspected by hardware), a bit indicating whether the page has been referenced (set by the hardware, inspected and cleared by OS) and a dirty bit (set by hardware, inspected and cleared by OS). The Nachos machine has NumPhysPages of physical memory starting at location mainMemory . Thus, page 0 starts at machine->mainMemory , while page N starts at mainMemory + N PageSize.

2.4.2 Software Managed TLB
To be lled in.]

2.5 Console Device
Nachos provides a terminal console device and a single disk device. Nachos devices are accessed through low-level primitives that simply initiate an I/O operation. The operation itself is performed later, with an \operation complete" interrupt notifying Nachos when the operation has completed. The Console class simulates the behavior of a character-oriented CRT device. Data can be written to the device one character at a time through the PutChar() routine. When a character has successfully been transmitted, a \transmit complete" interrupt takes place and the user-supplied handler is invoked. The interrupt handler presumably checks if more characters are waiting to be output, invoking PutChar again if appropriate. Likewise, input characters arrive one-at-a-time. When a new character arrives, the console device generates an interrupt and the user-supplied input interrupt service routine is invoked to retrieve the character from the device and (presumably) place it into a bu er from which higher-level routines (e.g., GetChar()) can retrieve it later. The Console object supports the following operations: 6

The constructor creates an instance of a terminal console. Argument readFile contains the Unix le name of where the data is to be read from if NULL, standard input is assumed. Likewise, argument writeFile indicates where output written to the console is to go if NULL, standard output is assumed. When a character becomes available for reading, readAvail is invoked with an argument of callArg to notify the Nachos that a character is available. The character itself is retrieved by calling Console::GetChar(). Upon return, it is assumed that the character has been retrieved and when the next one arrives, readAvail will be called again. void PutChar(char ch) Writes character ch to the output device. Once output has started, it is an error to invoke PutChar() again before the corresponding I/O complete interrupt has taken place. Once the console device has written the character to the device, it invokes the user-supplied procedure writeDone , passing it callArg as an argument. char GetChar() Retrieves a character from the console. GetChar returns EOF if no new data is available. Normally, the user would not invoke GetChar unless the availability of new data had rst been signalled via the readAvail() interrupt service routine. void CheckCharAvail() an internal procedure used to see if new data is available for reading. When a console device is created by the constructor, the appropriate Unix les (or stdin/stdout) are opened and a timer event is scheduled to take place 100 time units in the future. When the timer expires, the routine CheckCharAvail is invoked to see if any data is present. If so, CheckCharAvail reads that character and invokes the user-supplied input interrupt handler readAvail. It then schedules a new timer event so that the process repeats every 100 time units. Thus, CheckCharAvail simply polls every 100 clock ticks for new data, calling the interrupt service routine whenever data is present for processing. Device output is initiated by calling PutChar , giving it a single character to output. Once character output has been initiated, the device is made busy until the output complete interrupt takes place. PutChar simply outputs the one character, sets an internal ag to indicate that the device is busy, and then schedules a timer interrupt to take place 100 clock ticks later. When the timer expires, the state of the device is changed from busy to idle, and the user-supplied output interrupt complete routine is invoked. This routine would presumably invoke PutChar if additional output characters were queued awaiting output.

Console(char *readFile, char *writeFile, VoidFunctionPtr readAvail, VoidFunctionPtr write

2.6 Disk Device
The Disk object simulates the behavior of a real disk. The disk has only a single platter, with multiple tracks containing individual sectors. Each track contains the same number of sectors, and blocks are uniquely identi ed by their sector number. As with a real disk, the OS initiates operations to read or write a speci c sector, and a later interrupt indicates when the operation has actually completed. The Nachos disk allows only one pending operation 7

at a time the OS may initiate new operations only when the device is idle. Note that it is the responsibility of the OS to insure that new requests are not issued while the disk is busy servicing an earlier request. In order to simulate typical delays in accessing a disk, the Nachos Disk object dynamically varies the time between the initiation of an I/O operation and its corresponding I/O complete interrupt. The actual delay depends on how long it takes to move the disk head from its previous location to the new track, as well as the rotational delay encountered waiting for the desired block to rotate under the read/write head. The simulated disk contains NumTracks (32) tracks, each containing SectorsPerTrack (32) sectors. Individual sectors are SectorSize (128) bytes in size. In addition, Disk contains a \track bu er" cache. Immediately after seeking to a new track, the disk starts reading sectors, placing them in the track bu er. That way, a subsequent read request may nd the data already in the cache reducing access latency. The Disk object supports the following operations: assumes that the simulated disk is kept in the Unix le called name . If the le does not already exist, Nachos creates it and writes a \magic number" of 0x456789ab into the initial four bytes. The presence of a magic number allows Nachos to distinguish a le containing a Nachos simulated disk from one containing something else. Finally, Nachos insures that the rest of the le contains NULL sectors. All Nachos disks have the same size, given by the formula NumSectors SectorsPerTrack. If the le already exists, Nachos reads the rst 4 bytes to verify that they contain the expected Nachos \magic number," terminating if the check fails. Note that by default the contents of a Nachos disk is preserved across multiple Nachos sessions, allowing users to create a Nachos le in one session, and read it in another. However, if the disk contains a le system, and the le system is left in a corrupted state by a previous Nachos session, subsequent Nachos invocations are likely run into problems if they don't rst verify that the lesystem data structures are logically consistent. The last two constructor arguments are used to provide an \I/O complete" interrupt mechanism. Speci cally, the Nachos machine signals the completion of a Disk operation (e.g., read or write) by invoking the procedure callWhenDone , passing it an argument of callArg . As shown below, the SynchDisk object uses this routine to wake up a thread that has been suspended while waiting for I/O to complete. ReadRequest(int sectorNumber, char *data): Is invoked to read the speci ed sector number into the bu er data . In Nachos, all sectors are the same size (SectorSize ). Note that this operations returns immediately, before the transfer actually takes place. ReadRequest schedules an interrupt to take place sometime in the future, after a time roughly dependent on the seek distance needed to complete the operation. Only after the interrupt takes place is it correct to start using the data. WriteRequest(int sectorNumber, char *data): Similar to ReadRequest , except that it writes a single sector. 8

Disk(char *name, VoidFunctionPtr callWhenDone, int callArg): This constructor

ComputeLatency(int newSector, bool writing): estimates the latency required to ac-

cess the block newSector given the current position of the disk head. The routine is used in deciding when to schedule an I/O complete interrupt when servicing a read or write request.

3 Nachos Threads
In Nachos (and many systems) a process consists of: 1. An address space . The address space includes all the memory the process is allowed to reference. In some systems, two or more processes may share part of an address space, but in traditional systems the contents of an address space is private to that process. The address space is further broken down into 1) Executable code (e.g., the program's instructions), 2) Stack space for local variables and 3) Heap space for global variables and dynamically allocated memory (e.g., such as obtained by the Unix malloc or C++ new operator). In Unix, heap space is further broken down into BSS (contains variables initialized to 0) and DATA sections (initialized variables and other constants). 2. A single thread of control, e.g., the CPU executes instructions sequentially within the process. 3. Other objects, such as open le descriptors. That is, a process consists of a program, its data and all the state information (memory, registers, program counter, open les, etc.) associated with it. It is sometimes useful to allow multiple threads of control to execute concurrently within a single process. These individual threads of control are called threads. By default, processes have only a single thread associated with them, though it may be useful to have several. All the threads of a particular process share the same address space. In contrast, one generally thinks of processes as not sharing any of their address space with other processes. Speci cally, threads (like processes) have code, memory and other resources associated with them. Although threads share many objects with other threads of that process, threads have their own private local stack3 . One big di erence between threads and processes is that global variables are shared among all threads. Because threads execute concurrently with other threads, they must worry about synchronization and mutual exclusion when accessing shared memory. Nachos provides threads. Nachos threads execute and share the same code (the Nachos source code) and share the same global variables. The Nachos scheduler maintains a data structure called a ready list , which keeps track of the threads that are ready to execute. Threads on the ready list are ready to execute and
Actually, threads technically do share their stacks with other threads in the sense that a particular thread's stack will still be addressable by the other threads. In general, however, it is more useful to think of the stack as private, since each thread must have its own stack.
3

9

can be selected for executing by the scheduler at any time. Each thread has an associated state describing what the thread is currently doing. Nachos' threads are in one of four states:

READY: The thread is eligible to use the CPU (e.g, it's on the ready list), but another

thread happens to be running. When the scheduler selects a thread for execution, it removes it from the ready list and changes its state from READY to RUNNING. Only threads in the READY state should be found on the ready list. RUNNING: The thread is currently running. Only one thread can be in the RUNNING state at a time. In Nachos, the global variable currentThread always points to the currently running thread. BLOCKED: The thread is blocked waiting for some external event it cannot execute until that event takes place. Speci cally, the thread has put itself to sleep via Thread::Sleep(). It may be waiting on a condition variable, semaphore, etc. By de nition, a blocked thread does not reside on the ready list. JUST CREATED: The thread exists, but has no stack yet. This state is a temporary state used during thread creation. The Thread constructor creates a thread, whereas Thread::Fork() actually turns the thread into one that the CPU can execute (e.g., by placing it on the ready list).

In non-object oriented systems, operating systems maintain a data structure called a process table . Process (thread) table entries contain all the information associated with a process (e.g., saved register contents, current state, etc.). The process table information is frequently called a context block . In contrast to other systems, Nachos does not maintain an explicit process table. Instead, information associated with thread is maintained as (usually) private data of a Thread object instance. Thus, where a conventional operating system keeps thread information centralized in a single table, Nachos scatters its \thread table entries" all around memory to get at a speci c thread's information, a pointer to the thread instance is needed. The Nachos Thread object supports the following operations:

Thread *Thread(char *debugName) The Thread constructor does only minimal initialization. The thread's status is set to JUST CREATED, its stack is initialized to NULL, its given the name debugName , etc. Fork(VoidFunctionPtr func, int arg) does the interesting work of thread creation, turning a thread into one that the CPU can schedule and execute. Argument func is the address of a procedure where execution is to begin when the thread starts executing. Argument arg is a an argument that should be passed to the new thread. (Of course, procedure func must expect a single argument to be passed to it if it is to access the supplied argument.) Fork allocates stack space for the new thread, initializes the registers (by saving the initial value's in the thread's context block), etc. 10

One important detail must be considered. What should happen when procedure func returns? Since func was not called as a regular procedure call, there is no place for it to return to. Indeed, rather than returning, the thread running func should terminate. Fork takes care of this detail by building an initial activation record that makes this happen (described in detail below). void StackAllocate(VoidFunctionPtr func, int arg) This routine does the dirty work of allocating the stack and creating an initial activation record that causes execution to appear to begin in func . The details are a somewhat complicated. Speci cally, StackAllocate does the following: 1. Allocate memory for the stack. The default stack size is StackSize (4096) 4-byte integers. 2. Place a sentinel value at the top of the allocated stack. Whenever it switches to a new thread, the scheduler veri es that the sentinel value of the thread being switched out has not changed, as might happen if a thread over ows its stack during execution. 3. Initialize the program counter PC to point to the routine ThreadRoot . Instead of beginning execution at the user-supplied routine, execution actually begins in routine ThreadRoot . ThreadRoot does the following: (a) Calls an initialization routine that simply enables interrupts. (b) Calls the user-supplied function, passing it the supplied argument. (c) Calls thread::Finish(), to terminate the thread. Having thread execution begin in ThreadRoot rather than in the user-supplied routine makes it straightforward to terminate the thread when it nishes. The code for ThreadRoot is written in assembly language and is found in switch.s Note: ThreadRoot isn't run by the thread that calls Fork(). The newly created thread executes the instructions in ThreadRoot when it is scheduled and starts execution. Scheduler::FindNextToRun()). If no other threads are ready to execute, continue running the current thread. void Sleep() Suspend the current thread, change its state to BLOCKED, and remove it from the ready list. If the ready list is empty, invoke interrupt->Idle() to wait for the next interrupt. Sleep is called when the current thread needs to be blocked until some future event takes place. It is the responsibility of this \future event" to wake up the blocked thread and move it back on to the ready list. void Finish() Terminate the currently running thread. In particular, return such data structures as the stack to the system, etc. Note that it is not physically possible for a currently running thread to terminate itself properly. As the current thread executes, it makes use of its stack. How can we free the stack while the thread is still using 11

void Yield() Suspend the calling thread and select a new one for execution (by calling

it? The solution is to have a di erent thread actually deallocate the data structures of a terminated thread. Thus, Finish sets the global variable threadToBeDestroyed to point to the current thread, but does not actually terminate it. Finish then calls Sleep , which e ectively terminates the thread (e.g., it will never run again). Later, when the scheduler starts running another thread, the newly scheduled thread examines the threadToBeDestroyed variable and nishes the job.

3.1 Mechanics of Thread Switching
Switching the CPU from one thread to another involves suspending the current thread, saving its state (e.g., registers), and then restoring the state of the thread being switched to. The thread switch actually completes at the moment a new program counter is loaded into PC at that point, the CPU is no longer executing the thread switching code, it is executing code associated with the new thread. The routine Switch(oldThread, nextThread) actually performs a thread switch. Switch saves all of oldThread 's state (oldThread is the thread that is executing when Switch is called), so that it can resume executing the thread later, without the thread knowing it was suspended. Switch does the following: 1. Save all registers in oldThread 's context block . 2. What address should we save for the PC? That is, when we later resume running the just-suspended thread, where do we want it to continue execution? We want execution to resume as if the call to Switch() had returned via the normal procedure call mechanism. Speci cally, we want to resume execution at the instruction immediately following the call to Switch(). Thus, instead of saving the current PC, we place the return address (found on the stack in the thread's activation record) in the thread's context block. When the thread is resumed later, the resuming address loaded into the PC will be the instruction immediately following the \call" instruction that invoked Switch() earlier. Note: It is crucial that Switch() appear to be a regular procedure call to whoever calls it. That way, threads may call Switch() whenever they want. The call will appear to return just like a normal procedure call except that the return does not take place right away. Only after the scheduler decides to resume execution of the switched thread will it run again. 3. Once the current thread's state has been saved, load new values into the registers from the context block of the next thread. 4. At what exact point has a context switch taken place? When the current PC is replaced by the saved PC found in the process table. Once the saved PC is loaded, Switch() is no longer executing we are now executing instructions associated with the new thread, which should be the instruction immediately following the call to Switch(). As soon as the new PC is loaded, a context switch has taken place. 12

The routine Switch() is written in assembly language because it is a machine-depended routine. It has to manipulate registers, look into the thread's stack, etc. Note: After returning from Switch , the previous thread is no longer running. Thread nextThread is running now. But because it also called Switch() previously, it will return to the \right place" (the instruction after the call to Switch()). Thus, it looks like Switch() is a \normal" procedure call, but in fact, a thread switch has taken place.

3.2 Threads & Scheduling
Threads that are ready to run are kept on the ready list . A process is in the READY state only if it has all the resources it needs, other than the CPU. Processes blocked waiting for I/O, memory, etc. are generally stored in a queue associated with the resource being waited on. The scheduler decides which thread to run next. The scheduler is invoked whenever the current thread wishes to give up the CPU. For example, the current thread may have initiated an I/O operation and must wait for it to complete before executing further. Alternatively, Nachos may preempt the current thread in order to prevent one thread from monopolizing the CPU. The Nachos scheduling policy is simple: threads reside on a single, unprioritized ready list, and threads are selected in a round-robin fashion. That is, threads are always appended to the end of the ready list, and the scheduler always selects the thread at the front of the list. Scheduling is handled by routines in the Scheduler object: ready list. Note that ReadyToRun doesn't actually start running the thread it simply changes its state to READY and places it on the ready list. The thread won't start executing until later, when the scheduler chooses it. ReadyToRun is invoked, for example, by Thread::Fork() after a new thread has been created. Thread *FindNextToRun(): Select a ready thread and return it). FindNextToRun simply returns the thread at the front of the ready list. void Run(Thread *nextThread): Do the dirty work of suspending the current thread and switching to the new one. Note that it is the currently running thread that calls Run() . A thread calls this routine when it no longer wishes to execute.
Run() does the following:

void ReadyToRun(Thread *thread): Make thread ready to run and place it on the

1. Before actually switching to the new thread, check to see if the current thread overowed its stack. This is done by placing a sentinel value at the top of the stack when 13

the thread is initially created. If the running thread ever over ows its stack, the sentinel value will be overwritten, changing its value. By checking for the sentinel value every time we switch threads, we can catch threads over owing their stacks. 2. Change the state of newly selected thread to RUNNING. Nachos assumes that the calling routine (e.g. the current thread) has already changed its state to something else, (READY, BLOCKED, etc.) before calling Run(). 3. Actually switch to the next thread by invoking Switch(). After Switch returns, we are now executing as the new thread. Note, however, that because the thread being switched to previously called Switch from Run(), execution continues in Run() at the statement immediately following the call to Switch . 4. If the previous thread is terminating itself (as indicated by the threadToBeDestroyed variable), kill it now (after Switch()). As described in Section 3, threads cannot terminate themselves directly another thread must do so. It is important to understand that it is actually another thread that physically terminates the one that called Finish().

3.3 Synchronization and Mutual Exclusion
Low-level Nachos routines (including the ones discussed above) frequently disable and reenable interrupts to achieve mutual exclusion (e.g., by calling Interrupt::SetLevel()). Synchronization facilities are provided through semaphores. The Semaphore object provides the following operations: ing semaphore having an initial value of initialValue . The string debugName is also associated with the semaphore to simplify debugging. void P() Decrement the semaphore's count, blocking the caller if the count is zero. void V() Increment the semaphore's count, releasing one thread if any are blocked waiting on the count.

Semaphore(char* debugName, int initialValue) The constructor creates a new count-

3.4 Special Notes
When Nachos rst begins executing, it is executing as a single Unix process. Nachos turns this single user process into a single Nachos thread. Thus, by default, Nachos executes a single thread. When the Nachos entry point routine main returns, that thread exits as well. However, if other threads have been created and continue to exist, the Unix process continues executing Nachos. Only after all threads have terminated does the Unix Nachos process exit.

14

4 User-Level Processes
Nachos runs user programs in their own private address space. Nachos can run any MIPS binary, assuming that it restricts itself to only making system calls that Nachos understands. In Unix, \a.out" les are stored in \co " format. Nachos requires that executables be in the simpler \No " format. To convert binaries of one format to the other, use the co 2no program. Consult the Make le in the test directory for details. No -format les consist of four parts. The rst part, the No header, describes the contents of the rest of the le, giving information about the program's instructions, initialized variables and uninitialized variables. The No header resides at the very start of the le and contains pointers to the remaining sections. Speci cally, the No header contains:

no Magic A reserved \magic" number that indicates that the le is in No format. The

magic number is stored in the rst four bytes of the le. Before attempting to execute a user-program, Nachos checks the magic number to be sure that the le about to be executed is actually a Nachos executable. For each of the remaining sections, Nachos maintains the following information: virtualAddr What virtual address that segment begins at (normally zero). inFileAddr Pointer within the No le where that section actually begins (so that Nachos can read it into memory before execution begins). size The size (in bytes) of that segment.

When executing a program, Nachos creates an address space and copies the contents of the instruction and initialized variable segments into the address space. Note that the uninitialized variable section does not need to be read from the le. Since it is de ned to contain all zeros, Nachos simply allocates memory for it within the address space of the Nachos process and zeros it out.

4.1 Process Creation
Nachos processes are formed by creating an address space, allocating physical memory for the address space, loading the contents of the executable into physical memory, initializing registers and address translation tables, and then invoking machine::Run() to start execution. Run() simply \turns on" the simulated MIPS machine, having it enter an in nite loop that executes instructions one at a time). Stock Nachos assumes that only a single user program exists at a given time. Thus, when an address space is created, Nachos assumes that no one else is using physical memory and simply zeros out all of physical memory (e.g., the mainMemory character array). Nachos then reads the binary into physical memory starting at location mainMemory and initializes the translation tables to do a one-to-one mapping between virtual and physical addresses (e.g., so that any virtual address N maps directly into the physical address N). Initialization 15

of registers consists of zeroing them all out, setting PCReg and NextPCReg to 0 and 4 respectively, and setting the stackpointer to the largest virtual address of the process (the stack grows downward towards the heap and text). Nachos assumes that execution of userprograms begins at the rst instruction in the text segment (e.g., virtual address 0). When support for multiple user processes has been added, two other Nachos routines are necessary for process switching. Whenever the current processes is suspended (e.g., preempted or put to sleep), the scheduler invokes the routine AddrSpace::SaveUserState(), in order to properly save address-space related state that the low-level thread switching routines do not know about. This becomes necessary when using virtual memory when switching from one process to another, a new set of address translation tables needs to be loaded. The Nachos scheduler calls SaveUserState() whenever it is about to preempt one thread and switch to another. Likewise, before switching to a new thread, the Nachos scheduler invokes AddrSpace::RestoreUserState . RestoreUserState() insures that the proper address translation tables are loaded before execution resumes.

4.2 Creating a No Binary
Nachos is capable of executing a program containing arbitrary MIPS instructions. For example, C programs in the test directory are compiled using gcc on a MIPS machine to create \.o" les. To create an a.out binary le, the loader prepends the instructions in test/start.s before the code of the user program. File start.s contains initialization code that needs to be executed before the user's main program. Speci cally, the very rst instruction in start.s calls the user-supplied main routine, whereas the second instruction invokes the Nachos Exit system call, insuring that user processes terminate properly when their main program returns. In addition, start.s contains stub modules for invoking system calls (described below).

4.3 System Calls and Exception Handling
User programs invoke system calls by executing the MIPS \syscall" instruction, which generates a hardware trap into the Nachos kernel. The Nachos/MIPS simulator implements traps by invoking the Routine RaiseException(), passing it a arguments indicating the exact cause of the trap. RaiseException , in turn, calls ExceptionHandler to take care of the speci c problem. ExceptionHandler is passed a single argument indicating the precise cause of the trap. The \syscall" instruction indicates a system call is requested, but doesn't indicate which system call to perform. By convention, user programs place the code indicating the particular system call desired in register r2 before executing the \syscall" instruction. Additional arguments to the system call (when appropriate) can be found in registers r4-r7 , following the standard C procedure call linkage conventions. Function (and system call) return values are expected to be in register r2 on return. Warning: When accessing user memory from within the exception handler (or within Nachos in general), user-level addresses cannot be referenced directly. Recall that user-level processes execute in their own private address spaces, which the kernel cannot reference 16

#include "syscall.h" int main() { Halt() /* not reached */ }

Figure 1: Source for the program halt.c directly. Attempts to dereference pointers passed as arguments to system calls will likely lead to problems (e.g., segmentation faults) if referenced directly. Use ReadMem and WriteMem to dereference pointers passed as arguments to system calls. Consult Section 2.4 for more details.

4.4 Execution Trace of User-Level Process
Consider the simplest Nachos program, halt.c, which invokes the \halt" system call and does nothing else. Its source code is shown in Figure 1 When compiled, gcc -S generates the assembly language code shown in gure 2 (line numbers and additional comments have been added for clarity). The only instruction that directly relates to invoking the \halt" system call is given in line 27. The jal instruction executes a jump that transfers control to the label \Halt". Note that there is no label called \Halt" in this program. The code for \Halt" can be found in the le start.s . Lines 1-21 are assembler directives that don't actually generate any instructions. Lines 22-25 perform the standard procedure call linkage operations that are performed as part of starting execution in a new subroutine (e.g., saving the return address and allocating space on the stack for local variables). Line 26 is a call to a gcc-supplied library routine that Unix needs to execute before your program normally begins execution (it is not needed in Nachos, so a dummy routine is provided that does nothing). Lines 29-33 provide the standard code for returning from a procedure call, e ectively undoing the e ects of lines 22-25 (e.g., fetch the saved return address and then jump back to it). The actual instructions for making system calls are found in start.s . Figure 3 shows the subset of that le that is used by the halt program. Again, lines 1-7 are assembler directives rather than instructions. Line 8 is the rst actual instruction, and simply calls the procedure main , e.g., the main program in halt.c . Lines 9-10 are executed whenever the call to main returns, in which case we want to tell Nachos we are done via the \exit" system call. System calls are invoked at runtime by placing a code for the system call in register 2 and then executing the \syscall" machine instruction. The \syscall" instruction is a trap instruction, meaning that the next instruction to be executed will be the rst instruction of the trap handler. In Nachos, this e ectively means that execution continues now in the procedure ExceptionHandler . Consider lines 15-18, the steps involved in making an 17

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

.file # GNU C 2.4.5 # Cc1 defaults:

1 "halt.c" AL 1.1, MM 40] DECstation running ultrix compiled by GNU C

# Cc1 arguments (-G value = 0, Cpu = default, ISA = 1): # -G -quiet -dumpbase -o gcc2_compiled.: __gnu_compiled_c: .text .align 2 .globl main .loc .ent main: .frame .mask .fmask subu sw sw move jal jal $L1: move lw lw addu j .end $sp,$fp $31,20($sp) $fp,16($sp) $sp,$sp,24 $31 main # sp not trusted here $fp,24,$31 0xc0000000,-4 0x00000000,0 $sp,$sp,24 $31,20($sp) $fp,16($sp) $fp,$sp __main Halt # vars= 0, regs= 2/0, args = 16, extra= 0 1 16 main

# # # #

SP