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     struct 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. */
  39 void
  40 sema_down (struct semaphore *sema)
  41 {
  42   enum if_level old_level;
  43
  44   ASSERT (sema != NULL);
  45   ASSERT (!intr_context ());
  46
  47   old_level = intr_disable ();
  48   while (sema->value == 0)
  49     {
  50       struct thread_elem te;
  51       te.thread = thread_current ();
  52       list_push_back (&sema->waiters, &te.elem);
  53       thread_sleep ();
  54     }
  55   sema->value--;
  56   intr_set_level (old_level);
  57 }
  58
  59 /* Increments SEMA's value.  Wakes up one thread of those waiting
  60    for SEMA, if any.
  61
  62    This function may be called from an interrupt handler. */
  63 void
  64 sema_up (struct semaphore *sema)
  65 {
  66   enum if_level old_level;
  67
  68   ASSERT (sema != NULL);
  69
  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);
  74   sema->value++;
  75   intr_set_level (old_level);
  76 }
  77
  78 /* Return SEMA's name (for debugging purposes). */
  79 const char *
  80 sema_name (const struct semaphore *sema)
  81 {
  82   return sema->name;
  83 }
  84
  85 static void
  86 sema_test_helper (void *sema_)
  87 {
  88   struct semaphore *sema = sema_;
  89   int i;
  90
  91   for (i = 0; i < 10; i++)
  92     {
  93       sema_down (&sema[0]);
  94       sema_up (&sema[1]);
  95     }
  96 }
  97
  98 /* Self-test for semaphores that makes control "ping-pong"
  99    between a pair of threads.  Insert calls to printk() to see
 100    what's going on. */
 101 void
 102 sema_self_test (void)
 103 {
 104   struct thread *thread;
 105   struct semaphore sema[2];
 106   int i;
 107
 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++)
 112     {
 113       sema_up (&sema[0]);
 114       sema_down (&sema[1]);
 115     }
 116 }
 117 \f
 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
 122    it.
 123
 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. */
 134 void
 135 lock_init (struct lock *lock, const char *name)
 136 {
 137   ASSERT (lock != NULL);
 138   ASSERT (name != NULL);
 139
 140   strlcpy (lock->name, name, sizeof lock->name);
 141   lock->holder = NULL;
 142   sema_init (&lock->semaphore, 1, name);
 143 }
 144
 145 /* Acquires LOCK, sleeping until it becomes available if
 146    necessary.  The lock must not already be held by the current
 147    thread.
 148
 149    This function may sleep, so it must not be called within an
 150    interrupt handler. */
 151 void
 152 lock_acquire (struct lock *lock)
 153 {
 154   enum if_level old_level;
 155
 156   ASSERT (lock != NULL);
 157   ASSERT (!intr_context ());
 158   ASSERT (!lock_held_by_current_thread (lock));
 159
 160   old_level = intr_disable ();
 161   sema_down (&lock->semaphore);
 162   lock->holder = thread_current ();
 163   intr_set_level (old_level);
 164 }
 165
 166 /* Releases LOCK, which must be owned by the current thread.
 167
 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. */
 171 void
 172 lock_release (struct lock *lock)
 173 {
 174   enum if_level old_level;
 175
 176   ASSERT (lock != NULL);
 177   ASSERT (lock_held_by_current_thread (lock));
 178
 179   old_level = intr_disable ();
 180   lock->holder = NULL;
 181   sema_up (&lock->semaphore);
 182   intr_set_level (old_level);
 183 }
 184
 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.) */
 188 bool
 189 lock_held_by_current_thread (const struct lock *lock)
 190 {
 191   ASSERT (lock != NULL);
 192
 193   return lock->holder == thread_current ();
 194 }
 195
 196 /* Returns the name of LOCK (for debugging purposes). */
 197 const char *
 198 lock_name (const struct lock *lock)
 199 {
 200   ASSERT (lock != NULL);
 201
 202   return lock->name;
 203 }
 204 \f
 205 /* One semaphore in a list. */
 206 struct semaphore_elem
 207   {
 208     struct list_elem elem;
 209     struct semaphore semaphore;
 210   };
 211
 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
 215    upon it. */
 216 void
 217 cond_init (struct condition *cond, const char *name)
 218 {
 219   ASSERT (cond != NULL);
 220   ASSERT (name != NULL);
 221
 222   strlcpy (cond->name, name, sizeof cond->name);
 223   list_init (&cond->waiters);
 224 }
 225
 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
 229    this function.
 230
 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
 235    again.
 236
 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.
 241
 242    This function may sleep, so it must not be called within an
 243    interrupt handler. */
 244 void
 245 cond_wait (struct condition *cond, struct lock *lock)
 246 {
 247   struct semaphore_elem waiter;
 248
 249   ASSERT (cond != NULL);
 250   ASSERT (lock != NULL);
 251   ASSERT (!intr_context ());
 252   ASSERT (lock_held_by_current_thread (lock));
 253
 254   sema_init (&waiter.semaphore, 0, "condition");
 255   list_push_back (&cond->waiters, &waiter.elem);
 256   lock_release (lock);
 257   sema_down (&waiter.semaphore);
 258   lock_acquire (lock);
 259 }
 260
 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.
 264
 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. */
 268 void
 269 cond_signal (struct condition *cond, struct lock *lock)
 270 {
 271   ASSERT (cond != NULL);
 272   ASSERT (lock != NULL);
 273   ASSERT (!intr_context ());
 274   ASSERT (lock_held_by_current_thread (lock));
 275
 276   if (!list_empty (&cond->waiters))
 277     sema_up (&list_entry (list_pop_front (&cond->waiters),
 278                           struct semaphore_elem, elem)->semaphore);
 279 }
 280
 281 /* Wakes up all threads, if any, waiting on COND (protected by
 282    LOCK).  LOCK must be held before calling this function.
 283
 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. */
 287 void
 288 cond_broadcast (struct condition *cond, struct lock *lock)
 289 {
 290   ASSERT (cond != NULL);
 291   ASSERT (lock != NULL);
 292
 293   while (!list_empty (&cond->waiters))
 294     cond_signal (cond, lock);
 295 }
 296
 297 /* Returns COND's name (for debugging purposes). */
 298 const char *
 299 cond_name (const struct condition *cond)
 300 {
 301   ASSERT (cond != NULL);
 302
 303   return cond->name;
 304 }