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 thread *thread;
115 struct semaphore sema[2];
118 printf ("Testing semaphores...");
119 sema_init (&sema[0], 0, "ping");
120 sema_init (&sema[1], 0, "pong");
121 thread = thread_create ("sema-test", sema_test_helper, &sema);
122 for (i = 0; i < 10; i++)
125 sema_down (&sema[1]);
130 /* Thread function used by sema_self_test(). */
132 sema_test_helper (void *sema_)
134 struct semaphore *sema = sema_;
137 for (i = 0; i < 10; i++)
139 sema_down (&sema[0]);
144 /* Initializes LOCK and names it NAME (for debugging purposes).
145 A lock can be held by at most a single thread at any given
146 time. Our locks are not "recursive", that is, it is an error
147 for the thread currently holding a lock to try to acquire that
150 A lock is a specialization of a semaphore with an initial
151 value of 1. The difference between a lock and such a
152 semaphore is twofold. First, a semaphore can have a value
153 greater than 1, but a lock can only be owned by a single
154 thread at a time. Second, a semaphore does not have an owner,
155 meaning that one thread can "down" the semaphore and then
156 another one "up" it, but with a lock the same thread must both
157 acquire and release it. When these restrictions prove
158 onerous, it's a good sign that a semaphore should be used,
159 instead of a lock. */
161 lock_init (struct lock *lock, const char *name)
163 ASSERT (lock != NULL);
164 ASSERT (name != NULL);
166 strlcpy (lock->name, name, sizeof lock->name);
168 sema_init (&lock->semaphore, 1, name);
171 /* Acquires LOCK, sleeping until it becomes available if
172 necessary. The lock must not already be held by the current
175 This function may sleep, so it must not be called within an
176 interrupt handler. This function may be called with
177 interrupts disabled, but interrupts will be turned back on if
180 lock_acquire (struct lock *lock)
182 enum intr_level old_level;
184 ASSERT (lock != NULL);
185 ASSERT (!intr_context ());
186 ASSERT (!lock_held_by_current_thread (lock));
188 old_level = intr_disable ();
189 sema_down (&lock->semaphore);
190 lock->holder = thread_current ();
191 intr_set_level (old_level);
194 /* Releases LOCK, which must be owned by the current thread.
196 An interrupt handler cannot acquire a lock, so it does not
197 make sense to try to signal a condition variable within an
198 interrupt handler. */
200 lock_release (struct lock *lock)
202 enum intr_level old_level;
204 ASSERT (lock != NULL);
205 ASSERT (lock_held_by_current_thread (lock));
207 old_level = intr_disable ();
209 sema_up (&lock->semaphore);
210 intr_set_level (old_level);
213 /* Returns true if the current thread holds LOCK, false
214 otherwise. (Note that testing whether some other thread holds
215 a lock would be racy.) */
217 lock_held_by_current_thread (const struct lock *lock)
219 ASSERT (lock != NULL);
221 return lock->holder == thread_current ();
224 /* Returns the name of LOCK (for debugging purposes). */
226 lock_name (const struct lock *lock)
228 ASSERT (lock != NULL);
233 /* One semaphore in a list. */
234 struct semaphore_elem
236 list_elem elem; /* List element. */
237 struct semaphore semaphore; /* This semaphore. */
240 /* Initializes condition variable COND and names it NAME. A
241 condition variable allows one piece of code to signal a
242 condition and cooperating code to receive the signal and act
245 cond_init (struct condition *cond, const char *name)
247 ASSERT (cond != NULL);
248 ASSERT (name != NULL);
250 strlcpy (cond->name, name, sizeof cond->name);
251 list_init (&cond->waiters);
254 /* Atomically releases LOCK and waits for COND to be signaled by
255 some other piece of code. After COND is signalled, LOCK is
256 reacquired before returning. LOCK must be held before calling
259 The monitor implemented by this function is "Mesa" style, not
260 "Hoare" style, that is, sending and receiving a signal are not
261 an atomic operation. Thus, typically the caller must recheck
262 the condition after the wait completes and, if necessary, wait
265 A given condition variable is associated with only a single
266 lock, but one lock may be be associated with any number of
267 condition variables. That is, there is a one-to-many mapping
268 from locks to condition variables.
270 This function may sleep, so it must not be called within an
271 interrupt handler. This function may be called with
272 interrupts disabled, but interrupts will be turned back on if
275 cond_wait (struct condition *cond, struct lock *lock)
277 struct semaphore_elem waiter;
279 ASSERT (cond != NULL);
280 ASSERT (lock != NULL);
281 ASSERT (!intr_context ());
282 ASSERT (lock_held_by_current_thread (lock));
284 sema_init (&waiter.semaphore, 0, "condition");
285 list_push_back (&cond->waiters, &waiter.elem);
287 sema_down (&waiter.semaphore);
291 /* If any threads are waiting on COND (protected by LOCK), then
292 this function signals one of them to wake up from its wait.
293 LOCK must be held before calling this function.
295 An interrupt handler cannot acquire a lock, so it does not
296 make sense to try to signal a condition variable within an
297 interrupt handler. */
299 cond_signal (struct condition *cond, struct lock *lock)
301 ASSERT (cond != NULL);
302 ASSERT (lock != NULL);
303 ASSERT (!intr_context ());
304 ASSERT (lock_held_by_current_thread (lock));
306 if (!list_empty (&cond->waiters))
307 sema_up (&list_entry (list_pop_front (&cond->waiters),
308 struct semaphore_elem, elem)->semaphore);
311 /* Wakes up all threads, if any, waiting on COND (protected by
312 LOCK). LOCK must be held before calling this function.
314 An interrupt handler cannot acquire a lock, so it does not
315 make sense to try to signal a condition variable within an
316 interrupt handler. */
318 cond_broadcast (struct condition *cond, struct lock *lock)
320 ASSERT (cond != NULL);
321 ASSERT (lock != NULL);
323 while (!list_empty (&cond->waiters))
324 cond_signal (cond, lock);
327 /* Returns COND's name (for debugging purposes). */
329 cond_name (const struct condition *cond)
331 ASSERT (cond != NULL);