csenotes12

RAilway Project

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