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

   1 ? threads.1
   2 Index: Make.config
   3 ===================================================================
   4 RCS file: /u/blp/cvs/pintos/src/Make.config,v
   5 retrieving revision 1.2
   6 diff -u -p -u -r1.2 Make.config
   7 --- Make.config 20 Sep 2004 04:27:28 -0000      1.2
   8 +++ Make.config 11 Oct 2004 07:29:34 -0000
   9 @@ -23,7 +23,7 @@ CAT = cat
  10
  11  # Compiler and assembler invocation.
  12  WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -Wsystem-headers
  13 -CFLAGS = -g -O3 -MMD -msoft-float
  14 +CFLAGS = -g -MMD -msoft-float
  15  ASFLAGS = -Wa,--gstabs -MMD
  16
  17  %.o: %.c
  18 Index: devices/timer.c
  19 ===================================================================
  20 RCS file: /u/blp/cvs/pintos/src/devices/timer.c,v
  21 retrieving revision 1.15
  22 diff -u -p -u -r1.15 timer.c
  23 --- devices/timer.c     6 Oct 2004 18:27:00 -0000       1.15
  24 +++ devices/timer.c     11 Oct 2004 07:29:34 -0000
  25 @@ -109,6 +109,8 @@ timer_interrupt (struct intr_frame *args
  26  {
  27    ticks++;
  28    thread_tick ();
  29 +#if 0
  30    if (ticks % TIME_SLICE == 0)
  31      intr_yield_on_return ();
  32 +#endif
  33  }
  34 Index: threads/synch.c
  35 ===================================================================
  36 RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v
  37 retrieving revision 1.14
  38 diff -u -p -u -r1.14 synch.c
  39 --- threads/synch.c     29 Sep 2004 01:04:09 -0000      1.14
  40 +++ threads/synch.c     11 Oct 2004 07:29:34 -0000
  41 @@ -89,10 +89,32 @@ sema_up (struct semaphore *sema)
  42    ASSERT (sema != NULL);
  43
  44    old_level = intr_disable ();
  45 -  if (!list_empty (&sema->waiters))
  46 -    thread_unblock (list_entry (list_pop_front (&sema->waiters),
  47 -                                struct thread, elem));
  48    sema->value++;
  49 +  if (!list_empty (&sema->waiters))
  50 +    {
  51 +      struct thread *max;
  52 +      list_elem *e;
  53 +
  54 +      max = list_entry (list_front (&sema->waiters), struct thread, elem);
  55 +      for (e = list_begin (&sema->waiters);
  56 +           e != list_end (&sema->waiters); e = list_next (e))
  57 +        {
  58 +          struct thread *t = list_entry (e, struct thread, elem);
  59 +          if (t->priority > max->priority)
  60 +            max = t;
  61 +        }
  62 +      list_remove (&max->elem);
  63 +      thread_unblock (max);
  64 +
  65 +      /* Kind of a funny interaction with donation here.
  66 +         We only support donation for locks, and locks turn off
  67 +         interrupts before calling us, so we automatically don't
  68 +         do the yield here, delegating to lock_release(). */
  69 +      if (!intr_context ()
  70 +          && max->priority > thread_get_priority ()
  71 +          && old_level == INTR_ON)
  72 +        thread_yield ();
  73 +    }
  74    intr_set_level (old_level);
  75  }
  76
  77 @@ -166,6 +188,21 @@ lock_init (struct lock *lock, const char
  78    sema_init (&lock->semaphore, 1, name);
  79  }
  80
  81 +static void
  82 +revise_priority (struct thread *t)
  83 +{
  84 +  list_elem *e;
  85 +
  86 +  t->priority = t->normal_priority;
  87 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
  88 +       e = list_next (e))
  89 +    {
  90 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
  91 +      if (donor->priority > t->priority)
  92 +        t->priority = donor->priority;
  93 +    }
  94 +}
  95 +
  96  /* Acquires LOCK, sleeping until it becomes available if
  97     necessary.  The lock must not already be held by the current
  98     thread.
  99 @@ -184,6 +221,17 @@ lock_acquire (struct lock *lock)
 100    ASSERT (!lock_held_by_current_thread (lock));
 101
 102    old_level = intr_disable ();
 103 +
 104 +  if (lock->holder != NULL)
 105 +    {
 106 +      struct thread *donor = thread_current ();
 107 +      donor->want_lock = lock;
 108 +      donor->donee = lock->holder;
 109 +      list_push_back (&lock->holder->donors, &donor->donor_elem);
 110 +      revise_priority (lock->holder);
 111 +      //recurse_donation (&lock->holder);
 112 +    }
 113 +
 114    sema_down (&lock->semaphore);
 115    lock->holder = thread_current ();
 116    intr_set_level (old_level);
 117 @@ -198,13 +246,32 @@ void
 118  lock_release (struct lock *lock)
 119  {
 120    enum intr_level old_level;
 121 +  struct thread *t = thread_current ();
 122 +  list_elem *e, *next;
 123 +  bool did_donate = false;
 124
 125    ASSERT (lock != NULL);
 126    ASSERT (lock_held_by_current_thread (lock));
 127
 128    old_level = intr_disable ();
 129 +  for (e = list_begin (&t->donors); e != list_end (&t->donors);
 130 +       e = next)
 131 +    {
 132 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 133 +      next = list_next (e);
 134 +      if (donor->want_lock == lock)
 135 +        {
 136 +          donor->donee = NULL;
 137 +          list_remove (e);
 138 +          did_donate = true;
 139 +        }
 140 +    }
 141 +  revise_priority (t);
 142    lock->holder = NULL;
 143 +
 144    sema_up (&lock->semaphore);
 145 +  if (did_donate)
 146 +    thread_yield ();
 147    intr_set_level (old_level);
 148  }
 149
 150 Index: threads/test.c
 151 ===================================================================
 152 RCS file: /u/blp/cvs/pintos/src/threads/test.c,v
 153 retrieving revision 1.4
 154 diff -u -p -u -r1.4 test.c
 155 --- threads/test.c      17 Sep 2004 06:52:27 -0000      1.4
 156 +++ threads/test.c      11 Oct 2004 07:29:34 -0000
 157 @@ -1,110 +1,109 @@
 158 +/* Problem 1-3: Priority Scheduling tests.
 159 +
 160 +   Based on a test originally submitted for Stanford's CS 140 in
 161 +   winter 1999 by by Matt Franklin
 162 +   <startled@leland.stanford.edu>, Greg Hutchins
 163 +   <gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
 164 +   Modified by arens. */
 165 +
 166  #include "threads/test.h"
 167  #include <stdio.h>
 168  #include "threads/synch.h"
 169  #include "threads/thread.h"
 170 -#include "devices/timer.h"
 171
 172 -static void test_sleep (int iterations);
 173 +static void test_preempt (void);
 174 +static void test_fifo (void);
 175 +static void test_donate_return (void);
 176
 177  void
 178  test (void)
 179  {
 180 -  test_sleep (1);
 181 -  test_sleep (7);
 182 +  /* Make sure our prority is the default. */
 183 +  ASSERT (thread_get_priority () == PRI_DEFAULT);
 184 +
 185 +  //test_preempt ();
 186 +  //test_fifo ();
 187 +  test_donate_return ();
 188  }
 189  \f
 190 -/* Based on a test originally submitted for Stanford's CS 140 in
 191 -   winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
 192 -   Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
 193 -   <tolik@cs.stanford.edu>. */
 194 -struct sleep_thread_data
 195 -  {
 196 -    int64_t start;              /* Start time. */
 197 -    int duration;               /* Number of ticks to sleep. */
 198 -    int iterations;             /* Number of iterations to run. */
 199 -    int *product;               /* Largest product so far. */
 200 -    struct lock *lock;          /* Lock on access to `product'. */
 201 -    struct semaphore done;      /* Completion semaphore. */
 202 -    tid_t tid;                  /* Thread ID. */
 203 -  };
 204 +static thread_func simple_thread_func;
 205 +static thread_func acquire_thread_func;
 206
 207 -static void sleeper (void *);
 208 +static void
 209 +test_preempt (void)
 210 +{
 211 +  printf ("\n"
 212 +          "Testing priority preemption.\n");
 213 +  thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL);
 214 +  printf ("The high-priority thread should have already completed.\n"
 215 +          "Priority preemption test done.\n");
 216 +}
 217
 218  static void
 219 -test_sleep (int iterations)
 220 +test_fifo (void)
 221  {
 222 -  struct sleep_thread_data threads[5];
 223 -  const int thread_cnt = sizeof threads / sizeof *threads;
 224 -  struct lock lock;
 225 -  int64_t start;
 226 -  int product;
 227    int i;
 228 -
 229 +
 230    printf ("\n"
 231 -          "Testing %d sleeps per thread.\n"
 232 -          "If successful, product of iteration count and\n"
 233 -          "sleep duration will appear in nondescending order.\n",
 234 -          iterations);
 235 -
 236 -  /* Start all the threads. */
 237 -  product = 0;
 238 -  lock_init (&lock, "product");
 239 -  start = timer_ticks ();
 240 -  for (i = 0; i < thread_cnt; i++)
 241 +          "Testing FIFO preemption.\n"
 242 +          "5 threads will iterate 10 times in the same order each time.\n"
 243 +          "If the order varies then there is a bug.\n");
 244 +
 245 +  thread_set_priority (PRI_DEFAULT + 2);
 246 +  for (i = 0; i < 5; i++)
 247      {
 248 -      struct sleep_thread_data *t;
 249        char name[16];
 250 -
 251 -      snprintf (name, sizeof name, "thread %d", i);
 252 -      t = threads + i;
 253 -      t->start = start;
 254 -      t->duration = (i + 1) * 10;
 255 -      t->iterations = iterations;
 256 -      t->product = &product;
 257 -      t->lock = &lock;
 258 -      sema_init (&t->done, 0, name);
 259 -      t->tid = thread_create (name, PRI_DEFAULT, sleeper, t);
 260 -    }
 261 -
 262 -  /* Wait for all the threads to finish. */
 263 -  for (i = 0; i < thread_cnt; i++)
 264 -    {
 265 -#ifdef THREAD_JOIN_IMPLEMENTED
 266 -      thread_join (threads[i].tid);
 267 -#else
 268 -      sema_down (&threads[i].done);
 269 -#endif
 270 +      snprintf (name, sizeof name, "%d", i);
 271 +      thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL);
 272      }
 273 +  thread_set_priority (PRI_DEFAULT);
 274
 275 -  printf ("...done\n");
 276 +  printf ("FIFO preemption test done.\n");
 277  }
 278
 279  static void
 280 -sleeper (void *t_)
 281 +test_donate_return (void)
 282  {
 283 -  struct sleep_thread_data *t = t_;
 284 -  int i;
 285 +  struct lock lock;
 286
 287 -  for (i = 1; i <= t->iterations; i++)
 288 -    {
 289 -      int old_product;
 290 -      int new_product = i * t->duration;
 291 +  printf ("\n"
 292 +          "Testing priority donation.\n"
 293 +          "If the statements printed below are all true, you pass.\n");
 294
 295 -      timer_sleep ((t->start + new_product) - timer_ticks ());
 296 +  lock_init (&lock, "donor");
 297 +  lock_acquire (&lock);
 298 +  thread_create ("acquire1", PRI_DEFAULT + 1, acquire_thread_func, &lock);
 299 +  printf ("This thread should have priority %d.  Actual priority: %d.\n",
 300 +          PRI_DEFAULT + 1, thread_get_priority ());
 301 +  thread_create ("acquire2", PRI_DEFAULT + 2, acquire_thread_func, &lock);
 302 +  printf ("This thread should have priority %d.  Actual priority: %d.\n",
 303 +          PRI_DEFAULT + 2, thread_get_priority ());
 304 +  lock_release (&lock);
 305 +  printf ("acquire2 and acquire1 must already have finished, in that order.\n"
 306 +          "This should be the last line before finishing this test.\n"
 307 +          "Priority donation test done.\n");
 308 +}
 309
 310 -      lock_acquire (t->lock);
 311 -      old_product = *t->product;
 312 -      *t->product = new_product;
 313 -      lock_release (t->lock);
 314 -
 315 -      printf ("%s: duration=%d, iteration=%d, product=%d\n",
 316 -              thread_name (), t->duration, i, new_product);
 317 -
 318 -      if (old_product > new_product)
 319 -        printf ("%s: Out of order sleep completion (%d > %d)!\n",
 320 -                thread_name (), old_product, new_product);
 321 -    }
 322 +static void
 323 +simple_thread_func (void *aux UNUSED)
 324 +{
 325 +  int i;
 326
 327 -  /* Signal completion. */
 328 -  sema_up (&t->done);
 329 +  for (i = 0; i < 5; i++)
 330 +    {
 331 +      printf ("Thread %s iteration %d\n", thread_name (), i);
 332 +      thread_yield ();
 333 +    }
 334 +  printf ("Thread %s done!\n", thread_name ());
 335 +}
 336 +
 337 +static void
 338 +acquire_thread_func (void *lock_)
 339 +{
 340 +  struct lock *lock = lock_;
 341 +
 342 +  lock_acquire (lock);
 343 +  printf ("%s: got the lock\n", thread_name ());
 344 +  lock_release (lock);
 345 +  printf ("%s: done\n", thread_name ());
 346  }
 347 Index: threads/thread.c
 348 ===================================================================
 349 RCS file: /u/blp/cvs/pintos/src/threads/thread.c,v
 350 retrieving revision 1.48
 351 diff -u -p -u -r1.48 thread.c
 352 --- threads/thread.c    9 Oct 2004 18:01:37 -0000       1.48
 353 +++ threads/thread.c    11 Oct 2004 07:29:35 -0000
 354 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri
 355
 356    /* Add to run queue. */
 357    thread_unblock (t);
 358 +  if (priority > thread_get_priority ())
 359 +    thread_yield ();
 360
 361    return tid;
 362  }
 363 @@ -186,6 +188,16 @@ thread_block (void)
 364    schedule ();
 365  }
 366
 367 +static bool
 368 +thread_greater_priority (const list_elem *a_, const list_elem *b_,
 369 +                         void *aux UNUSED)
 370 +{
 371 +  const struct thread *a = list_entry (a_, struct thread, elem);
 372 +  const struct thread *b = list_entry (b_, struct thread, elem);
 373 +
 374 +  return a->priority > b->priority;
 375 +}
 376 +
 377  /* Transitions a blocked thread T to the ready-to-run state.
 378     This is an error if T is not blocked.  (Use thread_yield() to
 379     make the running thread ready.) */
 380 @@ -198,7 +210,7 @@ thread_unblock (struct thread *t)
 381
 382    old_level = intr_disable ();
 383    ASSERT (t->status == THREAD_BLOCKED);
 384 -  list_push_back (&ready_list, &t->elem);
 385 +  list_insert_ordered (&ready_list, &t->elem, thread_greater_priority, NULL);
 386    t->status = THREAD_READY;
 387    intr_set_level (old_level);
 388  }
 389 @@ -266,11 +278,33 @@ thread_yield (void)
 390    ASSERT (!intr_context ());
 391
 392    old_level = intr_disable ();
 393 -  list_push_back (&ready_list, &cur->elem);
 394 +  list_insert_ordered (&ready_list, &cur->elem, thread_greater_priority, NULL);
 395    cur->status = THREAD_READY;
 396    schedule ();
 397    intr_set_level (old_level);
 398  }
 399 +
 400 +void
 401 +thread_set_priority (int priority)
 402 +{
 403 +  struct thread *t = thread_current ();
 404 +  int old_priority = t->priority;
 405 +  t->normal_priority = priority;
 406 +  if (t->normal_priority > t->priority)
 407 +    t->priority = t->normal_priority;
 408 +  if (priority < old_priority)
 409 +    {
 410 +      /* FIXME: if this is still (one of) the highest priority
 411 +         threads then don't yield. */
 412 +      thread_yield ();
 413 +    }
 414 +}
 415 +
 416 +int
 417 +thread_get_priority (void)
 418 +{
 419 +  return thread_current ()->priority;
 420 +}
 421  \f
 422  /* Idle thread.  Executes when no other thread is ready to run. */
 423  static void
 424 @@ -335,8 +369,9 @@ init_thread (struct thread *t, const cha
 425    t->status = THREAD_BLOCKED;
 426    strlcpy (t->name, name, sizeof t->name);
 427    t->stack = (uint8_t *) t + PGSIZE;
 428 -  t->priority = priority;
 429 +  t->priority = t->normal_priority = priority;
 430    t->magic = THREAD_MAGIC;
 431 +  list_init (&t->donors);
 432  }
 433
 434  /* Allocates a SIZE-byte frame at the top of thread T's stack and
 435 Index: threads/thread.h
 436 ===================================================================
 437 RCS file: /u/blp/cvs/pintos/src/threads/thread.h,v
 438 retrieving revision 1.28
 439 diff -u -p -u -r1.28 thread.h
 440 --- threads/thread.h    29 Sep 2004 01:04:20 -0000      1.28
 441 +++ threads/thread.h    11 Oct 2004 07:29:35 -0000
 442 @@ -88,6 +88,13 @@ struct thread
 443      char name[16];                      /* Name (for debugging purposes). */
 444      uint8_t *stack;                     /* Saved stack pointer. */
 445      int priority;                       /* Priority. */
 446 +    int normal_priority;                /* Priority. */
 447 +
 448 +    /* Priority donation. */
 449 +    struct list donors;
 450 +    list_elem donor_elem;
 451 +    struct thread *donee;
 452 +    struct lock *want_lock;
 453
 454      /* Shared between thread.c and synch.c. */
 455      list_elem elem;                     /* List element. */