From 9b19a84ed640cb15e6ca87ddc025c90d78a5fbdc Mon Sep 17 00:00:00 2001 From: manuel Date: Fri, 11 May 2012 20:48:58 +0200 Subject: * fix possible race in thread_set_priority * fill in same parts of proj1.txt * use thread_get_priority() whenever possible --- proj1.txt | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 50 insertions(+), 3 deletions(-) (limited to 'proj1.txt') 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? -- cgit v1.2.3