Add another test that checks priority scheduling in the case of

priority donation to a blocked thread.
Idea and code by Godmar Back.

diff --git a/doc/threads.texi b/doc/threads.texi
index 51b52f7abb95b80966d3dc684ecfeafaeed5ca5b..f5e60585f685a9b0e8f0779192bb6bff108abc57 100644 (file)
--- 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 21d3b8737d1634f858a4e319659cebdbcfe69b13..5a7b400493d916b08f0a4538de98cb89d2976242 100644 (file)
--- 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 242dace9a69c7dc8ac32d9b5e9d1b88df54ec399..87ba8728962216562fc245bae15f997e7cb3fbe0 100644 (file)
--- 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 (file)
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 (file)
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 26de74be5f81eaf950bbb23bded7d4c565debcb2..b4b12cdc0ac311e5ee9e70e74dd85c4486b1c025 100644 (file)
--- 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 93c61ec78c7cc6a03ddbcab4bd362b02f6579fdb..46d99f8828d27f92f622816c70819844d528f54c 100644 (file)
--- 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;