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

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