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.  A semaphore is a
  36    nonnegative integer along with two atomic operators for
  37    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)
  46 {
  47   ASSERT (sema != NULL);
  48
  49   sema->value = value;
  50   list_init (&sema->waiters);
  51 }
  52
  53 /* Down or "P" operation on a semaphore.  Waits for SEMA's value
  54    to become positive and then atomically decrements it.
  55
  56    This function may sleep, so it must not be called within an
  57    interrupt handler.  This function may be called with
  58    interrupts disabled, but interrupts will be turned back on if
  59    we need to sleep. */
  60 void
  61 sema_down (struct semaphore *sema)
  62 {
  63   enum intr_level old_level;
  64
  65   ASSERT (sema != NULL);
  66   ASSERT (!intr_context ());
  67
  68   old_level = intr_disable ();
  69   while (sema->value == 0)
  70     {
  71       list_push_back (&sema->waiters, &thread_current ()->elem);
  72       thread_block ();
  73     }
  74   sema->value--;
  75   intr_set_level (old_level);
  76 }
  77
  78 /* Down or "P" operation on a semaphore, but only if the
  79    semaphore is not already 0.  Returns true if the semaphore is
  80    decremented, false otherwise.
  81
  82    This function may be called from an interrupt handler. */
  83 bool
  84 sema_try_down (struct semaphore *sema)
  85 {
  86   enum intr_level old_level;
  87   bool success;
  88
  89   ASSERT (sema != NULL);
  90
  91   old_level = intr_disable ();
  92   if (sema->value > 0)
  93     {
  94       sema->value--;
  95       success = true;
  96     }
  97   else
  98     success = false;
  99   intr_set_level (old_level);
 100
 101   return success;
 102 }
 103
 104 /* Up or "V" operation on a semaphore.  Increments SEMA's value
 105    and wakes up one thread of those waiting for SEMA, if any.
 106
 107    This function may be called from an interrupt handler. */
 108 void
 109 sema_up (struct semaphore *sema)
 110 {
 111   enum intr_level old_level;
 112
 113   ASSERT (sema != NULL);
 114
 115   old_level = intr_disable ();
 116   if (!list_empty (&sema->waiters))
 117     thread_unblock (list_entry (list_pop_front (&sema->waiters),
 118                                 struct thread, elem));
 119   sema->value++;
 120   intr_set_level (old_level);
 121 }
 122
 123 static void sema_test_helper (void *sema_);
 124
 125 /* Self-test for semaphores that makes control "ping-pong"
 126    between a pair of threads.  Insert calls to printf() to see
 127    what's going on. */
 128 void
 129 sema_self_test (void)
 130 {
 131   struct semaphore sema[2];
 132   int i;
 133
 134   printf ("Testing semaphores...");
 135   sema_init (&sema[0], 0);
 136   sema_init (&sema[1], 0);
 137   thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
 138   for (i = 0; i < 10; i++)
 139     {
 140       sema_up (&sema[0]);
 141       sema_down (&sema[1]);
 142     }
 143   printf ("done.\n");
 144 }
 145
 146 /* Thread function used by sema_self_test(). */
 147 static void
 148 sema_test_helper (void *sema_)
 149 {
 150   struct semaphore *sema = sema_;
 151   int i;
 152
 153   for (i = 0; i < 10; i++)
 154     {
 155       sema_down (&sema[0]);
 156       sema_up (&sema[1]);
 157     }
 158 }
 159 \f
 160 /* Initializes LOCK.  A lock can be held by at most a single
 161    thread at any given time.  Our locks are not "recursive", that
 162    is, it is an error for the thread currently holding a lock to
 163    try to acquire that lock.
 164
 165    A lock is a specialization of a semaphore with an initial
 166    value of 1.  The difference between a lock and such a
 167    semaphore is twofold.  First, a semaphore can have a value
 168    greater than 1, but a lock can only be owned by a single
 169    thread at a time.  Second, a semaphore does not have an owner,
 170    meaning that one thread can "down" the semaphore and then
 171    another one "up" it, but with a lock the same thread must both
 172    acquire and release it.  When these restrictions prove
 173    onerous, it's a good sign that a semaphore should be used,
 174    instead of a lock. */
 175 void
 176 lock_init (struct lock *lock)
 177 {
 178   ASSERT (lock != NULL);
 179
 180   lock->holder = NULL;
 181   sema_init (&lock->semaphore, 1);
 182 }
 183
 184 /* Acquires LOCK, sleeping until it becomes available if
 185    necessary.  The lock must not already be held by the current
 186    thread.
 187
 188    This function may sleep, so it must not be called within an
 189    interrupt handler.  This function may be called with
 190    interrupts disabled, but interrupts will be turned back on if
 191    we need to sleep. */
 192 void
 193 lock_acquire (struct lock *lock)
 194 {
 195   enum intr_level old_level;
 196
 197   ASSERT (lock != NULL);
 198   ASSERT (!intr_context ());
 199   ASSERT (!lock_held_by_current_thread (lock));
 200
 201   old_level = intr_disable ();
 202   sema_down (&lock->semaphore);
 203   lock->holder = thread_current ();
 204   intr_set_level (old_level);
 205 }
 206
 207 /* Tries to acquires LOCK and returns true if successful or false
 208    on failure.  The lock must not already be held by the current
 209    thread.
 210
 211    This function will not sleep, so it may be called within an
 212    interupt handler. */
 213 bool
 214 lock_try_acquire (struct lock *lock)
 215 {
 216   enum intr_level old_level;
 217   bool success;
 218
 219   ASSERT (lock != NULL);
 220   ASSERT (!lock_held_by_current_thread (lock));
 221
 222   old_level = intr_disable ();
 223   success = sema_try_down (&lock->semaphore);
 224   if (success)
 225     lock->holder = thread_current ();
 226   intr_set_level (old_level);
 227
 228   return success;
 229 }
 230
 231 /* Releases LOCK, which must be owned by the current thread.
 232
 233    An interrupt handler cannot acquire a lock, so it does not
 234    make sense to try to release a lock within an interrupt
 235    handler. */
 236 void
 237 lock_release (struct lock *lock)
 238 {
 239   enum intr_level old_level;
 240
 241   ASSERT (lock != NULL);
 242   ASSERT (lock_held_by_current_thread (lock));
 243
 244   old_level = intr_disable ();
 245   lock->holder = NULL;
 246   sema_up (&lock->semaphore);
 247   intr_set_level (old_level);
 248 }
 249
 250 /* Returns true if the current thread holds LOCK, false
 251    otherwise.  (Note that testing whether some other thread holds
 252    a lock would be racy.) */
 253 bool
 254 lock_held_by_current_thread (const struct lock *lock)
 255 {
 256   ASSERT (lock != NULL);
 257
 258   return lock->holder == thread_current ();
 259 }
 260 \f
 261 /* One semaphore in a list. */
 262 struct semaphore_elem
 263   {
 264     struct list_elem elem;              /* List element. */
 265     struct semaphore semaphore;         /* This semaphore. */
 266   };
 267
 268 /* Initializes condition variable COND.  A condition variable
 269    allows one piece of code to signal a condition and cooperating
 270    code to receive the signal and act upon it. */
 271 void
 272 cond_init (struct condition *cond)
 273 {
 274   ASSERT (cond != NULL);
 275
 276   list_init (&cond->waiters);
 277 }
 278
 279 /* Atomically releases LOCK and waits for COND to be signaled by
 280    some other piece of code.  After COND is signaled, LOCK is
 281    reacquired before returning.  LOCK must be held before calling
 282    this function.
 283
 284    The monitor implemented by this function is "Mesa" style, not
 285    "Hoare" style, that is, sending and receiving a signal are not
 286    an atomic operation.  Thus, typically the caller must recheck
 287    the condition after the wait completes and, if necessary, wait
 288    again.
 289
 290    A given condition variable is associated with only a single
 291    lock, but one lock may be associated with any number of
 292    condition variables.  That is, there is a one-to-many mapping
 293    from locks to condition variables.
 294
 295    This function may sleep, so it must not be called within an
 296    interrupt handler.  This function may be called with
 297    interrupts disabled, but interrupts will be turned back on if
 298    we need to sleep. */
 299 void
 300 cond_wait (struct condition *cond, struct lock *lock)
 301 {
 302   struct semaphore_elem waiter;
 303
 304   ASSERT (cond != NULL);
 305   ASSERT (lock != NULL);
 306   ASSERT (!intr_context ());
 307   ASSERT (lock_held_by_current_thread (lock));
 308
 309   sema_init (&waiter.semaphore, 0);
 310   list_push_back (&cond->waiters, &waiter.elem);
 311   lock_release (lock);
 312   sema_down (&waiter.semaphore);
 313   lock_acquire (lock);
 314 }
 315
 316 /* If any threads are waiting on COND (protected by LOCK), then
 317    this function signals one of them to wake up from its wait.
 318    LOCK must be held before calling this function.
 319
 320    An interrupt handler cannot acquire a lock, so it does not
 321    make sense to try to signal a condition variable within an
 322    interrupt handler. */
 323 void
 324 cond_signal (struct condition *cond, struct lock *lock UNUSED)
 325 {
 326   ASSERT (cond != NULL);
 327   ASSERT (lock != NULL);
 328   ASSERT (!intr_context ());
 329   ASSERT (lock_held_by_current_thread (lock));
 330
 331   if (!list_empty (&cond->waiters))
 332     sema_up (&list_entry (list_pop_front (&cond->waiters),
 333                           struct semaphore_elem, elem)->semaphore);
 334 }
 335
 336 /* Wakes up all threads, if any, waiting on COND (protected by
 337    LOCK).  LOCK must be held before calling this function.
 338
 339    An interrupt handler cannot acquire a lock, so it does not
 340    make sense to try to signal a condition variable within an
 341    interrupt handler. */
 342 void
 343 cond_broadcast (struct condition *cond, struct lock *lock)
 344 {
 345   ASSERT (cond != NULL);
 346   ASSERT (lock != NULL);
 347
 348   while (!list_empty (&cond->waiters))
 349     cond_signal (cond, lock);
 350 }