6 /* One thread in a list. */
10 struct thread *thread;
13 /* Initializes semaphore SEMA to VALUE and names it NAME (for
14 debugging purposes only). A semaphore is a nonnegative
15 integer along with two atomic operators for manipulating it:
17 - down or "P": wait for the value to become positive, then
20 - up or "V": increment the value (and wake up one waiting
23 sema_init (struct semaphore *sema, unsigned value, const char *name)
25 ASSERT (sema != NULL);
26 ASSERT (name != NULL);
28 strlcpy (sema->name, name, sizeof sema->name);
30 list_init (&sema->waiters);
33 /* Waits for SEMA's value to become positive and then
34 atomically decrements it.
36 This function may sleep, so it must not be called within an
37 interrupt handler. This function may be called with
38 interrupts disabled, but interrupts will be turned back on if
41 sema_down (struct semaphore *sema)
43 enum if_level old_level;
45 ASSERT (sema != NULL);
46 ASSERT (!intr_context ());
48 old_level = intr_disable ();
49 while (sema->value == 0)
51 struct thread_elem te;
52 te.thread = thread_current ();
53 list_push_back (&sema->waiters, &te.elem);
57 intr_set_level (old_level);
60 /* Increments SEMA's value. Wakes up one thread of those waiting
63 This function may be called from an interrupt handler. */
65 sema_up (struct semaphore *sema)
67 enum if_level old_level;
69 ASSERT (sema != NULL);
71 old_level = intr_disable ();
72 if (!list_empty (&sema->waiters))
73 thread_ready (list_entry (list_pop_front (&sema->waiters),
74 struct thread_elem, elem)->thread);
76 intr_set_level (old_level);
79 /* Return SEMA's name (for debugging purposes). */
81 sema_name (const struct semaphore *sema)
87 sema_test_helper (void *sema_)
89 struct semaphore *sema = sema_;
92 for (i = 0; i < 10; i++)
99 /* Self-test for semaphores that makes control "ping-pong"
100 between a pair of threads. Insert calls to printk() to see
103 sema_self_test (void)
105 struct thread *thread;
106 struct semaphore sema[2];
109 sema_init (&sema[0], 0, "ping");
110 sema_init (&sema[1], 0, "pong");
111 thread = thread_create ("sema-test", sema_test_helper, &sema);
112 for (i = 0; i < 10; i++)
115 sema_down (&sema[1]);
119 /* Initializes LOCK and names it NAME (for debugging purposes).
120 A lock can be held by at most a single thread at any given
121 time. Our locks are not "recursive", that is, it is an error
122 for the thread currently holding a lock to try to acquire that
125 A lock is a specialization of a semaphore with an initial
126 value of 1. The difference between a lock and such a
127 semaphore is twofold. First, a semaphore can have a value
128 greater than 1, but a lock can only be owned by a single
129 thread at a time. Second, a semaphore does not have an owner,
130 meaning that one thread can "down" the semaphore and then
131 another one "up" it, but with a lock the same thread must both
132 acquire and release it. When these restrictions prove
133 onerous, it's a good sign that a semaphore should be used,
134 instead of a lock. */
136 lock_init (struct lock *lock, const char *name)
138 ASSERT (lock != NULL);
139 ASSERT (name != NULL);
141 strlcpy (lock->name, name, sizeof lock->name);
143 sema_init (&lock->semaphore, 1, name);
146 /* Acquires LOCK, sleeping until it becomes available if
147 necessary. The lock must not already be held by the current
150 This function may sleep, so it must not be called within an
151 interrupt handler. This function may be called with
152 interrupts disabled, but interrupts will be turned back on if
155 lock_acquire (struct lock *lock)
157 enum if_level old_level;
159 ASSERT (lock != NULL);
160 ASSERT (!intr_context ());
161 ASSERT (!lock_held_by_current_thread (lock));
163 old_level = intr_disable ();
164 sema_down (&lock->semaphore);
165 lock->holder = thread_current ();
166 intr_set_level (old_level);
169 /* Releases LOCK, which must be owned by the current thread.
171 An interrupt handler cannot acquire a lock, so it does not
172 make sense to try to signal a condition variable within an
173 interrupt handler. */
175 lock_release (struct lock *lock)
177 enum if_level old_level;
179 ASSERT (lock != NULL);
180 ASSERT (lock_held_by_current_thread (lock));
182 old_level = intr_disable ();
184 sema_up (&lock->semaphore);
185 intr_set_level (old_level);
188 /* Returns true if the current thread holds LOCK, false
189 otherwise. (Note that testing whether some other thread holds
190 a lock would be racy.) */
192 lock_held_by_current_thread (const struct lock *lock)
194 ASSERT (lock != NULL);
196 return lock->holder == thread_current ();
199 /* Returns the name of LOCK (for debugging purposes). */
201 lock_name (const struct lock *lock)
203 ASSERT (lock != NULL);
208 /* One semaphore in a list. */
209 struct semaphore_elem
212 struct semaphore semaphore;
215 /* Initializes condition variable COND and names it NAME. A
216 condition variable allows one piece of code to signal a
217 condition and cooperating code to receive the signal and act
220 cond_init (struct condition *cond, const char *name)
222 ASSERT (cond != NULL);
223 ASSERT (name != NULL);
225 strlcpy (cond->name, name, sizeof cond->name);
226 list_init (&cond->waiters);
229 /* Atomically releases LOCK and waits for COND to be signaled by
230 some other piece of code. After COND is signalled, LOCK is
231 reacquired before returning. LOCK must be held before calling
234 The monitor implemented by this function is "Mesa" style, not
235 "Hoare" style. That is, sending a signal is not atomic with
236 delivering it. Thus, typically the caller must recheck the
237 condition after the wait completes and, if necessary, wait
240 A given condition variable is associated with only a single
241 lock, but one lock may be be associated with any number of
242 condition variables. That is, there is a one-to-many mapping
243 from locks to condition variables.
245 This function may sleep, so it must not be called within an
246 interrupt handler. This function may be called with
247 interrupts disabled, but interrupts will be turned back on if
250 cond_wait (struct condition *cond, struct lock *lock)
252 struct semaphore_elem waiter;
254 ASSERT (cond != NULL);
255 ASSERT (lock != NULL);
256 ASSERT (!intr_context ());
257 ASSERT (lock_held_by_current_thread (lock));
259 sema_init (&waiter.semaphore, 0, "condition");
260 list_push_back (&cond->waiters, &waiter.elem);
262 sema_down (&waiter.semaphore);
266 /* If any threads are waiting on COND (protected by LOCK), then
267 this function signals one of them to wake up from its wait.
268 LOCK must be held before calling this function.
270 An interrupt handler cannot acquire a lock, so it does not
271 make sense to try to signal a condition variable within an
272 interrupt handler. */
274 cond_signal (struct condition *cond, struct lock *lock)
276 ASSERT (cond != NULL);
277 ASSERT (lock != NULL);
278 ASSERT (!intr_context ());
279 ASSERT (lock_held_by_current_thread (lock));
281 if (!list_empty (&cond->waiters))
282 sema_up (&list_entry (list_pop_front (&cond->waiters),
283 struct semaphore_elem, elem)->semaphore);
286 /* Wakes up all threads, if any, waiting on COND (protected by
287 LOCK). LOCK must be held before calling this function.
289 An interrupt handler cannot acquire a lock, so it does not
290 make sense to try to signal a condition variable within an
291 interrupt handler. */
293 cond_broadcast (struct condition *cond, struct lock *lock)
295 ASSERT (cond != NULL);
296 ASSERT (lock != NULL);
298 while (!list_empty (&cond->waiters))
299 cond_signal (cond, lock);
302 /* Returns COND's name (for debugging purposes). */
304 cond_name (const struct condition *cond)
306 ASSERT (cond != NULL);