00001 // thread.cc 00002 // Routines to manage threads. These are the main operations: 00003 // 00004 // Fork -- create a thread to run a procedure concurrently 00005 // with the caller (this is done in two steps -- first 00006 // allocate the Thread object, then call Fork on it) 00007 // Begin -- called when the forked procedure starts up, to turn 00008 // interrupts on and clean up after last thread 00009 // Finish -- called when the forked procedure finishes, to clean up 00010 // Yield -- relinquish control over the CPU to another ready thread 00011 // Sleep -- relinquish control over the CPU, but thread is now blocked. 00012 // In other words, it will not run again, until explicitly 00013 // put back on the ready queue. 00014 // 00015 // Copyright (c) 1992-1996 The Regents of the University of California. 00016 // All rights reserved. See copyright.h for copyright notice and limitation 00017 // of liability and disclaimer of warranty provisions. 00018 00019 #include "copyright.h" 00020 #include "thread.h" 00021 #include "switch.h" 00022 #include "synch.h" 00023 #include "sysdep.h" 00024 00025 // this is put at the top of the execution stack, for detecting stack overflows 00026 const int STACK_FENCEPOST = 0xdedbeef; 00027 00028 //---------------------------------------------------------------------- 00029 // Thread::Thread 00030 // Initialize a thread control block, so that we can then call 00031 // Thread::Fork. 00032 // 00033 // "threadName" is an arbitrary string, useful for debugging. 00034 //---------------------------------------------------------------------- 00035 00036 Thread::Thread(char* threadName) 00037 { 00038 name = threadName; 00039 stackTop = NULL; 00040 stack = NULL; 00041 status = JUST_CREATED; 00042 for (int i = 0; i < MachineStateSize; i++) { 00043 machineState[i] = NULL; // not strictly necessary, since 00044 // new thread ignores contents 00045 // of machine registers 00046 } 00047 space = NULL; 00048 } 00049 00050 //---------------------------------------------------------------------- 00051 // Thread::~Thread 00052 // De-allocate a thread. 00053 // 00054 // NOTE: the current thread *cannot* delete itself directly, 00055 // since it is still running on the stack that we need to delete. 00056 // 00057 // NOTE: if this is the main thread, we can't delete the stack 00058 // because we didn't allocate it -- we got it automatically 00059 // as part of starting up Nachos. 00060 //---------------------------------------------------------------------- 00061 00062 Thread::~Thread() 00063 { 00064 DEBUG(dbgThread, "Deleting thread: " << name); 00065 00066 ASSERT(this != kernel->currentThread); 00067 if (stack != NULL) 00068 DeallocBoundedArray((char *) stack, StackSize * sizeof(int)); 00069 } 00070 00071 //---------------------------------------------------------------------- 00072 // Thread::Fork 00073 // Invoke (*func)(arg), allowing caller and callee to execute 00074 // concurrently. 00075 // 00076 // NOTE: although our definition allows only a single argument 00077 // to be passed to the procedure, it is possible to pass multiple 00078 // arguments by making them fields of a structure, and passing a pointer 00079 // to the structure as "arg". 00080 // 00081 // Implemented as the following steps: 00082 // 1. Allocate a stack 00083 // 2. Initialize the stack so that a call to SWITCH will 00084 // cause it to run the procedure 00085 // 3. Put the thread on the ready queue 00086 // 00087 // "func" is the procedure to run concurrently. 00088 // "arg" is a single argument to be passed to the procedure. 00089 //---------------------------------------------------------------------- 00090 00091 void 00092 Thread::Fork(VoidFunctionPtr func, void *arg) 00093 { 00094 Interrupt *interrupt = kernel->interrupt; 00095 Scheduler *scheduler = kernel->scheduler; 00096 IntStatus oldLevel; 00097 00098 DEBUG(dbgThread, "Forking thread: " << name << " f(a): " << (int) func << " " << arg); 00099 00100 StackAllocate(func, arg); 00101 00102 oldLevel = interrupt->SetLevel(IntOff); 00103 scheduler->ReadyToRun(this); // ReadyToRun assumes that interrupts 00104 // are disabled! 00105 (void) interrupt->SetLevel(oldLevel); 00106 } 00107 00108 //---------------------------------------------------------------------- 00109 // Thread::CheckOverflow 00110 // Check a thread's stack to see if it has overrun the space 00111 // that has been allocated for it. If we had a smarter compiler, 00112 // we wouldn't need to worry about this, but we don't. 00113 // 00114 // NOTE: Nachos will not catch all stack overflow conditions. 00115 // In other words, your program may still crash because of an overflow. 00116 // 00117 // If you get bizarre results (such as seg faults where there is no code) 00118 // then you *may* need to increase the stack size. You can avoid stack 00119 // overflows by not putting large data structures on the stack. 00120 // Don't do this: void foo() { int bigArray[10000]; ... } 00121 //---------------------------------------------------------------------- 00122 00123 void 00124 Thread::CheckOverflow() 00125 { 00126 if (stack != NULL) { 00127 #ifdef HPUX // Stacks grow upward on the Snakes 00128 ASSERT(stack[StackSize - 1] == STACK_FENCEPOST); 00129 #else 00130 ASSERT(*stack == STACK_FENCEPOST); 00131 #endif 00132 } 00133 } 00134 00135 //---------------------------------------------------------------------- 00136 // Thread::Begin 00137 // Called by ThreadRoot when a thread is about to begin 00138 // executing the forked procedure. 00139 // 00140 // It's main responsibilities are: 00141 // 1. deallocate the previously running thread if it finished 00142 // (see Thread::Finish()) 00143 // 2. enable interrupts (so we can get time-sliced) 00144 //---------------------------------------------------------------------- 00145 00146 void 00147 Thread::Begin () 00148 { 00149 ASSERT(this == kernel->currentThread); 00150 DEBUG(dbgThread, "Beginning thread: " << name); 00151 00152 kernel->scheduler->CheckToBeDestroyed(); 00153 kernel->interrupt->Enable(); 00154 } 00155 00156 //---------------------------------------------------------------------- 00157 // Thread::Finish 00158 // Called by ThreadRoot when a thread is returning from the 00159 // forked procedure or called it directly 00160 // 00161 // NOTE: we can't immediately de-allocate the thread data structure 00162 // or the execution stack, because we're still running in the thread 00163 // and we're still on the stack! Instead, we tell the scheduler 00164 // to call the destructor, once it is running in the context of a different thread. 00165 // 00166 // NOTE: we disable interrupts, because Sleep() assumes interrupts 00167 // are disabled. 00168 //---------------------------------------------------------------------- 00169 00170 // 00171 void 00172 Thread::Finish () 00173 { 00174 (void) kernel->interrupt->SetLevel(IntOff); 00175 ASSERT(this == kernel->currentThread); 00176 00177 DEBUG(dbgThread, "Finishing thread: " << name); 00178 00179 Sleep(TRUE); // invokes SWITCH 00180 // not reached 00181 } 00182 00183 //---------------------------------------------------------------------- 00184 // Thread::Yield 00185 // Relinquish the CPU if any other thread is ready to run. 00186 // If so, put the thread on the end of the ready list, so that 00187 // it will eventually be re-scheduled. 00188 // 00189 // NOTE: returns immediately if no other thread on the ready queue. 00190 // Otherwise returns when the thread eventually works its way 00191 // to the front of the ready list and gets re-scheduled. 00192 // 00193 // NOTE: we disable interrupts, so that looking at the thread 00194 // on the front of the ready list, and switching to it, can be done 00195 // atomically. On return, we re-set the interrupt level to its 00196 // original state, in case we are called with interrupts disabled. 00197 // 00198 // Similar to Thread::Sleep(), but a little different. 00199 //---------------------------------------------------------------------- 00200 00201 void 00202 Thread::Yield () 00203 { 00204 Thread *nextThread; 00205 IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff); 00206 00207 ASSERT(this == kernel->currentThread); 00208 00209 DEBUG(dbgThread, "Yielding thread: " << name); 00210 00211 nextThread = kernel->scheduler->FindNextToRun(); 00212 if (nextThread != NULL) { 00213 kernel->scheduler->ReadyToRun(this); 00214 kernel->scheduler->Run(nextThread, FALSE); 00215 } 00216 (void) kernel->interrupt->SetLevel(oldLevel); 00217 } 00218 00219 //---------------------------------------------------------------------- 00220 // Thread::Sleep 00221 // Relinquish the CPU, because the current thread has either 00222 // finished or is blocked waiting on a synchronization 00223 // variable (Semaphore, Lock, or Condition). In the latter case, 00224 // eventually some thread will wake this thread up, and put it 00225 // back on the ready queue, so that it can be re-scheduled. 00226 // 00227 // NOTE: if there are no threads on the ready queue, that means 00228 // we have no thread to run. "Interrupt::Idle" is called 00229 // to signify that we should idle the CPU until the next I/O interrupt 00230 // occurs (the only thing that could cause a thread to become 00231 // ready to run). 00232 // 00233 // NOTE: we assume interrupts are already disabled, because it 00234 // is called from the synchronization routines which must 00235 // disable interrupts for atomicity. We need interrupts off 00236 // so that there can't be a time slice between pulling the first thread 00237 // off the ready list, and switching to it. 00238 //---------------------------------------------------------------------- 00239 void 00240 Thread::Sleep (bool finishing) 00241 { 00242 Thread *nextThread; 00243 00244 ASSERT(this == kernel->currentThread); 00245 ASSERT(kernel->interrupt->getLevel() == IntOff); 00246 00247 DEBUG(dbgThread, "Sleeping thread: " << name); 00248 00249 status = BLOCKED; 00250 while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL) 00251 kernel->interrupt->Idle(); // no one to run, wait for an interrupt 00252 00253 // returns when it's time for us to run 00254 kernel->scheduler->Run(nextThread, finishing); 00255 } 00256 00257 //---------------------------------------------------------------------- 00258 // ThreadBegin, ThreadFinish, ThreadPrint 00259 // Dummy functions because C++ does not (easily) allow pointers to member 00260 // functions. So we create a dummy C function 00261 // (which we can pass a pointer to), that then simply calls the 00262 // member function. 00263 //---------------------------------------------------------------------- 00264 00265 static void ThreadFinish() { kernel->currentThread->Finish(); } 00266 static void ThreadBegin() { kernel->currentThread->Begin(); } 00267 void ThreadPrint(Thread *t) { t->Print(); } 00268 00269 #ifdef PARISC 00270 00271 //---------------------------------------------------------------------- 00272 // PLabelToAddr 00273 // On HPUX, function pointers don't always directly point to code, 00274 // so we need to do the conversion. 00275 //---------------------------------------------------------------------- 00276 00277 static void * 00278 PLabelToAddr(void *plabel) 00279 { 00280 int funcPtr = (int) plabel; 00281 00282 if (funcPtr & 0x02) { 00283 // L-Field is set. This is a PLT pointer 00284 funcPtr -= 2; // Get rid of the L bit 00285 return (*(void **)funcPtr); 00286 } else { 00287 // L-field not set. 00288 return plabel; 00289 } 00290 } 00291 #endif 00292 00293 //---------------------------------------------------------------------- 00294 // Thread::StackAllocate 00295 // Allocate and initialize an execution stack. The stack is 00296 // initialized with an initial stack frame for ThreadRoot, which: 00297 // enables interrupts 00298 // calls (*func)(arg) 00299 // calls Thread::Finish 00300 // 00301 // "func" is the procedure to be forked 00302 // "arg" is the parameter to be passed to the procedure 00303 //---------------------------------------------------------------------- 00304 00305 void 00306 Thread::StackAllocate (VoidFunctionPtr func, void *arg) 00307 { 00308 stack = (int *) AllocBoundedArray(StackSize * sizeof(int)); 00309 00310 #ifdef PARISC 00311 // HP stack works from low addresses to high addresses 00312 // everyone else works the other way: from high addresses to low addresses 00313 stackTop = stack + 16; // HP requires 64-byte frame marker 00314 stack[StackSize - 1] = STACK_FENCEPOST; 00315 #endif 00316 00317 #ifdef SPARC 00318 stackTop = stack + StackSize - 96; // SPARC stack must contains at 00319 // least 1 activation record 00320 // to start with. 00321 *stack = STACK_FENCEPOST; 00322 #endif 00323 00324 #ifdef PowerPC // RS6000 00325 stackTop = stack + StackSize - 16; // RS6000 requires 64-byte frame marker 00326 *stack = STACK_FENCEPOST; 00327 #endif 00328 00329 #ifdef DECMIPS 00330 stackTop = stack + StackSize - 4; // -4 to be on the safe side! 00331 *stack = STACK_FENCEPOST; 00332 #endif 00333 00334 #ifdef ALPHA 00335 stackTop = stack + StackSize - 8; // -8 to be on the safe side! 00336 *stack = STACK_FENCEPOST; 00337 #endif 00338 00339 00340 #ifdef x86 00341 // the x86 passes the return address on the stack. In order for SWITCH() 00342 // to go to ThreadRoot when we switch to this thread, the return addres 00343 // used in SWITCH() must be the starting address of ThreadRoot. 00344 stackTop = stack + StackSize - 4; // -4 to be on the safe side! 00345 *(--stackTop) = (int) ThreadRoot; 00346 *stack = STACK_FENCEPOST; 00347 #endif 00348 00349 #ifdef PARISC 00350 machineState[PCState] = PLabelToAddr(ThreadRoot); 00351 machineState[StartupPCState] = PLabelToAddr(ThreadBegin); 00352 machineState[InitialPCState] = PLabelToAddr(func); 00353 machineState[InitialArgState] = arg; 00354 machineState[WhenDonePCState] = PLabelToAddr(ThreadFinish); 00355 #else 00356 machineState[PCState] = (void*)ThreadRoot; 00357 machineState[StartupPCState] = (void*)ThreadBegin; 00358 machineState[InitialPCState] = (void*)func; 00359 machineState[InitialArgState] = (void*)arg; 00360 machineState[WhenDonePCState] = (void*)ThreadFinish; 00361 #endif 00362 } 00363 00364 #include "machine.h" 00365 00366 //---------------------------------------------------------------------- 00367 // Thread::SaveUserState 00368 // Save the CPU state of a user program on a context switch. 00369 // 00370 // Note that a user program thread has *two* sets of CPU registers -- 00371 // one for its state while executing user code, one for its state 00372 // while executing kernel code. This routine saves the former. 00373 //---------------------------------------------------------------------- 00374 00375 void 00376 Thread::SaveUserState() 00377 { 00378 for (int i = 0; i < NumTotalRegs; i++) 00379 userRegisters[i] = kernel->machine->ReadRegister(i); 00380 } 00381 00382 //---------------------------------------------------------------------- 00383 // Thread::RestoreUserState 00384 // Restore the CPU state of a user program on a context switch. 00385 // 00386 // Note that a user program thread has *two* sets of CPU registers -- 00387 // one for its state while executing user code, one for its state 00388 // while executing kernel code. This routine restores the former. 00389 //---------------------------------------------------------------------- 00390 00391 void 00392 Thread::RestoreUserState() 00393 { 00394 for (int i = 0; i < NumTotalRegs; i++) 00395 kernel->machine->WriteRegister(i, userRegisters[i]); 00396 } 00397 00398 00399 //---------------------------------------------------------------------- 00400 // SimpleThread 00401 // Loop 5 times, yielding the CPU to another ready thread 00402 // each iteration. 00403 // 00404 // "which" is simply a number identifying the thread, for debugging 00405 // purposes. 00406 //---------------------------------------------------------------------- 00407 00408 static void 00409 SimpleThread(int which) 00410 { 00411 int num; 00412 00413 for (num = 0; num < 5; num++) { 00414 cerr << "*** thread " << which << " looped " << num << " times\n"; 00415 kernel->currentThread->Yield(); 00416 } 00417 } 00418 00419 //---------------------------------------------------------------------- 00420 // Thread::SelfTest 00421 // Set up a ping-pong between two threads, by forking a thread 00422 // to call SimpleThread, and then calling SimpleThread ourselves. 00423 //---------------------------------------------------------------------- 00424 00425 void 00426 Thread::SelfTest() 00427 { 00428 DEBUG(dbgThread, "Entering Thread::SelfTest"); 00429 00430 Thread *t = new Thread("forked thread"); 00431 00432 t->Fork((VoidFunctionPtr) SimpleThread, (void *) 1); 00433 kernel->currentThread->Yield(); 00434 SimpleThread(0); 00435 } 00436