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);
166 sema_init (&lock->semaphore, 1, name);
169 /* Acquires LOCK, sleeping until it becomes available if
170 necessary. The lock must not already be held by the current
173 This function may sleep, so it must not be called within an
174 interrupt handler. This function may be called with
175 interrupts disabled, but interrupts will be turned back on if
178 lock_acquire (struct lock *lock)
180 enum intr_level old_level;
182 ASSERT (lock != NULL);
183 ASSERT (!intr_context ());
184 ASSERT (!lock_held_by_current_thread (lock));
186 old_level = intr_disable ();
187 sema_down (&lock->semaphore);
188 lock->holder = thread_current ();
189 intr_set_level (old_level);
192 /* Releases LOCK, which must be owned by the current thread.
194 An interrupt handler cannot acquire a lock, so it does not
195 make sense to try to signal a condition variable within an
196 interrupt handler. */
198 lock_release (struct lock *lock)
200 enum intr_level old_level;
202 ASSERT (lock != NULL);
203 ASSERT (lock_held_by_current_thread (lock));
205 old_level = intr_disable ();
207 sema_up (&lock->semaphore);
208 intr_set_level (old_level);
211 /* Returns true if the current thread holds LOCK, false
212 otherwise. (Note that testing whether some other thread holds
213 a lock would be racy.) */
215 lock_held_by_current_thread (const struct lock *lock)
217 ASSERT (lock != NULL);
219 return lock->holder == thread_current ();
222 /* Returns the name of LOCK (for debugging purposes). */
224 lock_name (const struct lock *lock)
226 ASSERT (lock != NULL);
228 return sema_name (&lock->semaphore);
231 /* One semaphore in a list. */
232 struct semaphore_elem
234 list_elem elem; /* List element. */
235 struct semaphore semaphore; /* This semaphore. */
238 /* Initializes condition variable COND and names it NAME. A
239 condition variable allows one piece of code to signal a
240 condition and cooperating code to receive the signal and act
243 cond_init (struct condition *cond, const char *name)
245 ASSERT (cond != NULL);
246 ASSERT (name != NULL);
248 strlcpy (cond->name, name, sizeof cond->name);
249 list_init (&cond->waiters);
252 /* Atomically releases LOCK and waits for COND to be signaled by
253 some other piece of code. After COND is signaled, LOCK is
254 reacquired before returning. LOCK must be held before calling
257 The monitor implemented by this function is "Mesa" style, not
258 "Hoare" style, that is, sending and receiving a signal are not
259 an atomic operation. Thus, typically the caller must recheck
260 the condition after the wait completes and, if necessary, wait
263 A given condition variable is associated with only a single
264 lock, but one lock may be associated with any number of
265 condition variables. That is, there is a one-to-many mapping
266 from locks to condition variables.
268 This function may sleep, so it must not be called within an
269 interrupt handler. This function may be called with
270 interrupts disabled, but interrupts will be turned back on if
273 cond_wait (struct condition *cond, struct lock *lock)
275 struct semaphore_elem waiter;
277 ASSERT (cond != NULL);
278 ASSERT (lock != NULL);
279 ASSERT (!intr_context ());
280 ASSERT (lock_held_by_current_thread (lock));
282 sema_init (&waiter.semaphore, 0, "condition");
283 list_push_back (&cond->waiters, &waiter.elem);
285 sema_down (&waiter.semaphore);
289 /* If any threads are waiting on COND (protected by LOCK), then
290 this function signals one of them to wake up from its wait.
291 LOCK must be held before calling this function.
293 An interrupt handler cannot acquire a lock, so it does not
294 make sense to try to signal a condition variable within an
295 interrupt handler. */
297 cond_signal (struct condition *cond, struct lock *lock)
299 ASSERT (cond != NULL);
300 ASSERT (lock != NULL);
301 ASSERT (!intr_context ());
302 ASSERT (lock_held_by_current_thread (lock));
304 if (!list_empty (&cond->waiters))
305 sema_up (&list_entry (list_pop_front (&cond->waiters),
306 struct semaphore_elem, elem)->semaphore);
309 /* Wakes up all threads, if any, waiting on COND (protected by
310 LOCK). LOCK must be held before calling this function.
312 An interrupt handler cannot acquire a lock, so it does not
313 make sense to try to signal a condition variable within an
314 interrupt handler. */
316 cond_broadcast (struct condition *cond, struct lock *lock)
318 ASSERT (cond != NULL);
319 ASSERT (lock != NULL);
321 while (!list_empty (&cond->waiters))
322 cond_signal (cond, lock);
325 /* Returns COND's name (for debugging purposes). */
327 cond_name (const struct condition *cond)
329 ASSERT (cond != NULL);