00001 // synch.cc 00002 // Routines for synchronizing threads. Three kinds of 00003 // synchronization routines are defined here: semaphores, locks 00004 // and condition variables. 00005 // 00006 // Any implementation of a synchronization routine needs some 00007 // primitive atomic operation. We assume Nachos is running on 00008 // a uniprocessor, and thus atomicity can be provided by 00009 // turning off interrupts. While interrupts are disabled, no 00010 // context switch can occur, and thus the current thread is guaranteed 00011 // to hold the CPU throughout, until interrupts are reenabled. 00012 // 00013 // Because some of these routines might be called with interrupts 00014 // already disabled (Semaphore::V for one), instead of turning 00015 // on interrupts at the end of the atomic operation, we always simply 00016 // re-set the interrupt state back to its original value (whether 00017 // that be disabled or enabled). 00018 // 00019 // Once we'e implemented one set of higher level atomic operations, 00020 // we can implement others using that implementation. We illustrate 00021 // this by implementing locks and condition variables on top of 00022 // semaphores, instead of directly enabling and disabling interrupts. 00023 // 00024 // Locks are implemented using a semaphore to keep track of 00025 // whether the lock is held or not -- a semaphore value of 0 means 00026 // the lock is busy; a semaphore value of 1 means the lock is free. 00027 // 00028 // The implementation of condition variables using semaphores is 00029 // a bit trickier, as explained below under Condition::Wait. 00030 // 00031 // Copyright (c) 1992-1996 The Regents of the University of California. 00032 // All rights reserved. See copyright.h for copyright notice and limitation 00033 // of liability and disclaimer of warranty provisions. 00034 00035 #include "copyright.h" 00036 #include "synch.h" 00037 #include "main.h" 00038 00039 //---------------------------------------------------------------------- 00040 // Semaphore::Semaphore 00041 // Initialize a semaphore, so that it can be used for synchronization. 00042 // 00043 // "debugName" is an arbitrary name, useful for debugging. 00044 // "initialValue" is the initial value of the semaphore. 00045 //---------------------------------------------------------------------- 00046 00047 Semaphore::Semaphore(char* debugName, int initialValue) 00048 { 00049 name = debugName; 00050 value = initialValue; 00051 queue = new List<Thread *>; 00052 } 00053 00054 //---------------------------------------------------------------------- 00055 // Semaphore::Semaphore 00056 // De-allocate semaphore, when no longer needed. Assume no one 00057 // is still waiting on the semaphore! 00058 //---------------------------------------------------------------------- 00059 00060 Semaphore::~Semaphore() 00061 { 00062 delete queue; 00063 } 00064 00065 //---------------------------------------------------------------------- 00066 // Semaphore::P 00067 // Wait until semaphore value > 0, then decrement. Checking the 00068 // value and decrementing must be done atomically, so we 00069 // need to disable interrupts before checking the value. 00070 // 00071 // Note that Thread::Sleep assumes that interrupts are disabled 00072 // when it is called. 00073 //---------------------------------------------------------------------- 00074 00075 void 00076 Semaphore::P() 00077 { 00078 Interrupt *interrupt = kernel->interrupt; 00079 Thread *currentThread = kernel->currentThread; 00080 00081 // disable interrupts 00082 IntStatus oldLevel = interrupt->SetLevel(IntOff); 00083 00084 while (value == 0) { // semaphore not available 00085 queue->Append(currentThread); // so go to sleep 00086 currentThread->Sleep(FALSE); 00087 } 00088 value--; // semaphore available, consume its value 00089 00090 // re-enable interrupts 00091 (void) interrupt->SetLevel(oldLevel); 00092 } 00093 00094 //---------------------------------------------------------------------- 00095 // Semaphore::V 00096 // Increment semaphore value, waking up a waiter if necessary. 00097 // As with P(), this operation must be atomic, so we need to disable 00098 // interrupts. Scheduler::ReadyToRun() assumes that interrupts 00099 // are disabled when it is called. 00100 //---------------------------------------------------------------------- 00101 00102 void 00103 Semaphore::V() 00104 { 00105 Interrupt *interrupt = kernel->interrupt; 00106 00107 // disable interrupts 00108 IntStatus oldLevel = interrupt->SetLevel(IntOff); 00109 00110 if (!queue->IsEmpty()) { // make thread ready. 00111 kernel->scheduler->ReadyToRun(queue->RemoveFront()); 00112 } 00113 value++; 00114 00115 // re-enable interrupts 00116 (void) interrupt->SetLevel(oldLevel); 00117 } 00118 00119 //---------------------------------------------------------------------- 00120 // Semaphore::SelfTest, SelfTestHelper 00121 // Test the semaphore implementation, by using a semaphore 00122 // to control two threads ping-ponging back and forth. 00123 //---------------------------------------------------------------------- 00124 00125 static Semaphore *ping; 00126 static void 00127 SelfTestHelper (Semaphore *pong) 00128 { 00129 for (int i = 0; i < 10; i++) { 00130 ping->P(); 00131 pong->V(); 00132 } 00133 } 00134 00135 void 00136 Semaphore::SelfTest() 00137 { 00138 Thread *helper = new Thread("ping"); 00139 00140 ASSERT(value == 0); // otherwise test won't work! 00141 ping = new Semaphore("ping", 0); 00142 helper->Fork((VoidFunctionPtr) SelfTestHelper, this); 00143 for (int i = 0; i < 10; i++) { 00144 ping->V(); 00145 this->P(); 00146 } 00147 delete ping; 00148 } 00149 00150 //---------------------------------------------------------------------- 00151 // Lock::Lock 00152 // Initialize a lock, so that it can be used for synchronization. 00153 // Initially, unlocked. 00154 // 00155 // "debugName" is an arbitrary name, useful for debugging. 00156 //---------------------------------------------------------------------- 00157 00158 Lock::Lock(char* debugName) 00159 { 00160 name = debugName; 00161 semaphore = new Semaphore("lock", 1); // initially, unlocked 00162 lockHolder = NULL; 00163 } 00164 00165 //---------------------------------------------------------------------- 00166 // Lock::~Lock 00167 // Deallocate a lock 00168 //---------------------------------------------------------------------- 00169 Lock::~Lock() 00170 { 00171 delete semaphore; 00172 } 00173 00174 //---------------------------------------------------------------------- 00175 // Lock::Acquire 00176 // Atomically wait until the lock is free, then set it to busy. 00177 // Equivalent to Semaphore::P(), with the semaphore value of 0 00178 // equal to busy, and semaphore value of 1 equal to free. 00179 //---------------------------------------------------------------------- 00180 00181 void Lock::Acquire() 00182 { 00183 semaphore->P(); 00184 lockHolder = kernel->currentThread; 00185 } 00186 00187 //---------------------------------------------------------------------- 00188 // Lock::Release 00189 // Atomically set lock to be free, waking up a thread waiting 00190 // for the lock, if any. 00191 // Equivalent to Semaphore::V(), with the semaphore value of 0 00192 // equal to busy, and semaphore value of 1 equal to free. 00193 // 00194 // By convention, only the thread that acquired the lock 00195 // may release it. 00196 //--------------------------------------------------------------------- 00197 00198 void Lock::Release() 00199 { 00200 ASSERT(IsHeldByCurrentThread()); 00201 lockHolder = NULL; 00202 semaphore->V(); 00203 } 00204 00205 //---------------------------------------------------------------------- 00206 // Condition::Condition 00207 // Initialize a condition variable, so that it can be 00208 // used for synchronization. Initially, no one is waiting 00209 // on the condition. 00210 // 00211 // "debugName" is an arbitrary name, useful for debugging. 00212 //---------------------------------------------------------------------- 00213 Condition::Condition(char* debugName, Lock * conditionLock) 00214 { 00215 name = debugName; 00216 condLock=conditionLock; 00217 waitQueue = new List<Semaphore *>; 00218 } 00219 00220 //---------------------------------------------------------------------- 00221 // Condition::Condition 00222 // Deallocate the data structures implementing a condition variable. 00223 //---------------------------------------------------------------------- 00224 00225 Condition::~Condition() 00226 { 00227 delete waitQueue; 00228 } 00229 00230 //---------------------------------------------------------------------- 00231 // Condition::Wait 00232 // Atomically release monitor lock and go to sleep. 00233 // Our implementation uses semaphores to implement this, by 00234 // allocating a semaphore for each waiting thread. The signaller 00235 // will V() this semaphore, so there is no chance the waiter 00236 // will miss the signal, even though the lock is released before 00237 // calling P(). 00238 // 00239 // Note: we assume Mesa-style semantics, which means that the 00240 // waiter must re-acquire the monitor lock when waking up. 00241 // 00242 // "conditionLock" -- lock protecting the use of this condition 00243 //---------------------------------------------------------------------- 00244 00245 void Condition::Wait() 00246 { 00247 Semaphore *waiter; 00248 00249 ASSERT(condLock->IsHeldByCurrentThread()); 00250 00251 waiter = new Semaphore("condition", 0); 00252 waitQueue->Append(waiter); 00253 condLock->Release(); 00254 waiter->P(); 00255 condLock->Acquire(); 00256 delete waiter; 00257 } 00258 00259 //---------------------------------------------------------------------- 00260 // Condition::Signal 00261 // Wake up a thread waiting on this condition, if any. 00262 // 00263 // Note: we assume Mesa-style semantics, which means that the 00264 // signaller doesn't give up control immediately to the thread 00265 // being woken up (unlike Hoare-style). 00266 // 00267 // Also note: we assume the caller holds the monitor lock 00268 // (unlike what is described in Birrell's paper). This allows 00269 // us to access waitQueue without disabling interrupts. 00270 // 00271 // "conditionLock" -- lock protecting the use of this condition 00272 //---------------------------------------------------------------------- 00273 00274 void Condition::Signal() 00275 { 00276 Semaphore *waiter; 00277 00278 ASSERT(condLock->IsHeldByCurrentThread()); 00279 00280 if (!waitQueue->IsEmpty()) { 00281 waiter = waitQueue->RemoveFront(); 00282 waiter->V(); 00283 } 00284 } 00285 00286 //---------------------------------------------------------------------- 00287 // Condition::Broadcast 00288 // Wake up all threads waiting on this condition, if any. 00289 // 00290 // "conditionLock" -- lock protecting the use of this condition 00291 //---------------------------------------------------------------------- 00292 00293 void Condition::Broadcast() 00294 { 00295 while (!waitQueue->IsEmpty()) { 00296 Signal(); 00297 } 00298 }