7 /* One thread in a list. */
11 struct thread *thread;
14 /* Initializes semaphore SEMA to VALUE and names it NAME (for
15 debugging purposes only). A semaphore is a nonnegative
16 integer along with two atomic operators for manipulating it:
18 - down or "P": wait for the value to become positive, then
21 - up or "V": increment the value (and wake up one waiting
24 sema_init (struct semaphore *sema, unsigned value, const char *name)
26 ASSERT (sema != NULL);
27 ASSERT (name != NULL);
29 strlcpy (sema->name, name, sizeof sema->name);
31 list_init (&sema->waiters);
34 /* Waits for SEMA's value to become positive and then
35 atomically decrements it.
37 This function may sleep, so it must not be called within an
38 interrupt handler. This function may be called with
39 interrupts disabled, but interrupts will be turned back on if
42 sema_down (struct semaphore *sema)
44 enum if_level old_level;
46 ASSERT (sema != NULL);
47 ASSERT (!intr_context ());
49 old_level = intr_disable ();
50 while (sema->value == 0)
52 struct thread_elem te;
53 te.thread = thread_current ();
54 list_push_back (&sema->waiters, &te.elem);
58 intr_set_level (old_level);
61 /* Increments SEMA's value. Wakes up one thread of those waiting
64 This function may be called from an interrupt handler. */
66 sema_up (struct semaphore *sema)
68 enum if_level old_level;
70 ASSERT (sema != NULL);
72 old_level = intr_disable ();
73 if (!list_empty (&sema->waiters))
74 thread_ready (list_entry (list_pop_front (&sema->waiters),
75 struct thread_elem, elem)->thread);
77 intr_set_level (old_level);
80 /* Return SEMA's name (for debugging purposes). */
82 sema_name (const struct semaphore *sema)
88 sema_test_helper (void *sema_)
90 struct semaphore *sema = sema_;
93 for (i = 0; i < 10; i++)
100 /* Self-test for semaphores that makes control "ping-pong"
101 between a pair of threads. Insert calls to printk() to see
104 sema_self_test (void)
106 struct thread *thread;
107 struct semaphore sema[2];
110 sema_init (&sema[0], 0, "ping");
111 sema_init (&sema[1], 0, "pong");
112 thread = thread_create ("sema-test", sema_test_helper, &sema);
113 for (i = 0; i < 10; i++)
116 sema_down (&sema[1]);
120 /* Initializes LOCK and names it NAME (for debugging purposes).
121 A lock can be held by at most a single thread at any given
122 time. Our locks are not "recursive", that is, it is an error
123 for the thread currently holding a lock to try to acquire that
126 A lock is a specialization of a semaphore with an initial
127 value of 1. The difference between a lock and such a
128 semaphore is twofold. First, a semaphore can have a value
129 greater than 1, but a lock can only be owned by a single
130 thread at a time. Second, a semaphore does not have an owner,
131 meaning that one thread can "down" the semaphore and then
132 another one "up" it, but with a lock the same thread must both
133 acquire and release it. When these restrictions prove
134 onerous, it's a good sign that a semaphore should be used,
135 instead of a lock. */
137 lock_init (struct lock *lock, const char *name)
139 ASSERT (lock != NULL);
140 ASSERT (name != NULL);
142 strlcpy (lock->name, name, sizeof lock->name);
144 sema_init (&lock->semaphore, 1, name);
147 /* Acquires LOCK, sleeping until it becomes available if
148 necessary. The lock must not already be held by the current
151 This function may sleep, so it must not be called within an
152 interrupt handler. This function may be called with
153 interrupts disabled, but interrupts will be turned back on if
156 lock_acquire (struct lock *lock)
158 enum if_level old_level;
160 ASSERT (lock != NULL);
161 ASSERT (!intr_context ());
162 ASSERT (!lock_held_by_current_thread (lock));
164 old_level = intr_disable ();
165 sema_down (&lock->semaphore);
166 lock->holder = thread_current ();
167 intr_set_level (old_level);
170 /* Releases LOCK, which must be owned by the current thread.
172 An interrupt handler cannot acquire a lock, so it does not
173 make sense to try to signal a condition variable within an
174 interrupt handler. */
176 lock_release (struct lock *lock)
178 enum if_level old_level;
180 ASSERT (lock != NULL);
181 ASSERT (lock_held_by_current_thread (lock));
183 old_level = intr_disable ();
185 sema_up (&lock->semaphore);
186 intr_set_level (old_level);
189 /* Returns true if the current thread holds LOCK, false
190 otherwise. (Note that testing whether some other thread holds
191 a lock would be racy.) */
193 lock_held_by_current_thread (const struct lock *lock)
195 ASSERT (lock != NULL);
197 return lock->holder == thread_current ();
200 /* Returns the name of LOCK (for debugging purposes). */
202 lock_name (const struct lock *lock)
204 ASSERT (lock != NULL);
209 /* One semaphore in a list. */
210 struct semaphore_elem
213 struct semaphore semaphore;
216 /* Initializes condition variable COND and names it NAME. A
217 condition variable allows one piece of code to signal a
218 condition and cooperating code to receive the signal and act
221 cond_init (struct condition *cond, const char *name)
223 ASSERT (cond != NULL);
224 ASSERT (name != NULL);
226 strlcpy (cond->name, name, sizeof cond->name);
227 list_init (&cond->waiters);
230 /* Atomically releases LOCK and waits for COND to be signaled by
231 some other piece of code. After COND is signalled, LOCK is
232 reacquired before returning. LOCK must be held before calling
235 The monitor implemented by this function is "Mesa" style, not
236 "Hoare" style. That is, sending a signal is not atomic with
237 delivering it. Thus, typically the caller must recheck the
238 condition after the wait completes and, if necessary, wait
241 A given condition variable is associated with only a single
242 lock, but one lock may be be associated with any number of
243 condition variables. That is, there is a one-to-many mapping
244 from locks to condition variables.
246 This function may sleep, so it must not be called within an
247 interrupt handler. This function may be called with
248 interrupts disabled, but interrupts will be turned back on if
251 cond_wait (struct condition *cond, struct lock *lock)
253 struct semaphore_elem waiter;
255 ASSERT (cond != NULL);
256 ASSERT (lock != NULL);
257 ASSERT (!intr_context ());
258 ASSERT (lock_held_by_current_thread (lock));
260 sema_init (&waiter.semaphore, 0, "condition");
261 list_push_back (&cond->waiters, &waiter.elem);
263 sema_down (&waiter.semaphore);
267 /* If any threads are waiting on COND (protected by LOCK), then
268 this function signals one of them to wake up from its wait.
269 LOCK must be held before calling this function.
271 An interrupt handler cannot acquire a lock, so it does not
272 make sense to try to signal a condition variable within an
273 interrupt handler. */
275 cond_signal (struct condition *cond, struct lock *lock)
277 ASSERT (cond != NULL);
278 ASSERT (lock != NULL);
279 ASSERT (!intr_context ());
280 ASSERT (lock_held_by_current_thread (lock));
282 if (!list_empty (&cond->waiters))
283 sema_up (&list_entry (list_pop_front (&cond->waiters),
284 struct semaphore_elem, elem)->semaphore);
287 /* Wakes up all threads, if any, waiting on COND (protected by
288 LOCK). LOCK must be held before calling this function.
290 An interrupt handler cannot acquire a lock, so it does not
291 make sense to try to signal a condition variable within an
292 interrupt handler. */
294 cond_broadcast (struct condition *cond, struct lock *lock)
296 ASSERT (cond != NULL);
297 ASSERT (lock != NULL);
299 while (!list_empty (&cond->waiters))
300 cond_signal (cond, lock);
303 /* Returns COND's name (for debugging purposes). */
305 cond_name (const struct condition *cond)
307 ASSERT (cond != NULL);