4.1 KThread and Nachos thread life cycles

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 tcb is contained by each KThread object 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. The life cycle of KThread is illustrated in Figure 26.

• statusNew: A newly created, yet to be forked thread.
• statusReady: A thread waiting for access to the CPU. KThread.ready() will add the thread to the ready queue and set the status to statusReady.
• statusRunning: The thread currently using the CPU. KThread.restoreState() is responsible for setting status to statusRunning, and is called by KThread.runNextThread().
• statusBlocked: A thread which is asleep (as set by KThread.sleep()), waiting on some resource besides the CPU.
• statusFinished: A thread scheduled for destruction. Use KThread.finish() to set this status.

Internally, Nachos implements threading using a Java thread for each TCB object. 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. For the understanding of KThread, we can focus on its public methods.

The life cycle of a KThread object starts when it is created. The first KThread is created in the initalize method of ThreadKernel:

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

If the current thread exists, calling the constructor for KThread with a Runnable object will simply create a new TCB object with the default status statusNew. Note that the KThread object is not yet added to the ready queue until its KThread.fork() method is called. KThread.fork() causes the Java thread by the associated TCB object to begin execution and calls the KThread.ready() method, which puts the KThread object in the ready queue.

Note that KThread.fork() differs from Unix fork system calls, which returns twice, once in the parent process and once in the child process. KThread.fork() only serves to prepare the associated KThread for scheduling.

Other public KThread methods related to the thread life cycle include, KThread.run(), KThread.sleep(), KThread.yield(), KThread.finish(), KThread.join():

• KThread.run()
• KThread.yield() causes the current thread to relinquish it CPU, add itself to the ready queue and switch to the next thread (or the idle thread) in the ready queue based on the scheduler. Recall that in a time-shared OS, context switches can happen either a thread finishes its execution, its CPU slice is up, it is blocked on some resources, or it yields voluntarily.
• KThread.sleep() is called when the current thread has either finished or been blocked. If the current thread is blocked (on a synchronization primitive, i.e. a Semaphore, Lock, or Condition), eventually some thread will wake this thread up, putting it back on the ready queue so that it can be rescheduled. The logic of waking a thread has to be implemented by the respective primitives.
• KThread.join() is used by a calling thread to wait for the callee thread to finish before it can proceed. Consider the following example:
  1   ...
  2   KThread t1 = new KThread(new Runnable() {
  3   public void run() {
  4   do something;
  5   }
  6   }
  7  
  8   KThread t2 = new KThread(new Runnable() {
  9   public void run() {
  10   do something else;
  11   }
  12   }
  13  
  14   ...
  15  
  16   t1.join();
  17   t2.join();
  18  
  19   System.out.println("Finished\n");
  20  
  21   ...

  The main thread is blocked and would not reach line 19 until both threads finish. Since a current thread cannot join itself, in KThread.join(), this thread (the callee) should be different from the current thread (the caller). In the thread and synchronization project, you will be asked to complete the implementation of KThread.join().

• KThread.finish() finishes the current thread and schedule it to be destroyed when it is safe to do so.