pintos-os.org Git - pintos-anon/blob - solutions/p1-3.patch

   1 Index: threads/synch.c
   2 ===================================================================
   3 RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v
   4 retrieving revision 1.14
   5 diff -u -p -u -r1.14 synch.c
   6 --- threads/synch.c     29 Sep 2004 01:04:09 -0000      1.14
   7 +++ threads/synch.c     11 Oct 2004 07:29:34 -0000
   8 @@ -89,10 +89,32 @@ sema_up (struct semaphore *sema)
   9    ASSERT (sema != NULL);
  10
  11    old_level = intr_disable ();
  12 -  if (!list_empty (&sema->waiters))
  13 -    thread_unblock (list_entry (list_pop_front (&sema->waiters),
  14 -                                struct thread, elem));
  15    sema->value++;
  16 +  if (!list_empty (&sema->waiters))
  17 +    {
  18 +      struct thread *max;
  19 +      list_elem *e;
  20 +
  21 +      max = list_entry (list_front (&sema->waiters), struct thread, elem);
  22 +      for (e = list_begin (&sema->waiters);
  23 +           e != list_end (&sema->waiters); e = list_next (e))
  24 +        {
  25 +          struct thread *t = list_entry (e, struct thread, elem);
  26 +          if (t->priority > max->priority)
  27 +            max = t;
  28 +        }
  29 +      list_remove (&max->elem);
  30 +      thread_unblock (max);
  31 +
  32 +      /* Kind of a funny interaction with donation here.
  33 +         We only support donation for locks, and locks turn off
  34 +         interrupts before calling us, so we automatically don't
  35 +         do the yield here, delegating to lock_release(). */
  36 +      if (!intr_context ()
  37 +          && max->priority > thread_get_priority ()
  38 +          && old_level == INTR_ON)
  39 +        thread_yield ();
  40 +    }
  41    intr_set_level (old_level);
  42  }
  43
  44 @@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char
  45    sema_init (&lock->semaphore, 1, name);
  46  }
  47
  48 +static void
  49 +revise_priority (struct thread *t)
  50 +{
  51 +  list_elem *e;
  52 +
  53 +  t->priority = t->normal_priority;
  54 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
  55 +       e = list_next (e))
  56 +    {
  57 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
  58 +      if (donor->priority > t->priority)
  59 +        t->priority = donor->priority;
  60 +    }
  61 +}
  62 +
  63  /* Acquires LOCK, sleeping until it becomes available if
  64     necessary.  The lock must not already be held by the current
  65     thread.
  66 @@ -184,6 +221,17 @@ lock_acquire (struct lock *lock)
  67    ASSERT (!lock_held_by_current_thread (lock));
  68
  69    old_level = intr_disable ();
  70 +
  71 +  if (lock->holder != NULL)
  72 +    {
  73 +      struct thread *donor = thread_current ();
  74 +      donor->want_lock = lock;
  75 +      donor->donee = lock->holder;
  76 +      list_push_back (&lock->holder->donors, &donor->donor_elem);
  77 +      revise_priority (lock->holder);
  78 +      //recurse_donation (&lock->holder);
  79 +    }
  80 +
  81    sema_down (&lock->semaphore);
  82    lock->holder = thread_current ();
  83    intr_set_level (old_level);
  84 @@ -198,13 +246,32 @@ void
  85  lock_release (struct lock *lock)
  86  {
  87    enum intr_level old_level;
  88 +  struct thread *t = thread_current ();
  89 +  list_elem *e, *next;
  90 +  bool did_donate = false;
  91
  92    ASSERT (lock != NULL);
  93    ASSERT (lock_held_by_current_thread (lock));
  94
  95    old_level = intr_disable ();
  96 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
  97 +       e = next)
  98 +    {
  99 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 100 +      next = list_next (e);
 101 +      if (donor->want_lock == lock)
 102 +        {
 103 +          donor->donee = NULL;
 104 +          list_remove (e);
 105 +          did_donate = true;
 106 +        }
 107 +    }
 108 +  revise_priority (t);
 109    lock->holder = NULL;
 110 +
 111    sema_up (&lock->semaphore);
 112 +  if (did_donate)
 113 +    thread_yield ();
 114    intr_set_level (old_level);
 115  }
 116
 117 diff -u -p -u -p -r1.48 thread.c
 118 --- threads/thread.c    9 Oct 2004 18:01:37 -0000       1.48
 119 +++ threads/thread.c    14 Oct 2004 05:21:08 -0000
 120 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
 121
 122    /* Add to run queue. */
 123    thread_unblock (t);
 124 +  if (priority > thread_get_priority ())
 125 +    thread_yield ();
 126
 127    return tid;
 128  }
 129 @@ -186,6 +188,16 @@ thread_block (void)
 130    schedule ();
 131  }
 132
 133 +static bool
 134 +thread_greater_priority (const list_elem *a_, const list_elem *b_,
 135 +                         void *aux UNUSED)
 136 +{
 137 +  const struct thread *a = list_entry (a_, struct thread, elem);
 138 +  const struct thread *b = list_entry (b_, struct thread, elem);
 139 +
 140 +  return a->priority > b->priority;
 141 +}
 142 +
 143  /* Transitions a blocked thread T to the ready-to-run state.
 144     This is an error if T is not blocked.  (Use thread_yield() to
 145     make the running thread ready.) */
 146 @@ -198,7 +210,7 @@ thread_unblock (struct thread *t)
 147
 148    old_level = intr_disable ();
 149    ASSERT (t->status == THREAD_BLOCKED);
 150 -  list_push_back (&ready_list, &t->elem);
 151 +  list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL);
 152    t->status = THREAD_READY;
 153    intr_set_level (old_level);
 154  }
 155 @@ -266,11 +278,44 @@ thread_yield (void)
 156    ASSERT (!intr_context ());
 157
 158    old_level = intr_disable ();
 159 -  list_push_back (&ready_list, &cur->elem);
 160 +  list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL);
 161    cur->status = THREAD_READY;
 162    schedule ();
 163    intr_set_level (old_level);
 164  }
 165 +
 166 +void
 167 +thread_set_priority (int priority)
 168 +{
 169 +  struct thread *t = thread_current ();
 170 +  int old_priority, new_priority;
 171 +  list_elem *e;
 172 +
 173 +  old_priority = t->priority;
 174 +  new_priority = t->normal_priority = priority;
 175 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
 176 +       e = list_next (e))
 177 +    {
 178 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 179 +      if (donor->priority > t->priority)
 180 +        new_priority = donor->priority;
 181 +    }
 182 +
 183 +  t->priority = new_priority;
 184 +
 185 +  if (new_priority < old_priority)
 186 +    {
 187 +      /* FIXME: if this is still (one of) the highest priority
 188 +         threads then don't yield. */
 189 +      thread_yield ();
 190 +    }
 191 +}
 192 +
 193 +int
 194 +thread_get_priority (void)
 195 +{
 196 +  return thread_current ()->priority;
 197 +}
 198  \f
 199  /* Idle thread.  Executes when no other thread is ready to run. */
 200  static void
 201 @@ -335,8 +380,9 @@ init_thread (struct thread *t, const cha
 202    t->status = THREAD_BLOCKED;
 203    strlcpy (t->name, name, sizeof t->name);
 204    t->stack = (uint8_t *) t + PGSIZE;
 205 -  t->priority = priority;
 206 +  t->priority = t->normal_priority = priority;
 207    t->magic = THREAD_MAGIC;
 208 +  list_init (&t->donors);
 209  }
 210
 211  /* Allocates a SIZE-byte frame at the top of thread T's stack and
 212 Index: threads/thread.h
 213 ===================================================================
 214 RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v
 215 retrieving revision 1.28
 216 diff -u -p -u -r1.28 thread.h
 217 --- threads/thread.h    29 Sep 2004 01:04:20 -0000      1.28
 218 +++ threads/thread.h    11 Oct 2004 07:29:35 -0000
 219 @@ -88,6 +88,13 @@ struct thread
 220      char name[16];                      /* Name (for debugging purposes). */
 221      uint8_t *stack;                     /* Saved stack pointer. */
 222      int priority;                       /* Priority. */
 223 +    int normal_priority;                /* Priority. */
 224 +
 225 +    /* Priority donation. */
 226 +    struct list donors;
 227 +    list_elem donor_elem;
 228 +    struct thread *donee;
 229 +    struct lock *want_lock;
 230
 231      /* Shared between thread.c and synch.c. */
 232      list_elem elem;                     /* List element. */