00001 // synch.h 00002 // Data structures for synchronizing threads. 00003 // 00004 // Three kinds of synchronization are defined here: semaphores, 00005 // locks, and condition variables. 00006 // 00007 // Note that all the synchronization objects take a "name" as 00008 // part of the initialization. This is solely for debugging purposes. 00009 // 00010 // Copyright (c) 1992-1996 The Regents of the University of California. 00011 // All rights reserved. See copyright.h for copyright notice and limitation 00012 // synch.h -- synchronization primitives. 00013 00014 #ifndef SYNCH_H 00015 #define SYNCH_H 00016 00017 #include "copyright.h" 00018 #include "thread.h" 00019 #include "list.h" 00020 #include "main.h" 00021 00022 // The following class defines a "semaphore" whose value is a non-negative 00023 // integer. The semaphore has only two operations P() and V(): 00024 // 00025 // P() -- waits until value > 0, then decrement 00026 // 00027 // V() -- increment, waking up a thread waiting in P() if necessary 00028 // 00029 // Note that the interface does *not* allow a thread to read the value of 00030 // the semaphore directly -- even if you did read the value, the 00031 // only thing you would know is what the value used to be. You don't 00032 // know what the value is now, because by the time you get the value 00033 // into a register, a context switch might have occurred, 00034 // and some other thread might have called P or V, so the true value might 00035 // now be different. 00036 00037 class Semaphore { 00038 public: 00039 Semaphore(char* debugName, int initialValue); // set initial value 00040 ~Semaphore(); // de-allocate semaphore 00041 char* getName() { return name;} // debugging assist 00042 00043 void P(); // these are the only operations on a semaphore 00044 void V(); // they are both *atomic* 00045 void SelfTest(); // test routine for semaphore implementation 00046 00047 private: 00048 char* name; // useful for debugging 00049 int value; // semaphore value, always >= 0 00050 List<Thread *> *queue; 00051 // threads waiting in P() for the value to be > 0 00052 }; 00053 00054 // The following class defines a "lock". A lock can be BUSY or FREE. 00055 // There are only two operations allowed on a lock: 00056 // 00057 // Acquire -- wait until the lock is FREE, then set it to BUSY 00058 // 00059 // Release -- set lock to be FREE, waking up a thread waiting 00060 // in Acquire if necessary 00061 // 00062 // In addition, by convention, only the thread that acquired the lock 00063 // may release it. As with semaphores, you can't read the lock value 00064 // (because the value might change immediately after you read it). 00065 00066 class Lock { 00067 public: 00068 Lock(char* debugName); // initialize lock to be FREE 00069 ~Lock(); // deallocate lock 00070 char* getName() { return name; } // debugging assist 00071 00072 void Acquire(); // these are the only operations on a lock 00073 void Release(); // they are both *atomic* 00074 00075 bool IsHeldByCurrentThread() { 00076 return lockHolder == kernel->currentThread; } 00077 // return true if the current thread 00078 // holds this lock. 00079 00080 // Note: SelfTest routine provided by SynchList 00081 00082 private: 00083 char *name; // debugging assist 00084 Thread *lockHolder; // thread currently holding lock 00085 Semaphore *semaphore; // we use a semaphore to implement lock 00086 }; 00087 00088 // The following class defines a "condition variable". A condition 00089 // variable does not have a value, but threads may be queued, waiting 00090 // on the variable. 00091 // 00092 // All operations on a condition variable must be made while 00093 // the current thread has acquired a lock. Indeed, all accesses 00094 // to a given condition variable must be protected by the same lock. 00095 // In other words, mutual exclusion must be enforced among threads calling 00096 // the condition variable operations. 00097 // 00098 // These are only operations on a condition variable: 00099 // 00100 // Wait() -- release the lock, relinquish the CPU until signaled, 00101 // then re-acquire the lock 00102 // 00103 // Signal() -- wake up a thread, if there are any waiting on 00104 // the condition 00105 // 00106 // Broadcast() -- wake up all threads waiting on the condition 00107 // 00108 // In Nachos, condition variables are assumed to obey *Mesa*-style 00109 // semantics. When a Signal or Broadcast wakes up another thread, 00110 // it simply puts the thread on the ready list, and it is the responsibility 00111 // of the woken thread to re-acquire the lock (this re-acquire is 00112 // taken care of within Wait()). By contrast, some define condition 00113 // variables according to *Hoare*-style semantics -- where the signalling 00114 // thread gives up control over the lock and the CPU to the woken thread, 00115 // which runs immediately and gives back control over the lock to the 00116 // signaller when the woken thread leaves the critical section. 00117 // 00118 // The consequence of using Mesa-style semantics is that some other thread 00119 // can acquire the lock, and change data structures, before the woken 00120 // thread gets a chance to run. The advantage to Mesa-style semantics 00121 // is that it is a lot easier to implement than Hoare-style. 00122 00123 class Condition { 00124 public: 00125 Condition(char* debugName, Lock * conditionLock); // initialize condition to 00126 // "no one waiting" 00127 ~Condition(); // deallocate the condition 00128 char* getName() { return (name); } 00129 00130 void Wait(); // these are the 3 operations on 00131 // condition variables; releasing the 00132 // lock and going to sleep are 00133 // *atomic* in Wait() 00134 void Signal(); // conditionLock must be held by 00135 void Broadcast();// the currentThread for all of 00136 // these operations 00137 // SelfTest routine provided by SyncLists 00138 00139 private: 00140 char* name; 00141 Lock * condLock; 00142 List<Semaphore *> *waitQueue; // list of waiting threads 00143 }; 00144 #endif // SYNCH_H