From 2791793b038dec7e3365d6570bff5c3afaaa188c Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
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.
---
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 +
7 files changed, 118 insertions(+), 10 deletions(-)
create mode 100644 src/tests/threads/priority-donate-sema.c
create mode 100644 src/tests/threads/priority-donate-sema.ck
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 <gback@cs.vt.edu>. */
+
+#include <stdio.h>
+#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