From 158ea87fba909161a084c29feff29a168725fe4e Mon Sep 17 00:00:00 2001
From: manuel <manuel@mausz.at>
Date: Mon, 7 May 2012 18:01:20 +0200
Subject: first priority donation implementation

---
 threads/thread.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 74 insertions(+), 12 deletions(-)

(limited to 'threads/thread.c')

diff --git a/threads/thread.c b/threads/thread.c
index 3fefbd8..17d21bd 100644
--- a/threads/thread.c
+++ b/threads/thread.c
@@ -71,9 +71,9 @@ static void schedule (void);
 void thread_schedule_tail (struct thread *prev);
 static tid_t allocate_tid (void);
 
-//TODO: should take donated priority into account
-static bool
-ready_list_cmp_less(const struct list_elem *a, const struct list_elem *b,
+/* comparison function for our descending ordered ready list. */
+bool
+priority_list_cmp_greater(const struct list_elem *a, const struct list_elem *b,
   void *AUX UNUSED)
 {
   struct thread *t1 = list_entry (a, struct thread, elem);
@@ -222,7 +222,10 @@ thread_create (const char *name, int priority,
 
   /* Add to run queue. */
   thread_unblock (t);
-  thread_yield ();
+
+  /* and yield the cpu in case we have a higher priority */
+  if (t->priority > thread_current ()->priority)
+    thread_yield ();
 
   return tid;
 }
@@ -261,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, &ready_list_cmp_less, NULL);
+  list_insert_ordered (&ready_list, &t->elem, &priority_list_cmp_greater, NULL);
   t->status = THREAD_READY;
   intr_set_level (old_level);
 }
@@ -332,7 +335,7 @@ thread_yield (void)
 
   old_level = intr_disable ();
   if (cur != idle_thread)
-    list_insert_ordered (&ready_list, &cur->elem, &ready_list_cmp_less, NULL);
+    list_insert_ordered (&ready_list, &cur->elem, &priority_list_cmp_greater, NULL);
   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);
@@ -359,14 +362,71 @@ thread_foreach (thread_action_func *func, void *aux)
 void
 thread_set_priority (int new_priority)
 {
-  thread_current ()->priority = new_priority;
+  struct thread *cur = thread_current ();
+  if (cur->priority == new_priority)
+    return;
+
+  if (cur->is_donated)
+  {
+    cur->saved_priority = new_priority;
+    /* make sure we don't lower a donated priority */
+    if (new_priority < cur->priority)
+      return;
+  }
+  thread_other_set_priority (cur, new_priority);
+}
 
-  /* compare priority with the highest priority in the list */
-  if (!list_empty (&ready_list))
+void
+thread_other_set_priority (struct thread *t, int new_priority)
+{
+  ASSERT (is_thread (t));
+
+  if (t->priority == new_priority)
+    return;
+
+  t->priority = new_priority;
+
+  if (t->status == THREAD_READY)
+  {
+    /* sort our ordered list */
+    list_remove (&t->elem);
+    list_insert_ordered (&ready_list, &t->elem, &priority_list_cmp_greater, NULL);
+  }
+  else if (t->status == THREAD_RUNNING && !list_empty (&ready_list))
+  {
+    /* compare priority with the highest priority in the list */
+    struct thread *t2 = list_entry (list_front (&ready_list), struct thread, elem);
+    if (t2->priority > t->priority)
+      thread_yield ();
+  }
+}
+
+void
+thread_donate_priority (struct thread *donator, struct thread *donee)
+{
+  ASSERT (is_thread (donator));
+  ASSERT (is_thread (donee));
+
+  /* make sure we don't lower a donated priority */
+  if (donator->priority < donee->priority)
+    return;
+
+  /* store our base priority */
+  if (!donee->is_donated)
+  {
+    donee->saved_priority = donee->priority;
+    donee->is_donated = true;
+  }
+  thread_other_set_priority (donee, donator->priority);
+}
+
+void
+thread_donation_pass_back (void)
+{
+  if (thread_current ()->is_donated)
   {
-    struct thread *t = list_entry (list_front (&ready_list), struct thread, elem);
-    if (t->priority > thread_current ()->priority)
-      thread_yield();
+    thread_current ()->is_donated = false;
+    thread_set_priority (thread_current ()->saved_priority);
   }
 }
 
@@ -497,6 +557,8 @@ init_thread (struct thread *t, const char *name, int priority)
 #ifdef USERPROG
   list_init(&t->children);
 #endif
+  t->is_donated = false;
+  list_init (&t->locks);
 }
 
 /* Allocates a SIZE-byte frame at the top of thread T's stack and
-- 
cgit v1.2.3