1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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 <gback@cs.vt.edu> */
#include <stdio.h>
#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
|
