fix wrong behavior of cond_wait/cond_signal in donation case.

we can't pre-sort the waiters list here either. it's the same as with
sema_up/sema_down

3 files changed, 26 insertions, 19 deletions

diff --git a/proj1.txt b/proj1.txt
index 274ef34..27b0d17 100644
--- a/proj1.txt
+++ b/proj1.txt
@@ -34,6 +34,19 @@ http://hynek.me/studies/sched_ausarbeitung.pdf
 >> `struct' member, global or static variable, `typedef', or
 >> enumeration.  Identify the purpose of each in 25 words or less.
 
+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 ...the lock the thread currently tries to acquire (but hasn't yet)
+
+struct lock:
+  int priority              ...the priority of the thread with the highest priority currently acquiring the lock
+  struct list_elem elem     ...list element for (struct thread)->locks
+
+struct semaphore_elem:
+  struct thread *thread     ...the current waiting thread
+
 >> B2: Explain the data structure used to track priority donation.
 >> Use ASCII art to diagram a nested donation.  (Alternately, submit a
 >> .png file.)
diff --git a/threads/synch.c b/threads/synch.c
index db204f5..d7e5e39 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -34,8 +34,6 @@
 
 static bool lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
     void *AUX UNUSED);
-static bool semaphore_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
@@ -353,16 +351,6 @@ cond_init (struct condition *cond)
   list_init (&cond->waiters);
 }
 
-/* comparison function for our descending ordered condition waiters list. */
-static bool
-semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
-    void *aux UNUSED)
-{
-  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->thread->priority > s2->thread->priority);
-}
-
 /* Atomically releases LOCK and waits for COND to be signaled by
    some other piece of code.  After COND is signaled, LOCK is
    reacquired before returning.  LOCK must be held before calling
@@ -396,9 +384,9 @@ cond_wait (struct condition *cond, struct lock *lock)
   sema_init (&waiter.semaphore, 0);
   /* 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);
+  /* and add condition to our waiters list. sorting isn't useful here either.
+     see sema_up()/cond_signal() for more details */
+  list_push_back (&cond->waiters, &waiter->elem);
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);
@@ -419,9 +407,15 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
   ASSERT (!intr_context ());
   ASSERT (lock_held_by_current_thread (lock));
 
-  if (!list_empty (&cond->waiters)) 
-    sema_up (&list_entry (list_pop_front (&cond->waiters),
-                          struct semaphore_elem, elem)->semaphore);
+  /* we can't sort the list during insertion that easily as the priority of
+     blocked/waiting threads may change due to priority donation.
+     this is the same as with sema_down()/sema_up() */
+  if (!list_empty (&cond->waiters))
+  {
+      list_sort (&cond->waiters, &semaphore_priority_cmp_greater, NULL);
+      sema_up (&list_entry (list_pop_front (&cond->waiters),
+            struct semaphore_elem, elem)->semaphore);
+  }
 }
 
 /* Wakes up all threads, if any, waiting on COND (protected by
diff --git a/threads/thread.h b/threads/thread.h
index fd4f8a6..9125937 100644
--- a/threads/thread.h
+++ b/threads/thread.h
@@ -111,7 +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) */
+    struct lock *blocked_lock;          /* the lock the thread currently tries to acquire (but hasn't yet) */
   };
 
 /* If false (default), use round-robin scheduler.