00001 /* This file is derived from source code for the Nachos 00002 //105631688674 00003 instructional operating system. The Nachos copyright notice 00004 is reproduced in full below. */ 00005 00006 /* Copyright (c) 1992-1996 The Regents of the University of California. 00007 All rights reserved. 00008 00009 Permission to use, copy, modify, and distribute this software 00010 and its documentation for any purpose, without fee, and 00011 without written agreement is hereby granted, provided that the 00012 above copyright notice and the following two paragraphs appear 00013 in all copies of this software. 00014 00015 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO 00016 ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR 00017 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE 00018 AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA 00019 HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00020 00021 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY 00022 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 00023 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 00024 PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" 00025 BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO 00026 PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR 00027 MODIFICATIONS. 00028 */ 00029 00030 #include "threads/synch.h" 00031 #include <stdio.h> 00032 #include <string.h> 00033 #include "threads/interrupt.h" 00034 #include "threads/thread.h" 00035 00036 /* Initializes semaphore SEMA to VALUE. A semaphore is a 00037 nonnegative integer along with two atomic operators for 00038 manipulating it: 00039 00040 - down or "P": wait for the value to become positive, then 00041 decrement it. 00042 00043 - up or "V": increment the value (and wake up one waiting 00044 thread, if any). */ 00045 void 00046 sema_init (struct semaphore *sema, unsigned value) 00047 { 00048 ASSERT (sema != NULL); 00049 00050 sema->value = value; 00051 list_init (&sema->waiters); 00052 } 00053 00054 /* Down or "P" operation on a semaphore. Waits for SEMA's value 00055 to become positive and then atomically decrements it. 00056 00057 This function may sleep, so it must not be called within an 00058 interrupt handler. This function may be called with 00059 interrupts disabled, but if it sleeps then the next scheduled 00060 thread will probably turn interrupts back on. */ 00061 void 00062 sema_down (struct semaphore *sema) 00063 { 00064 enum intr_level old_level; 00065 00066 ASSERT (sema != NULL); 00067 ASSERT (!intr_context ()); 00068 00069 old_level = intr_disable (); 00070 while (sema->value == 0) 00071 { 00072 list_push_back (&sema->waiters, &thread_current ()->elem); 00073 thread_block (); 00074 } 00075 sema->value--; 00076 intr_set_level (old_level); 00077 } 00078 00079 /* Down or "P" operation on a semaphore, but only if the 00080 semaphore is not already 0. Returns true if the semaphore is 00081 decremented, false otherwise. 00082 00083 This function may be called from an interrupt handler. */ 00084 bool 00085 sema_try_down (struct semaphore *sema) 00086 { 00087 enum intr_level old_level; 00088 bool success; 00089 00090 ASSERT (sema != NULL); 00091 00092 old_level = intr_disable (); 00093 if (sema->value > 0) 00094 { 00095 sema->value--; 00096 success = true; 00097 } 00098 else 00099 success = false; 00100 intr_set_level (old_level); 00101 00102 return success; 00103 } 00104 00105 /* Up or "V" operation on a semaphore. Increments SEMA's value 00106 and wakes up one thread of those waiting for SEMA, if any. 00107 00108 This function may be called from an interrupt handler. */ 00109 void 00110 sema_up (struct semaphore *sema) 00111 { 00112 enum intr_level old_level; 00113 00114 ASSERT (sema != NULL); 00115 00116 old_level = intr_disable (); 00117 if (!list_empty (&sema->waiters)) 00118 thread_unblock (list_entry (list_pop_front (&sema->waiters), 00119 struct thread, elem)); 00120 sema->value++; 00121 intr_set_level (old_level); 00122 } 00123 00124 static void sema_test_helper (void *sema_); 00125 00126 /* Self-test for semaphores that makes control "ping-pong" 00127 between a pair of threads. Insert calls to printf() to see 00128 what's going on. */ 00129 void 00130 sema_self_test (void) 00131 { 00132 struct semaphore sema[2]; 00133 int i; 00134 00135 printf ("Testing semaphores..."); 00136 sema_init (&sema[0], 0); 00137 sema_init (&sema[1], 0); 00138 thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema); 00139 for (i = 0; i < 10; i++) 00140 { 00141 sema_up (&sema[0]); 00142 sema_down (&sema[1]); 00143 } 00144 printf ("done.\n"); 00145 } 00146 00147 /* Thread function used by sema_self_test(). */ 00148 static void 00149 sema_test_helper (void *sema_) 00150 { 00151 struct semaphore *sema = sema_; 00152 int i; 00153 00154 for (i = 0; i < 10; i++) 00155 { 00156 sema_down (&sema[0]); 00157 sema_up (&sema[1]); 00158 } 00159 } 00160 00161 /* Initializes LOCK. A lock can be held by at most a single 00162 thread at any given time. Our locks are not "recursive", that 00163 is, it is an error for the thread currently holding a lock to 00164 try to acquire that lock. 00165 00166 A lock is a specialization of a semaphore with an initial 00167 value of 1. The difference between a lock and such a 00168 semaphore is twofold. First, a semaphore can have a value 00169 greater than 1, but a lock can only be owned by a single 00170 thread at a time. Second, a semaphore does not have an owner, 00171 meaning that one thread can "down" the semaphore and then 00172 another one "up" it, but with a lock the same thread must both 00173 acquire and release it. When these restrictions prove 00174 onerous, it's a good sign that a semaphore should be used, 00175 instead of a lock. */ 00176 void 00177 lock_init (struct lock *lock) 00178 { 00179 ASSERT (lock != NULL); 00180 00181 lock->holder = NULL; 00182 sema_init (&lock->semaphore, 1); 00183 } 00184 00185 /* Acquires LOCK, sleeping until it becomes available if 00186 necessary. The lock must not already be held by the current 00187 thread. 00188 00189 This function may sleep, so it must not be called within an 00190 interrupt handler. This function may be called with 00191 interrupts disabled, but interrupts will be turned back on if 00192 we need to sleep. */ 00193 void 00194 lock_acquire (struct lock *lock) 00195 { 00196 ASSERT (lock != NULL); 00197 ASSERT (!intr_context ()); 00198 ASSERT (!lock_held_by_current_thread (lock)); 00199 00200 sema_down (&lock->semaphore); 00201 lock->holder = thread_current (); 00202 } 00203 00204 /* Tries to acquires LOCK and returns true if successful or false 00205 on failure. The lock must not already be held by the current 00206 thread. 00207 00208 This function will not sleep, so it may be called within an 00209 interrupt handler. */ 00210 bool 00211 lock_try_acquire (struct lock *lock) 00212 { 00213 bool success; 00214 00215 ASSERT (lock != NULL); 00216 ASSERT (!lock_held_by_current_thread (lock)); 00217 00218 success = sema_try_down (&lock->semaphore); 00219 if (success) 00220 lock->holder = thread_current (); 00221 return success; 00222 } 00223 00224 /* Releases LOCK, which must be owned by the current thread. 00225 00226 An interrupt handler cannot acquire a lock, so it does not 00227 make sense to try to release a lock within an interrupt 00228 handler. */ 00229 void 00230 lock_release (struct lock *lock) 00231 { 00232 ASSERT (lock != NULL); 00233 ASSERT (lock_held_by_current_thread (lock)); 00234 00235 lock->holder = NULL; 00236 sema_up (&lock->semaphore); 00237 } 00238 00239 /* Returns true if the current thread holds LOCK, false 00240 otherwise. (Note that testing whether some other thread holds 00241 a lock would be racy.) */ 00242 bool 00243 lock_held_by_current_thread (const struct lock *lock) 00244 { 00245 ASSERT (lock != NULL); 00246 00247 return lock->holder == thread_current (); 00248 } 00249 00250 /* One semaphore in a list. */ 00251 struct semaphore_elem 00252 { 00253 struct list_elem elem; /* List element. */ 00254 struct semaphore semaphore; /* This semaphore. */ 00255 }; 00256 00257 /* Initializes condition variable COND. A condition variable 00258 allows one piece of code to signal a condition and cooperating 00259 code to receive the signal and act upon it. */ 00260 void 00261 cond_init (struct condition *cond) 00262 { 00263 ASSERT (cond != NULL); 00264 00265 list_init (&cond->waiters); 00266 } 00267 00268 /* Atomically releases LOCK and waits for COND to be signaled by 00269 some other piece of code. After COND is signaled, LOCK is 00270 reacquired before returning. LOCK must be held before calling 00271 this function. 00272 00273 The monitor implemented by this function is "Mesa" style, not 00274 "Hoare" style, that is, sending and receiving a signal are not 00275 an atomic operation. Thus, typically the caller must recheck 00276 the condition after the wait completes and, if necessary, wait 00277 again. 00278 00279 A given condition variable is associated with only a single 00280 lock, but one lock may be associated with any number of 00281 condition variables. That is, there is a one-to-many mapping 00282 from locks to condition variables. 00283 00284 This function may sleep, so it must not be called within an 00285 interrupt handler. This function may be called with 00286 interrupts disabled, but interrupts will be turned back on if 00287 we need to sleep. */ 00288 void 00289 cond_wait (struct condition *cond, struct lock *lock) 00290 { 00291 struct semaphore_elem waiter; 00292 00293 ASSERT (cond != NULL); 00294 ASSERT (lock != NULL); 00295 ASSERT (!intr_context ()); 00296 ASSERT (lock_held_by_current_thread (lock)); 00297 00298 sema_init (&waiter.semaphore, 0); 00299 list_push_back (&cond->waiters, &waiter.elem); 00300 lock_release (lock); 00301 sema_down (&waiter.semaphore); 00302 lock_acquire (lock); 00303 } 00304 00305 /* If any threads are waiting on COND (protected by LOCK), then 00306 this function signals one of them to wake up from its wait. 00307 LOCK must be held before calling this function. 00308 00309 An interrupt handler cannot acquire a lock, so it does not 00310 make sense to try to signal a condition variable within an 00311 interrupt handler. */ 00312 void 00313 cond_signal (struct condition *cond, struct lock *lock UNUSED) 00314 { 00315 ASSERT (cond != NULL); 00316 ASSERT (lock != NULL); 00317 ASSERT (!intr_context ()); 00318 ASSERT (lock_held_by_current_thread (lock)); 00319 00320 if (!list_empty (&cond->waiters)) 00321 sema_up (&list_entry (list_pop_front (&cond->waiters), 00322 struct semaphore_elem, elem)->semaphore); 00323 } 00324 00325 /* Wakes up all threads, if any, waiting on COND (protected by 00326 LOCK). LOCK must be held before calling this function. 00327 00328 An interrupt handler cannot acquire a lock, so it does not 00329 make sense to try to signal a condition variable within an 00330 interrupt handler. */ 00331 void 00332 cond_broadcast (struct condition *cond, struct lock *lock) 00333 { 00334 ASSERT (cond != NULL); 00335 ASSERT (lock != NULL); 00336 00337 while (!list_empty (&cond->waiters)) 00338 cond_signal (cond, lock); 00339 }
1.5.6