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
|
+--------------------+
| 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.)
TODO
---- ALGORITHMS ----
>> B3: How do you ensure that the highest priority thread waiting for
>> a lock, semaphore, or condition variable wakes up first?
TODO
>> B4: Describe the sequence of events when a call to lock_acquire()
>> causes a priority donation. How is nested donation handled?
TODO
>> B5: Describe the sequence of events when lock_release() is called
>> on a lock that a higher-priority thread is waiting for.
---- 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?
Acutally 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 needs only a few cpu
instructions because we sort the list of locks during insertion and whenever a
donated priority changes. This allows us to retreive 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 during 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?
|
