From 0eb663f85c834786c5b98186bb55a3e3224b8a2f Mon Sep 17 00:00:00 2001 From: Godmar Back Date: Sat, 6 Jan 2007 19:00:52 +0000 Subject: [PATCH] - added priority-donate-chain test which tests 8-level deep nested donation - adjusted weights for P1 Grading file --- src/tests/threads/Grading | 6 +- src/tests/threads/Make.tests | 2 + src/tests/threads/Rubric.priority | 12 ++- src/tests/threads/priority-donate-chain.c | 114 +++++++++++++++++++++ src/tests/threads/priority-donate-chain.ck | 46 +++++++++ src/tests/threads/tests.c | 1 + src/tests/threads/tests.h | 1 + 7 files changed, 174 insertions(+), 8 deletions(-) create mode 100644 src/tests/threads/priority-donate-chain.c create mode 100644 src/tests/threads/priority-donate-chain.ck diff --git a/src/tests/threads/Grading b/src/tests/threads/Grading index 88a4923..c9be35f 100644 --- a/src/tests/threads/Grading +++ b/src/tests/threads/Grading @@ -1,6 +1,6 @@ # Percentage of the testing point total designated for each set of # tests. -33.3% tests/threads/Rubric.alarm -33.3% tests/threads/Rubric.priority -33.4% tests/threads/Rubric.mlfqs +20.0% tests/threads/Rubric.alarm +40.0% tests/threads/Rubric.priority +40.0% tests/threads/Rubric.mlfqs diff --git a/src/tests/threads/Make.tests b/src/tests/threads/Make.tests index 0a270e2..4569035 100644 --- a/src/tests/threads/Make.tests +++ b/src/tests/threads/Make.tests @@ -7,6 +7,7 @@ alarm-negative priority-change priority-donate-one \ priority-donate-multiple priority-donate-multiple2 \ priority-donate-nest priority-donate-sema priority-donate-lower \ priority-fifo priority-preempt priority-sema priority-condvar \ +priority-donate-chain \ mlfqs-load-1 mlfqs-load-60 mlfqs-load-avg mlfqs-recent-1 mlfqs-fair-2 \ mlfqs-fair-20 mlfqs-nice-2 mlfqs-nice-10 mlfqs-block) @@ -28,6 +29,7 @@ tests/threads_SRC += tests/threads/priority-fifo.c tests/threads_SRC += tests/threads/priority-preempt.c tests/threads_SRC += tests/threads/priority-sema.c tests/threads_SRC += tests/threads/priority-condvar.c +tests/threads_SRC += tests/threads/priority-donate-chain.c tests/threads_SRC += tests/threads/mlfqs-load-1.c tests/threads_SRC += tests/threads/mlfqs-load-60.c tests/threads_SRC += tests/threads/mlfqs-load-avg.c diff --git a/src/tests/threads/Rubric.priority b/src/tests/threads/Rubric.priority index e8ee82c..652bc99 100644 --- a/src/tests/threads/Rubric.priority +++ b/src/tests/threads/Rubric.priority @@ -1,13 +1,15 @@ Functionality of priority scheduler: +3 priority-change 3 priority-preempt + +3 priority-fifo +3 priority-sema +3 priority-condvar + 3 priority-donate-one 3 priority-donate-multiple 3 priority-donate-multiple2 3 priority-donate-nest +5 priority-donate-chain 3 priority-donate-sema 3 priority-donate-lower -3 priority-change - -3 priority-fifo -3 priority-sema -3 priority-condvar diff --git a/src/tests/threads/priority-donate-chain.c b/src/tests/threads/priority-donate-chain.c new file mode 100644 index 0000000..3ffabca --- /dev/null +++ b/src/tests/threads/priority-donate-chain.c @@ -0,0 +1,114 @@ +/* The main thread set its priority to PRI_MIN and creates 7 threads + (thread 1..7) with priorities PRI_MIN + 3, 6, 9, 12, ... + The main thread initializes 8 locks: lock 0..7 and acquires lock 0. + + When thread[i] starts, it first acquires lock[i] (unless i == 7.) + Subsequently, thread[i] attempts to acquire lock[i-1], which is held by + thread[i-1], except for lock[0], which is held by the main thread. + Because the lock is held, thread[i] donates its priority to thread[i-1], + which donates to thread[i-2], and so on until the main thread + receives the donation. + + After threads[1..7] have been created and are blocked on locks[0..7], + the main thread releases lock[0], unblocking thread[1], and being + preempted by it. + Thread[1] then completes acquiring lock[0], then releases lock[0], + then releases lock[1], unblocking thread[2], etc. + Thread[7] finally acquires & releases lock[7] and exits, allowing + thread[6], then thread[5] etc. to run and exit until finally the + main thread exits. + + In addition, interloper threads are created at priority levels + p = PRI_MIN + 2, 5, 8, 11, ... which should not be run until the + corresponding thread with priority p + 1 has finished. + + Written by Godmar Back */ + +#include +#include "tests/threads/tests.h" +#include "threads/init.h" +#include "threads/synch.h" +#include "threads/thread.h" + +#define NESTING_DEPTH 8 + +struct lock_pair + { + struct lock *second; + struct lock *first; + }; + +static thread_func donor_thread_func; +static thread_func interloper_thread_func; + +void +test_priority_donate_chain (void) +{ + int i; + struct lock locks[NESTING_DEPTH - 1]; + struct lock_pair lock_pairs[NESTING_DEPTH]; + + /* This test does not work with the MLFQS. */ + ASSERT (!thread_mlfqs); + + thread_set_priority (PRI_MIN); + + for (i = 0; i < NESTING_DEPTH - 1; i++) + lock_init (&locks[i]); + + lock_acquire (&locks[0]); + msg ("%s got lock.", thread_name ()); + + for (i = 1; i < NESTING_DEPTH; i++) + { + char name[16]; + int thread_priority; + + snprintf (name, sizeof name, "thread %d", i); + thread_priority = PRI_MIN + i * 3; + lock_pairs[i].first = i < NESTING_DEPTH - 1 ? locks + i: NULL; + lock_pairs[i].second = locks + i - 1; + + thread_create (name, thread_priority, donor_thread_func, lock_pairs + i); + msg ("%s should have priority %d. Actual priority: %d.", + thread_name (), thread_priority, thread_get_priority ()); + + snprintf (name, sizeof name, "interloper %d", i); + thread_create (name, thread_priority - 1, interloper_thread_func, NULL); + } + + lock_release (&locks[0]); + msg ("%s finishing with priority %d.", thread_name (), + thread_get_priority ()); +} + +static void +donor_thread_func (void *locks_) +{ + struct lock_pair *locks = locks_; + + if (locks->first) + lock_acquire (locks->first); + + lock_acquire (locks->second); + msg ("%s got lock", thread_name ()); + + lock_release (locks->second); + msg ("%s should have priority %d. Actual priority: %d", + thread_name (), (NESTING_DEPTH - 1) * 3, + thread_get_priority ()); + + if (locks->first) + lock_release (locks->first); + + msg ("%s finishing with priority %d.", thread_name (), + thread_get_priority ()); +} + +static void +interloper_thread_func (void *arg_ UNUSED) +{ + msg ("%s finished.", thread_name ()); +} + +// vim: sw=2 diff --git a/src/tests/threads/priority-donate-chain.ck b/src/tests/threads/priority-donate-chain.ck new file mode 100644 index 0000000..213e649 --- /dev/null +++ b/src/tests/threads/priority-donate-chain.ck @@ -0,0 +1,46 @@ +# -*- perl -*- +use strict; +use warnings; +use tests::tests; +check_expected ([<<'EOF']); +(priority-donate-chain) begin +(priority-donate-chain) main got lock. +(priority-donate-chain) main should have priority 3. Actual priority: 3. +(priority-donate-chain) main should have priority 6. Actual priority: 6. +(priority-donate-chain) main should have priority 9. Actual priority: 9. +(priority-donate-chain) main should have priority 12. Actual priority: 12. +(priority-donate-chain) main should have priority 15. Actual priority: 15. +(priority-donate-chain) main should have priority 18. Actual priority: 18. +(priority-donate-chain) main should have priority 21. Actual priority: 21. +(priority-donate-chain) thread 1 got lock +(priority-donate-chain) thread 1 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 2 got lock +(priority-donate-chain) thread 2 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 3 got lock +(priority-donate-chain) thread 3 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 4 got lock +(priority-donate-chain) thread 4 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 5 got lock +(priority-donate-chain) thread 5 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 6 got lock +(priority-donate-chain) thread 6 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 7 got lock +(priority-donate-chain) thread 7 should have priority 21. Actual priority: 21 +(priority-donate-chain) thread 7 finishing with priority 21. +(priority-donate-chain) interloper 7 finished. +(priority-donate-chain) thread 6 finishing with priority 18. +(priority-donate-chain) interloper 6 finished. +(priority-donate-chain) thread 5 finishing with priority 15. +(priority-donate-chain) interloper 5 finished. +(priority-donate-chain) thread 4 finishing with priority 12. +(priority-donate-chain) interloper 4 finished. +(priority-donate-chain) thread 3 finishing with priority 9. +(priority-donate-chain) interloper 3 finished. +(priority-donate-chain) thread 2 finishing with priority 6. +(priority-donate-chain) interloper 2 finished. +(priority-donate-chain) thread 1 finishing with priority 3. +(priority-donate-chain) interloper 1 finished. +(priority-donate-chain) main finishing with priority 0. +(priority-donate-chain) end +EOF +pass; diff --git a/src/tests/threads/tests.c b/src/tests/threads/tests.c index 3f0327f..af15aee 100644 --- a/src/tests/threads/tests.c +++ b/src/tests/threads/tests.c @@ -24,6 +24,7 @@ static const struct test tests[] = {"priority-donate-nest", test_priority_donate_nest}, {"priority-donate-sema", test_priority_donate_sema}, {"priority-donate-lower", test_priority_donate_lower}, + {"priority-donate-chain", test_priority_donate_chain}, {"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 81e9663..cd9d489 100644 --- a/src/tests/threads/tests.h +++ b/src/tests/threads/tests.h @@ -18,6 +18,7 @@ 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_donate_lower; +extern test_func test_priority_donate_chain; extern test_func test_priority_fifo; extern test_func test_priority_preempt; extern test_func test_priority_sema; -- 2.30.2