Page principale | Liste des namespaces | Hiérarchie des classes | Liste des classes | Répertoires | Liste des fichiers | Membres de namespace | Membres de classe | Membres de fichier

synch.cc

Aller à la documentation de ce fichier.
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 }

Généré le Sun Jan 15 00:45:45 2006 pour Système NachOS : par  doxygen 1.4.4