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
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html40/loose.dtd">
<HTML>
<!-- Created on March, 6 2012 by texi2html 1.66 -->
<!--
Written by: Lionel Cons <Lionel.Cons@cern.ch> (original author)
Karl Berry <karl@freefriends.org>
Olaf Bachmann <obachman@mathematik.uni-kl.de>
and many others.
Maintained by: Many creative people <dev@texi2html.cvshome.org>
Send bugs and suggestions to <users@texi2html.cvshome.org>
-->
<HEAD>
<TITLE>Pintos Projects: Project 1--Threads</TITLE>
<META NAME="description" CONTENT="Pintos Projects: Project 1--Threads">
<META NAME="keywords" CONTENT="Pintos Projects: Project 1--Threads">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META NAME="Generator" CONTENT="texi2html 1.66">
<LINK REL="stylesheet" HREF="pintos.css">
</HEAD>
<BODY >
<A NAME="SEC41"></A>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_2.html#SEC15"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_4.html#SEC47"> >> </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
</TR></TABLE>
<HR SIZE=2>
<H1> 3. Project 1: Threads </H1>
<!--docid::SEC41::-->
<P>
In this assignment, we give you a minimally functional thread system.
Your job is to extend the functionality of this system to gain a
better understanding of synchronization problems.
</P>
<P>
You will be working primarily in the <Q><TT>threads</TT></Q> directory for
this assignment, with some work in the <Q><TT>devices</TT></Q> directory on the
side. Compilation should be done in the <Q><TT>threads</TT></Q> directory.
</P>
<P>
Before you read the description of this project, you should read all of
the following sections: <A HREF="pintos_1.html#SEC1">1. Introduction</A>, <A HREF="pintos_6.html#SEC89">B. Coding Standards</A>,
<A HREF="pintos_8.html#SEC96">D. Debugging Tools</A>, and <A HREF="pintos_9.html#SEC109">E. Development Tools</A>. You should at least
skim the material from <A HREF="pintos_5.html#SEC49">A.1 Loading</A> through <A HREF="pintos_5.html#SEC69">A.5 Memory Allocation</A>, especially <A HREF="pintos_5.html#SEC58">A.3 Synchronization</A>.
</P>
<P>
<A NAME="Project 1 Background"></A>
<HR SIZE="6">
<A NAME="SEC42"></A>
<H2> 3.1 Background </H2>
<!--docid::SEC42::-->
<P>
Before you start with project 1, be sure to refresh your knowledge
on the thread subsystem introduced in the last project
(<A HREF="pintos_2.html#SEC16">2.1 Understanding Threads</A>).
</P>
<P>
<A NAME="Project 1 Requirements"></A>
<HR SIZE="6">
<A NAME="SEC43"></A>
<H2> 3.2 Requirements </H2>
<!--docid::SEC43::-->
<P>
<A NAME="Project 1 Design Document"></A>
<HR SIZE="6">
<A NAME="SEC44"></A>
<H3> 3.2.1 Design Document </H3>
<!--docid::SEC44::-->
<P>
Before you turn in your project, you must copy <A HREF="threads.tmpl">the
project 1 design document template</A> into your source tree under the name
<Q><TT>pintos/src/threads/DESIGNDOC</TT></Q> and fill it in. We recommend that
you read the design document template before you start working on the
project.
</P>
<P>
<A NAME="Priority Scheduling"></A>
<HR SIZE="6">
<A NAME="SEC45"></A>
<H3> 3.2.2 Priority Scheduling </H3>
<!--docid::SEC45::-->
<P>
Implement priority scheduling in Pintos.
When a thread is added to the ready list that has a higher priority
than the currently running thread, the current thread should
immediately yield the processor to the new thread. Similarly, when
threads are waiting for a lock, semaphore, or condition variable, the
highest priority waiting thread should be awakened first. A thread
may raise or lower its own priority at any time, but lowering its
priority such that it no longer has the highest priority must cause it
to immediately yield the CPU.
</P>
<P>
Thread priorities range from <CODE>PRI_MIN</CODE> (0) to <CODE>PRI_MAX</CODE> (63).
Lower numbers correspond to lower priorities, so that priority 0
is the lowest priority and priority 63 is the highest.
The initial thread priority is passed as an argument to
<CODE>thread_create()</CODE>. If there's no reason to choose another
priority, use <CODE>PRI_DEFAULT</CODE> (31). The <CODE>PRI_</CODE> macros are
defined in <Q><TT>threads/thread.h</TT></Q>, and you should not change their
values.
</P>
<P>
One issue with priority scheduling is "priority inversion". Consider
high, medium, and low priority threads <VAR>H</VAR>, <VAR>M</VAR>, and <VAR>L</VAR>,
respectively. If <VAR>H</VAR> needs to wait for <VAR>L</VAR> (for instance, for a
lock held by <VAR>L</VAR>), and <VAR>M</VAR> is on the ready list, then <VAR>H</VAR>
will never get the CPU because the low priority thread will not get any
CPU time. A partial fix for this problem is for <VAR>H</VAR> to "donate"
its priority to <VAR>L</VAR> while <VAR>L</VAR> is holding the lock, then recall
the donation once <VAR>L</VAR> releases (and thus <VAR>H</VAR> acquires) the lock.
</P>
<P>
Implement priority donation. You will need to account for all different
situations in which priority donation is required. Be sure to handle
multiple donations, in which multiple priorities are donated to a single
thread. You must also handle nested donation: if <VAR>H</VAR> is waiting on
a lock that <VAR>M</VAR> holds and <VAR>M</VAR> is waiting on a lock that <VAR>L</VAR>
holds, then both <VAR>M</VAR> and <VAR>L</VAR> should be boosted to <VAR>H</VAR>'s
priority. If necessary, you may impose a reasonable limit on depth of
nested priority donation, such as 8 levels.
</P>
<P>
You must implement priority donation for locks. You need not
implement priority donation for the other Pintos synchronization
constructs. You do need to implement priority scheduling in all
cases.
</P>
<P>
Finally, implement the following functions that allow a thread to
examine and modify its own priority. Skeletons for these functions are
provided in <Q><TT>threads/thread.c</TT></Q>.
</P>
<P>
<A NAME="IDX2"></A>
</P>
<DL>
<DT><U>Function:</U> void <B>thread_set_priority</B> (int <VAR>new_priority</VAR>)
<DD>Sets the current thread's priority to <VAR>new_priority</VAR>. If the
current thread no longer has the highest priority, yields.
</DL>
<P>
<A NAME="IDX3"></A>
</P>
<DL>
<DT><U>Function:</U> int <B>thread_get_priority</B> (void)
<DD>Returns the current thread's priority. In the presence of priority
donation, returns the higher (donated) priority.
</DL>
<P>
You need not provide any interface to allow a thread to directly modify
other threads' priorities.
</P>
<P>
The priority scheduler is not a necessary for project 2.
</P>
<P>
<A NAME="Project 1 FAQ"></A>
<HR SIZE="6">
<A NAME="SEC46"></A>
<H2> 3.3 FAQ </H2>
<!--docid::SEC46::-->
<P>
</P>
<DL COMPACT>
<DT><B>How much code will I need to write?</B>
<DD><P>
Here's a summary of our reference solution, produced by the
<CODE>diffstat</CODE> program. The final row gives total lines inserted
and deleted; a changed line counts as both an insertion and a deletion.
</P>
<P>
The reference solution represents just one possible solution. Many
other solutions are also possible and many of those differ greatly from
the reference solution. Some excellent solutions may not modify all the
files modified by the reference solution, and some may modify files not
modified by the reference solution.
</P>
<P>
<TABLE><tr><td> </td><td class=example><pre> threads/interrupt.c | 3 +-
threads/synch.c | 55 ++++++++++++++++++--
threads/synch.h | 2 +
threads/thread.c | 111 +++++++++++++++++++++++++++++++++++-----
threads/thread.h | 10 +++-
5 files changed, 160 insertions(+), 21 deletions(-)
</pre></td></tr></table><P>
</P>
<DT><B>Doesn't priority scheduling lead to starvation?</B>
<DD><P>
Yes, strict priority scheduling can lead to starvation
because a thread will not run if any higher-priority thread is runnable.
The advanced scheduler introduces a mechanism for dynamically
changing thread priorities.
</P>
<P>
Strict priority scheduling is valuable in real-time systems because it
offers the programmer more control over which jobs get processing
time. High priorities are generally reserved for time-critical
tasks. It's not "fair," but it addresses other concerns not
applicable to a general-purpose operating system.
</P>
<P>
</P>
<DT><B>What thread should run after a lock has been released?</B>
<DD><P>
When a lock is released, the highest priority thread waiting for that
lock should be unblocked and put on the list of ready threads. The
scheduler should then run the highest priority thread on the ready
list.
</P>
<P>
</P>
<DT><B>If the highest-priority thread yields, does it continue running?</B>
<DD><P>
Yes. If there is a single highest-priority thread, it continues
running until it blocks or finishes, even if it calls
<CODE>thread_yield()</CODE>.
If multiple threads have the same highest priority,
<CODE>thread_yield()</CODE> should switch among them in "round robin" order.
</P>
<P>
</P>
<DT><B>What happens to the priority of a donating thread?</B>
<DD><P>
Priority donation only changes the priority of the donee
thread. The donor thread's priority is unchanged.
Priority donation is not additive: if thread <VAR>A</VAR> (with priority 5) donates
to thread <VAR>B</VAR> (with priority 3), then <VAR>B</VAR>'s new priority is 5, not 8.
</P>
<P>
</P>
<DT><B>Can a thread's priority change while it is on the ready queue?</B>
<DD><P>
Yes. Consider a ready, low-priority thread <VAR>L</VAR> that holds a lock.
High-priority thread <VAR>H</VAR> attempts to acquire the lock and blocks,
thereby donating its priority to ready thread <VAR>L</VAR>.
</P>
<P>
</P>
<DT><B>Can a thread's priority change while it is blocked?</B>
<DD><P>
Yes. While a thread that has acquired lock <VAR>L</VAR> is blocked for any
reason, its priority can increase by priority donation if a
higher-priority thread attempts to acquire <VAR>L</VAR>. This case is
checked by the <CODE>priority-donate-sema</CODE> test.
</P>
<P>
</P>
<DT><B>Can a thread added to the ready list preempt the processor?</B>
<DD><P>
Yes. If a thread added to the ready list has higher priority than the
running thread, the correct behavior is to immediately yield the
processor. It is not acceptable to wait for the next timer interrupt.
The highest priority thread should run as soon as it is runnable,
preempting whatever thread is currently running.
</P>
<P>
</P>
<DT><B>How does <CODE>thread_set_priority()</CODE> affect a thread receiving donations?</B>
<DD><P>
It sets the thread's base priority. The thread's effective priority
becomes the higher of the newly set priority or the highest donated
priority. When the donations are released, the thread's priority
becomes the one set through the function call. This behavior is checked
by the <CODE>priority-donate-lower</CODE> test.
</P>
<P>
</P>
<DT><B>Doubled test names in output make them fail.</B>
<DD><P>
Suppose you are seeing output in which some test names are doubled,
like this:
</P>
<P>
<TABLE><tr><td> </td><td class=example><pre>(alarm-priority) begin
(alarm-priority) (alarm-priority) Thread priority 30 woke up.
Thread priority 29 woke up.
(alarm-priority) Thread priority 28 woke up.
</pre></td></tr></table><P>
What is happening is that output from two threads is being
interleaved. That is, one thread is printing <CODE>"(alarm-priority)
Thread priority 29 woke up.\n"</CODE> and another thread is printing
<CODE>"(alarm-priority) Thread priority 30 woke up.\n"</CODE>, but the first
thread is being preempted by the second in the middle of its output.
</P>
<P>
This problem indicates a bug in your priority scheduler. After all, a
thread with priority 29 should not be able to run while a thread with
priority 30 has work to do.
</P>
<P>
Normally, the implementation of the <CODE>printf()</CODE> function in the
Pintos kernel attempts to prevent such interleaved output by acquiring
a console lock during the duration of the <CODE>printf</CODE> call and
releasing it afterwards. However, the output of the test name,
e.g., <CODE>(alarm-priority)</CODE>, and the message following it is output
using two calls to <CODE>printf</CODE>, resulting in the console lock being
acquired and released twice.
</DL>
<A NAME="Project 2--Virtual Memory"></A>
<HR SIZE="6">
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_3.html#SEC41"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_4.html#SEC47"> >> </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
</TR></TABLE>
<BR>
<FONT SIZE="-1">
This document was generated
by on <I>March, 6 2012</I>
using <A HREF="http://texi2html.cvshome.org"><I>texi2html</I></A>
</FONT>
</BODY>
</HTML>
|
