Nachos OS slides
Nachos OS slides
Nachos Instructional OS
CS 270, Tao Yang, Spring 2011
What is Nachos OS?
Allow students to examine, modify and execute
operating system software.
A skeletal OS that supports
Simulates MIPS instruction execution.
Running on a virtual machine, executed as a single
Unix process in a hosting OS.
Over 9K lines of C++ code.
Can understand its basic mechanisms by reading about 12K lines of code.
Nachos kernel threads
Nachos OS modules
(Threads mgm, File System, Code execution/memory mapping,
Simulated MIPS Machine
(CPU, Memory, Disk, Console)
Base Operating System
(Linux for our class)
Steps to Install Nachos
Obtain and install Nachos source code.
Compile the source code using gmake
Run threads demo under the threads
subdirectory (just run kernel test threads).
Copy the source code from
Run user program demo under the userprog
Nachos code directory
machine --- Basic machine specification (MIPS
threads --- threads management (HW1).
userprog -- binary code execution and system calls
vm -- virtual memory (HW3).
filesys -- file system (HW3)
test -- binary test code
network -- networking protocol
bin -- utilities/tools (binary format conversion)
Source code reading and HW1
Objectives of next 2 weeks
Scan through ~1,000-2,000 lines of code
under threads directory
Learn how context switch is accomplished among
Learn how thread scheduling is done.
Learn how locks/synchronization are implemented
Few hundred lines of code
Sample solution for Task 1, 2, &3 are available
Single-threaded vs multithreaded
Sample Example of Nacho Threads
Thread *t1 = new Thread("forked thread1");
Thread *t2 = new Thread("forked thread2");
Create 2 new threads.
Start to fork and execute a
function in each child thread.
executes the same
printf(“Hello %d\n”, i);
Function executed by
Nachos threads execute and share the same code, share same global
Nachos scheduler maintains a ready list, containing all threads that
are ready to execute.
Each thread is in one of four states: READY, RUNNING, BLOCKED,
Each thread object maintains a context block.
Thread object supports the following operations:
Thread(char *debugName). Create a thread.
Fork(VoidFunctionPtr func, int arg). Let a thread execute a
Yield(). Suspend the calling thread and select a new one for
Sleep(). Suspend the current thread, change its state to
BLOCKED, and remove it from the ready list
Nachos Thread States and
In HW 1 we are only
concerned with the
states in this box.
interrupt or ExceptionHandler
When running in user
mode, the thread
executes within the
machine simulator. HW
2 covers this.
Switching involves suspending current thread, saving
its state, and restoring the state of new thread.
Following code involved in execution: the old code,
the new code, and the code that performs switching.
Save all registers in oldThread's context block.
Save the program address to be used when the
old thread is resumed.
Load new values into the registers from the
context block of the new thread.
Once the saved PC of the new thread is loaded,
Switch() is no longer executing.
Scheduler object for thread
A scheduler decides which thread to run next by scanning the
The scheduler is invoked whenever the current thread gives up
The current Nachos scheduling policy is round-robin: new
threads are appended to the end of the ready list, and the
scheduler selects the front of the list.
The Scheduler object has the following operations:
Make thread ready to run and place it on the ready list.
Semaphore object for thread
Disable and re-enable interrupts to achieve mutual
exclusion (e.g., by calling Interrupt::SetLevel()).
Operations for a Semaphore object:
Semaphore(char* debugName, int initialValue)
P(): Decrement the semaphore's count, blocking
the caller if the count is zero.
V() :Increment the semaphore's count, releasing
one thread if any are blocked waiting on the
Key steps when Nachos executes
After you type ``nachos'' under threads subdirectory:
It is executing as a single Unix process.
The main() calls
Initialize() to start up interrupt handling, create a
scheduler for managing the ready queue.
ThreadTest() (to be explained for HW 1).
currentThread->Finish() to let other threads
continue to run.
Key Calling graph when Nachos
executes under thread directory
All files are in threads
func() such as
Executed by SWITCH(oldThread, nextThread)
# call startup procedure. For a
new thread, it is InterruptEnable().
# call main procedure
# when were done, call clean up
When will thread:Finish() be called?
At the end of the forked thread. Check ThreadRoot assembly
At the end of the main() thread.
Thread:Finish() calls scheduler->run() to run a new
thread. Will the old thread (that calls Thread:Finish())
be returned and continue to be executed?
No. Because the following is called first.
threadToBeDestroyed = currentThread;
Scheduler->Run() will delete such TCB
In Sleep() or Yield(), the interrupt is turned off before calling
scheduler->() to execute another thread.
When will interrupt be turned on?
In executing the switched thread, ThreadRoot() assembly code
first executes StartupPC function which is
machineState[StartupPCState] = (int) InterruptEnable;
HW 1: threads & synchronization
Work under threads subdirectory.
Modify ThreadTest() to do simple threads
programming (spawning multiple threads).
Implement locks and condition variables (missing
from the file synch.cc).
Read Nachos code and add few hundred lines of code.
Undocumented sample solution is provided.
HW 1: Files involved
main.cc, threadtest.cc -- a simple test of our thread routines.
thread.h thread.cc -- Nachos thread data structure and operations.
scheduler.h scheduler.cc -- The thread ready list.
synch.h synch.cc -- synchronization routines.
Other related files.
synchlist.h, synchlist.cc -- synchronized access to lists using
locks/conditions (useful examples for your programming).
list.h list.cc -- generic list management.
system.h, system.cc -- Nachos startup/shutdown routines.
utility.h utility.cc -- some useful definitions and debugging routines.
interrupt.h interrupt.cc -- manage interrupts.
time.h timer.cc -- clock emulation.
switch.h, switch.s -- assembly code for thread switching.
stats.h stats.cc -- collect interesting statistics.
HW Sample solution
Has an old solution for HW1, HW2, HW3
HW1 threads subdirectory. ~400 lines of new code.
~50% are for Tasks 1/2/3. Code for task 4 is not useful.
HW2 -> userprog subdirectory. ~1300 lines of new code.
HW3 -> vm and filesys. ~1200 lines of new code. 800 may
Mixed benefits/problems in using other students’ code.
e.g. Not well documented, not fully tested. Possibly awkward
Still your responsibility to produce good solutions
(correctness, performance, style).