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