1 files changed, 36 insertions, 31 deletions

diff --git a/threads/synch.c b/threads/synch.c
index 2cb4805..6ffe1de 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -73,9 +73,8 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
-      /* add thread to our ordered waiters list */
-      list_insert_ordered (&sema->waiters, &thread_current ()->elem,
-          &thread_priority_cmp_greater, NULL);
+      /* sorting the list here isn't useful. see sema_up() for more details */
+      list_push_back (&sema->waiters, &thread_current ()->elem);
       thread_block ();
     }
   sema->value--;
@@ -116,21 +115,27 @@ void
 sema_up (struct semaphore *sema) 
 {
   enum intr_level old_level;
-  struct thread *t = NULL;
+  bool yield = false;
 
   ASSERT (sema != NULL);
 
   old_level = intr_disable ();
-  while (!list_empty (&sema->waiters))
-  {
-    t = list_entry (list_pop_front (&sema->waiters), struct thread, elem);
-    thread_unblock (t);
-  }
+  if (!list_empty (&sema->waiters))
+    {
+      /* we can't sort the list during insertion that easily as the priority of
+         blocked/waiting threads may change due to priority donation.
+         we only need to unblock one thread thus we simply sort the list here */
+      list_sort (&sema->waiters, &thread_priority_cmp_greater, NULL);
+      struct thread *t = list_entry (list_pop_front (&sema->waiters), struct thread, elem);
+      /* thread_unblock() doesn't yield so check if there's a need */
+      if (t->priority > thread_current ()->priority)
+        yield = true;
+      thread_unblock (t);
+    }
   sema->value++;
   intr_set_level (old_level);
 
-  /* thread_unblock() doesn't yield so check if there's a need */
-  if (t != NULL && t->priority > thread_current ()->priority)
+  if (yield)
     thread_yield();
 }
 
@@ -224,22 +229,22 @@ lock_acquire (struct lock *lock)
   ASSERT (!lock_held_by_current_thread (lock));
 
   if (lock->holder != NULL)
-  {
-    /* check for a possible priority donation */
-    if (cur->priority > lock->priority)
     {
-      /* the new priority of this lock is our own priority */
-      lock->priority = cur->priority;
-
-      /* the lock priority changed so we need to sort the lock list of the lock holder */
-      list_remove (&lock->elem);
-      list_insert_ordered (&lock->holder->locks, &lock->elem,
-          lock_priority_cmp_greater, NULL);
-
-      /* finally donate our priority */
-      thread_donate_priority (cur, lock->holder);
+      /* check for a possible priority donation */
+      if (cur->priority > lock->priority)
+        {
+          /* the new priority of this lock is our own priority */
+          lock->priority = cur->priority;
+
+          /* the lock priority changed so we need to sort the lock list of the lock holder */
+          list_remove (&lock->elem);
+          list_insert_ordered (&lock->holder->locks, &lock->elem,
+              lock_priority_cmp_greater, NULL);
+
+          /* finally donate our priority */
+          thread_donate_priority (cur, lock->holder);
+        }
     }
-  }
 
   sema_down (&lock->semaphore);
   lock->holder = cur;
@@ -296,12 +301,12 @@ lock_release (struct lock *lock)
     /* we don't hold another lock so restore our base priority */
     thread_donation_pass_back ();
   else
-  {
-    /* we still hold at least one lock so change our priority to the priority of the lock */
-    struct lock *lock2 = list_entry (list_front (&cur->locks), struct lock, elem);
-    /* (forced) priority change */
-    thread_other_set_priority (cur, lock2->priority);
-  }
+    {
+      /* we still hold at least one lock so change our priority to the priority of the lock */
+      struct lock *lock2 = list_entry (list_front (&cur->locks), struct lock, elem);
+      /* (forced) priority change */
+      thread_other_set_priority (cur, lock2->priority);
+    }
 }
 
 /* Returns true if the current thread holds LOCK, false