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

   1 Index: src/threads/synch.c
   2 ===================================================================
   3 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v
   4 retrieving revision 1.15
   5 diff -u -p -u -r1.15 synch.c
   6 --- src/threads/synch.c 31 Dec 2004 21:13:38 -0000      1.15
   7 +++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000
   8 @@ -77,6 +77,18 @@ sema_down (struct semaphore *sema)
   9    intr_set_level (old_level);
  10  }
  11
  12 +/* Returns true if thread A has lower priority than thread B. */
  13 +static bool
  14 +donated_lower_priority (const struct list_elem *a_,
  15 +                        const struct list_elem *b_,
  16 +                        void *aux UNUSED)
  17 +{
  18 +  const struct thread *a = list_entry (a_, struct thread, donor_elem);
  19 +  const struct thread *b = list_entry (b_, struct thread, donor_elem);
  20 +
  21 +  return a->priority < b->priority;
  22 +}
  23 +
  24  /* Up or "V" operation on a semaphore.  Increments SEMA's value
  25     and wakes up one thread of those waiting for SEMA, if any.
  26
  27 @@ -89,10 +100,28 @@ sema_up (struct semaphore *sema)
  28    ASSERT (sema != NULL);
  29
  30    old_level = intr_disable ();
  31 -  if (!list_empty (&sema->waiters))
  32 -    thread_unblock (list_entry (list_pop_front (&sema->waiters),
  33 -                                struct thread, elem));
  34    sema->value++;
  35 +  if (!list_empty (&sema->waiters))
  36 +    {
  37 +      /* Find highest-priority waiting thread. */
  38 +      struct thread *max = list_entry (list_max (&sema->waiters,
  39 +                                                 donated_lower_priority, NULL),
  40 +                                       struct thread, elem);
  41 +
  42 +      /* Remove `max' from wait list and unblock. */
  43 +      list_remove (&max->elem);
  44 +      thread_unblock (max);
  45 +
  46 +      /* Yield to a higher-priority thread, if we're running in a
  47 +         context where it makes sense to do so.
  48 +
  49 +         Kind of a funny interaction with donation here.
  50 +         We only support donation for locks, and locks turn off
  51 +         interrupts before calling us, so we automatically don't
  52 +         do the yield here, delegating to lock_release(). */
  53 +      if (!intr_context () && old_level == INTR_ON)
  54 +        thread_yield_to_higher_priority ();
  55 +    }
  56    intr_set_level (old_level);
  57  }
  58
  59 @@ -184,6 +213,23 @@ lock_acquire (struct lock *lock)
  60    ASSERT (!lock_held_by_current_thread (lock));
  61
  62    old_level = intr_disable ();
  63 +
  64 +  if (lock->holder != NULL)
  65 +    {
  66 +      /* Donate our priority to the thread holding the lock.
  67 +         First, update the data structures. */
  68 +      struct thread *donor = thread_current ();
  69 +      donor->want_lock = lock;
  70 +      donor->donee = lock->holder;
  71 +      list_push_back (&lock->holder->donors, &donor->donor_elem);
  72 +
  73 +      /* Now implement the priority donation itself
  74 +         by recomputing the donee's priority
  75 +         and cascading the donation as far as necessary. */
  76 +      while (donor->donee != NULL && thread_recompute_priority (donor->donee))
  77 +        donor = donor->donee;
  78 +    }
  79 +
  80    sema_down (&lock->semaphore);
  81    lock->holder = thread_current ();
  82    intr_set_level (old_level);
  83 @@ -198,13 +244,38 @@ void
  84  lock_release (struct lock *lock)
  85  {
  86    enum intr_level old_level;
  87 +  struct thread *t = thread_current ();
  88 +  struct list_elem *e;
  89
  90    ASSERT (lock != NULL);
  91    ASSERT (lock_held_by_current_thread (lock));
  92
  93    old_level = intr_disable ();
  94 +
  95 +  /* Remove donations from threads that want the lock we're
  96 +     releasing. */
  97 +  for (e = list_begin (&t->donors); e != list_end (&t->donors); )
  98 +    {
  99 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 100 +      if (donor->want_lock == lock)
 101 +        {
 102 +          donor->donee = NULL;
 103 +          e = list_remove (e);
 104 +        }
 105 +      else
 106 +        e = list_next (e);
 107 +    }
 108 +
 109 +  /* Release lock. */
 110    lock->holder = NULL;
 111    sema_up (&lock->semaphore);
 112 +
 113 +  /* Recompute our priority based on our remaining donations,
 114 +     then yield to a higher-priority ready thread if one now
 115 +     exists. */
 116 +  thread_recompute_priority (t);
 117 +  thread_yield_to_higher_priority ();
 118 +
 119    intr_set_level (old_level);
 120  }
 121
 122 Index: src/threads/thread.c
 123 ===================================================================
 124 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v
 125 retrieving revision 1.48
 126 diff -u -p -u -r1.48 thread.c
 127 --- src/threads/thread.c        9 Oct 2004 18:01:37 -0000       1.48
 128 +++ src/threads/thread.c        31 Dec 2004 22:31:03 -0000
 129 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
 130
 131    /* Add to run queue. */
 132    thread_unblock (t);
 133 +  if (priority > thread_get_priority ())
 134 +    thread_yield ();
 135
 136    return tid;
 137  }
 138 @@ -186,6 +188,19 @@ thread_block (void)
 139    schedule ();
 140  }
 141
 142 +/* Returns true if A has higher priority than B,
 143 +   within a list of threads. */
 144 +static bool
 145 +thread_higher_priority (const struct list_elem *a_,
 146 +                        const struct list_elem *b_,
 147 +                        void *aux UNUSED)
 148 +{
 149 +  const struct thread *a = list_entry (a_, struct thread, elem);
 150 +  const struct thread *b = list_entry (b_, struct thread, elem);
 151 +
 152 +  return a->priority > b->priority;
 153 +}
 154 +
 155  /* Transitions a blocked thread T to the ready-to-run state.
 156     This is an error if T is not blocked.  (Use thread_yield() to
 157     make the running thread ready.) */
 158 @@ -198,7 +212,7 @@ thread_unblock (struct thread *t)
 159
 160    old_level = intr_disable ();
 161    ASSERT (t->status == THREAD_BLOCKED);
 162 -  list_push_back (&ready_list, &t->elem);
 163 +  list_insert_ordered (&ready_list, &t->elem, thread_higher_priority, NULL);
 164    t->status = THREAD_READY;
 165    intr_set_level (old_level);
 166  }
 167 @@ -266,8 +280,8 @@ thread_yield (void)
 168    ASSERT (!intr_context ());
 169
 170    old_level = intr_disable ();
 171 -  list_push_back (&ready_list, &cur->elem);
 172 +  list_insert_ordered (&ready_list, &cur->elem, thread_higher_priority, NULL);
 173    cur->status = THREAD_READY;
 174    schedule ();
 175    intr_set_level (old_level);
 176  }
 177 @@ -274,19 +288,75 @@
 178  {
 179  }
 180
 181 -/* Sets the current thread's priority to NEW_PRIORITY. */
 182 -void
 183 -thread_set_priority (int new_priority)
 184 -{
 185 -  thread_current ()->priority = new_priority;
 186 -}
 187 -
 188 -/* Returns the current thread's priority. */
 189 -int
 190 -thread_get_priority (void)
 191 -{
 192 -  return thread_current ()->priority;
 193 -}
 194 +
 195 +/* Sets the current thread's priority to PRIORITY. */
 196 +void
 197 +thread_set_priority (int priority)
 198 +{
 199 +  struct thread *t = thread_current ();
 200 +  enum intr_level old_level;
 201 +
 202 +  t->normal_priority = priority;
 203 +
 204 +  old_level = intr_disable ();
 205 +  while (thread_recompute_priority (t) && t->donee != NULL)
 206 +    t = t->donee;
 207 +  thread_yield_to_higher_priority ();
 208 +  intr_set_level (old_level);
 209 +}
 210 +
 211 +/* Returns the current thread's priority. */
 212 +int
 213 +thread_get_priority (void)
 214 +{
 215 +  return thread_current ()->priority;
 216 +}
 217 +
 218 +/* Returns true if thread A has lower priority than thread B,
 219 +   within a list of donors. */
 220 +static bool
 221 +donated_lower_priority (const struct list_elem *a_,
 222 +                        const struct list_elem *b_,
 223 +                        void *aux UNUSED)
 224 +{
 225 +  const struct thread *a = list_entry (a_, struct thread, donor_elem);
 226 +  const struct thread *b = list_entry (b_, struct thread, donor_elem);
 227 +
 228 +  return a->priority < b->priority;
 229 +}
 230 +
 231 +/* Recomputes T's priority in terms of its normal priority and
 232 +   its donors' priorities, if any.
 233 +   Returns true if T's new priority is higher than its old
 234 +   priority, false otherwise. */
 235 +bool
 236 +thread_recompute_priority (struct thread *t)
 237 +{
 238 +  int old = t->priority;
 239 +  int donation = 0;
 240 +  if (!list_empty (&t->donors))
 241 +    donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
 242 +                           struct thread, donor_elem)->priority;
 243 +  t->priority = donation > t->normal_priority ? donation : t->normal_priority;
 244 +  return t->priority > old;
 245 +}
 246 +
 247 +/* If the ready list contains a thread with a higher priority,
 248 +   yields to it. */
 249 +void
 250 +thread_yield_to_higher_priority (void)
 251 +{
 252 +  enum intr_level old_level = intr_disable ();
 253 +  if (!list_empty (&ready_list))
 254 +    {
 255 +      struct thread *cur = thread_current ();
 256 +      struct thread *max = list_entry (list_front (&ready_list),
 257 +                                       struct thread, elem);
 258 +      if (max->priority > cur->priority)
 259 +        thread_yield ();
 260 +    }
 261 +  intr_set_level (old_level);
 262 +}
 263  \f
 264  /* Idle thread.  Executes when no other thread is ready to run. */
 265  static void
 266 @@ -335,8 +417,9 @@ init_thread (struct thread *t, const cha
 267    t->status = THREAD_BLOCKED;
 268    strlcpy (t->name, name, sizeof t->name);
 269    t->stack = (uint8_t *) t + PGSIZE;
 270 -  t->priority = priority;
 271 +  t->priority = t->normal_priority = priority;
 272    t->magic = THREAD_MAGIC;
 273 +  list_init (&t->donors);
 274  }
 275
 276  /* Allocates a SIZE-byte frame at the top of thread T's stack and
 277 Index: src/threads/thread.h
 278 ===================================================================
 279 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v
 280 retrieving revision 1.28
 281 diff -u -p -u -r1.28 thread.h
 282 --- src/threads/thread.h        29 Sep 2004 01:04:20 -0000      1.28
 283 +++ src/threads/thread.h        31 Dec 2004 22:31:03 -0000
 284 @@ -87,7 +87,14 @@ struct thread
 285      enum thread_status status;          /* Thread state. */
 286      char name[16];                      /* Name (for debugging purposes). */
 287      uint8_t *stack;                     /* Saved stack pointer. */
 288 -    int priority;                       /* Priority. */
 289 +
 290 +    /* Thread priority. */
 291 +    int priority;                       /* Priority, including donations. */
 292 +    int normal_priority;                /* Priority, without donations. */
 293 +    struct list donors;                 /* Threads donating priority to us. */
 294 +    struct list_elem donor_elem;        /* Element in donors list. */
 295 +    struct thread *donee;               /* Thread we're donating to. */
 296 +    struct lock *want_lock;             /* Lock we're waiting to acquire. */
 297
 298      /* Shared between thread.c and synch.c. */
 299      struct list_elem elem;              /* List element. */
 300 @@ -118,6 +125,8 @@ const char *thread_name (void);
 301
 302  void thread_exit (void) NO_RETURN;
 303  void thread_yield (void);
 304 +void thread_yield_to_higher_priority (void);
 305 +bool thread_recompute_priority (struct thread *);
 306
 307  void thread_set_priority (int);
 308  int thread_get_priority (void);