SHARE
TWEET

Untitled

a guest Nov 9th, 2019 74 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. /* Initializes semaphore SEMA to VALUE.  A semaphore is a
  35.    nonnegative integer along with two atomic operators for
  36.    manipulating it:
  37.  
  38.    - down or "P": wait for the value to become positive, then
  39.      decrement it.
  40.  
  41.    - up or "V": increment the value (and wake up one waiting
  42.      thread, if any). */
  43. void
  44. sema_init (struct semaphore *sema, unsigned value)
  45. {
  46.   ASSERT (sema != NULL);
  47.  
  48.   sema->value = value;
  49.   list_init (&sema->waiters);
  50. }
  51.  
  52. /* Down or "P" operation on a semaphore.  Waits for SEMA's value
  53.    to become positive and then atomically decrements it.
  54.  
  55.    This function may sleep, so it must not be called within an
  56.    interrupt handler.  This function may be called with
  57.    interrupts disabled, but if it sleeps then the next scheduled
  58.    thread will probably turn interrupts back on. */
  59. void
  60. sema_down (struct semaphore *sema)
  61. {
  62.  
  63.   enum intr_level old_level;
  64.  
  65.   ASSERT (sema != NULL);
  66.   ASSERT (!intr_context ());
  67.   old_level = intr_disable ();
  68.   while (sema->value == 0)
  69.     {
  70.       list_push_back (&sema->waiters, &thread_current ()->elem);
  71.       //printf("%s add to sema-waiters\n", thread_current()->name);
  72.       //SortSemaWaiters(ChooseMaxPriorThreadSema(sema), sema);
  73.       thread_block ();
  74.     }
  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. struct thread *
  106. ChooseMaxPriorThreadSema(struct semaphore *sema_1)
  107. {
  108.   // printf("OneMore\n");
  109.   struct thread *tempMax, *targetProc, *startProc;  
  110.   tempMax=list_entry (list_pop_front (&sema_1->waiters), struct thread, elem);
  111.   startProc=tempMax;
  112.   //printf("Start Process=%s\n", startProc->name);
  113.   int maxPrior=tempMax->priority;
  114.   if (list_empty(&sema_1->waiters))
  115.   {
  116.     //printf("EMPTY\n");
  117.     return tempMax;
  118.   }
  119.   list_push_back (&sema_1->waiters, &tempMax->elem);
  120.   targetProc=list_entry (list_pop_front (&sema_1->waiters), struct thread, elem);
  121.   while (startProc!=targetProc)
  122.   {
  123.     //printf("%s=?%s\n", targetProc->name, startProc->name);
  124.     if (maxPrior<targetProc->priority)
  125.     {
  126.       if (tempMax!=startProc)
  127.       list_push_back (&sema_1->waiters, &tempMax->elem);
  128.       tempMax=targetProc;
  129.       maxPrior=targetProc->priority;
  130.     }
  131.     else
  132.     {
  133.       list_push_back (&sema_1->waiters, &targetProc->elem);
  134.     }
  135.    
  136.     targetProc=list_entry (list_pop_front (&sema_1->waiters), struct thread, elem);
  137.   }
  138.   if (tempMax!=startProc)
  139.   {
  140.     list_push_back (&sema_1->waiters, &targetProc->elem);
  141.   }
  142.  
  143.   return tempMax;
  144. }
  145. int SortSemaWaiters(struct thread *firstProc, struct semaphore *sema_2)
  146. {
  147.   int SortNum=1;
  148.   list_push_back (&sema_2->waiters, &firstProc->elem);
  149.   struct thread *tempMax, *targetProc, *helpProc;
  150.   tempMax=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  151.   if (tempMax==firstProc)
  152.   {
  153.     list_push_back(&sema_2->waiters, &tempMax->elem);
  154.     //printf("So EMPTY\n");
  155.     return 0;
  156.   }
  157.   //printf("No \n");
  158.   targetProc=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  159.   while (tempMax!=firstProc)
  160.   {
  161.     if (tempMax->priority<targetProc->priority)
  162.     {
  163.       list_push_back (&sema_2->waiters, &tempMax->elem);
  164.       tempMax=targetProc;
  165.     }
  166.     else
  167.     {
  168.       list_push_back (&sema_2->waiters, &targetProc->elem);
  169.     }
  170.     targetProc=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  171.     if (targetProc==firstProc)
  172.     {
  173.       list_push_front(&sema_2->waiters, &targetProc->elem);
  174.       for (int p=0; p<SortNum; p++)
  175.       {
  176.         helpProc=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  177.         list_push_back (&sema_2->waiters, &helpProc->elem);
  178.       }
  179.       list_push_back (&sema_2->waiters, &tempMax->elem);
  180.       SortNum++;
  181.       tempMax=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  182.       targetProc=list_entry (list_pop_front (&sema_2->waiters), struct thread, elem);
  183.     }
  184.   }
  185.   list_push_front(&sema_2->waiters, &targetProc->elem);
  186.   list_push_front (&sema_2->waiters, &tempMax->elem);
  187.   return 0;
  188. }
  189. /* Up or "V" operation on a semaphore.  Increments SEMA's value
  190.    and wakes up one thread of those waiting for SEMA, if any.
  191.  
  192.    This function may be called from an interrupt handler. */
  193. void
  194. sema_up (struct semaphore *sema)
  195. {
  196.   struct thread *popa;
  197.  
  198.   enum intr_level old_level;
  199.   ASSERT (sema != NULL);
  200.   old_level = intr_disable ();
  201.   if (!list_empty (&sema->waiters))
  202.   {
  203.     popa=ChooseMaxPriorThreadSema(sema);
  204.    // SortSemaWaiters(popa, sema);
  205.     //popa=list_entry (list_pop_front (&sema->waiters),
  206.                               //  struct thread, elem);
  207.     //printf("%s\n", popa->name);
  208.     //thread_unblock (list_entry (list_pop_front (&sema->waiters),
  209.             //                    struct thread, elem));
  210.     //printf("%s\n", thread_current()->name);
  211.     //thread_yield();
  212.     //thread_unblock (list_entry (list_pop_front (&sema->waiters),
  213.     //                            struct thread, elem));
  214.     //popa=ChooseMaxPriorThreadSema(sema);
  215.     //printf("\n");
  216.    // printf("%s is unblocked and put in the ready-list.\n", popa->name);
  217.    // printf("Sema_Waiters : ");
  218.    // for (struct list_elem* p = list_begin(&sema->waiters); p != list_end(&sema->waiters); p = p->next) {
  219.    //   printf("%d ", list_entry(p, struct thread, elem)->priority);
  220.     //}
  221.    // printf("\n");
  222.    
  223.     sema->value++;
  224.     //printf("Sema->value=%d\n", sema->value);
  225.     thread_unblock_for_sema (popa);
  226.      sema->value--;
  227.     //printf("This thread complited unblock!\n");
  228.   }
  229.   //printf("%d\n", sema->value);
  230.   //thread_unblock (ChooseMaxPriorThreadSema(sema));
  231.   sema->value++;
  232.   //printf("%d ", sema->value);
  233.   intr_set_level (old_level);
  234. }
  235.  
  236. static void sema_test_helper (void *sema_);
  237.  
  238. /* Self-test for semaphores that makes control "ping-pong"
  239.    between a pair of threads.  Insert calls to printf() to see
  240.    what's going on. */
  241. void
  242. sema_self_test (void)
  243. {
  244.   struct semaphore sema[2];
  245.   int i;
  246.  
  247.   printf ("Testing semaphores...");
  248.   sema_init (&sema[0], 0);
  249.   sema_init (&sema[1], 0);
  250.   thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
  251.   for (i = 0; i < 10; i++)
  252.     {
  253.       sema_up (&sema[0]);
  254.       sema_down (&sema[1]);
  255.     }
  256.   printf ("done.\n");
  257. }
  258.  
  259. /* Thread function used by sema_self_test(). */
  260. static void
  261. sema_test_helper (void *sema_)
  262. {
  263.   struct semaphore *sema = sema_;
  264.   int i;
  265.  
  266.   for (i = 0; i < 10; i++)
  267.     {
  268.       sema_down (&sema[0]);
  269.       sema_up (&sema[1]);
  270.     }
  271. }
  272. /* Initializes LOCK.  A lock can be held by at most a single
  273.    thread at any given time.  Our locks are not "recursive", that
  274.    is, it is an error for the thread currently holding a lock to
  275.    try to acquire that lock.
  276.  
  277.    A lock is a specialization of a semaphore with an initial
  278.    value of 1.  The difference between a lock and such a
  279.    semaphore is twofold.  First, a semaphore can have a value
  280.    greater than 1, but a lock can only be owned by a single
  281.    thread at a time.  Second, a semaphore does not have an owner,
  282.    meaning that one thread can "down" the semaphore and then
  283.    another one "up" it, but with a lock the same thread must both
  284.    acquire and release it.  When these restrictions prove
  285.    onerous, it's a good sign that a semaphore should be used,
  286.    instead of a lock. */
  287. void
  288. lock_init (struct lock *lock)
  289. {
  290.   ASSERT (lock != NULL);
  291.  
  292.   lock->holder = NULL;
  293.   sema_init (&lock->semaphore, 1);
  294. }
  295.  
  296. /* Acquires LOCK, sleeping until it becomes available if
  297.    necessary.  The lock must not already be held by the current
  298.    thread.
  299.  
  300.    This function may sleep, so it must not be called within an
  301.    interrupt handler.  This function may be called with
  302.    interrupts disabled, but interrupts will be turned back on if
  303.    we need to sleep. */
  304. void
  305. lock_acquire (struct lock *lock)
  306. {
  307.   ASSERT (lock != NULL);
  308.   ASSERT (!intr_context ());
  309.   ASSERT (!lock_held_by_current_thread (lock));
  310.  
  311.   sema_down (&lock->semaphore);
  312.   lock->holder = thread_current ();
  313. }
  314.  
  315. /* Tries to acquires LOCK and returns true if successful or false
  316.    on failure.  The lock must not already be held by the current
  317.    thread.
  318.  
  319.    This function will not sleep, so it may be called within an
  320.    interrupt handler. */
  321. bool
  322. lock_try_acquire (struct lock *lock)
  323. {
  324.   bool success;
  325.  
  326.   ASSERT (lock != NULL);
  327.   ASSERT (!lock_held_by_current_thread (lock));
  328.  
  329.   success = sema_try_down (&lock->semaphore);
  330.   if (success)
  331.     lock->holder = thread_current ();
  332.   return success;
  333. }
  334.  
  335. /* Releases LOCK, which must be owned by the current thread.
  336.  
  337.    An interrupt handler cannot acquire a lock, so it does not
  338.    make sense to try to release a lock within an interrupt
  339.    handler. */
  340. void
  341. lock_release (struct lock *lock)
  342. {
  343.   ASSERT (lock != NULL);
  344.   ASSERT (lock_held_by_current_thread (lock));
  345.  
  346.   lock->holder = NULL;
  347.   sema_up (&lock->semaphore);
  348. }
  349.  
  350. /* Returns true if the current thread holds LOCK, false
  351.    otherwise.  (Note that testing whether some other thread holds
  352.    a lock would be racy.) */
  353. bool
  354. lock_held_by_current_thread (const struct lock *lock)
  355. {
  356.   ASSERT (lock != NULL);
  357.  
  358.   return lock->holder == thread_current ();
  359. }
  360. /* One semaphore in a list. */
  361. struct semaphore_elem
  362.   {
  363.     struct list_elem elem;              /* List element. */
  364.     struct semaphore semaphore;         /* This semaphore. */
  365.   };
  366.  
  367. /* Initializes condition variable COND.  A condition variable
  368.    allows one piece of code to signal a condition and cooperating
  369.    code to receive the signal and act upon it. */
  370. void
  371. cond_init (struct condition *cond)
  372. {
  373.   ASSERT (cond != NULL);
  374.  
  375.   list_init (&cond->waiters);
  376. }
  377.  
  378. /* Atomically releases LOCK and waits for COND to be signaled by
  379.    some other piece of code.  After COND is signaled, LOCK is
  380.    reacquired before returning.  LOCK must be held before calling
  381.    this function.
  382.  
  383.    The monitor implemented by this function is "Mesa" style, not
  384.    "Hoare" style, that is, sending and receiving a signal are not
  385.    an atomic operation.  Thus, typically the caller must recheck
  386.    the condition after the wait completes and, if necessary, wait
  387.    again.
  388.  
  389.    A given condition variable is associated with only a single
  390.    lock, but one lock may be associated with any number of
  391.    condition variables.  That is, there is a one-to-many mapping
  392.    from locks to condition variables.
  393.  
  394.    This function may sleep, so it must not be called within an
  395.    interrupt handler.  This function may be called with
  396.    interrupts disabled, but interrupts will be turned back on if
  397.    we need to sleep. */
  398. void
  399. cond_wait (struct condition *cond, struct lock *lock)
  400. {
  401.   struct semaphore_elem waiter;
  402.  
  403.   ASSERT (cond != NULL);
  404.   ASSERT (lock != NULL);
  405.   ASSERT (!intr_context ());
  406.   ASSERT (lock_held_by_current_thread (lock));
  407.  
  408.   sema_init (&waiter.semaphore, 0);
  409.   list_push_back (&cond->waiters, &waiter.elem);
  410.   lock_release (lock);
  411.   sema_down (&waiter.semaphore);
  412.   lock_acquire (lock);
  413. }
  414.  
  415. /* If any threads are waiting on COND (protected by LOCK), then
  416.    this function signals one of them to wake up from its wait.
  417.    LOCK must be held before calling this function.
  418.  
  419.    An interrupt handler cannot acquire a lock, so it does not
  420.    make sense to try to signal a condition variable within an
  421.    interrupt handler. */
  422. struct semaphore *
  423. ChooseMaxPriorCondWaiters(struct condition *cond_1)
  424. {
  425.   // printf("OneMore\n");
  426.   struct semaphore_elem *tempMaxSema, *targetSema, *startSema;  
  427.   tempMaxSema=list_entry (list_pop_front (&cond_1->waiters), struct semaphore_elem, elem);
  428.   startSema=tempMaxSema;
  429.   //printf("Start Process=%s\n", startProc->name);
  430.   int maxPrior=list_entry (list_begin(&tempMaxSema->semaphore.waiters), struct thread, elem)->priority;
  431.   if (list_empty(&cond_1->waiters))
  432.   {
  433.     //printf("EMPTY\n");
  434.     return &tempMaxSema->semaphore;
  435.   }
  436.  
  437.   list_push_back (&cond_1->waiters, &tempMaxSema->elem);
  438.  
  439.   targetSema=list_entry (list_pop_front (&cond_1->waiters), struct semaphore_elem, elem);
  440.  
  441.   while (&startSema->semaphore!=&targetSema->semaphore)
  442.   {
  443.     //printf("%s=?%s\n", targetProc->name, startProc->name);
  444.     if (maxPrior<list_entry (list_begin(&targetSema->semaphore.waiters), struct thread, elem)->priority)
  445.     {
  446.       if (tempMaxSema!=startSema)
  447.        list_push_back (&cond_1->waiters, &tempMaxSema->elem);
  448.       tempMaxSema=targetSema;
  449.       maxPrior=list_entry (list_begin(&targetSema->semaphore.waiters), struct thread, elem)->priority;
  450.  
  451.     }
  452.     else
  453.     {
  454.       list_push_back (&cond_1->waiters, &targetSema->elem);
  455.     }
  456.    
  457.     targetSema=list_entry (list_pop_front (&cond_1->waiters), struct semaphore_elem, elem);
  458.    
  459.   }
  460.   if (tempMaxSema!=startSema)
  461.   {
  462.     list_push_back (&cond_1->waiters, &targetSema->elem);
  463.   }
  464.  
  465.   return &tempMaxSema->semaphore;
  466. }
  467. void
  468. cond_signal (struct condition *cond, struct lock *lock UNUSED)
  469. {
  470.   ASSERT (cond != NULL);
  471.   ASSERT (lock != NULL);
  472.   ASSERT (!intr_context ());
  473.   ASSERT (lock_held_by_current_thread (lock));
  474.  
  475.   if (!list_empty (&cond->waiters))
  476.   {
  477.     sema_up(ChooseMaxPriorCondWaiters(cond));
  478.   }
  479.    // sema_up (&list_entry (list_pop_front (&cond->waiters),
  480.     //                      struct semaphore_elem, elem)->semaphore);
  481.  
  482. }
  483.  
  484. /* Wakes up all threads, if any, waiting on COND (protected by
  485.    LOCK).  LOCK must be held before calling this function.
  486.  
  487.    An interrupt handler cannot acquire a lock, so it does not
  488.    make sense to try to signal a condition variable within an
  489.    interrupt handler. */
  490. void
  491. cond_broadcast (struct condition *cond, struct lock *lock)
  492. {
  493.   ASSERT (cond != NULL);
  494.   ASSERT (lock != NULL);
  495.  
  496.   while (!list_empty (&cond->waiters))
  497.     cond_signal (cond, lock);
  498. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top