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

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