From d9e0c55d118d0a3923b440b7811f8d1d6db9e1d7 Mon Sep 17 00:00:00 2001 From: manuel Date: Sun, 13 May 2012 18:30:41 +0200 Subject: fill in the missing questions of proj1.txt --- proj1.txt | 126 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 113 insertions(+), 13 deletions(-) (limited to 'proj1.txt') 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. -- cgit v1.2.3