3. Threads and Scheduling

Nachos provides a kernel threading package, allowing multiple tasks to run concurrently (see nachos.threads.ThreadedKernel and nachos.threads.KThread). Once the user-prcesses are implmented (phase 2), some threads may be running the MIPS processor simulation. As the scheduler and thread package are concerned, there is no difference between a thread running the MIPS simulation and one running just kernel Java code.

3.1. Thread Package

All Nachos threads are instances of nachos.threads.KThread (threads capable of running user-level MIPS code are a subclass of KThread, nachos.userprog.UThread). A nachos.machine.TCB object is contained by each KThread and provides low-level support for context switches, thread creation, thread destruction, and thread yield.

Every KThread has a status member that tracks the state of the thread. Certain KThread methods will fail (with a Lib.assert()) if called on threads in the wrong state; check the KThread Javadoc for details.


A newly created, yet to be forked thread.


A thread waiting for access to the CPU. KThread.ready() will add the thread to the ready queue and set the status to statusReady.


The thread currently using the CPU. KThread.restoreState() is responsible for setting status to statusRunning, and is called by KThread.runNextThread().


A thread which is asleep (as set by KThread.sleep()), waiting on some resource besides the CPU.


A thread scheduled for destruction. Use KThread.finish() to set this status.

Internally, Nachos implements threading using a Java thread for each TCB. The Java threads are synchronized by the TCBs such that exactly one is running at any given time. This provides the illusion of context switches saving state for the current thread and loading the saved state of the new thread. This detail, however, is only important for use with debuggers (which will show multiple Java threads), as the behavior is equivelant to a context switch on a real processor.

3.2. Scheduler

A sub-class (specified in the nachos.conf) of the abstract base class nachos.threads.Scheduler is responsible for scheduling threads for all limited resources, be it the CPU, a synchronization construct like a lock, or even a thread join operation. For each resource a nachos.threads.ThreadQueue is created by Scheduler.newThreadQueue(). The implementation of the resource (e.g. nachos.threads.Semaphore class) is responsible for adding KThreads to the ThreadQueue (ThreadQueue.waitForAccess()) and requesting the ThreadQueue return the next thread (ThreadQueue.nextThread()). Thus, all scheduling decisions (including those regarding the CPU's ready queue) reduce to the selection of the next thread by the ThreadQueue objects[1].

Various phases of the project will require modifications to the scheduler base class. The nachos.threads.RoundRobinScheduler is the default, and implements a fully functional (though naive) FIFO scheduler. Phase 1 of the projects requires the student to complete the nachos.threads.PriorityScheduler; for phase 2, students complete nachos.threads.LotteryScheduler.

3.3. Creating the First Thread

Upto the point where the Kernel is created, the boot process is fairly easy to follow - Nachos is just making Java objects, same as any other Java program. Also like any other single-threaded Java program, Nachos code is executing on the initial Java thread created automaticaly for it by Java. ThreadedKernel.initialize() has the task of starting threading:

public void initialize(String[] args) {
      // start threading
      new KThread(null);

The first clue that something special is happening should be that the new KThread object created is not stored in a variable inside initialize(). The constructor for KThread follows the following procedure the first time it is called:

  1. Create the ready queue (ThreadedKernel.scheduler.newThreadQueue()).

  2. Allocate the CPU to the new KThread object being created (readyQueue.acquire(this)).

  3. Set KThread.currentThread to the new KThread being made.

  4. Set the TCB object of the new KThread to TCB.currentTCB(). In doing so, the currently running Java thread is assigned to the new KThread object being created.

  5. Change the status of the new KThread from the default (statusNew) to statusRunning. This bypasses the statusReady state.

  6. Create an idle thread.

    1. Make another new KThread, with the target set to an infinite yield() loop.

    2. Fork the idle thread off from the main thread.

After this procedure, there are two KThread objects, each with a TCB object (one for the main thread, and one for the idle thread). The main thread is not special - the scheduler treats it exactly like any other KThread. The main thread can create other threads, it can die, it can block. The Nachos session will not end until all KThreads finish, regardless of whether the main thread is alive.

For the most part the idle thread is also a normal thread, which can be contexted switched like any other. The only difference is it will never be added to the ready queue (KThread.ready() has an explicit check for the idle thread). Instead, if readyQueue.nextThread() returns null, the thread system will switch to the idle thread.

Note: While the Nachos idle thread does nothing but yield() forever, some systems use the idle thread to do work. One common use is zeroing memory to prepare it for reallocation.

3.4. Creating More Threads

Creating subsequent threads is much simpler. As described in the KThread Javadoc, a new KThread is created, passing the constructor a Runnable object. Then, fork() is called:

KThread newThread = new KThread(myRunnable);

This sequence results in the new thread being placed on the ready queue. The currently running thread does not immediatly yield, however.

3.4.1. Java Anonymous Classes in Nachos

The Nachos source is relatively clean, using only basic Java, with the exception of the use of anonymous classes to replicate the functionality of function pointers in C++. The following code illustrates the use of an anonymous class to create a new KThread object which, when forked, will execute the myFunction() method of the encolosing object.

Runnable myRunnable = new Runnable() {
		public void run() {
KThread newThread = new KThread(myRunnable);

This code creates a new object of type Runnable inside the context of the enclosing object. Since myRunnable has no method myFunction(), executing myRunnable.run() will cause Java to look in the enclosing class for a myFunction() method.

3.5. On Thread Death

All threads have some resources allocated to them which are neccessary for the thread to run (e.g. the TCB object). Since the thread itself cannot deallocate these resources while it is running, it leaves a virtual will asking the next thread which runs to deallocate its resources. This is implemented in KThread.finish(), which sets KThread.toBeDestroyed to the currently running thread. It then sets current thread's status field to statusFinished and calls sleep().

Since the thread is not waiting on a ThreadQueue object, its sleep will be permanent (that is, Nachos will never try to wake the thread). This scheme does, however, require that after every context switch, the newly running thread must check toBeDestroyed.

Note: In the C++ version of Nachos, thread death was complicated by the explicit memory deallocation required, combined with dangling references that still pointing to the thread after death (for example, most thread join() implementations requires some reference to the thread). In Java, the garbage collector is responsible for noticing when these references are detached, significantly simplifying the thread finishing process.



The ThreadQueue object representing the ready queue is stored in the static variable KThread.readyQueue.