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 ++++++++++++++++++++++++++++++++++++++++++++++++++--- threads/synch.c | 16 ++++++++-------- threads/thread.c | 21 ++++++++++++++++++++- 3 files changed, 78 insertions(+), 12 deletions(-) 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? diff --git a/threads/synch.c b/threads/synch.c index 98905b1..a1b7549 100644 --- a/threads/synch.c +++ b/threads/synch.c @@ -128,7 +128,7 @@ sema_up (struct semaphore *sema) list_sort (&sema->waiters, &thread_priority_cmp_greater, NULL); struct thread *t = list_entry (list_pop_front (&sema->waiters), struct thread, elem); /* thread_unblock() doesn't yield so check if there's a need */ - if (t->priority > thread_current ()->priority) + if (t->priority > thread_get_priority ()) yield = true; thread_unblock (t); } @@ -240,10 +240,10 @@ lock_acquire (struct lock *lock) while (blocked_lock != NULL && blocked_lock->holder != NULL) { /* check for a possible priority donation */ - if (cur->priority > blocked_lock->priority) + if (thread_get_priority () > blocked_lock->priority) { /* the new priority of this lock is our own priority */ - blocked_lock->priority = cur->priority; + blocked_lock->priority = thread_get_priority (); /* the lock priority changed so we need to sort the lock list of the lock holder */ list_remove (&blocked_lock->elem); @@ -264,7 +264,7 @@ lock_acquire (struct lock *lock) cur->blocked_lock = NULL; /* the priority of this lock is our own priority */ - lock->priority = cur->priority; + lock->priority = thread_get_priority (); /* save the locks we hold in descending order of their priority */ list_insert_ordered (&lock->holder->locks, &lock->elem, @@ -305,7 +305,7 @@ lock_release (struct lock *lock) ASSERT (lock_held_by_current_thread (lock)); lock->holder = NULL; - //lock->priority = we don't care as the next lock_acquire()-call does + //lock->priority = we don't care since the next lock_acquire()-call does sema_up (&lock->semaphore); /* we don't hold the lock any longer so remove it from the lock list */ @@ -424,9 +424,9 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED) this is the same as with sema_down()/sema_up() */ if (!list_empty (&cond->waiters)) { - list_sort (&cond->waiters, &semaphore_priority_cmp_greater, NULL); - sema_up (&list_entry (list_pop_front (&cond->waiters), - struct semaphore_elem, elem)->semaphore); + list_sort (&cond->waiters, &semaphore_priority_cmp_greater, NULL); + sema_up (&list_entry (list_pop_front (&cond->waiters), + struct semaphore_elem, elem)->semaphore); } } diff --git a/threads/thread.c b/threads/thread.c index 61ab5d9..cf404b6 100644 --- a/threads/thread.c +++ b/threads/thread.c @@ -379,12 +379,26 @@ thread_set_priority (int new_priority) void thread_other_set_priority (struct thread *t, int new_priority) { + enum intr_level old_level; + bool yield = false; + ASSERT (is_thread (t)); ASSERT (new_priority >= PRI_MIN && new_priority <= PRI_MAX); if (t->priority == new_priority) return; + /* we need to disable interrupts here because after changing the thread's + priority and a possible timer interrupt which triggers thread_yield() we + could run into a couple of races. 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 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. */ + old_level = intr_disable (); + t->priority = new_priority; if (t->status == THREAD_READY) @@ -398,8 +412,13 @@ thread_other_set_priority (struct thread *t, int new_priority) /* compare priority with the highest priority in the list */ struct thread *t2 = list_entry (list_front (&ready_list), struct thread, elem); if (t2->priority > t->priority) - thread_yield (); + yield = true; } + + intr_set_level (old_level); + + if (yield) + thread_yield (); } void -- cgit v1.2.3