+Index: src/threads/synch.c
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v
+retrieving revision 1.15
+diff -u -p -u -r1.15 synch.c
+--- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15
++++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000
+@@ -77,6 +77,18 @@ sema_down (struct semaphore *sema)
+ intr_set_level (old_level);
+ }
+
++/* Returns true if thread A has lower priority than thread B. */
++static bool
++donated_lower_priority (const struct list_elem *a_,
++ const struct list_elem *b_,
++ void *aux UNUSED)
++{
++ const struct thread *a = list_entry (a_, struct thread, donor_elem);
++ const struct thread *b = list_entry (b_, struct thread, donor_elem);
++
++ return a->priority < b->priority;
++}
++
+ /* Up or "V" operation on a semaphore. Increments SEMA's value
+ and wakes up one thread of those waiting for SEMA, if any.
+
+@@ -89,10 +100,28 @@ sema_up (struct semaphore *sema)
+ ASSERT (sema != NULL);
+
+ old_level = intr_disable ();
+- if (!list_empty (&sema->waiters))
+- thread_unblock (list_entry (list_pop_front (&sema->waiters),
+- struct thread, elem));
+ sema->value++;
++ if (!list_empty (&sema->waiters))
++ {
++ /* Find highest-priority waiting thread. */
++ struct thread *max = list_entry (list_max (&sema->waiters,
++ donated_lower_priority, NULL),
++ struct thread, elem);
++
++ /* Remove `max' from wait list and unblock. */
++ list_remove (&max->elem);
++ thread_unblock (max);
++
++ /* Yield to a higher-priority thread, if we're running in a
++ context where it makes sense to do so.
++
++ Kind of a funny interaction with donation here.
++ We only support donation for locks, and locks turn off
++ interrupts before calling us, so we automatically don't
++ do the yield here, delegating to lock_release(). */
++ if (!intr_context () && old_level == INTR_ON)
++ thread_yield_to_higher_priority ();
++ }
+ intr_set_level (old_level);
+ }
+
+@@ -184,6 +213,23 @@ lock_acquire (struct lock *lock)
+ ASSERT (!lock_held_by_current_thread (lock));
+
+ old_level = intr_disable ();
++
++ if (lock->holder != NULL)
++ {
++ /* Donate our priority to the thread holding the lock.
++ First, update the data structures. */
++ struct thread *donor = thread_current ();
++ donor->want_lock = lock;
++ donor->donee = lock->holder;
++ list_push_back (&lock->holder->donors, &donor->donor_elem);
++
++ /* Now implement the priority donation itself
++ by recomputing the donee's priority
++ and cascading the donation as far as necessary. */
++ while (donor->donee != NULL && thread_recompute_priority (donor->donee))
++ donor = donor->donee;
++ }
++
+ sema_down (&lock->semaphore);
+ lock->holder = thread_current ();
+ intr_set_level (old_level);
+@@ -198,13 +244,38 @@ void
+ lock_release (struct lock *lock)