* fix possible race in thread_set_priority

* fill in same parts of proj1.txt
* use thread_get_priority() whenever possible

3 files changed, 78 insertions, 12 deletions

diff --git a/proj1.txt b/proj1.txt
index 27b0d17..0cb22e1 100644
--- a/proj1.txt
+++ b/proj1.txt
@@ -35,13 +35,16 @@ http://hynek.me/studies/sched_ausarbeitung.pdf
 >> 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 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 *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
+  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:
@@ -51,14 +54,20 @@ struct semaphore_elem:
 >> Use ASCII art to diagram a nested donation.  (Alternately, submit a
 >> .png file.)
 
+TODO
+
 ---- ALGORITHMS ----
 
 >> B3: How do you ensure that the highest priority thread waiting for
 >> a lock, semaphore, or condition variable wakes up first?
 
+TODO
+
 >> B4: Describe the sequence of events when a call to lock_acquire()
 >> causes a priority donation.  How is nested donation handled?
 
+TODO
+
 >> B5: Describe the sequence of events when lock_release() is called
 >> on a lock that a higher-priority thread is waiting for.
 
@@ -68,11 +77,43 @@ struct semaphore_elem:
 >> how your implementation avoids it.  Can you use a lock to avoid
 >> this race?
 
+thread_set_priority() first changes the priority and then has to either just
+re-sort the ready list or has to decide whether it should yield by comparing the
+priorities of the current thread and the thread with the highest priority in
+the ready list. the gap between changing the priority and doing the other stuff
+raises a few possible races if the timer interrupt triggers in between.
+e.g. no proper sorted ready list, corrupt ready list (wrong internal pointers)
+or the timer interrupt fires after calling list_empty() but before list_front()
+while having only two threads (one active, the other one ready). the scheduler
+then schedules the other thread which runs and perhaps terminates, thus removing
+itself from all lists. after that our thread gets scheduled again and reads from
+an empty list, although it wasn't empty before.
+
+Using a lock instead of disabling the interrupts would require locking the
+access to the ready list everywhere. This doesn't follow the already established
+conventions and would rather be a lot more cpu intensive.
+
 ---- RATIONALE ----
 
 >> B7: Why did you choose this design?  In what ways is it superior to
 >> another design you considered?
 
+Acutally we didn't consider any other design. We first tried to solve the
+assignment without pre-planning and just started coding but that failed.
+Afterwards we looked at the various cases, did some drafts and decided on the
+required structure modifications. That did work quite well.
+
+In case of priority donation with locks our design needs only a few cpu
+instructions because we sort the list of locks during insertion and whenever a
+donated priority changes. This allows us to retreive the next donated priority
+with just looking at the first element in the list.
+
+In case of priority donation with semaphores and conditions we can't sort the
+blocked/waiting threads during insertion as their priority may change afterwards
+and we don't have any reference to currently used semaphores/conditions inside
+the thread structure. Thus we simply sort the whole list inside sema_up()/
+cond_signal() before unblocking the next thread.
+
                            SURVEY QUESTIONS
                            ================
 
@@ -85,6 +126,10 @@ the quarter.
 >> In your opinion, was this assignment, or any one of the three problems
 >> in it, too easy or too hard?  Did it take too long or too little time?
 
+working on the priority donation without being able to use printf() inside
+lock_acquire()/lock_release() (as printf() requires a lock for the console
+itself) was challenging.
+
 >> Did you find that working on a particular part of the assignment gave
 >> you greater insight into some aspect of OS design?
 
@@ -92,6 +137,8 @@ the quarter.
 >> future quarters to help them solve the problems?  Conversely, did you
 >> find any of our guidance to be misleading?
 
+do not use printf() inside lock_acquire()/lock_release() :)
+
 >> Do you have any suggestions for the TAs to more effectively assist
 >> students, either for future quarters or the remaining projects?
 
diff --git a/threads/synch.c b/threads/synch.c
index 98905b1..a1b7549 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -128,7 +128,7 @@ sema_up (struct semaphore *sema)
       list_sort (&sema->waiters, &thread_priority_cmp_greater, NULL);
       struct thread *t = list_entry (list_pop_front (&sema->waiters), struct thread, elem);
       /* thread_unblock() doesn't yield so check if there's a need */
-      if (t->priority > thread_current ()->priority)
+      if (t->priority > thread_get_priority ())
         yield = true;
       thread_unblock (t);
     }
@@ -240,10 +240,10 @@ lock_acquire (struct lock *lock)
   while (blocked_lock != NULL && blocked_lock->holder != NULL)
     {
       /* check for a possible priority donation */
-      if (cur->priority > blocked_lock->priority)
+      if (thread_get_priority () > blocked_lock->priority)
         {
           /* the new priority of this lock is our own priority */
-          blocked_lock->priority = cur->priority;
+          blocked_lock->priority = thread_get_priority ();
 
           /* the lock priority changed so we need to sort the lock list of the lock holder */
           list_remove (&blocked_lock->elem);
@@ -264,7 +264,7 @@ lock_acquire (struct lock *lock)
   cur->blocked_lock = NULL;
 
   /* the priority of this lock is our own priority */
-  lock->priority = cur->priority;
+  lock->priority = thread_get_priority ();
 
   /* save the locks we hold in descending order of their priority */
   list_insert_ordered (&lock->holder->locks, &lock->elem,
@@ -305,7 +305,7 @@ lock_release (struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
 
   lock->holder = NULL;
-  //lock->priority = we don't care as the next lock_acquire()-call does
+  //lock->priority = we don't care since 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 */
@@ -424,9 +424,9 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
      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);
+    list_sort (&cond->waiters, &semaphore_priority_cmp_greater, NULL);
+    sema_up (&list_entry (list_pop_front (&cond->waiters),
+          struct semaphore_elem, elem)->semaphore);
   }
 }
 
diff --git a/threads/thread.c b/threads/thread.c
index 61ab5d9..cf404b6 100644
--- a/threads/thread.c
+++ b/threads/thread.c
@@ -379,12 +379,26 @@ thread_set_priority (int new_priority)
 void
 thread_other_set_priority (struct thread *t, int new_priority)
 {
+  enum intr_level old_level;
+  bool yield = false;
+
   ASSERT (is_thread (t));
   ASSERT (new_priority >= PRI_MIN && new_priority <= PRI_MAX);
 
   if (t->priority == new_priority)
     return;
 
+  /* we need to disable interrupts here because after changing the thread's
+     priority and a possible timer interrupt which triggers thread_yield() we
+     could run into a couple of races. e.g. no proper sorted ready list,
+     corrupt ready list (wrong internal pointers) or the timer interrupt fires
+     after calling list_empty() but before list_front() while having only two
+     threads (one active, the other one ready). the scheduler then schedules the
+     other thread which runs and terminates, thus removing itself from all lists.
+     after that our thread gets scheduled again and reads from an empty list,
+     although it wasn't empty before. */
+  old_level = intr_disable ();
+
   t->priority = new_priority;
 
   if (t->status == THREAD_READY)
@@ -398,8 +412,13 @@ thread_other_set_priority (struct thread *t, int new_priority)
       /* 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 ();
+        yield = true;
     }
+
+  intr_set_level (old_level);
+
+  if (yield)
+    thread_yield ();
 }
 
 void