Scheduler

4.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 reduce to the selection of the next thread by the ThreadQueue objects. Recall the implementation of KThread.runNextThread():

1   private static void runNextThread() {
2   KThread nextThread = readyQueue.nextThread();
3   if (nextThread == null)
4   nextThread = idleThread;
5
6   nextThread.run();
7   }

Line 2 calls readyQueue.nextThread() to find the next thread in the ready queue for CPU.

The nachos.threads.RoundRobinScheduler is the default, and implements a fully functional (though naive) FIFO scheduler. In the Scheduling project, you will be implementing a priority queue scheduling that deals with priority inversion.

The scheduler object is created by the ThreadKernel.initialize():

1   public void initialize(String[] args) {
2   // set scheduler
3   String schedulerName = Config.getString("ThreadedKernel.scheduler");
4   scheduler = (Scheduler) Lib.constructObject(schedulerName);
5   ...
6   }

Thus, by specifying the appropriate scheduler in the config file, one will initialize the respective scheduler object.

Implement note:

Only one type of scheduler can be used for all resources (though each has its own ThreadQueue).
In implementing a new scheduler, one may also have to implement its own ThreadQueue class.

[next] [prev] [prev-tail] [front] [up]