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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
Projekt 1 - Threads
===================
alarm clock
-----------
The simplest strategy is to maintain a wait list for
all threads blocked for sleep.
* In 'timer_interrupt', check for threads which can be
unblocked from sleeping
* In 'sleep', set sleep timeout in thread, block the
thread and put it on the sleep list
Notes:
* There are three places where a thread is added to the
ready list:
- thread_init
- thread_yield
- thread_unblock
* Iterate list with removal:
for (e = list_begin (&list); e != list_end (&list); )
if(...)
e = list_remove(e)->prev;
/* Unblock must be called AFTER removing, as thread.elem is reused */
else
e = list_next(e);
Stats:
pintos/src/devices/timer.c | 40 ++++++++++++++++++++++++++++++++++++++--
pintos/src/threads/thread.h | 3 +++
2 files changed, 41 insertions(+), 2 deletions(-)
Design & Implementation time: 4 hours
Priority Scheduler
------------------
A simple implementation of the priority scheduler (64 priority levels, round robin within
one priority group).
* If a new task arrives with a higher priority, switch to this group
* If the currently active group is empty, search for the group with the next highest priority
Notes:
* thread_{init,unblock,yield} now call thread_ready, which updates the lowest ready priority
* The thread_unblock operation does not yield a new thread immediately. Therefore, we need to check
later whether we need to switch to a higher priority thread (via thread_yield).
As thread_unblock is called with interrupts off, it seemed best to perform
this check when interrupts are enabled. This is only necessary if a higher priority task
is ready.
* First attempt passed alarm-priority, but failed to pass the priority-preempt test.
But the debugging facilities are fantastic, so it was easy to spot the problem
* Wolfgang suggested to yield a software interrupt when unblocking instead of modifying
interrupt_enable.
Stats:
pintos/src/threads/interrupt.c | 3 +-
pintos/src/threads/thread.c | 60 ++++++++++++++++++++++++++++++++--------
pintos/src/threads/thread.h | 1 +
3 files changed, 51 insertions(+), 13 deletions(-)
Design and implementation time: 3 hours
Priority Locks
--------------
We also need to select higher priority task first from locks, semaphores and condition variables.
This easiest implementation searches for the thread with the highest priority in the wait queue.
Notes:
* It is sufficient to implement the priority based selection twice, for sema_up and
cond_signal. cond_signal is a little bit harder, as we need to store the priority
(or the waiting thread) in the semaphore_elem type
* There are some handy list utility functions; in this case, list_max does a fine job
for both sema_up and cond_signal
* It is difficult to implement this in an efficient (sublinear) way, because priority donation
may boost a thread at any time!
Stats:
pintos/src/threads/synch.c | 40 ++++++++++++++++++++++++++++++++++------
1 files changed, 34 insertions(+), 6 deletions(-)
Design and Implementation time: 1 hour
Priority Donation
-----------------
If a thread aquires a lock, the lock holder needs to be boosted to the donated priority.
We need to deal with nesting and chaining:
* Lock/Thread correspondence: Each lock is associated with at most one thread that holds it.
Therefore, donated priority can be associated with a lock.
* If a thread t wants to obtain a lock L, and a thread with a lower priority holds it,
the thread holding the lock is boosted to the priority of the requesting thread
* Chaining: If the boosted thread is also blocked on a lock, than we also need to donate
the priority to that lock, in a transitive way.
* Nesting: If a thread may hold more than one lock, we need to keep track of the donation
to each lock. When a lock is released or the static priority changes, the highest priority
donated to other locks is assigned to the thread.
With this information, the following rules seem suitable (without proof of correctness):
* If thread T tries to aquire lock L
==> if(L.owner)
T.locked_on = L
donate_priority (L, T.priority)
end
donate_priority (L ,p) :=
L.priority v= p
L.holder.priority v= p
donate_priority( L.holder.locked_on, p)
end
* If a thread T aquires a lock L
==> L.holder = T
T.locks += L
T.lock_on = none
* If a thread T releases a lock L
==> L.holder = none
T.locks -= L
T.priority = max (T.locks.priority, static_priority)
To implement this, each thread needs to maintain a list of locks, a static priority,
and a reference to the lock blocking it.
Notes:
* Difficult to design, really a challenge.
Literature (short paper) could be helpful.
Maybe it would be interesting to ask for correctness proof sketches?
* First design was wrong, because I assumed locks are aquired in FIFO fashion
* First implementation failed to pass donate tests, due to a typo. Debugging
facilities are fantastic, no problem to spot this one.
* Next try, priority-donate-lower failed. Looking at the source code revealed that
we need to recompute the priority at the end of thread_set_priority.
* Next try, priority-donate-chain failed. Chaining is tricky to get right;
in my implementation, chained donations were lost after one lock was released.
* It would be an interesting option to ask for new test cases from the students
* I think it would also be a cool task to write a test for a RMS scheduling
scenario with blocking.
Stats:
pintos/src/threads/synch.c | 15 ++++++++++++
pintos/src/threads/synch.h | 6 +++-
pintos/src/threads/thread.c | 53 +++++++++++++++++++++++++++++++++++++++++-
pintos/src/threads/thread.h | 9 ++++++-
pintos/src/utils/pintos | 2 +-
Design: 5h
Implementation: 3h
|
