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:

void ReadyToRun(Thread *thread):

Make thread ready to run and place it on the 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:

1. Before actually switching to the new thread, check to see if the current thread overflowed its stack. This is done by placing a sentinel value at the top of the stack when the thread is initially created. If the running thread ever overflows 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 overflowing 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().