first priority donation implementation

1 files changed, 68 insertions, 3 deletions

diff --git a/threads/synch.c b/threads/synch.c
index 317c68a..1f15bb9 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -32,6 +32,9 @@
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 
+static bool lock_list_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+    void *AUX UNUSED);
+
 /* Initializes semaphore SEMA to VALUE.  A semaphore is a
    nonnegative integer along with two atomic operators for
    manipulating it:
@@ -68,7 +71,8 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
-      list_push_back (&sema->waiters, &thread_current ()->elem);
+      /* add thread to our ordered waiters list */
+      list_insert_ordered (&sema->waiters, &thread_current ()->elem, &priority_list_cmp_greater, NULL);
       thread_block ();
     }
   sema->value--;
@@ -181,6 +185,17 @@ lock_init (struct lock *lock)
   sema_init (&lock->semaphore, 1);
 }
 
+/* comparison function for our descending ordered lock list. */
+static bool
+lock_list_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+    void *AUX UNUSED)
+{
+  struct lock *l1 = list_entry (a, struct lock, elem);
+  struct lock *l2 = list_entry (b, struct lock, elem);
+  /* descending order - put newer in front */
+  return (l1->priority >= l2->priority);
+}
+
 /* Acquires LOCK, sleeping until it becomes available if
    necessary.  The lock must not already be held by the current
    thread.
@@ -192,12 +207,41 @@ lock_init (struct lock *lock)
 void
 lock_acquire (struct lock *lock)
 {
+  struct thread *cur = thread_current ();
+
   ASSERT (lock != NULL);
   ASSERT (!intr_context ());
   ASSERT (!lock_held_by_current_thread (lock));
 
+  if (lock->holder != NULL)
+  {
+    //printf("[%d] acquire: lock=%p prio=%d\n", cur->tid, lock, cur->priority);
+
+    /* 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_list_priority_cmp_greater, NULL);
+
+      /* finally donate our priority */
+      thread_donate_priority (cur, lock->holder);
+    }
+  }
+
   sema_down (&lock->semaphore);
-  lock->holder = thread_current ();
+  lock->holder = cur;
+
+  /* the priority of this lock is our own priority */
+  lock->priority = cur->priority;
+
+  /* save the locks we hold in descending order of their priority */
+  list_insert_ordered (&lock->holder->locks, &lock->elem,
+      lock_list_priority_cmp_greater, NULL);
 }
 
 /* Tries to acquires LOCK and returns true if successful or false
@@ -228,11 +272,31 @@ lock_try_acquire (struct lock *lock)
 void
 lock_release (struct lock *lock) 
 {
+  struct thread *cur = thread_current ();
+
   ASSERT (lock != NULL);
   ASSERT (lock_held_by_current_thread (lock));
 
   lock->holder = NULL;
+  //lock->priority = we don't care as the next lock_acquire ()-call does
   sema_up (&lock->semaphore);
+
+  /* we don't hold the lock any longer so remove it from the lock list */
+  list_remove (&lock->elem);
+
+  if (list_empty (&cur->locks))
+  {
+    //printf("[%d] restoring prio from %d to %d\n", cur->tid, cur->priority, cur->saved_priority);
+    /* 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);
+  }
 }
 
 /* Returns true if the current thread holds LOCK, false
@@ -295,7 +359,8 @@ cond_wait (struct condition *cond, struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
   
   sema_init (&waiter.semaphore, 0);
-  list_push_back (&cond->waiters, &waiter.elem);
+  /* add thread to our ordered waiters list */
+  list_insert_ordered (&cond->waiters, &waiter.elem, &priority_list_cmp_greater, NULL);
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);