00001 // scheduler.cc 00002 // Routines to choose the next thread to run, and to dispatch to 00003 // that thread. 00004 // 00005 // These routines assume that interrupts are already disabled. 00006 // If interrupts are disabled, we can assume mutual exclusion 00007 // (since we are on a uniprocessor). 00008 // 00009 // NOTE: We can't use Locks to provide mutual exclusion here, since 00010 // if we needed to wait for a lock, and the lock was busy, we would 00011 // end up calling FindNextToRun(), and that would put us in an 00012 // infinite loop. 00013 // 00014 // Very simple implementation -- no priorities, straight FIFO. 00015 // Might need to be improved in later assignments. 00016 // 00017 // Copyright (c) 1992-1996 The Regents of the University of California. 00018 // All rights reserved. See copyright.h for copyright notice and limitation 00019 // of liability and disclaimer of warranty provisions. 00020 00021 #include "copyright.h" 00022 #include "debug.h" 00023 #include "scheduler.h" 00024 #include "main.h" 00025 00026 //---------------------------------------------------------------------- 00027 // Scheduler::Scheduler 00028 // Initialize the list of ready but not running threads. 00029 // Initially, no ready threads. 00030 //---------------------------------------------------------------------- 00031 00032 Scheduler::Scheduler() 00033 { 00034 readyList = new List<Thread *>; 00035 toBeDestroyed = NULL; 00036 } 00037 00038 //---------------------------------------------------------------------- 00039 // Scheduler::~Scheduler 00040 // De-allocate the list of ready threads. 00041 //---------------------------------------------------------------------- 00042 00043 Scheduler::~Scheduler() 00044 { 00045 delete readyList; 00046 } 00047 00048 //---------------------------------------------------------------------- 00049 // Scheduler::ReadyToRun 00050 // Mark a thread as ready, but not running. 00051 // Put it on the ready list, for later scheduling onto the CPU. 00052 // 00053 // "thread" is the thread to be put on the ready list. 00054 //---------------------------------------------------------------------- 00055 00056 void 00057 Scheduler::ReadyToRun (Thread *thread) 00058 { 00059 ASSERT(kernel->interrupt->getLevel() == IntOff); 00060 DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName()); 00061 00062 thread->setStatus(READY); 00063 readyList->Append(thread); 00064 } 00065 00066 //---------------------------------------------------------------------- 00067 // Scheduler::FindNextToRun 00068 // Return the next thread to be scheduled onto the CPU. 00069 // If there are no ready threads, return NULL. 00070 // Side effect: 00071 // Thread is removed from the ready list. 00072 //---------------------------------------------------------------------- 00073 00074 Thread * 00075 Scheduler::FindNextToRun () 00076 { 00077 ASSERT(kernel->interrupt->getLevel() == IntOff); 00078 00079 if (readyList->IsEmpty()) { 00080 return NULL; 00081 } else { 00082 return readyList->RemoveFront(); 00083 } 00084 } 00085 00086 //---------------------------------------------------------------------- 00087 // Scheduler::Run 00088 // Dispatch the CPU to nextThread. Save the state of the old thread, 00089 // and load the state of the new thread, by calling the machine 00090 // dependent context switch routine, SWITCH. 00091 // 00092 // Note: we assume the state of the previously running thread has 00093 // already been changed from running to blocked or ready (depending). 00094 // Side effect: 00095 // The global variable kernel->currentThread becomes nextThread. 00096 // 00097 // "nextThread" is the thread to be put into the CPU. 00098 // "finishing" is set if the current thread is to be deleted 00099 // once we're no longer running on its stack 00100 // (when the next thread starts running) 00101 //---------------------------------------------------------------------- 00102 00103 void 00104 Scheduler::Run (Thread *nextThread, bool finishing) 00105 { 00106 Thread *oldThread = kernel->currentThread; 00107 00108 ASSERT(kernel->interrupt->getLevel() == IntOff); 00109 00110 if (finishing) { // mark that we need to delete current thread 00111 ASSERT(toBeDestroyed == NULL); 00112 toBeDestroyed = oldThread; 00113 } 00114 00115 if (oldThread->space != NULL) { // if this thread is a user program, 00116 oldThread->SaveUserState(); // save the user's CPU registers 00117 oldThread->space->SaveState(); 00118 } 00119 00120 oldThread->CheckOverflow(); // check if the old thread 00121 // had an undetected stack overflow 00122 00123 kernel->currentThread = nextThread; // switch to the next thread 00124 nextThread->setStatus(RUNNING); // nextThread is now running 00125 00126 DEBUG(dbgThread, "Switching from: " << oldThread->getName() << " to: " << nextThread->getName()); 00127 00128 // This is a machine-dependent assembly language routine defined 00129 // in switch.s. You may have to think 00130 // a bit to figure out what happens after this, both from the point 00131 // of view of the thread and from the perspective of the "outside world". 00132 00133 SWITCH(oldThread, nextThread); 00134 00135 // we're back, running oldThread 00136 00137 // interrupts are off when we return from switch! 00138 ASSERT(kernel->interrupt->getLevel() == IntOff); 00139 00140 DEBUG(dbgThread, "Now in thread: " << oldThread->getName()); 00141 00142 CheckToBeDestroyed(); // check if thread we were running 00143 // before this one has finished 00144 // and needs to be cleaned up 00145 00146 if (oldThread->space != NULL) { // if there is an address space 00147 oldThread->RestoreUserState(); // to restore, do it. 00148 oldThread->space->RestoreState(); 00149 } 00150 } 00151 00152 //---------------------------------------------------------------------- 00153 // Scheduler::CheckToBeDestroyed 00154 // If the old thread gave up the processor because it was finishing, 00155 // we need to delete its carcass. Note we cannot delete the thread 00156 // before now (for example, in Thread::Finish()), because up to this 00157 // point, we were still running on the old thread's stack! 00158 //---------------------------------------------------------------------- 00159 00160 void 00161 Scheduler::CheckToBeDestroyed() 00162 { 00163 if (toBeDestroyed != NULL) { 00164 delete toBeDestroyed; 00165 toBeDestroyed = NULL; 00166 } 00167 } 00168 00169 //---------------------------------------------------------------------- 00170 // Scheduler::Print 00171 // Print the scheduler state -- in other words, the contents of 00172 // the ready list. For debugging. 00173 //---------------------------------------------------------------------- 00174 void 00175 Scheduler::Print() 00176 { 00177 cout << "Ready list contents:\n"; 00178 readyList->Apply(ThreadPrint); 00179 }