fill in the missing questions of proj1.txtproj1

1 files changed, 113 insertions, 13 deletions

diff --git a/proj1.txt b/proj1.txt
index 0cb22e1..03c61f0 100644
--- a/proj1.txt
+++ b/proj1.txt
@@ -54,23 +54,123 @@ struct semaphore_elem:
 >> Use ASCII art to diagram a nested donation.  (Alternately, submit a
 >> .png file.)
 
-TODO
+In case a priority gets donated to a thread we store the origin/base priority
+in the variable "saved_priority" inside the structure of the thread itself.
+Additional we flip the boolean variable "is_donated".
+For multiple priority donations we store the maximum donated priority to a lock
+inside the structure of a lock. Additional we store an ordered list of locks a
+thread is currently holding. This combination allows us to donate a priority to
+a lock and alter the holders priority. In case this lock gets released we either
+restore the holder's base/origin priority (if the lock list is empty) or change
+the holder's priority to highest priority donated by the locks the thread still
+holds (the lock list is not empty). See B5 for additional information.
+
+For nested priority donation we additional store a pointer to the lock the
+thread is waiting on ("blocked_lock"). We then walk recursively from the current
+lock to the lock the holder of the current lock is waiting on and at the same
+time donate the thread's priority to the occurring holders. The loop ends as
+soon as no holder of a lock in this chain is waiting on another lock. See B4 for
+additional information.
+
+Nested donation example:
+* 3 threads with different priority
+* 2 locks
+* L holds lock A
+* M holds lock B and is waiting on lock A
+* H is waiting on lock B
+
+ _____
+|     |              Legend:
+|  L  |              x ...thread holds lock
+|_____|              o ...thread is waiting on lock
+   |
+/--|---------------------------\
+|  x     o             Lock A  |
+\--------|---------------------/
+       __|__
+      |     |
+      |  M  |
+      |_____|
+         |
+/--------|---------------------\
+|        x     o       Lock B  |
+\--------------|---------------/
+             __|__
+            |     |
+            |  H  |
+            |_____|
+
+L.locks = [A]
+L.blocked_lock = NULL
+M.locks = [B]
+M.blocked_lock = A
+H.locks = []
+H.blocked_lock = B
+
+H enters the nested priority loop and donates its priority to
+H.blocked_lock.holder (=M):
+=> M.priority = H
+
+H donates its priority to M.blocked_lock.holder (=L):
+=> L.priority = H
+
+Loop ends as L.blocked_lock is NULL
 
 ---- ALGORITHMS ----
 
 >> B3: How do you ensure that the highest priority thread waiting for
 >> a lock, semaphore, or condition variable wakes up first?
 
-TODO
+We use list_sort() inside sema_up() to sort the list of blocked/waiting threads
+by their priority. Afterwards we unblock the first thread in the list which is
+the thread with the highest priority.
+This ensures working locks as well (lock implementation uses semaphores).
+
+For conditions the list of blocked/waiting threads consists of elements of the
+structure semaphore_elem which itself contains a semaphore. In order to sort
+this list by the thread's priority we simply added a pointer pointing to the
+thread structure owning the element in the list. Just as in sema_up() we use
+list_sort() inside cond_signal() to sort the list and unblock the thread with
+the highest priority.
+
+See B7 for a reason why used list_sort() instead of list_insert_ordered().
 
 >> B4: Describe the sequence of events when a call to lock_acquire()
 >> causes a priority donation.  How is nested donation handled?
 
-TODO
+In lock_acquire() we first check if the lock is already held by another thread.
+In case there is a holder we check for a possible priority donation by comparing
+the thread's priority with the priority of the lock which is the same value as
+the current priority of the holder.
+We need this additional priority variable per lock because a thread may hold
+multiple locks which could donate any number of priorities to this thread.
+As soon as the thread releases one of these locks we need to change the thread's
+priority to the highest (donated) priority of the other locks the thread still
+holds. See B5 on how we accomplish this.
+
+For nested priority donation we not only have to donate the thread's priority to
+the holder of the lock the thread currently is waiting on but also have to look
+into the depth if the holder itself is waiting on another lock too. This
+lookup/recursion continues until a thread holding a lock in the chain isn't
+waiting on another lock (blocked_lock isn't set).
+For every lock in this chain we donate the priority of the current thread to
+their holder.
 
 >> B5: Describe the sequence of events when lock_release() is called
 >> on a lock that a higher-priority thread is waiting for.
 
+In order to handle multiple priority donations to the same lock we not only
+store the currently donated priority inside the lock structure (as already
+described in B4) but also a list of currently held locks of a thread. This list
+is ordered by the locks priority. In lock_release() we first check if this
+ordered lock list is empty and then call thread_donation_pass_back() which
+restores the origin priority of the thread.
+In case the list is not empty we simply retreive the first lock and change the
+thread's current priority to the priority of the lock. This is accomplished by
+calling thread_other_set_priority() which yields the cpu in case the new
+priority is lower than the priority of the thread with the highest priority in
+the ready list.
+
 ---- SYNCHRONIZATION ----
 
 >> B6: Describe a potential race in thread_set_priority() and explain
@@ -80,13 +180,13 @@ TODO
 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
+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)
+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
+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
+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
@@ -98,18 +198,18 @@ conventions and would rather be a lot more cpu intensive.
 >> 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
+Actually 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 locks our design only consumes little cpu
+instructions because we sort the list of locks by their donated priority upon
+insertion and whenever a donated priority changes. This allows us to retrieve
+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
+blocked/waiting threads on 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.