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