* fix possible race in thread_set_priority

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

1 files changed, 50 insertions, 3 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?