major: added support for nested priority donation

minor: replaced priority with a pointer to the waiting thread in condition handling
status: 0/18 failed!

3 files changed, 24 insertions, 9 deletions

diff --git a/threads/synch.c b/threads/synch.c
index 6ffe1de..364b769 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -223,32 +223,45 @@ void
 lock_acquire (struct lock *lock)
 {
   struct thread *cur = thread_current ();
+  struct lock *blocked_lock;
 
   ASSERT (lock != NULL);
   ASSERT (!intr_context ());
   ASSERT (!lock_held_by_current_thread (lock));
 
+  /* nested priority donation: save currently blocked lock */
   if (lock->holder != NULL)
+    cur->blocked_lock = lock;
+
+  /* nested priority donation: we loop backwards: lock -> holder -> blocked_lock
+     and donate our priority */
+  blocked_lock = lock;
+  while (blocked_lock != NULL && blocked_lock->holder != NULL)
     {
       /* check for a possible priority donation */
-      if (cur->priority > lock->priority)
+      if (cur->priority > blocked_lock->priority)
         {
           /* the new priority of this lock is our own priority */
-          lock->priority = cur->priority;
+          blocked_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,
+          list_remove (&blocked_lock->elem);
+          list_insert_ordered (&blocked_lock->holder->locks, &blocked_lock->elem,
               lock_priority_cmp_greater, NULL);
 
           /* finally donate our priority */
-          thread_donate_priority (cur, lock->holder);
+          thread_donate_priority (cur, blocked_lock->holder);
         }
+
+        blocked_lock = blocked_lock->holder->blocked_lock;
     }
 
   sema_down (&lock->semaphore);
   lock->holder = cur;
 
+  /* nested priority donation: we got the lock, reset blocked_lock */
+  cur->blocked_lock = NULL;
+
   /* the priority of this lock is our own priority */
   lock->priority = cur->priority;
 
@@ -325,7 +338,7 @@ struct semaphore_elem
   {
     struct list_elem elem;              /* List element. */
     struct semaphore semaphore;         /* This semaphore. */
-    int priority;                       /* the priority of the waiting thread */
+    struct thread *thread;              /* the current waiting thread */
   };
 
 /* Initializes condition variable COND.  A condition variable
@@ -346,7 +359,7 @@ semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem
 {
   const struct semaphore_elem *s1 = list_entry (a, struct semaphore_elem, elem);
   const struct semaphore_elem *s2 = list_entry (b, struct semaphore_elem, elem);
-  return (s1->priority > s2->priority);
+  return (s1->thread->priority > s2->thread->priority);
 }
 
 /* Atomically releases LOCK and waits for COND to be signaled by
@@ -380,8 +393,8 @@ cond_wait (struct condition *cond, struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
   
   sema_init (&waiter.semaphore, 0);
-  /* set condition priority */
-  waiter.priority = thread_current ()->priority;
+  /* set thread of waiter */
+  waiter.thread = thread_current ();
   /* and add condition to our ordered waiters list */
   list_insert_ordered (&cond->waiters, &waiter.elem,
       &semaphore_priority_cmp_greater, NULL);
diff --git a/threads/thread.c b/threads/thread.c
index 358d3a1..61ab5d9 100644
--- a/threads/thread.c
+++ b/threads/thread.c
@@ -380,6 +380,7 @@ void
 thread_other_set_priority (struct thread *t, int new_priority)
 {
   ASSERT (is_thread (t));
+  ASSERT (new_priority >= PRI_MIN && new_priority <= PRI_MAX);
 
   if (t->priority == new_priority)
     return;
diff --git a/threads/thread.h b/threads/thread.h
index 8cfafe6..fd4f8a6 100644
--- a/threads/thread.h
+++ b/threads/thread.h
@@ -111,6 +111,7 @@ struct thread
     int is_donated;                     /* flag if threads priority has been donated by another thread */
     int saved_priority;                 /* saved base priority in case of priority dontation */
     struct list locks;                  /* list of locks the thread currently holds */
+    struct lock *blocked_lock;          /* lock the thread currently trys to accquire (but hasn't yet) */
   };
 
 /* If false (default), use round-robin scheduler.