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

   1 diff -Nur ../../src/devices/timer.c src/devices/timer.c
   2 --- ../../src/devices/timer.c   2008-08-27 08:04:38.000000000 -0400
   3 +++ src/devices/timer.c 2008-08-27 12:42:33.000000000 -0400
   4 @@ -24,6 +24,9 @@
   5     Initialized by timer_calibrate(). */
   6  static unsigned loops_per_tick;
   7
   8 +/* Threads waiting in timer_sleep(). */
   9 +static struct list wait_list;
  10 +
  11  static intr_handler_func timer_interrupt;
  12  static bool too_many_loops (unsigned loops);
  13  static void busy_wait (int64_t loops);
  14 @@ -45,6 +48,8 @@
  15    outb (0x40, count >> 8);
  16
  17    intr_register_ext (0x20, timer_interrupt, "8254 Timer");
  18 +
  19 +  list_init (&wait_list);
  20  }
  21
  22  /* Calibrates loops_per_tick, used to implement brief delays. */
  23 @@ -93,16 +98,37 @@
  24    return timer_ticks () - then;
  25  }
  26
  27 +/* Compares two threads based on their wake-up times. */
  28 +static bool
  29 +compare_threads_by_wakeup_time (const struct list_elem *a_,
  30 +                                const struct list_elem *b_,
  31 +                                void *aux UNUSED)
  32 +{
  33 +  const struct thread *a = list_entry (a_, struct thread, timer_elem);
  34 +  const struct thread *b = list_entry (b_, struct thread, timer_elem);
  35 +
  36 +  return a->wakeup_time < b->wakeup_time;
  37 +}
  38 +
  39  /* Sleeps for approximately TICKS timer ticks.  Interrupts must
  40     be turned on. */
  41  void
  42  timer_sleep (int64_t ticks)
  43  {
  44 -  int64_t start = timer_ticks ();
  45 +  struct thread *t = thread_current ();
  46 +
  47 +  /* Schedule our wake-up time. */
  48 +  t->wakeup_time = timer_ticks () + ticks;
  49
  50 +  /* Atomically insert the current thread into the wait list. */
  51    ASSERT (intr_get_level () == INTR_ON);
  52 -  while (timer_elapsed (start) < ticks)
  53 -    thread_yield ();
  54 +  intr_disable ();
  55 +  list_insert_ordered (&wait_list, &t->timer_elem,
  56 +                       compare_threads_by_wakeup_time, NULL);
  57 +  intr_enable ();
  58 +
  59 +  /* Wait. */
  60 +  sema_down (&t->timer_sema);
  61  }
  62
  63  /* Sleeps for approximately MS milliseconds.  Interrupts must be
  64 @@ -181,6 +207,17 @@
  65  {
  66    ticks++;
  67    thread_tick ();
  68 +
  69 +  while (!list_empty (&wait_list))
  70 +    {
  71 +      struct thread *t = list_entry (list_front (&wait_list),
  72 +                                     struct thread, timer_elem);
  73 +      if (ticks < t->wakeup_time)
  74 +        break;
  75 +      sema_up (&t->timer_sema);
  76 +      thread_yield_to_higher_priority ();
  77 +      list_pop_front (&wait_list);
  78 +    }
  79  }
  80
  81  /* Returns true if LOOPS iterations waits for more than one timer
  82 diff -Nur ../../src/tests/Make.tests src/tests/Make.tests
  83 --- ../../src/tests/Make.tests  2007-01-11 22:07:10.000000000 -0500
  84 +++ src/tests/Make.tests        2008-08-27 13:00:45.000000000 -0400
  85 @@ -51,6 +51,10 @@
  86  # Prevent an environment variable VERBOSE from surprising us.
  87  VERBOSE =
  88
  89 +# Append utils directory to fall back to pintos script in source tree
  90 +# unless user places a different script in their path.
  91 +export PATH := $(PATH):$(SRCDIR)/utils
  92 +
  93  TESTCMD = pintos -v -k -T $(TIMEOUT)
  94  TESTCMD += $(SIMULATOR)
  95  TESTCMD += $(PINTOSOPTS)
  96 diff -Nur ../../src/threads/fixed-point.h src/threads/fixed-point.h
  97 --- ../../src/threads/fixed-point.h     1969-12-31 19:00:00.000000000 -0500
  98 +++ src/threads/fixed-point.h   2008-08-27 12:42:33.000000000 -0400
  99 @@ -0,0 +1,120 @@
 100 +#ifndef THREADS_FIXED_POINT_H
 101 +#define THREADS_FIXED_POINT_H
 102 +
 103 +#include <debug.h>
 104 +
 105 +/* Parameters. */
 106 +#define FIX_BITS 32             /* Total bits per fixed-point number. */
 107 +#define FIX_P 16                /* Number of integer bits. */
 108 +#define FIX_Q 16                /* Number of fractional bits. */
 109 +#define FIX_F (1 << FIX_Q)      /* pow(2, FIX_Q). */
 110 +
 111 +#define FIX_MIN_INT (-FIX_MAX_INT)      /* Smallest representable integer. */
 112 +#define FIX_MAX_INT ((1 << FIX_P) - 1)  /* Largest representable integer. */
 113 +
 114 +/* A fixed-point number. */
 115 +typedef struct
 116 +  {
 117 +    int f;
 118 +  }
 119 +fixed_point_t;
 120 +
 121 +/* Returns a fixed-point number with F as its internal value. */
 122 +static inline fixed_point_t
 123 +__mk_fix (int f)
 124 +{
 125 +  fixed_point_t x;
 126 +  x.f = f;
 127 +  return x;
 128 +}
 129 +
 130 +/* Returns fixed-point number corresponding to integer N. */
 131 +static inline fixed_point_t
 132 +fix_int (int n)
 133 +{
 134 +  ASSERT (n >= FIX_MIN_INT && n <= FIX_MAX_INT);
 135 +  return __mk_fix (n * FIX_F);
 136 +}
 137 +
 138 +/* Returns fixed-point number corresponding to N divided by D. */
 139 +static inline fixed_point_t
 140 +fix_frac (int n, int d)
 141 +{
 142 +  ASSERT (d != 0);
 143 +  ASSERT (n / d >= FIX_MIN_INT && n / d <= FIX_MAX_INT);
 144 +  return __mk_fix ((long long) n * FIX_F / d);
 145 +}
 146 +
 147 +/* Returns X rounded to the nearest integer. */
 148 +static inline int
 149 +fix_round (fixed_point_t x)
 150 +{
 151 +  return (x.f + FIX_F / 2) / FIX_F;
 152 +}
 153 +
 154 +/* Returns X truncated down to the nearest integer. */
 155 +static inline int
 156 +fix_trunc (fixed_point_t x)
 157 +{
 158 +  return x.f / FIX_F;
 159 +}
 160 +
 161 +/* Returns X + Y. */
 162 +static inline fixed_point_t
 163 +fix_add (fixed_point_t x, fixed_point_t y)
 164 +{
 165 +  return __mk_fix (x.f + y.f);
 166 +}
 167 +
 168 +/* Returns X - Y. */
 169 +static inline fixed_point_t
 170 +fix_sub (fixed_point_t x, fixed_point_t y)
 171 +{
 172 +  return __mk_fix (x.f - y.f);
 173 +}
 174 +
 175 +/* Returns X * Y. */
 176 +static inline fixed_point_t
 177 +fix_mul (fixed_point_t x, fixed_point_t y)
 178 +{
 179 +  return __mk_fix ((long long) x.f * y.f / FIX_F);
 180 +}
 181 +
 182 +/* Returns X * N. */
 183 +static inline fixed_point_t
 184 +fix_scale (fixed_point_t x, int n)
 185 +{
 186 +  ASSERT (n >= 0);
 187 +  return __mk_fix (x.f * n);
 188 +}
 189 +
 190 +/* Returns X / Y. */
 191 +static inline fixed_point_t
 192 +fix_div (fixed_point_t x, fixed_point_t y)
 193 +{
 194 +  return __mk_fix ((long long) x.f * FIX_F / y.f);
 195 +}
 196 +
 197 +/* Returns X / N. */
 198 +static inline fixed_point_t
 199 +fix_unscale (fixed_point_t x, int n)
 200 +{
 201 +  ASSERT (n > 0);
 202 +  return __mk_fix (x.f / n);
 203 +}
 204 +
 205 +/* Returns 1 / X. */
 206 +static inline fixed_point_t
 207 +fix_inv (fixed_point_t x)
 208 +{
 209 +  return fix_div (fix_int (1), x);
 210 +}
 211 +
 212 +/* Returns -1 if X < Y, 0 if X == Y, 1 if X > Y. */
 213 +static inline int
 214 +fix_compare (fixed_point_t x, fixed_point_t y)
 215 +{
 216 +  return x.f < y.f ? -1 : x.f > y.f;
 217 +}
 218 +
 219 +#endif /* threads/fixed-point.h */
 220 diff -Nur ../../src/threads/synch.c src/threads/synch.c
 221 --- ../../src/threads/synch.c   2006-07-20 22:05:37.000000000 -0400
 222 +++ src/threads/synch.c 2008-08-27 12:42:33.000000000 -0400
 223 @@ -113,10 +113,28 @@
 224    ASSERT (sema != NULL);
 225
 226    old_level = intr_disable ();
 227 -  if (!list_empty (&sema->waiters))
 228 -    thread_unblock (list_entry (list_pop_front (&sema->waiters),
 229 -                                struct thread, elem));
 230    sema->value++;
 231 +  if (!list_empty (&sema->waiters))
 232 +    {
 233 +      /* Find highest-priority waiting thread. */
 234 +      struct thread *max = list_entry (list_max (&sema->waiters,
 235 +                                                 thread_lower_priority, NULL),
 236 +                                       struct thread, elem);
 237 +
 238 +      /* Remove `max' from wait list and unblock. */
 239 +      list_remove (&max->elem);
 240 +      thread_unblock (max);
 241 +
 242 +      /* Yield to a higher-priority thread, if we're running in a
 243 +         context where it makes sense to do so.
 244 +
 245 +         Kind of a funny interaction with donation here.
 246 +         We only support donation for locks, and locks turn off
 247 +         interrupts before calling us, so we automatically don't
 248 +         do the yield here, delegating to lock_release(). */
 249 +      if (!intr_context () && old_level == INTR_ON)
 250 +        thread_yield_to_higher_priority ();
 251 +    }
 252    intr_set_level (old_level);
 253  }
 254
 255 @@ -192,12 +210,33 @@
 256  void
 257  lock_acquire (struct lock *lock)
 258  {
 259 +  enum intr_level old_level;
 260 +
 261    ASSERT (lock != NULL);
 262    ASSERT (!intr_context ());
 263    ASSERT (!lock_held_by_current_thread (lock));
 264
 265 +  old_level = intr_disable ();
 266 +
 267 +  if (lock->holder != NULL)
 268 +    {
 269 +      /* Donate our priority to the thread holding the lock.
 270 +         First, update the data structures. */
 271 +      struct thread *donor = thread_current ();
 272 +      donor->want_lock = lock;
 273 +      donor->donee = lock->holder;
 274 +      list_push_back (&lock->holder->donors, &donor->donor_elem);
 275 +
 276 +      /* Now implement the priority donation itself
 277 +         by recomputing the donee's priority
 278 +         and cascading the donation as far as necessary. */
 279 +      if (donor->donee != NULL)
 280 +        thread_recompute_priority (donor->donee);
 281 +    }
 282 +
 283    sema_down (&lock->semaphore);
 284    lock->holder = thread_current ();
 285 +  intr_set_level (old_level);
 286  }
 287
 288  /* Tries to acquires LOCK and returns true if successful or false
 289 @@ -228,11 +267,39 @@
 290  void
 291  lock_release (struct lock *lock)
 292  {
 293 +  enum intr_level old_level;
 294 +  struct thread *t = thread_current ();
 295 +  struct list_elem *e;
 296 +
 297    ASSERT (lock != NULL);
 298    ASSERT (lock_held_by_current_thread (lock));
 299
 300 +  old_level = intr_disable ();
 301 +
 302 +  /* Return donations to threads that want this lock. */
 303 +  for (e = list_begin (&t->donors); e != list_end (&t->donors); )
 304 +    {
 305 +      struct thread *donor = list_entry (e, struct thread, donor_elem);
 306 +      if (donor->want_lock == lock)
 307 +        {
 308 +          donor->donee = NULL;
 309 +          e = list_remove (e);
 310 +        }
 311 +      else
 312 +        e = list_next (e);
 313 +    }
 314 +
 315 +  /* Release lock. */
 316    lock->holder = NULL;
 317    sema_up (&lock->semaphore);
 318 +
 319 +  /* Recompute our priority based on our remaining donations,
 320 +     then yield to a higher-priority ready thread if one now
 321 +     exists. */
 322 +  thread_recompute_priority (t);
 323 +  thread_yield_to_higher_priority ();
 324 +
 325 +  intr_set_level (old_level);
 326  }
 327
 328  /* Returns true if the current thread holds LOCK, false
 329 @@ -251,6 +318,7 @@
 330    {
 331      struct list_elem elem;              /* List element. */
 332      struct semaphore semaphore;         /* This semaphore. */
 333 +    struct thread *thread;              /* Thread. */
 334    };
 335
 336  /* Initializes condition variable COND.  A condition variable
 337 @@ -295,12 +363,26 @@
 338    ASSERT (lock_held_by_current_thread (lock));
 339
 340    sema_init (&waiter.semaphore, 0);
 341 +  waiter.thread = thread_current ();
 342    list_push_back (&cond->waiters, &waiter.elem);
 343    lock_release (lock);
 344    sema_down (&waiter.semaphore);
 345    lock_acquire (lock);
 346  }
 347
 348 +static bool
 349 +semaphore_elem_lower_priority (const struct list_elem *a_,
 350 +                               const struct list_elem *b_,
 351 +                               void *aux UNUSED)
 352 +{
 353 +  const struct semaphore_elem *a
 354 +    = list_entry (a_, struct semaphore_elem, elem);
 355 +  const struct semaphore_elem *b
 356 +    = list_entry (b_, struct semaphore_elem, elem);
 357 +
 358 +  return a->thread->priority < b->thread->priority;
 359 +}
 360 +
 361  /* If any threads are waiting on COND (protected by LOCK), then
 362     this function signals one of them to wake up from its wait.
 363     LOCK must be held before calling this function.
 364 @@ -317,8 +399,12 @@
 365    ASSERT (lock_held_by_current_thread (lock));
 366
 367    if (!list_empty (&cond->waiters))
 368 -    sema_up (&list_entry (list_pop_front (&cond->waiters),
 369 -                          struct semaphore_elem, elem)->semaphore);
 370 +    {
 371 +      struct list_elem *max
 372 +        = list_max (&cond->waiters, semaphore_elem_lower_priority, NULL);
 373 +      list_remove (max);
 374 +      sema_up (&list_entry (max, struct semaphore_elem, elem)->semaphore);
 375 +    }
 376  }
 377
 378  /* Wakes up all threads, if any, waiting on COND (protected by
 379 diff -Nur ../../src/threads/thread.c src/threads/thread.c
 380 --- ../../src/threads/thread.c  2008-08-27 13:06:01.000000000 -0400
 381 +++ src/threads/thread.c        2008-08-27 13:14:12.000000000 -0400
 382 @@ -5,11 +5,13 @@
 383  #include <stdio.h>
 384  #include <string.h>
 385  #include "threads/flags.h"
 386 +#include "threads/init.h"
 387  #include "threads/interrupt.h"
 388  #include "threads/intr-stubs.h"
 389  #include "threads/palloc.h"
 390  #include "threads/switch.h"
 391  #include "threads/synch.h"
 392 +#include "devices/timer.h"
 393  #include "threads/vaddr.h"
 394  #ifdef USERPROG
 395  #include "userprog/process.h"
 396 @@ -53,6 +55,7 @@
 397  /* Scheduling. */
 398  #define TIME_SLICE 4            /* # of timer ticks to give each thread. */
 399  static unsigned thread_ticks;   /* # of timer ticks since last yield. */
 400 +static fixed_point_t load_avg;  /* Load average. */
 401
 402  /* If false (default), use round-robin scheduler.
 403     If true, use multi-level feedback queue scheduler.
 404 @@ -92,6 +95,7 @@
 405    lock_init (&tid_lock);
 406    list_init (&ready_list);
 407    list_init (&all_list);
 408 +  load_avg = fix_int (0);
 409
 410    /* Set up a thread structure for the running thread. */
 411    initial_thread = running_thread ();
 412 @@ -117,6 +121,18 @@
 413    sema_down (&idle_started);
 414  }
 415
 416 +/* Adjust recent CPU of a thread based on load factor
 417 +   and recompute its priority. */
 418 +static void
 419 +adjust_recent_cpu (struct thread *t, void *aux)
 420 +{
 421 +  fixed_point_t load_factor = *(fixed_point_t *)aux;
 422 +
 423 +  t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
 424 +                           fix_int (t->nice));
 425 +  thread_recompute_priority (t);
 426 +}
 427 +
 428  /* Called by the timer interrupt handler at each timer tick.
 429     Thus, this function runs in an external interrupt context. */
 430  void
 431 @@ -134,9 +150,41 @@
 432    else
 433      kernel_ticks++;
 434
 435 -  /* Enforce preemption. */
 436 -  if (++thread_ticks >= TIME_SLICE)
 437 -    intr_yield_on_return ();
 438 +  if (thread_mlfqs)
 439 +    {
 440 +      /* Update load average. */
 441 +      if (timer_ticks () % TIMER_FREQ == 0)
 442 +        {
 443 +          size_t ready_threads = list_size (&ready_list);
 444 +          if (t != idle_thread)
 445 +            ready_threads++;
 446 +
 447 +          load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg),
 448 +                              fix_mul (fix_frac (1, 60), fix_int (ready_threads)));
 449 +        }
 450 +
 451 +      /* Increment running process's recent_cpu. */
 452 +      if (t != idle_thread)
 453 +        t->recent_cpu = fix_add (t->recent_cpu, fix_int (1));
 454 +
 455 +      /* Update recent_cpu and thread priorities once per second. */
 456 +      if (timer_ticks () % TIMER_FREQ == 0)
 457 +        {
 458 +          fixed_point_t twice_load = fix_scale (load_avg, 2);
 459 +          fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1));
 460 +          fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1);
 461 +
 462 +          thread_foreach (adjust_recent_cpu, &load_factor);
 463 +        }
 464 +    }
 465 +
 466 +  /* Switch threads if time slice has expired. */
 467 +  if (++thread_ticks >= TIME_SLICE)
 468 +    {
 469 +      if (thread_mlfqs)
 470 +        thread_recompute_priority (thread_current ());
 471 +      intr_yield_on_return ();
 472 +    }
 473  }
 474
 475  /* Prints thread statistics. */
 476 @@ -166,12 +214,13 @@
 477  thread_create (const char *name, int priority,
 478                 thread_func *function, void *aux)
 479  {
 480 +  struct thread *cur = thread_current ();
 481    struct thread *t;
 482    struct kernel_thread_frame *kf;
 483    struct switch_entry_frame *ef;
 484    struct switch_threads_frame *sf;
 485 -  tid_t tid;
 486    enum intr_level old_level;
 487 +  tid_t tid;
 488
 489    ASSERT (function != NULL);
 490
 491 @@ -181,8 +230,10 @@
 492      return TID_ERROR;
 493
 494    /* Initialize thread. */
 495 -  init_thread (t, name, priority);
 496 +  init_thread (t, name, thread_mlfqs ? cur->priority : priority);
 497    tid = t->tid = allocate_tid ();
 498 +  t->nice = cur->nice;
 499 +  t->recent_cpu = cur->recent_cpu;
 500
 501    /* Prepare thread for first run by initializing its stack.
 502       Do this atomically so intermediate values for the 'stack'
 503 @@ -208,6 +259,8 @@
 504
 505    /* Add to run queue. */
 506    thread_unblock (t);
 507 +  if (priority > thread_get_priority ())
 508 +    thread_yield ();
 509
 510    return tid;
 511  }
 512 @@ -228,6 +281,19 @@
 513    schedule ();
 514  }
 515
 516 +/* Returns true if A has lower priority than B,
 517 +   within a list of threads. */
 518 +bool
 519 +thread_lower_priority (const struct list_elem *a_,
 520 +                        const struct list_elem *b_,
 521 +                        void *aux UNUSED)
 522 +{
 523 +  const struct thread *a = list_entry (a_, struct thread, elem);
 524 +  const struct thread *b = list_entry (b_, struct thread, elem);
 525 +
 526 +  return a->priority < b->priority;
 527 +}
 528 +
 529  /* Transitions a blocked thread T to the ready-to-run state.
 530     This is an error if T is not blocked.  (Use thread_yield() to
 531     make the running thread ready.)
 532 @@ -339,11 +405,26 @@
 533      }
 534  }
 535
 536 -/* Sets the current thread's priority to NEW_PRIORITY. */
 537 +static void
 538 +recompute_priority_chain (void)
 539 +{
 540 +  enum intr_level old_level = intr_disable ();
 541 +  thread_recompute_priority (thread_current ());
 542 +  thread_yield_to_higher_priority ();
 543 +  intr_set_level (old_level);
 544 +}
 545 +
 546 +/* Sets the current thread's priority to PRIORITY. */
 547  void
 548 -thread_set_priority (int new_priority)
 549 +thread_set_priority (int priority)
 550  {
 551 -  thread_current ()->priority = new_priority;
 552 +  if (!thread_mlfqs)
 553 +    {
 554 +      struct thread *t = thread_current ();
 555 +
 556 +      t->normal_priority = priority;
 557 +      recompute_priority_chain ();
 558 +    }
 559  }
 560
 561  /* Returns the current thread's priority. */
 562 @@ -355,33 +436,98 @@
 563
 564  /* Sets the current thread's nice value to NICE. */
 565  void
 566 -thread_set_nice (int nice UNUSED)
 567 +thread_set_nice (int nice)
 568  {
 569 -  /* Not yet implemented. */
 570 +  thread_current ()->nice = nice;
 571 +  recompute_priority_chain ();
 572  }
 573
 574  /* Returns the current thread's nice value. */
 575  int
 576  thread_get_nice (void)
 577  {
 578 -  /* Not yet implemented. */
 579 -  return 0;
 580 +  return thread_current ()->nice;
 581  }
 582
 583 -/* Returns 100 times the system load average. */
 584  int
 585  thread_get_load_avg (void)
 586  {
 587 -  /* Not yet implemented. */
 588 -  return 0;
 589 +  int load_avg_int;
 590 +  enum intr_level level = intr_disable ();
 591 +  load_avg_int = fix_round (fix_scale (load_avg, 100));
 592 +  intr_set_level (level);
 593 +  return load_avg_int;
 594  }
 595
 596 -/* Returns 100 times the current thread's recent_cpu value. */
 597  int
 598  thread_get_recent_cpu (void)
 599  {
 600 -  /* Not yet implemented. */
 601 -  return 0;
 602 +  int recent_cpu_int;
 603 +  enum intr_level level = intr_disable ();
 604 +  recent_cpu_int = fix_round (fix_scale (thread_current ()->recent_cpu, 100));
 605 +  intr_set_level (level);
 606 +  return recent_cpu_int;
 607 +}
 608 +
 609 +/* Returns true if thread A has lower priority than thread B,
 610 +   within a list of donors. */
 611 +static bool
 612 +donated_lower_priority (const struct list_elem *a_,
 613 +                        const struct list_elem *b_,
 614 +                        void *aux UNUSED)
 615 +{
 616 +  const struct thread *a = list_entry (a_, struct thread, donor_elem);
 617 +  const struct thread *b = list_entry (b_, struct thread, donor_elem);
 618 +
 619 +  return a->priority < b->priority;
 620 +}
 621 +
 622 +/* Recomputes T's priority in terms of its normal priority and
 623 +   its donors' priorities, if any,
 624 +   and cascades the donation as necessary. */
 625 +void
 626 +thread_recompute_priority (struct thread *t)
 627 +{
 628 +  int old_priority = t->priority;
 629 +  int default_priority = t->normal_priority;
 630 +  int donation = PRI_MIN;
 631 +  if (thread_mlfqs)
 632 +    {
 633 +      default_priority = PRI_MAX - fix_round (t->recent_cpu) / 4 - t->nice * 2;
 634 +      if (default_priority < PRI_MIN)
 635 +        default_priority = PRI_MIN;
 636 +      else if (default_priority > PRI_MAX)
 637 +        default_priority = PRI_MAX;
 638 +    }
 639 +  if (!list_empty (&t->donors))
 640 +    donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
 641 +                           struct thread, donor_elem)->priority;
 642 +  t->priority = donation > default_priority ? donation : default_priority;
 643 +  if (t->priority > old_priority && t->donee != NULL)
 644 +    thread_recompute_priority (t->donee);
 645 +}
 646 +
 647 +/* If the ready list contains a thread with a higher priority,
 648 +   yields to it. */
 649 +void
 650 +thread_yield_to_higher_priority (void)
 651 +{
 652 +  enum intr_level old_level = intr_disable ();
 653 +  if (!list_empty (&ready_list))
 654 +    {
 655 +      struct thread *cur = thread_current ();
 656 +      struct thread *max = list_entry (list_max (&ready_list,
 657 +                                                 thread_lower_priority, NULL),
 658 +                                       struct thread, elem);
 659 +      if (max->priority > cur->priority)
 660 +        {
 661 +          if (intr_context ())
 662 +            intr_yield_on_return ();
 663 +          else
 664 +            thread_yield ();
 665 +        }
 666 +    }
 667 +  intr_set_level (old_level);
 668  }
 669  \f
 670  /* Idle thread.  Executes when no other thread is ready to run.
 671 @@ -467,8 +613,10 @@
 672    t->status = THREAD_BLOCKED;
 673    strlcpy (t->name, name, sizeof t->name);
 674    t->stack = (uint8_t *) t + PGSIZE;
 675 -  t->priority = priority;
 676 +  t->priority = t->normal_priority = priority;
 677    t->magic = THREAD_MAGIC;
 678 +  sema_init (&t->timer_sema, 0);
 679 +  list_init (&t->donors);
 680    list_push_back (&all_list, &t->allelem);
 681  }
 682
 683 @@ -495,8 +643,14 @@
 684  {
 685    if (list_empty (&ready_list))
 686      return idle_thread;
 687 -  else
 688 -    return list_entry (list_pop_front (&ready_list), struct thread, elem);
 689 +  else
 690 +    {
 691 +      struct thread *max
 692 +        = list_entry (list_max (&ready_list, thread_lower_priority, NULL),
 693 +                      struct thread, elem);
 694 +      list_remove (&max->elem);
 695 +      return max;
 696 +    }
 697  }
 698
 699  /* Completes a thread switch by activating the new thread's page
 700 diff -Nur ../../src/threads/thread.h src/threads/thread.h
 701 --- ../../src/threads/thread.h  2008-08-27 08:45:26.000000000 -0400
 702 +++ src/threads/thread.h        2008-08-27 12:45:31.000000000 -0400
 703 @@ -4,6 +4,8 @@
 704  #include <debug.h>
 705  #include <list.h>
 706  #include <stdint.h>
 707 +#include "threads/synch.h"
 708 +#include "threads/fixed-point.h"
 709
 710  /* States in a thread's life cycle. */
 711  enum thread_status
 712 @@ -87,12 +89,26 @@
 713      enum thread_status status;          /* Thread state. */
 714      char name[16];                      /* Name (for debugging purposes). */
 715      uint8_t *stack;                     /* Saved stack pointer. */
 716 -    int priority;                       /* Priority. */
 717 +
 718 +    /* Scheduler data. */
 719 +    int priority;                       /* Priority, including donations. */
 720 +    int normal_priority;                /* Priority, without donations. */
 721 +    struct list donors;                 /* Threads donating priority to us. */
 722 +    struct list_elem donor_elem;        /* Element in donors list. */
 723 +    struct thread *donee;               /* Thread we're donating to. */
 724 +    struct lock *want_lock;             /* Lock we're waiting to acquire. */
 725 +    int nice;                           /* Niceness. */
 726 +    fixed_point_t recent_cpu;           /* Recent amount of CPU time. */
 727      struct list_elem allelem;           /* List element for all threads list. */
 728
 729      /* Shared between thread.c and synch.c. */
 730      struct list_elem elem;              /* List element. */
 731
 732 +    /* Alarm clock. */
 733 +    int64_t wakeup_time;                /* Time to wake this thread up. */
 734 +    struct list_elem timer_elem;        /* Element in wait_list. */
 735 +    struct semaphore timer_sema;        /* Semaphore. */
 736 +
 737  #ifdef USERPROG
 738      /* Owned by userprog/process.c. */
 739      uint32_t *pagedir;                  /* Page directory. */
 740 @@ -125,6 +141,10 @@
 741
 742  void thread_exit (void) NO_RETURN;
 743  void thread_yield (void);
 744 +void thread_yield_to_higher_priority (void);
 745 +void thread_recompute_priority (struct thread *);
 746 +bool thread_lower_priority (const struct list_elem *, const struct list_elem *,
 747 +                            void *aux);
 748
 749  /* Performs some operation on thread t, given auxiliary data AUX. */
 750  typedef void thread_action_func (struct thread *t, void *aux);