pintos-os.org Git - pintos-anon/blob - src/threads/synch.c

   1 #include "synch.h"
   2 #include "interrupt.h"
   3 #include "lib.h"
   4 #include "thread.h"
   5
   6 /* One thread in a list. */
   7 struct thread_elem
   8   {
   9     list_elem elem;
  10     struct thread *thread;
  11   };
  12
  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:
  16
  17    - down or "P": wait for the value to become positive, then
  18      decrement it.
  19
  20    - up or "V": increment the value (and wake up one waiting
  21      thread, if any). */
  22 void
  23 sema_init (struct semaphore *sema, unsigned value, const char *name)
  24 {
  25   ASSERT (sema != NULL);
  26   ASSERT (name != NULL);
  27
  28   strlcpy (sema->name, name, sizeof sema->name);
  29   sema->value = value;
  30   list_init (&sema->waiters);
  31 }
  32
  33 /* Waits for SEMA's value to become positive and then
  34    atomically decrements it.
  35
  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
  39    we need to sleep. */
  40 void
  41 sema_down (struct semaphore *sema)
  42 {
  43   enum intr_level old_level;
  44
  45   ASSERT (sema != NULL);
  46   ASSERT (!intr_context ());
  47
  48   old_level = intr_disable ();
  49   while (sema->value == 0)
  50     {
  51       struct thread_elem te;
  52       te.thread = thread_current ();
  53       list_push_back (&sema->waiters, &te.elem);
  54       thread_sleep ();
  55     }
  56   sema->value--;
  57   intr_set_level (old_level);
  58 }
  59
  60 /* Increments SEMA's value.  Wakes up one thread of those waiting
  61    for SEMA, if any.
  62
  63    This function may be called from an interrupt handler. */
  64 void
  65 sema_up (struct semaphore *sema)
  66 {
  67   enum intr_level old_level;
  68
  69   ASSERT (sema != NULL);
  70
  71   old_level = intr_disable ();
  72   if (!list_empty (&sema->waiters))
  73     thread_wake (list_entry (list_pop_front (&sema->waiters),
  74                              struct thread_elem, elem)->thread);
  75   sema->value++;
  76   intr_set_level (old_level);
  77 }
  78
  79 /* Return SEMA's name (for debugging purposes). */
  80 const char *
  81 sema_name (const struct semaphore *sema)
  82 {
  83   return sema->name;
  84 }
  85
  86 static void
  87 sema_test_helper (void *sema_)
  88 {
  89   struct semaphore *sema = sema_;
  90   int i;
  91
  92   for (i = 0; i < 10; i++)
  93     {
  94       sema_down (&sema[0]);
  95       sema_up (&sema[1]);
  96     }
  97 }
  98
  99 /* Self-test for semaphores that makes control "ping-pong"
 100    between a pair of threads.  Insert calls to printk() to see
 101    what's going on. */
 102 void
 103 sema_self_test (void)
 104 {
 105   struct thread *thread;
 106   struct semaphore sema[2];
 107   int i;
 108
 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++)
 113     {
 114       sema_up (&sema[0]);
 115       sema_down (&sema[1]);
 116     }
 117 }
 118 \f
 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
 123    lock.
 124
 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. */
 135 void
 136 lock_init (struct lock *lock, const char *name)
 137 {
 138   ASSERT (lock != NULL);
 139   ASSERT (name != NULL);
 140
 141   strlcpy (lock->name, name, sizeof lock->name);
 142   lock->holder = NULL;
 143   sema_init (&lock->semaphore, 1, name);
 144 }
 145
 146 /* Acquires LOCK, sleeping until it becomes available if
 147    necessary.  The lock must not already be held by the current
 148    thread.
 149
 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
 153    we need to sleep. */
 154 void
 155 lock_acquire (struct lock *lock)
 156 {
 157   enum intr_level old_level;
 158
 159   ASSERT (lock != NULL);
 160   ASSERT (!intr_context ());
 161   ASSERT (!lock_held_by_current_thread (lock));
 162
 163   old_level = intr_disable ();
 164   sema_down (&lock->semaphore);
 165   lock->holder = thread_current ();
 166   intr_set_level (old_level);
 167 }
 168
 169 /* Releases LOCK, which must be owned by the current thread.
 170
 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. */
 174 void
 175 lock_release (struct lock *lock)
 176 {
 177   enum intr_level old_level;
 178
 179   ASSERT (lock != NULL);
 180   ASSERT (lock_held_by_current_thread (lock));
 181
 182   old_level = intr_disable ();
 183   lock->holder = NULL;
 184   sema_up (&lock->semaphore);
 185   intr_set_level (old_level);
 186 }
 187
 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.) */
 191 bool
 192 lock_held_by_current_thread (const struct lock *lock)
 193 {
 194   ASSERT (lock != NULL);
 195
 196   return lock->holder == thread_current ();
 197 }
 198
 199 /* Returns the name of LOCK (for debugging purposes). */
 200 const char *
 201 lock_name (const struct lock *lock)
 202 {
 203   ASSERT (lock != NULL);
 204
 205   return lock->name;
 206 }
 207 \f
 208 /* One semaphore in a list. */
 209 struct semaphore_elem
 210   {
 211     list_elem elem;
 212     struct semaphore semaphore;
 213   };
 214
 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
 218    upon it. */
 219 void
 220 cond_init (struct condition *cond, const char *name)
 221 {
 222   ASSERT (cond != NULL);
 223   ASSERT (name != NULL);
 224
 225   strlcpy (cond->name, name, sizeof cond->name);
 226   list_init (&cond->waiters);
 227 }
 228
 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
 232    this function.
 233
 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
 238    again.
 239
 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.
 244
 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
 248    we need to sleep. */
 249 void
 250 cond_wait (struct condition *cond, struct lock *lock)
 251 {
 252   struct semaphore_elem waiter;
 253
 254   ASSERT (cond != NULL);
 255   ASSERT (lock != NULL);
 256   ASSERT (!intr_context ());
 257   ASSERT (lock_held_by_current_thread (lock));
 258
 259   sema_init (&waiter.semaphore, 0, "condition");
 260   list_push_back (&cond->waiters, &waiter.elem);
 261   lock_release (lock);
 262   sema_down (&waiter.semaphore);
 263   lock_acquire (lock);
 264 }
 265
 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.
 269
 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. */
 273 void
 274 cond_signal (struct condition *cond, struct lock *lock)
 275 {
 276   ASSERT (cond != NULL);
 277   ASSERT (lock != NULL);
 278   ASSERT (!intr_context ());
 279   ASSERT (lock_held_by_current_thread (lock));
 280
 281   if (!list_empty (&cond->waiters))
 282     sema_up (&list_entry (list_pop_front (&cond->waiters),
 283                           struct semaphore_elem, elem)->semaphore);
 284 }
 285
 286 /* Wakes up all threads, if any, waiting on COND (protected by
 287    LOCK).  LOCK must be held before calling this function.
 288
 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. */
 292 void
 293 cond_broadcast (struct condition *cond, struct lock *lock)
 294 {
 295   ASSERT (cond != NULL);
 296   ASSERT (lock != NULL);
 297
 298   while (!list_empty (&cond->waiters))
 299     cond_signal (cond, lock);
 300 }
 301
 302 /* Returns COND's name (for debugging purposes). */
 303 const char *
 304 cond_name (const struct condition *cond)
 305 {
 306   ASSERT (cond != NULL);
 307
 308   return cond->name;
 309 }