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

   1 /* This file is derived from source code for the Nachos
   2    instructional operating system.  The Nachos copyright notice
   3    is reproduced in full below. */
   4
   5 /* Copyright (c) 1992-1996 The Regents of the University of California.
   6    All rights reserved.
   7
   8    Permission to use, copy, modify, and distribute this software
   9    and its documentation for any purpose, without fee, and
  10    without written agreement is hereby granted, provided that the
  11    above copyright notice and the following two paragraphs appear
  12    in all copies of this software.
  13
  14    IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
  15    ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
  16    CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
  17    AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
  18    HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  19
  20    THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
  21    WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  22    WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23    PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
  24    BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
  25    PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
  26    MODIFICATIONS.
  27 */
  28
  29 #include "threads/synch.h"
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include "threads/interrupt.h"
  33 #include "threads/thread.h"
  34
  35 /* Initializes semaphore SEMA to VALUE and names it NAME (for
  36    debugging purposes only).  A semaphore is a nonnegative
  37    integer along with two atomic operators for manipulating it:
  38
  39    - down or "P": wait for the value to become positive, then
  40      decrement it.
  41
  42    - up or "V": increment the value (and wake up one waiting
  43      thread, if any). */
  44 void
  45 sema_init (struct semaphore *sema, unsigned value, const char *name)
  46 {
  47   ASSERT (sema != NULL);
  48   ASSERT (name != NULL);
  49
  50   strlcpy (sema->name, name, sizeof sema->name);
  51   sema->value = value;
  52   list_init (&sema->waiters);
  53 }
  54
  55 /* Down or "P" operation on a semaphore.  Waits for SEMA's value
  56    to become positive and then atomically decrements it.
  57
  58    This function may sleep, so it must not be called within an
  59    interrupt handler.  This function may be called with
  60    interrupts disabled, but interrupts will be turned back on if
  61    we need to sleep. */
  62 void
  63 sema_down (struct semaphore *sema)
  64 {
  65   enum intr_level old_level;
  66
  67   ASSERT (sema != NULL);
  68   ASSERT (!intr_context ());
  69
  70   old_level = intr_disable ();
  71   while (sema->value == 0)
  72     {
  73       list_push_back (&sema->waiters, &thread_current ()->elem);
  74       thread_block ();
  75     }
  76   sema->value--;
  77   intr_set_level (old_level);
  78 }
  79
  80 /* Up or "V" operation on a semaphore.  Increments SEMA's value
  81    and wakes up one thread of those waiting for SEMA, if any.
  82
  83    This function may be called from an interrupt handler. */
  84 void
  85 sema_up (struct semaphore *sema)
  86 {
  87   enum intr_level old_level;
  88
  89   ASSERT (sema != NULL);
  90
  91   old_level = intr_disable ();
  92   if (!list_empty (&sema->waiters))
  93     thread_unblock (list_entry (list_pop_front (&sema->waiters),
  94                                 struct thread, elem));
  95   sema->value++;
  96   intr_set_level (old_level);
  97 }
  98
  99 /* Return SEMA's name (for debugging purposes). */
 100 const char *
 101 sema_name (const struct semaphore *sema)
 102 {
 103   return sema->name;
 104 }
 105
 106 static void sema_test_helper (void *sema_);
 107
 108 /* Self-test for semaphores that makes control "ping-pong"
 109    between a pair of threads.  Insert calls to printf() to see
 110    what's going on. */
 111 void
 112 sema_self_test (void)
 113 {
 114   struct thread *thread;
 115   struct semaphore sema[2];
 116   int i;
 117
 118   printf ("Testing semaphores...");
 119   sema_init (&sema[0], 0, "ping");
 120   sema_init (&sema[1], 0, "pong");
 121   thread = thread_create ("sema-test", sema_test_helper, &sema);
 122   for (i = 0; i < 10; i++)
 123     {
 124       sema_up (&sema[0]);
 125       sema_down (&sema[1]);
 126     }
 127   printf ("done.\n");
 128 }
 129
 130 /* Thread function used by sema_self_test(). */
 131 static void
 132 sema_test_helper (void *sema_)
 133 {
 134   struct semaphore *sema = sema_;
 135   int i;
 136
 137   for (i = 0; i < 10; i++)
 138     {
 139       sema_down (&sema[0]);
 140       sema_up (&sema[1]);
 141     }
 142 }
 143 \f
 144 /* Initializes LOCK and names it NAME (for debugging purposes).
 145    A lock can be held by at most a single thread at any given
 146    time.  Our locks are not "recursive", that is, it is an error
 147    for the thread currently holding a lock to try to acquire that
 148    lock.
 149
 150    A lock is a specialization of a semaphore with an initial
 151    value of 1.  The difference between a lock and such a
 152    semaphore is twofold.  First, a semaphore can have a value
 153    greater than 1, but a lock can only be owned by a single
 154    thread at a time.  Second, a semaphore does not have an owner,
 155    meaning that one thread can "down" the semaphore and then
 156    another one "up" it, but with a lock the same thread must both
 157    acquire and release it.  When these restrictions prove
 158    onerous, it's a good sign that a semaphore should be used,
 159    instead of a lock. */
 160 void
 161 lock_init (struct lock *lock, const char *name)
 162 {
 163   ASSERT (lock != NULL);
 164   ASSERT (name != NULL);
 165
 166   strlcpy (lock->name, name, sizeof lock->name);
 167   lock->holder = NULL;
 168   sema_init (&lock->semaphore, 1, name);
 169 }
 170
 171 /* Acquires LOCK, sleeping until it becomes available if
 172    necessary.  The lock must not already be held by the current
 173    thread.
 174
 175    This function may sleep, so it must not be called within an
 176    interrupt handler.  This function may be called with
 177    interrupts disabled, but interrupts will be turned back on if
 178    we need to sleep. */
 179 void
 180 lock_acquire (struct lock *lock)
 181 {
 182   enum intr_level old_level;
 183
 184   ASSERT (lock != NULL);
 185   ASSERT (!intr_context ());
 186   ASSERT (!lock_held_by_current_thread (lock));
 187
 188   old_level = intr_disable ();
 189   sema_down (&lock->semaphore);
 190   lock->holder = thread_current ();
 191   intr_set_level (old_level);
 192 }
 193
 194 /* Releases LOCK, which must be owned by the current thread.
 195
 196    An interrupt handler cannot acquire a lock, so it does not
 197    make sense to try to signal a condition variable within an
 198    interrupt handler. */
 199 void
 200 lock_release (struct lock *lock)
 201 {
 202   enum intr_level old_level;
 203
 204   ASSERT (lock != NULL);
 205   ASSERT (lock_held_by_current_thread (lock));
 206
 207   old_level = intr_disable ();
 208   lock->holder = NULL;
 209   sema_up (&lock->semaphore);
 210   intr_set_level (old_level);
 211 }
 212
 213 /* Returns true if the current thread holds LOCK, false
 214    otherwise.  (Note that testing whether some other thread holds
 215    a lock would be racy.) */
 216 bool
 217 lock_held_by_current_thread (const struct lock *lock)
 218 {
 219   ASSERT (lock != NULL);
 220
 221   return lock->holder == thread_current ();
 222 }
 223
 224 /* Returns the name of LOCK (for debugging purposes). */
 225 const char *
 226 lock_name (const struct lock *lock)
 227 {
 228   ASSERT (lock != NULL);
 229
 230   return lock->name;
 231 }
 232 \f
 233 /* One semaphore in a list. */
 234 struct semaphore_elem
 235   {
 236     list_elem elem;                     /* List element. */
 237     struct semaphore semaphore;         /* This semaphore. */
 238   };
 239
 240 /* Initializes condition variable COND and names it NAME.  A
 241    condition variable allows one piece of code to signal a
 242    condition and cooperating code to receive the signal and act
 243    upon it. */
 244 void
 245 cond_init (struct condition *cond, const char *name)
 246 {
 247   ASSERT (cond != NULL);
 248   ASSERT (name != NULL);
 249
 250   strlcpy (cond->name, name, sizeof cond->name);
 251   list_init (&cond->waiters);
 252 }
 253
 254 /* Atomically releases LOCK and waits for COND to be signaled by
 255    some other piece of code.  After COND is signalled, LOCK is
 256    reacquired before returning.  LOCK must be held before calling
 257    this function.
 258
 259    The monitor implemented by this function is "Mesa" style, not
 260    "Hoare" style, that is, sending and receiving a signal are not
 261    an atomic operation.  Thus, typically the caller must recheck
 262    the condition after the wait completes and, if necessary, wait
 263    again.
 264
 265    A given condition variable is associated with only a single
 266    lock, but one lock may be be associated with any number of
 267    condition variables.  That is, there is a one-to-many mapping
 268    from locks to condition variables.
 269
 270    This function may sleep, so it must not be called within an
 271    interrupt handler.  This function may be called with
 272    interrupts disabled, but interrupts will be turned back on if
 273    we need to sleep. */
 274 void
 275 cond_wait (struct condition *cond, struct lock *lock)
 276 {
 277   struct semaphore_elem waiter;
 278
 279   ASSERT (cond != NULL);
 280   ASSERT (lock != NULL);
 281   ASSERT (!intr_context ());
 282   ASSERT (lock_held_by_current_thread (lock));
 283
 284   sema_init (&waiter.semaphore, 0, "condition");
 285   list_push_back (&cond->waiters, &waiter.elem);
 286   lock_release (lock);
 287   sema_down (&waiter.semaphore);
 288   lock_acquire (lock);
 289 }
 290
 291 /* If any threads are waiting on COND (protected by LOCK), then
 292    this function signals one of them to wake up from its wait.
 293    LOCK must be held before calling this function.
 294
 295    An interrupt handler cannot acquire a lock, so it does not
 296    make sense to try to signal a condition variable within an
 297    interrupt handler. */
 298 void
 299 cond_signal (struct condition *cond, struct lock *lock)
 300 {
 301   ASSERT (cond != NULL);
 302   ASSERT (lock != NULL);
 303   ASSERT (!intr_context ());
 304   ASSERT (lock_held_by_current_thread (lock));
 305
 306   if (!list_empty (&cond->waiters))
 307     sema_up (&list_entry (list_pop_front (&cond->waiters),
 308                           struct semaphore_elem, elem)->semaphore);
 309 }
 310
 311 /* Wakes up all threads, if any, waiting on COND (protected by
 312    LOCK).  LOCK must be held before calling this function.
 313
 314    An interrupt handler cannot acquire a lock, so it does not
 315    make sense to try to signal a condition variable within an
 316    interrupt handler. */
 317 void
 318 cond_broadcast (struct condition *cond, struct lock *lock)
 319 {
 320   ASSERT (cond != NULL);
 321   ASSERT (lock != NULL);
 322
 323   while (!list_empty (&cond->waiters))
 324     cond_signal (cond, lock);
 325 }
 326
 327 /* Returns COND's name (for debugging purposes). */
 328 const char *
 329 cond_name (const struct condition *cond)
 330 {
 331   ASSERT (cond != NULL);
 332
 333   return cond->name;
 334 }