+--------------------+ | 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.) 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. ---- 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? 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 ================ 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?