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