From 57c893ae56f151efc96fabebbb4c8ec039cb56ef Mon Sep 17 00:00:00 2001
From: manuel <manuel@mausz.at>
Date: Tue, 8 May 2012 02:35:22 +0200
Subject: * fixed sema_up which didn't yield the cpu * fixed wrong condition
 comperator * renamed the comperator functions to better explain their compare
 element * current status: 3 of 18 tests failed

---
 threads/synch.c  | 51 +++++++++++++++++++++++++++++++++++++++------------
 threads/thread.c | 12 ++++++------
 threads/thread.h |  2 +-
 3 files changed, 46 insertions(+), 19 deletions(-)

diff --git a/threads/synch.c b/threads/synch.c
index 1f15bb9..92008ef 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -32,8 +32,10 @@
 #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,
+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
@@ -72,7 +74,8 @@ sema_down (struct semaphore *sema)
   while (sema->value == 0) 
     {
       /* add thread to our ordered waiters list */
-      list_insert_ordered (&sema->waiters, &thread_current ()->elem, &priority_list_cmp_greater, NULL);
+      list_insert_ordered (&sema->waiters, &thread_current ()->elem,
+          &thread_priority_cmp_greater, NULL);
       thread_block ();
     }
   sema->value--;
@@ -113,15 +116,25 @@ void
 sema_up (struct semaphore *sema) 
 {
   enum intr_level old_level;
+  bool yield = false;
 
   ASSERT (sema != NULL);
 
   old_level = intr_disable ();
-  if (!list_empty (&sema->waiters)) 
-    thread_unblock (list_entry (list_pop_front (&sema->waiters),
-                                struct thread, elem));
+  if (!list_empty (&sema->waiters))
+  {
+    struct thread *t = list_entry (list_pop_front (&sema->waiters),
+        struct thread, elem);
+    thread_unblock (t);
+    /* thread_unblock() doesn't yield so check if there's a need */
+    if (t->priority > thread_current ()->priority)
+      yield = true;
+  }
   sema->value++;
   intr_set_level (old_level);
+
+  if (yield)
+    thread_yield();
 }
 
 static void sema_test_helper (void *sema_);
@@ -187,11 +200,11 @@ lock_init (struct lock *lock)
 
 /* 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,
+lock_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);
+  const struct lock *l1 = list_entry (a, struct lock, elem);
+  const struct lock *l2 = list_entry (b, struct lock, elem);
   /* descending order - put newer in front */
   return (l1->priority >= l2->priority);
 }
@@ -226,7 +239,7 @@ lock_acquire (struct lock *lock)
       /* 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);
+          lock_priority_cmp_greater, NULL);
 
       /* finally donate our priority */
       thread_donate_priority (cur, lock->holder);
@@ -241,7 +254,7 @@ lock_acquire (struct lock *lock)
 
   /* 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);
+      lock_priority_cmp_greater, NULL);
 }
 
 /* Tries to acquires LOCK and returns true if successful or false
@@ -315,6 +328,7 @@ struct semaphore_elem
   {
     struct list_elem elem;              /* List element. */
     struct semaphore semaphore;         /* This semaphore. */
+    int priority;                       /* the priority of the waiting thread */
   };
 
 /* Initializes condition variable COND.  A condition variable
@@ -328,6 +342,16 @@ 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->priority > s2->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
@@ -359,8 +383,11 @@ cond_wait (struct condition *cond, struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
   
   sema_init (&waiter.semaphore, 0);
-  /* add thread to our ordered waiters list */
-  list_insert_ordered (&cond->waiters, &waiter.elem, &priority_list_cmp_greater, NULL);
+  /* set condition priority */
+  waiter.priority = thread_current ()->priority;
+  /* and add condition to our ordered waiters list */
+  list_insert_ordered (&cond->waiters, &waiter.elem,
+      &semaphore_priority_cmp_greater, NULL);
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);
diff --git a/threads/thread.c b/threads/thread.c
index 17d21bd..a7db106 100644
--- a/threads/thread.c
+++ b/threads/thread.c
@@ -73,11 +73,11 @@ static tid_t allocate_tid (void);
 
 /* comparison function for our descending ordered ready list. */
 bool
-priority_list_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+thread_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
   void *AUX UNUSED)
 {
-  struct thread *t1 = list_entry (a, struct thread, elem);
-  struct thread *t2 = list_entry (b, struct thread, elem);
+  const struct thread *t1 = list_entry (a, struct thread, elem);
+  const struct thread *t2 = list_entry (b, struct thread, elem);
   return (t1->priority > t2->priority);
 }
 
@@ -264,7 +264,7 @@ thread_unblock (struct thread *t)
   old_level = intr_disable ();
   ASSERT (t->status == THREAD_BLOCKED);
   /* add thread to our ordered ready_list */
-  list_insert_ordered (&ready_list, &t->elem, &priority_list_cmp_greater, NULL);
+  list_insert_ordered (&ready_list, &t->elem, &thread_priority_cmp_greater, NULL);
   t->status = THREAD_READY;
   intr_set_level (old_level);
 }
@@ -335,7 +335,7 @@ thread_yield (void)
 
   old_level = intr_disable ();
   if (cur != idle_thread)
-    list_insert_ordered (&ready_list, &cur->elem, &priority_list_cmp_greater, NULL);
+    list_insert_ordered (&ready_list, &cur->elem, &thread_priority_cmp_greater, NULL);
   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);
@@ -390,7 +390,7 @@ thread_other_set_priority (struct thread *t, int new_priority)
   {
     /* sort our ordered list */
     list_remove (&t->elem);
-    list_insert_ordered (&ready_list, &t->elem, &priority_list_cmp_greater, NULL);
+    list_insert_ordered (&ready_list, &t->elem, &thread_priority_cmp_greater, NULL);
   }
   else if (t->status == THREAD_RUNNING && !list_empty (&ready_list))
   {
diff --git a/threads/thread.h b/threads/thread.h
index a6ef25d..8bc6512 100644
--- a/threads/thread.h
+++ b/threads/thread.h
@@ -118,7 +118,7 @@ struct thread
    Controlled by kernel command-line option "-o mlfqs". */
 extern bool thread_mlfqs;
 
-bool priority_list_cmp_greater (const struct list_elem *a, const struct list_elem *b,
+bool thread_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
     void *aux);
 
 void thread_init (void);
-- 
cgit v1.2.3