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

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