7 /* One thread in a list. */
10 struct list_elem elem;
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
40 sema_down (struct semaphore *sema)
42 enum if_level old_level;
44 ASSERT (sema != NULL);
45 ASSERT (!intr_context ());
47 old_level = intr_disable ();
48 while (sema->value == 0)
50 struct thread_elem te;
51 te.thread = thread_current ();
52 list_push_back (&sema->waiters, &te.elem);
56 intr_set_level (old_level);
59 /* Increments SEMA's value. Wakes up one thread of those waiting
62 This function may be called from an interrupt handler. */
64 sema_up (struct semaphore *sema)
66 enum if_level old_level;
68 ASSERT (sema != NULL);
70 old_level = intr_disable ();
71 if (!list_empty (&sema->waiters))
72 thread_ready (list_entry (list_pop_front (&sema->waiters),
73 struct thread_elem, elem)->thread);
75 intr_set_level (old_level);
78 /* Return SEMA's name (for debugging purposes). */
80 sema_name (const struct semaphore *sema)
86 sema_test_helper (void *sema_)
88 struct semaphore *sema = sema_;
91 for (i = 0; i < 10; i++)
98 /* Self-test for semaphores that makes control "ping-pong"
99 between a pair of threads. Insert calls to printk() to see
102 sema_self_test (void)
104 struct thread *thread;
105 struct semaphore sema[2];
108 sema_init (&sema[0], 0, "ping");
109 sema_init (&sema[1], 0, "pong");
110 thread = thread_create ("sema-test", sema_test_helper, &sema);
111 for (i = 0; i < 10; i++)
114 sema_down (&sema[1]);
118 /* Initializes LOCK and names it NAME (for debugging purposes).
119 A lock can be held by at most a single thread at any given
120 time. Our locks are not "recursive", meaning that it is an
121 error for a thread that holds a lock to attempt to reacquire
124 A lock is a specialization of a semaphore with an initial
125 value of 1. The difference between a lock and such a
126 semaphore is twofold. First, a semaphore can have a value
127 greater than 1, but a lock can only be owned by a single
128 thread at a time. Second, a semaphore does not have an owner,
129 meaning that one thread can "down" the semaphore and then
130 another one "up" it, but with a lock the same thread must both
131 acquire and release it. When these restrictions prove
132 onerous, it's a good sign that a semaphore should be used,
133 instead of a lock. */
135 lock_init (struct lock *lock, const char *name)
137 ASSERT (lock != NULL);
138 ASSERT (name != NULL);
140 strlcpy (lock->name, name, sizeof lock->name);
142 sema_init (&lock->semaphore, 1, name);
145 /* Acquires LOCK, sleeping until it becomes available if
146 necessary. The lock must not already be held by the current
149 This function may sleep, so it must not be called within an
150 interrupt handler. */
152 lock_acquire (struct lock *lock)
154 enum if_level old_level;
156 ASSERT (lock != NULL);
157 ASSERT (!intr_context ());
158 ASSERT (!lock_held_by_current_thread (lock));
160 old_level = intr_disable ();
161 sema_down (&lock->semaphore);
162 lock->holder = thread_current ();
163 intr_set_level (old_level);
166 /* Releases LOCK, which must be owned by the current thread.
168 An interrupt handler cannot acquire a lock, so it does not
169 make sense to try to signal a condition variable within an
170 interrupt handler. */
172 lock_release (struct lock *lock)
174 enum if_level old_level;
176 ASSERT (lock != NULL);
177 ASSERT (lock_held_by_current_thread (lock));
179 old_level = intr_disable ();
181 sema_up (&lock->semaphore);
182 intr_set_level (old_level);
185 /* Returns true if the current thread holds LOCK, false
186 otherwise. (Note that testing whether some other thread holds
187 a lock would be racy.) */
189 lock_held_by_current_thread (const struct lock *lock)
191 ASSERT (lock != NULL);
193 return lock->holder == thread_current ();
196 /* Returns the name of LOCK (for debugging purposes). */
198 lock_name (const struct lock *lock)
200 ASSERT (lock != NULL);
205 /* One semaphore in a list. */
206 struct semaphore_elem
208 struct list_elem elem;
209 struct semaphore semaphore;
212 /* Initializes condition variable COND and names it NAME. A
213 condition variable allows one piece of code to signal a
214 condition and cooperating code to receive the signal and act
217 cond_init (struct condition *cond, const char *name)
219 ASSERT (cond != NULL);
220 ASSERT (name != NULL);
222 strlcpy (cond->name, name, sizeof cond->name);
223 list_init (&cond->waiters);
226 /* Atomically releases LOCK and waits for COND to be signaled by
227 some other piece of code. After COND is signalled, LOCK is
228 reacquired before returning. LOCK must be held before calling
231 The monitor implemented by this function is "Mesa" style, not
232 "Hoare" style. That is, sending a signal is not atomic with
233 delivering it. Thus, typically the caller must recheck the
234 condition after the wait completes and, if necessary, wait
237 A given condition variable is associated with only a single
238 lock, but one lock may be be associated with any number of
239 condition variables. That is, there is a one-to-many mapping
240 from locks to condition variables.
242 This function may sleep, so it must not be called within an
243 interrupt handler. */
245 cond_wait (struct condition *cond, struct lock *lock)
247 struct semaphore_elem waiter;
249 ASSERT (cond != NULL);
250 ASSERT (lock != NULL);
251 ASSERT (!intr_context ());
252 ASSERT (lock_held_by_current_thread (lock));
254 sema_init (&waiter.semaphore, 0, "condition");
255 list_push_back (&cond->waiters, &waiter.elem);
257 sema_down (&waiter.semaphore);
261 /* If any threads are waiting on COND (protected by LOCK), then
262 this function signals one of them to wake up from its wait.
263 LOCK must be held before calling this function.
265 An interrupt handler cannot acquire a lock, so it does not
266 make sense to try to signal a condition variable within an
267 interrupt handler. */
269 cond_signal (struct condition *cond, struct lock *lock)
271 ASSERT (cond != NULL);
272 ASSERT (lock != NULL);
273 ASSERT (!intr_context ());
274 ASSERT (lock_held_by_current_thread (lock));
276 if (!list_empty (&cond->waiters))
277 sema_up (&list_entry (list_pop_front (&cond->waiters),
278 struct semaphore_elem, elem)->semaphore);
281 /* Wakes up all threads, if any, waiting on COND (protected by
282 LOCK). LOCK must be held before calling this function.
284 An interrupt handler cannot acquire a lock, so it does not
285 make sense to try to signal a condition variable within an
286 interrupt handler. */
288 cond_broadcast (struct condition *cond, struct lock *lock)
290 ASSERT (cond != NULL);
291 ASSERT (lock != NULL);
293 while (!list_empty (&cond->waiters))
294 cond_signal (cond, lock);
297 /* Returns COND's name (for debugging purposes). */
299 cond_name (const struct condition *cond)
301 ASSERT (cond != NULL);