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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
+--------------------+
| CS 140 |
| PROJECT 1: THREADS |
| DESIGN DOCUMENT |
+--------------------+
---- GROUP ----
>> Fill in the names and email addresses of your group members.
Peter Ketscher <e9651415@mail.student.tuwien.ac.at>
Karoline Knoth <e0326266@student.tuwien.ac.at>
Manuel Mausz <manuel-uni@mausz.at>
---- PRELIMINARIES ----
>> If you have any preliminary comments on your submission, notes for the
>> TAs, or extra credit, please give them here.
>> Please cite any offline or online sources you consulted while
>> preparing your submission, other than the Pintos documentation, course
>> text, lecture notes, and course staff.
Stallings, W. - Operating Systems
http://en.wikipedia.org/wiki/Priority_inversion
http://hynek.me/studies/sched_ausarbeitung.pdf
PRIORITY SCHEDULING
===================
---- DATA STRUCTURES ----
>> B1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration. Identify the purpose of each in 25 words or less.
struct thread:
int is_donated ...flag if threads priority has been donated by
another thread
int saved_priority ...saved base priority in case of priority dontation
struct list locks ...list of locks the thread currently holds
struct lock *blocked_lock ...the lock the thread currently tries to acquire
(but hasn't yet)
struct lock:
int priority ...the priority of the thread with the highest
priority currently acquiring the lock
struct list_elem elem ...list element for (struct thread)->locks
struct semaphore_elem:
struct thread *thread ...the current waiting thread
>> B2: Explain the data structure used to track priority donation.
>> Use ASCII art to diagram a nested donation. (Alternately, submit a
>> .png file.)
In case a priority gets donated to a thread we store the origin/base priority
in the variable "saved_priority" inside the structure of the thread itself.
Additional we flip the boolean variable "is_donated".
For multiple priority donations we store the maximum donated priority to a lock
inside the structure of a lock. Additional we store an ordered list of locks a
thread is currently holding. This combination allows us to donate a priority to
a lock and alter the holders priority. In case this lock gets released we either
restore the holder's base/origin priority (if the lock list is empty) or change
the holder's priority to highest priority donated by the locks the thread still
holds (the lock list is not empty). See B5 for additional information.
For nested priority donation we additional store a pointer to the lock the
thread is waiting on ("blocked_lock"). We then walk recursively from the current
lock to the lock the holder of the current lock is waiting on and at the same
time donate the thread's priority to the occurring holders. The loop ends as
soon as no holder of a lock in this chain is waiting on another lock. See B4 for
additional information.
Nested donation example:
* 3 threads with different priority
* 2 locks
* L holds lock A
* M holds lock B and is waiting on lock A
* H is waiting on lock B
_____
| | Legend:
| L | x ...thread holds lock
|_____| o ...thread is waiting on lock
|
/--|---------------------------\
| x o Lock A |
\--------|---------------------/
__|__
| |
| M |
|_____|
|
/--------|---------------------\
| x o Lock B |
\--------------|---------------/
__|__
| |
| H |
|_____|
L.locks = [A]
L.blocked_lock = NULL
M.locks = [B]
M.blocked_lock = A
H.locks = []
H.blocked_lock = B
H enters the nested priority loop and donates its priority to
H.blocked_lock.holder (=M):
=> M.priority = H
H donates its priority to M.blocked_lock.holder (=L):
=> L.priority = H
Loop ends as L.blocked_lock is NULL
---- ALGORITHMS ----
>> B3: How do you ensure that the highest priority thread waiting for
>> a lock, semaphore, or condition variable wakes up first?
We use list_sort() inside sema_up() to sort the list of blocked/waiting threads
by their priority. Afterwards we unblock the first thread in the list which is
the thread with the highest priority.
This ensures working locks as well (lock implementation uses semaphores).
For conditions the list of blocked/waiting threads consists of elements of the
structure semaphore_elem which itself contains a semaphore. In order to sort
this list by the thread's priority we simply added a pointer pointing to the
thread structure owning the element in the list. Just as in sema_up() we use
list_sort() inside cond_signal() to sort the list and unblock the thread with
the highest priority.
See B7 for a reason why used list_sort() instead of list_insert_ordered().
>> B4: Describe the sequence of events when a call to lock_acquire()
>> causes a priority donation. How is nested donation handled?
In lock_acquire() we first check if the lock is already held by another thread.
In case there is a holder we check for a possible priority donation by comparing
the thread's priority with the priority of the lock which is the same value as
the current priority of the holder.
We need this additional priority variable per lock because a thread may hold
multiple locks which could donate any number of priorities to this thread.
As soon as the thread releases one of these locks we need to change the thread's
priority to the highest (donated) priority of the other locks the thread still
holds. See B5 on how we accomplish this.
For nested priority donation we not only have to donate the thread's priority to
the holder of the lock the thread currently is waiting on but also have to look
into the depth if the holder itself is waiting on another lock too. This
lookup/recursion continues until a thread holding a lock in the chain isn't
waiting on another lock (blocked_lock isn't set).
For every lock in this chain we donate the priority of the current thread to
their holder.
>> B5: Describe the sequence of events when lock_release() is called
>> on a lock that a higher-priority thread is waiting for.
In order to handle multiple priority donations to the same lock we not only
store the currently donated priority inside the lock structure (as already
described in B4) but also a list of currently held locks of a thread. This list
is ordered by the locks priority. In lock_release() we first check if this
ordered lock list is empty and then call thread_donation_pass_back() which
restores the origin priority of the thread.
In case the list is not empty we simply retreive the first lock and change the
thread's current priority to the priority of the lock. This is accomplished by
calling thread_other_set_priority() which yields the cpu in case the new
priority is lower than the priority of the thread with the highest priority in
the ready list.
---- SYNCHRONIZATION ----
>> B6: Describe a potential race in thread_set_priority() and explain
>> how your implementation avoids it. Can you use a lock to avoid
>> this race?
thread_set_priority() first changes the priority and then has to either just
re-sort the ready list or has to decide whether it should yield by comparing the
priorities of the current thread and the thread with the highest priority in
the ready list. The gap between changing the priority and doing the other stuff
raises a few possible races if the timer interrupt triggers in between.
E.g. no proper sorted ready list, corrupt ready list (wrong internal pointers)
or the timer interrupt fires after calling list_empty() but before list_front()
while having only two threads (one active, the other one ready). The scheduler
then schedules the other thread which runs and perhaps terminates, thus removing
itself from all lists. After that our thread gets scheduled again and reads from
an empty list, although it wasn't empty before.
Using a lock instead of disabling the interrupts would require locking the
access to the ready list everywhere. This doesn't follow the already established
conventions and would rather be a lot more cpu intensive.
---- RATIONALE ----
>> B7: Why did you choose this design? In what ways is it superior to
>> another design you considered?
Actually we didn't consider any other design. We first tried to solve the
assignment without pre-planning and just started coding but that failed.
Afterwards we looked at the various cases, did some drafts and decided on the
required structure modifications. That did work quite well.
In case of priority donation with locks our design only consumes little cpu
instructions because we sort the list of locks by their donated priority upon
insertion and whenever a donated priority changes. This allows us to retrieve
the next donated priority with just looking at the first element in the list.
In case of priority donation with semaphores and conditions we can't sort the
blocked/waiting threads on insertion as their priority may change afterwards
and we don't have any reference to currently used semaphores/conditions inside
the thread structure. Thus we simply sort the whole list inside sema_up()/
cond_signal() before unblocking the next thread.
SURVEY QUESTIONS
================
Answering these questions is optional, but it will help us improve the
course in future quarters. Feel free to tell us anything you
want--these questions are just to spur your thoughts. You may also
choose to respond anonymously in the course evaluations at the end of
the quarter.
>> In your opinion, was this assignment, or any one of the three problems
>> in it, too easy or too hard? Did it take too long or too little time?
working on the priority donation without being able to use printf() inside
lock_acquire()/lock_release() (as printf() requires a lock for the console
itself) was challenging.
>> Did you find that working on a particular part of the assignment gave
>> you greater insight into some aspect of OS design?
>> Is there some particular fact or hint we should give students in
>> future quarters to help them solve the problems? Conversely, did you
>> find any of our guidance to be misleading?
do not use printf() inside lock_acquire()/lock_release() :)
>> Do you have any suggestions for the TAs to more effectively assist
>> students, either for future quarters or the remaining projects?
>> Any other comments?
|
