From e373cd64cfe799b3cb148e1117f3b3184b5a6457 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 17 May 2006 22:07:27 +0000 Subject: [PATCH] Add another test that locks & unlocks in FIFO order instead of stack order, to catch more bugs. Idea and code by Godmar Back. --- TODO | 13 --- src/tests/threads/Make.tests | 2 + src/tests/threads/Rubric.priority | 11 +-- src/tests/threads/priority-donate-multiple2.c | 90 +++++++++++++++++++ .../threads/priority-donate-multiple2.ck | 18 ++++ src/tests/threads/tests.c | 1 + src/tests/threads/tests.h | 1 + 7 files changed, 118 insertions(+), 18 deletions(-) create mode 100644 src/tests/threads/priority-donate-multiple2.c create mode 100644 src/tests/threads/priority-donate-multiple2.ck diff --git a/TODO b/TODO index 522847a..dbafb18 100644 --- a/TODO +++ b/TODO @@ -40,10 +40,6 @@ incorrect implementations to pass with a perfect score. We are seeing the following wrong implementations pass all tests: -- Implementations that assume locks are released in the opposite order -in which they're acquired. The students implement this by -popping/pushing on the donation list. - - 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 @@ -53,19 +49,10 @@ picking the maximum thread on unblock. Neither of these two cases is detected; do you currently check for these mistakes manually? -I wrote a test that checks for the first case; it is here: -http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple-2.patch - -[...] - 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 -I put the other tests up here: -http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple2.c -http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple2.ck - From: "Godmar Back" Subject: multiple threads waking up at same clock tick To: "Ben Pfaff" diff --git a/src/tests/threads/Make.tests b/src/tests/threads/Make.tests index d59d5c4..21d3b87 100644 --- a/src/tests/threads/Make.tests +++ b/src/tests/threads/Make.tests @@ -4,6 +4,7 @@ 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) @@ -17,6 +18,7 @@ tests/threads_SRC += tests/threads/alarm-negative.c tests/threads_SRC += tests/threads/priority-change.c 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-fifo.c tests/threads_SRC += tests/threads/priority-preempt.c diff --git a/src/tests/threads/Rubric.priority b/src/tests/threads/Rubric.priority index 819885b..242dace 100644 --- a/src/tests/threads/Rubric.priority +++ b/src/tests/threads/Rubric.priority @@ -1,9 +1,10 @@ Functionality of priority scheduler: -5 priority-preempt -5 priority-donate-one -5 priority-donate-multiple -5 priority-donate-nest -5 priority-change +4 priority-preempt +4 priority-donate-one +4 priority-donate-multiple +4 priority-donate-multiple2 +4 priority-donate-nest +4 priority-change 3 priority-fifo 3 priority-sema diff --git a/src/tests/threads/priority-donate-multiple2.c b/src/tests/threads/priority-donate-multiple2.c new file mode 100644 index 0000000..a9e0dd5 --- /dev/null +++ b/src/tests/threads/priority-donate-multiple2.c @@ -0,0 +1,90 @@ +/* The main thread acquires locks A and B, then it creates three + higher-priority threads. The first two of these threads block + acquiring one of the locks and thus donate their priority to + the main thread. The main thread releases the locks in turn + and relinquishes its donated priorities, allowing the third thread + to run. + + In this test, the main thread releases the locks in a different + order compared to priority-donate-multiple.c. + + Written by Godmar Back . + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by Matt Franklin , + Greg Hutchins , Yu Ping Hu + . Modified by arens. */ + +#include +#include "tests/threads/tests.h" +#include "threads/init.h" +#include "threads/synch.h" +#include "threads/thread.h" + +static thread_func a_thread_func; +static thread_func b_thread_func; +static thread_func c_thread_func; + +void +test_priority_donate_multiple2 (void) +{ + struct lock a, b; + + /* 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 (&a); + lock_init (&b); + + lock_acquire (&a); + lock_acquire (&b); + + thread_create ("a", PRI_DEFAULT + 3, a_thread_func, &a); + msg ("Main thread should have priority %d. Actual priority: %d.", + PRI_DEFAULT + 3, thread_get_priority ()); + + thread_create ("c", PRI_DEFAULT + 1, c_thread_func, NULL); + + thread_create ("b", PRI_DEFAULT + 5, b_thread_func, &b); + msg ("Main thread should have priority %d. Actual priority: %d.", + PRI_DEFAULT + 5, thread_get_priority ()); + + lock_release (&a); + msg ("Main thread should have priority %d. Actual priority: %d.", + PRI_DEFAULT + 5, thread_get_priority ()); + + lock_release (&b); + msg ("Threads b, a, c should have just finished, in that order."); + msg ("Main thread should have priority %d. Actual priority: %d.", + PRI_DEFAULT, thread_get_priority ()); +} + +static void +a_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + msg ("Thread a acquired lock a."); + lock_release (lock); + msg ("Thread a finished."); +} + +static void +b_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + msg ("Thread b acquired lock b."); + lock_release (lock); + msg ("Thread b finished."); +} + +static void +c_thread_func (void *a_ UNUSED) +{ + msg ("Thread c finished."); +} diff --git a/src/tests/threads/priority-donate-multiple2.ck b/src/tests/threads/priority-donate-multiple2.ck new file mode 100644 index 0000000..3855afd --- /dev/null +++ b/src/tests/threads/priority-donate-multiple2.ck @@ -0,0 +1,18 @@ +# -*- perl -*- +use strict; +use warnings; +use tests::tests; +check_expected ([<<'EOF']); +(priority-donate-multiple2) begin +(priority-donate-multiple2) Main thread should have priority 34. Actual priority: 34. +(priority-donate-multiple2) Main thread should have priority 36. Actual priority: 36. +(priority-donate-multiple2) Main thread should have priority 36. Actual priority: 36. +(priority-donate-multiple2) Thread b acquired lock b. +(priority-donate-multiple2) Thread b finished. +(priority-donate-multiple2) Thread a acquired lock a. +(priority-donate-multiple2) Thread a finished. +(priority-donate-multiple2) Thread c finished. +(priority-donate-multiple2) Threads b, a, c should have just finished, in that order. +(priority-donate-multiple2) Main thread should have priority 31. Actual priority: 31. +(priority-donate-multiple2) end +EOF diff --git a/src/tests/threads/tests.c b/src/tests/threads/tests.c index 07a32e4..26de74b 100644 --- a/src/tests/threads/tests.c +++ b/src/tests/threads/tests.c @@ -19,6 +19,7 @@ static const struct test tests[] = {"priority-change", test_priority_change}, {"priority-donate-one", test_priority_donate_one}, {"priority-donate-multiple", test_priority_donate_multiple}, + {"priority-donate-multiple2", test_priority_donate_multiple2}, {"priority-donate-nest", test_priority_donate_nest}, {"priority-fifo", test_priority_fifo}, {"priority-preempt", test_priority_preempt}, diff --git a/src/tests/threads/tests.h b/src/tests/threads/tests.h index bbe9adb..93c61ec 100644 --- a/src/tests/threads/tests.h +++ b/src/tests/threads/tests.h @@ -13,6 +13,7 @@ extern test_func test_alarm_negative; 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_nest; extern test_func test_priority_fifo; extern test_func test_priority_preempt; -- 2.30.2