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 and names it NAME (for
36 debugging purposes only). A semaphore is a nonnegative
37 integer along with two atomic operators for manipulating it:
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, const char *name)
47 ASSERT (sema != NULL);
48 ASSERT (name != NULL);
50 strlcpy (sema->name, name, sizeof sema->name);
52 list_init (&sema->waiters);
55 /* Down or "P" operation on a semaphore. Waits for SEMA's value
56 to become positive and then atomically decrements it.
58 This function may sleep, so it must not be called within an
59 interrupt handler. This function may be called with
60 interrupts disabled, but interrupts will be turned back on if
63 sema_down (struct semaphore *sema)
65 enum intr_level old_level;
67 ASSERT (sema != NULL);
68 ASSERT (!intr_context ());
70 old_level = intr_disable ();
71 while (sema->value == 0)
73 list_push_back (&sema->waiters, &thread_current ()->elem);
77 intr_set_level (old_level);
80 /* Up or "V" operation on a semaphore. Increments SEMA's value
81 and wakes up one thread of those waiting for SEMA, if any.
83 This function may be called from an interrupt handler. */
85 sema_up (struct semaphore *sema)
87 enum intr_level old_level;
89 ASSERT (sema != NULL);
91 old_level = intr_disable ();
92 if (!list_empty (&sema->waiters))
93 thread_unblock (list_entry (list_pop_front (&sema->waiters),
94 struct thread, elem));
96 intr_set_level (old_level);
99 /* Return SEMA's name (for debugging purposes). */
101 sema_name (const struct semaphore *sema)
106 static void sema_test_helper (void *sema_);
108 /* Self-test for semaphores that makes control "ping-pong"
109 between a pair of threads. Insert calls to printf() to see
112 sema_self_test (void)
114 struct semaphore sema[2];
117 printf ("Testing semaphores...");
118 sema_init (&sema[0], 0, "ping");
119 sema_init (&sema[1], 0, "pong");
120 thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
121 for (i = 0; i < 10; i++)
124 sema_down (&sema[1]);
129 /* Thread function used by sema_self_test(). */
131 sema_test_helper (void *sema_)
133 struct semaphore *sema = sema_;
136 for (i = 0; i < 10; i++)
138 sema_down (&sema[0]);
143 /* Initializes LOCK and names it NAME (for debugging purposes).
144 A lock can be held by at most a single thread at any given
145 time. Our locks are not "recursive", that is, it is an error
146 for the thread currently holding a lock to try to acquire that
149 A lock is a specialization of a semaphore with an initial
150 value of 1. The difference between a lock and such a
151 semaphore is twofold. First, a semaphore can have a value
152 greater than 1, but a lock can only be owned by a single
153 thread at a time. Second, a semaphore does not have an owner,
154 meaning that one thread can "down" the semaphore and then
155 another one "up" it, but with a lock the same thread must both
156 acquire and release it. When these restrictions prove
157 onerous, it's a good sign that a semaphore should be used,
158 instead of a lock. */
160 lock_init (struct lock *lock, const char *name)
162 ASSERT (lock != NULL);
163 ASSERT (name != NULL);
165 strlcpy (lock->name, name, sizeof lock->name);
167 sema_init (&lock->semaphore, 1, name);
170 /* Acquires LOCK, sleeping until it becomes available if
171 necessary. The lock must not already be held by the current
174 This function may sleep, so it must not be called within an
175 interrupt handler. This function may be called with
176 interrupts disabled, but interrupts will be turned back on if
179 lock_acquire (struct lock *lock)
181 enum intr_level old_level;
183 ASSERT (lock != NULL);
184 ASSERT (!intr_context ());
185 ASSERT (!lock_held_by_current_thread (lock));
187 old_level = intr_disable ();
188 sema_down (&lock->semaphore);
189 lock->holder = thread_current ();
190 intr_set_level (old_level);
193 /* Releases LOCK, which must be owned by the current thread.
195 An interrupt handler cannot acquire a lock, so it does not
196 make sense to try to signal a condition variable within an
197 interrupt handler. */
199 lock_release (struct lock *lock)
201 enum intr_level old_level;
203 ASSERT (lock != NULL);
204 ASSERT (lock_held_by_current_thread (lock));
206 old_level = intr_disable ();
208 sema_up (&lock->semaphore);
209 intr_set_level (old_level);
212 /* Returns true if the current thread holds LOCK, false
213 otherwise. (Note that testing whether some other thread holds
214 a lock would be racy.) */
216 lock_held_by_current_thread (const struct lock *lock)
218 ASSERT (lock != NULL);
220 return lock->holder == thread_current ();
223 /* Returns the name of LOCK (for debugging purposes). */
225 lock_name (const struct lock *lock)
227 ASSERT (lock != NULL);
232 /* One semaphore in a list. */
233 struct semaphore_elem
235 list_elem elem; /* List element. */
236 struct semaphore semaphore; /* This semaphore. */
239 /* Initializes condition variable COND and names it NAME. A
240 condition variable allows one piece of code to signal a
241 condition and cooperating code to receive the signal and act
244 cond_init (struct condition *cond, const char *name)
246 ASSERT (cond != NULL);
247 ASSERT (name != NULL);
249 strlcpy (cond->name, name, sizeof cond->name);
250 list_init (&cond->waiters);
253 /* Atomically releases LOCK and waits for COND to be signaled by
254 some other piece of code. After COND is signalled, LOCK is
255 reacquired before returning. LOCK must be held before calling
258 The monitor implemented by this function is "Mesa" style, not
259 "Hoare" style, that is, sending and receiving a signal are not
260 an atomic operation. Thus, typically the caller must recheck
261 the condition after the wait completes and, if necessary, wait
264 A given condition variable is associated with only a single
265 lock, but one lock may be be associated with any number of
266 condition variables. That is, there is a one-to-many mapping
267 from locks to condition variables.
269 This function may sleep, so it must not be called within an
270 interrupt handler. This function may be called with
271 interrupts disabled, but interrupts will be turned back on if
274 cond_wait (struct condition *cond, struct lock *lock)
276 struct semaphore_elem waiter;
278 ASSERT (cond != NULL);
279 ASSERT (lock != NULL);
280 ASSERT (!intr_context ());
281 ASSERT (lock_held_by_current_thread (lock));
283 sema_init (&waiter.semaphore, 0, "condition");
284 list_push_back (&cond->waiters, &waiter.elem);
286 sema_down (&waiter.semaphore);
290 /* If any threads are waiting on COND (protected by LOCK), then
291 this function signals one of them to wake up from its wait.
292 LOCK must be held before calling this function.
294 An interrupt handler cannot acquire a lock, so it does not
295 make sense to try to signal a condition variable within an
296 interrupt handler. */
298 cond_signal (struct condition *cond, struct lock *lock)
300 ASSERT (cond != NULL);
301 ASSERT (lock != NULL);
302 ASSERT (!intr_context ());
303 ASSERT (lock_held_by_current_thread (lock));
305 if (!list_empty (&cond->waiters))
306 sema_up (&list_entry (list_pop_front (&cond->waiters),
307 struct semaphore_elem, elem)->semaphore);
310 /* Wakes up all threads, if any, waiting on COND (protected by
311 LOCK). LOCK must be held before calling this function.
313 An interrupt handler cannot acquire a lock, so it does not
314 make sense to try to signal a condition variable within an
315 interrupt handler. */
317 cond_broadcast (struct condition *cond, struct lock *lock)
319 ASSERT (cond != NULL);
320 ASSERT (lock != NULL);
322 while (!list_empty (&cond->waiters))
323 cond_signal (cond, lock);
326 /* Returns COND's name (for debugging purposes). */
328 cond_name (const struct condition *cond)
330 ASSERT (cond != NULL);