1 /* This file is derived from source code for the Nachos
2 instructional operating system. The Nachos copyright notice
3 is reproduced in full below. */
5 /* Copyright (c) 1992-1996 The Regents of the University of California.
8 Permission to use, copy, modify, and distribute this software
9 and its documentation for any purpose, without fee, and
10 without written agreement is hereby granted, provided that the
11 above copyright notice and the following two paragraphs appear
12 in all copies of this software.
14 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
15 ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
16 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
17 AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
18 HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
20 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
21 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
24 BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
25 PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
29 #include "threads/synch.h"
32 #include "threads/interrupt.h"
33 #include "threads/thread.h"
35 /* Initializes semaphore SEMA to VALUE. A semaphore is a
36 nonnegative integer along with two atomic operators for
39 - down or "P": wait for the value to become positive, then
42 - up or "V": increment the value (and wake up one waiting
45 sema_init (struct semaphore *sema, unsigned value)
47 ASSERT (sema != NULL);
50 list_init (&sema->waiters);
53 /* Down or "P" operation on a semaphore. Waits for SEMA's value
54 to become positive and then atomically decrements it.
56 This function may sleep, so it must not be called within an
57 interrupt handler. This function may be called with
58 interrupts disabled, but interrupts will be turned back on if
61 sema_down (struct semaphore *sema)
63 enum intr_level old_level;
65 ASSERT (sema != NULL);
66 ASSERT (!intr_context ());
68 old_level = intr_disable ();
69 while (sema->value == 0)
71 list_push_back (&sema->waiters, &thread_current ()->elem);
75 intr_set_level (old_level);
78 /* Down or "P" operation on a semaphore, but only if the
79 semaphore is not already 0. Returns true if the semaphore is
80 decremented, false otherwise.
82 This function may be called from an interrupt handler. */
84 sema_try_down (struct semaphore *sema)
86 enum intr_level old_level;
89 ASSERT (sema != NULL);
91 old_level = intr_disable ();
99 intr_set_level (old_level);
104 /* Up or "V" operation on a semaphore. Increments SEMA's value
105 and wakes up one thread of those waiting for SEMA, if any.
107 This function may be called from an interrupt handler. */
109 sema_up (struct semaphore *sema)
111 enum intr_level old_level;
113 ASSERT (sema != NULL);
115 old_level = intr_disable ();
116 if (!list_empty (&sema->waiters))
117 thread_unblock (list_entry (list_pop_front (&sema->waiters),
118 struct thread, elem));
120 intr_set_level (old_level);
123 static void sema_test_helper (void *sema_);
125 /* Self-test for semaphores that makes control "ping-pong"
126 between a pair of threads. Insert calls to printf() to see
129 sema_self_test (void)
131 struct semaphore sema[2];
134 printf ("Testing semaphores...");
135 sema_init (&sema[0], 0);
136 sema_init (&sema[1], 0);
137 thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
138 for (i = 0; i < 10; i++)
141 sema_down (&sema[1]);
146 /* Thread function used by sema_self_test(). */
148 sema_test_helper (void *sema_)
150 struct semaphore *sema = sema_;
153 for (i = 0; i < 10; i++)
155 sema_down (&sema[0]);
160 /* Initializes LOCK. A lock can be held by at most a single
161 thread at any given time. Our locks are not "recursive", that
162 is, it is an error for the thread currently holding a lock to
163 try to acquire that lock.
165 A lock is a specialization of a semaphore with an initial
166 value of 1. The difference between a lock and such a
167 semaphore is twofold. First, a semaphore can have a value
168 greater than 1, but a lock can only be owned by a single
169 thread at a time. Second, a semaphore does not have an owner,
170 meaning that one thread can "down" the semaphore and then
171 another one "up" it, but with a lock the same thread must both
172 acquire and release it. When these restrictions prove
173 onerous, it's a good sign that a semaphore should be used,
174 instead of a lock. */
176 lock_init (struct lock *lock)
178 ASSERT (lock != NULL);
181 sema_init (&lock->semaphore, 1);
184 /* Acquires LOCK, sleeping until it becomes available if
185 necessary. The lock must not already be held by the current
188 This function may sleep, so it must not be called within an
189 interrupt handler. This function may be called with
190 interrupts disabled, but interrupts will be turned back on if
193 lock_acquire (struct lock *lock)
195 enum intr_level old_level;
197 ASSERT (lock != NULL);
198 ASSERT (!intr_context ());
199 ASSERT (!lock_held_by_current_thread (lock));
201 old_level = intr_disable ();
202 sema_down (&lock->semaphore);
203 lock->holder = thread_current ();
204 intr_set_level (old_level);
207 /* Tries to acquires LOCK and returns true if successful or false
208 on failure. The lock must not already be held by the current
211 This function will not sleep, so it may be called within an
214 lock_try_acquire (struct lock *lock)
216 enum intr_level old_level;
219 ASSERT (lock != NULL);
220 ASSERT (!lock_held_by_current_thread (lock));
222 old_level = intr_disable ();
223 success = sema_try_down (&lock->semaphore);
225 lock->holder = thread_current ();
226 intr_set_level (old_level);
231 /* Releases LOCK, which must be owned by the current thread.
233 An interrupt handler cannot acquire a lock, so it does not
234 make sense to try to release a lock within an interrupt
237 lock_release (struct lock *lock)
239 enum intr_level old_level;
241 ASSERT (lock != NULL);
242 ASSERT (lock_held_by_current_thread (lock));
244 old_level = intr_disable ();
246 sema_up (&lock->semaphore);
247 intr_set_level (old_level);
250 /* Returns true if the current thread holds LOCK, false
251 otherwise. (Note that testing whether some other thread holds
252 a lock would be racy.) */
254 lock_held_by_current_thread (const struct lock *lock)
256 ASSERT (lock != NULL);
258 return lock->holder == thread_current ();
261 /* One semaphore in a list. */
262 struct semaphore_elem
264 struct list_elem elem; /* List element. */
265 struct semaphore semaphore; /* This semaphore. */
268 /* Initializes condition variable COND. A condition variable
269 allows one piece of code to signal a condition and cooperating
270 code to receive the signal and act upon it. */
272 cond_init (struct condition *cond)
274 ASSERT (cond != NULL);
276 list_init (&cond->waiters);
279 /* Atomically releases LOCK and waits for COND to be signaled by
280 some other piece of code. After COND is signaled, LOCK is
281 reacquired before returning. LOCK must be held before calling
284 The monitor implemented by this function is "Mesa" style, not
285 "Hoare" style, that is, sending and receiving a signal are not
286 an atomic operation. Thus, typically the caller must recheck
287 the condition after the wait completes and, if necessary, wait
290 A given condition variable is associated with only a single
291 lock, but one lock may be associated with any number of
292 condition variables. That is, there is a one-to-many mapping
293 from locks to condition variables.
295 This function may sleep, so it must not be called within an
296 interrupt handler. This function may be called with
297 interrupts disabled, but interrupts will be turned back on if
300 cond_wait (struct condition *cond, struct lock *lock)
302 struct semaphore_elem waiter;
304 ASSERT (cond != NULL);
305 ASSERT (lock != NULL);
306 ASSERT (!intr_context ());
307 ASSERT (lock_held_by_current_thread (lock));
309 sema_init (&waiter.semaphore, 0);
310 list_push_back (&cond->waiters, &waiter.elem);
312 sema_down (&waiter.semaphore);
316 /* If any threads are waiting on COND (protected by LOCK), then
317 this function signals one of them to wake up from its wait.
318 LOCK must be held before calling this function.
320 An interrupt handler cannot acquire a lock, so it does not
321 make sense to try to signal a condition variable within an
322 interrupt handler. */
324 cond_signal (struct condition *cond, struct lock *lock UNUSED)
326 ASSERT (cond != NULL);
327 ASSERT (lock != NULL);
328 ASSERT (!intr_context ());
329 ASSERT (lock_held_by_current_thread (lock));
331 if (!list_empty (&cond->waiters))
332 sema_up (&list_entry (list_pop_front (&cond->waiters),
333 struct semaphore_elem, elem)->semaphore);
336 /* Wakes up all threads, if any, waiting on COND (protected by
337 LOCK). LOCK must be held before calling this function.
339 An interrupt handler cannot acquire a lock, so it does not
340 make sense to try to signal a condition variable within an
341 interrupt handler. */
343 cond_broadcast (struct condition *cond, struct lock *lock)
345 ASSERT (cond != NULL);
346 ASSERT (lock != NULL);
348 while (!list_empty (&cond->waiters))
349 cond_signal (cond, lock);