+--------------------+ | CS 140 | | PROJECT 1: THREADS | | DESIGN DOCUMENT | +--------------------+ ---- GROUP ---- >> Fill in the names and email addresses of your group members. Peter Ketscher Karoline Knoth Manuel Mausz ---- PRELIMINARIES ---- >> If you have any preliminary comments on your submission, notes for the >> TAs, or extra credit, please give them here. >> Please cite any offline or online sources you consulted while >> preparing your submission, other than the Pintos documentation, course >> text, lecture notes, and course staff. Stallings, W. - Operating Systems http://en.wikipedia.org/wiki/Priority_inversion http://hynek.me/studies/sched_ausarbeitung.pdf PRIORITY SCHEDULING =================== ---- DATA STRUCTURES ---- >> B1: Copy here the declaration of each new or changed `struct' or >> `struct' member, global or static variable, `typedef', or >> 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 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: 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: struct thread *thread ...the current waiting thread >> B2: Explain the data structure used to track priority donation. >> Use ASCII art to diagram a nested donation. (Alternately, submit a >> .png file.) 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? 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? 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 >> 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? 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 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 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. SURVEY QUESTIONS ================ Answering these questions is optional, but it will help us improve the course in future quarters. Feel free to tell us anything you want--these questions are just to spur your thoughts. You may also choose to respond anonymously in the course evaluations at the end of 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? >> Is there some particular fact or hint we should give students in >> 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? >> Any other comments?