1 /* The main thread set its priority to PRI_MIN and creates 7 threads
2 (thread 1..7) with priorities PRI_MIN + 3, 6, 9, 12, ...
3 The main thread initializes 8 locks: lock 0..7 and acquires lock 0.
5 When thread[i] starts, it first acquires lock[i] (unless i == 7.)
6 Subsequently, thread[i] attempts to acquire lock[i-1], which is held by
7 thread[i-1], except for lock[0], which is held by the main thread.
8 Because the lock is held, thread[i] donates its priority to thread[i-1],
9 which donates to thread[i-2], and so on until the main thread
10 receives the donation.
12 After threads[1..7] have been created and are blocked on locks[0..7],
13 the main thread releases lock[0], unblocking thread[1], and being
15 Thread[1] then completes acquiring lock[0], then releases lock[0],
16 then releases lock[1], unblocking thread[2], etc.
17 Thread[7] finally acquires & releases lock[7] and exits, allowing
18 thread[6], then thread[5] etc. to run and exit until finally the
21 In addition, interloper threads are created at priority levels
22 p = PRI_MIN + 2, 5, 8, 11, ... which should not be run until the
23 corresponding thread with priority p + 1 has finished.
25 Written by Godmar Back <gback@cs.vt.edu> */
28 #include "tests/threads/tests.h"
29 #include "threads/init.h"
30 #include "threads/synch.h"
31 #include "threads/thread.h"
33 #define NESTING_DEPTH 8
41 static thread_func donor_thread_func;
42 static thread_func interloper_thread_func;
45 test_priority_donate_chain (void)
48 struct lock locks[NESTING_DEPTH - 1];
49 struct lock_pair lock_pairs[NESTING_DEPTH];
51 /* This test does not work with the MLFQS. */
52 ASSERT (!thread_mlfqs);
54 thread_set_priority (PRI_MIN);
56 for (i = 0; i < NESTING_DEPTH - 1; i++)
57 lock_init (&locks[i]);
59 lock_acquire (&locks[0]);
60 msg ("%s got lock.", thread_name ());
62 for (i = 1; i < NESTING_DEPTH; i++)
67 snprintf (name, sizeof name, "thread %d", i);
68 thread_priority = PRI_MIN + i * 3;
69 lock_pairs[i].first = i < NESTING_DEPTH - 1 ? locks + i: NULL;
70 lock_pairs[i].second = locks + i - 1;
72 thread_create (name, thread_priority, donor_thread_func, lock_pairs + i);
73 msg ("%s should have priority %d. Actual priority: %d.",
74 thread_name (), thread_priority, thread_get_priority ());
76 snprintf (name, sizeof name, "interloper %d", i);
77 thread_create (name, thread_priority - 1, interloper_thread_func, NULL);
80 lock_release (&locks[0]);
81 msg ("%s finishing with priority %d.", thread_name (),
82 thread_get_priority ());
86 donor_thread_func (void *locks_)
88 struct lock_pair *locks = locks_;
91 lock_acquire (locks->first);
93 lock_acquire (locks->second);
94 msg ("%s got lock", thread_name ());
96 lock_release (locks->second);
97 msg ("%s should have priority %d. Actual priority: %d",
98 thread_name (), (NESTING_DEPTH - 1) * 3,
99 thread_get_priority ());
102 lock_release (locks->first);
104 msg ("%s finishing with priority %d.", thread_name (),
105 thread_get_priority ());
109 interloper_thread_func (void *arg_ UNUSED)
111 msg ("%s finished.", thread_name ());