From edb2693ddd1f451e190a81da0ddda4df845fb246 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 17 May 2006 22:56:20 +0000 Subject: [PATCH] Add another test that checks priority scheduling in the case of priority donation to a blocked thread. Idea and code by Godmar Back. --- TODO | 27 -------- doc/threads.texi | 7 ++ src/tests/threads/Make.tests | 9 +-- src/tests/threads/Rubric.priority | 13 ++-- src/tests/threads/priority-donate-sema.c | 82 +++++++++++++++++++++++ src/tests/threads/priority-donate-sema.ck | 15 +++++ src/tests/threads/tests.c | 1 + src/tests/threads/tests.h | 1 + 8 files changed, 118 insertions(+), 37 deletions(-) create mode 100644 src/tests/threads/priority-donate-sema.c create mode 100644 src/tests/threads/priority-donate-sema.ck diff --git a/TODO b/TODO index dbafb18..53a7060 100644 --- a/TODO +++ b/TODO @@ -26,33 +26,6 @@ Add a system call "get_kernel_memory_information". User programs could engage in a variety of activities and notice leaks by checking the kernel memory statistics. ---- - -From: "Godmar Back" -Subject: priority donation tests -To: "Ben Pfaff" -Date: Fri, 3 Mar 2006 11:02:08 -0500 - -Ben, - -it seems the priority donation tests are somewhat incomplete and allow -incorrect implementations to pass with a perfect score. - -We are seeing the following wrong implementations pass all tests: - -- Implementations that assume that the priority of a thread waiting on -a semaphore or condition variable cannot change between when the -thread was blocked and when it is unblocked. The students implement -this by doing an insert into an ordered list on block, rather than -picking the maximum thread on unblock. - -Neither of these two cases is detected; do you currently check for -these mistakes manually? - -I also wrote a test case for the second scenario: -http://people.cs.vt.edu/~gback/pintos/priority-donate-sema.c -http://people.cs.vt.edu/~gback/pintos/priority-donate-sema.ck - From: "Godmar Back" Subject: multiple threads waking up at same clock tick To: "Ben Pfaff" diff --git a/doc/threads.texi b/doc/threads.texi index 51b52f7..f5e6058 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -697,6 +697,13 @@ priority to @var{L}. @var{L} releases the lock and thus loses the CPU and is moved to the ready queue. Now @var{L}'s old priority is restored while it is in the ready queue. +@item Can a thread's priority change while it is blocked? + +Yes. While a thread that has acquired lock @var{L} is blocked for any +reason, its priority can increase by priority donation if a +higher-priority thread attempts to acquire @var{L}. This case is +checked by the @code{priority-donate-sema} test. + @item Can a thread added to the ready list preempt the processor? Yes. If a thread added to the ready list has higher priority than the diff --git a/src/tests/threads/Make.tests b/src/tests/threads/Make.tests index 21d3b87..5a7b400 100644 --- a/src/tests/threads/Make.tests +++ b/src/tests/threads/Make.tests @@ -4,10 +4,10 @@ tests/threads_TESTS = $(addprefix tests/threads/,alarm-single \ alarm-multiple alarm-priority alarm-zero alarm-negative \ priority-change priority-donate-one priority-donate-multiple \ -priority-donate-multiple2 \ -priority-donate-nest priority-fifo priority-preempt priority-sema \ -priority-condvar mlfqs-load-1 mlfqs-load-60 mlfqs-load-avg \ -mlfqs-recent-1 mlfqs-fair-2 mlfqs-fair-20 mlfqs-nice-2 mlfqs-nice-10) +priority-donate-multiple2 priority-donate-nest priority-donate-sema \ +priority-fifo priority-preempt priority-sema priority-condvar \ +mlfqs-load-1 mlfqs-load-60 mlfqs-load-avg mlfqs-recent-1 mlfqs-fair-2 \ +mlfqs-fair-20 mlfqs-nice-2 mlfqs-nice-10) # Sources for tests. tests/threads_SRC = tests/threads/tests.c @@ -20,6 +20,7 @@ tests/threads_SRC += tests/threads/priority-donate-one.c tests/threads_SRC += tests/threads/priority-donate-multiple.c tests/threads_SRC += tests/threads/priority-donate-multiple2.c tests/threads_SRC += tests/threads/priority-donate-nest.c +tests/threads_SRC += tests/threads/priority-donate-sema.c tests/threads_SRC += tests/threads/priority-fifo.c tests/threads_SRC += tests/threads/priority-preempt.c tests/threads_SRC += tests/threads/priority-sema.c diff --git a/src/tests/threads/Rubric.priority b/src/tests/threads/Rubric.priority index 242dace..87ba872 100644 --- a/src/tests/threads/Rubric.priority +++ b/src/tests/threads/Rubric.priority @@ -1,10 +1,11 @@ Functionality of priority scheduler: -4 priority-preempt -4 priority-donate-one -4 priority-donate-multiple -4 priority-donate-multiple2 -4 priority-donate-nest -4 priority-change +3 priority-preempt +3 priority-donate-one +3 priority-donate-multiple +3 priority-donate-multiple2 +3 priority-donate-nest +3 priority-donate-sema +3 priority-change 3 priority-fifo 3 priority-sema diff --git a/src/tests/threads/priority-donate-sema.c b/src/tests/threads/priority-donate-sema.c new file mode 100644 index 0000000..89fd93d --- /dev/null +++ b/src/tests/threads/priority-donate-sema.c @@ -0,0 +1,82 @@ +/* Low priority thread L acquires a lock, then blocks downing a + semaphore. Medium priority thread M then blocks waiting on + the same semaphore. Next, high priority thread H attempts to + acquire the lock, donating its priority to L. + + Next, the main thread ups the semaphore, waking up L. L + releases the lock, which wakes up H. H "up"s the semaphore, + waking up M. H terminates, then M, then L, and finally the + main thread. + + Written by Godmar Back . */ + +#include +#include "tests/threads/tests.h" +#include "threads/init.h" +#include "threads/synch.h" +#include "threads/thread.h" + +struct lock_and_sema + { + struct lock lock; + struct semaphore sema; + }; + +static thread_func l_thread_func; +static thread_func m_thread_func; +static thread_func h_thread_func; + +void +test_priority_donate_sema (void) +{ + struct lock_and_sema ls; + + /* This test does not work with the MLFQS. */ + ASSERT (!enable_mlfqs); + + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + lock_init (&ls.lock); + sema_init (&ls.sema, 0); + thread_create ("low", PRI_DEFAULT + 1, l_thread_func, &ls); + thread_create ("med", PRI_DEFAULT + 3, m_thread_func, &ls); + thread_create ("high", PRI_DEFAULT + 5, h_thread_func, &ls); + sema_up (&ls.sema); + msg ("Main thread finished."); +} + +static void +l_thread_func (void *ls_) +{ + struct lock_and_sema *ls = ls_; + + lock_acquire (&ls->lock); + msg ("Thread L acquired lock."); + sema_down (&ls->sema); + msg ("Thread L downed semaphore."); + lock_release (&ls->lock); + msg ("Thread L finished."); +} + +static void +m_thread_func (void *ls_) +{ + struct lock_and_sema *ls = ls_; + + sema_down (&ls->sema); + msg ("Thread M finished."); +} + +static void +h_thread_func (void *ls_) +{ + struct lock_and_sema *ls = ls_; + + lock_acquire (&ls->lock); + msg ("Thread H acquired lock."); + + sema_up (&ls->sema); + lock_release (&ls->lock); + msg ("Thread H finished."); +} diff --git a/src/tests/threads/priority-donate-sema.ck b/src/tests/threads/priority-donate-sema.ck new file mode 100644 index 0000000..904dbc1 --- /dev/null +++ b/src/tests/threads/priority-donate-sema.ck @@ -0,0 +1,15 @@ +# -*- perl -*- +use strict; +use warnings; +use tests::tests; +check_expected ([<<'EOF']); +(priority-donate-sema) begin +(priority-donate-sema) Thread L acquired lock. +(priority-donate-sema) Thread L downed semaphore. +(priority-donate-sema) Thread H acquired lock. +(priority-donate-sema) Thread H finished. +(priority-donate-sema) Thread M finished. +(priority-donate-sema) Thread L finished. +(priority-donate-sema) Main thread finished. +(priority-donate-sema) end +EOF diff --git a/src/tests/threads/tests.c b/src/tests/threads/tests.c index 26de74b..b4b12cd 100644 --- a/src/tests/threads/tests.c +++ b/src/tests/threads/tests.c @@ -21,6 +21,7 @@ static const struct test tests[] = {"priority-donate-multiple", test_priority_donate_multiple}, {"priority-donate-multiple2", test_priority_donate_multiple2}, {"priority-donate-nest", test_priority_donate_nest}, + {"priority-donate-sema", test_priority_donate_sema}, {"priority-fifo", test_priority_fifo}, {"priority-preempt", test_priority_preempt}, {"priority-sema", test_priority_sema}, diff --git a/src/tests/threads/tests.h b/src/tests/threads/tests.h index 93c61ec..46d99f8 100644 --- a/src/tests/threads/tests.h +++ b/src/tests/threads/tests.h @@ -14,6 +14,7 @@ extern test_func test_priority_change; extern test_func test_priority_donate_one; extern test_func test_priority_donate_multiple; extern test_func test_priority_donate_multiple2; +extern test_func test_priority_donate_sema; extern test_func test_priority_donate_nest; extern test_func test_priority_fifo; extern test_func test_priority_preempt; -- 2.30.2