summaryrefslogtreecommitdiffstats
path: root/doc/pintos_3.html
diff options
context:
space:
mode:
authormanuel <manuel@mausz.at>2012-03-26 12:54:45 +0200
committermanuel <manuel@mausz.at>2012-03-26 12:54:45 +0200
commitb5f0874cd96ee2a62aabc645b9626c2749cb6a01 (patch)
tree1262e4bbe0634de6650be130c36e0538240f4cbf /doc/pintos_3.html
downloadprogos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.gz
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.bz2
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.zip
initial pintos checkin
Diffstat (limited to 'doc/pintos_3.html')
-rw-r--r--doc/pintos_3.html375
1 files changed, 375 insertions, 0 deletions
diff --git a/doc/pintos_3.html b/doc/pintos_3.html
new file mode 100644
index 0000000..c90148d
--- /dev/null
+++ b/doc/pintos_3.html
@@ -0,0 +1,375 @@
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
2 "http://www.w3.org/TR/html40/loose.dtd">
3<HTML>
4<!-- Created on March, 6 2012 by texi2html 1.66 -->
5<!--
6Written by: Lionel Cons <Lionel.Cons@cern.ch> (original author)
7 Karl Berry <karl@freefriends.org>
8 Olaf Bachmann <obachman@mathematik.uni-kl.de>
9 and many others.
10Maintained by: Many creative people <dev@texi2html.cvshome.org>
11Send bugs and suggestions to <users@texi2html.cvshome.org>
12
13-->
14<HEAD>
15<TITLE>Pintos Projects: Project 1--Threads</TITLE>
16
17<META NAME="description" CONTENT="Pintos Projects: Project 1--Threads">
18<META NAME="keywords" CONTENT="Pintos Projects: Project 1--Threads">
19<META NAME="resource-type" CONTENT="document">
20<META NAME="distribution" CONTENT="global">
21<META NAME="Generator" CONTENT="texi2html 1.66">
22<LINK REL="stylesheet" HREF="pintos.css">
23</HEAD>
24
25<BODY >
26
27<A NAME="SEC41"></A>
28<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
29<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_2.html#SEC15"> &lt;&lt; </A>]</TD>
30<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_4.html#SEC47"> &gt;&gt; </A>]</TD>
31<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
32<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
33<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
34<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
35</TR></TABLE>
36
37<HR SIZE=2>
38<H1> 3. Project 1: Threads </H1>
39<!--docid::SEC41::-->
40<P>
41
42In this assignment, we give you a minimally functional thread system.
43Your job is to extend the functionality of this system to gain a
44better understanding of synchronization problems.
45</P>
46<P>
47
48You will be working primarily in the <Q><TT>threads</TT></Q> directory for
49this assignment, with some work in the <Q><TT>devices</TT></Q> directory on the
50side. Compilation should be done in the <Q><TT>threads</TT></Q> directory.
51</P>
52<P>
53
54Before you read the description of this project, you should read all of
55the following sections: <A HREF="pintos_1.html#SEC1">1. Introduction</A>, <A HREF="pintos_6.html#SEC89">B. Coding Standards</A>,
56<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
57skim 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>.
58</P>
59<P>
60
61<A NAME="Project 1 Background"></A>
62<HR SIZE="6">
63<A NAME="SEC42"></A>
64<H2> 3.1 Background </H2>
65<!--docid::SEC42::-->
66<P>
67
68Before you start with project 1, be sure to refresh your knowledge
69on the thread subsystem introduced in the last project
70(<A HREF="pintos_2.html#SEC16">2.1 Understanding Threads</A>).
71</P>
72<P>
73
74<A NAME="Project 1 Requirements"></A>
75<HR SIZE="6">
76<A NAME="SEC43"></A>
77<H2> 3.2 Requirements </H2>
78<!--docid::SEC43::-->
79<P>
80
81<A NAME="Project 1 Design Document"></A>
82<HR SIZE="6">
83<A NAME="SEC44"></A>
84<H3> 3.2.1 Design Document </H3>
85<!--docid::SEC44::-->
86<P>
87
88Before you turn in your project, you must copy <A HREF="threads.tmpl">the
89project 1 design document template</A> into your source tree under the name
90<Q><TT>pintos/src/threads/DESIGNDOC</TT></Q> and fill it in. We recommend that
91you read the design document template before you start working on the
92project.
93</P>
94<P>
95
96<A NAME="Priority Scheduling"></A>
97<HR SIZE="6">
98<A NAME="SEC45"></A>
99<H3> 3.2.2 Priority Scheduling </H3>
100<!--docid::SEC45::-->
101<P>
102
103Implement priority scheduling in Pintos.
104When a thread is added to the ready list that has a higher priority
105than the currently running thread, the current thread should
106immediately yield the processor to the new thread. Similarly, when
107threads are waiting for a lock, semaphore, or condition variable, the
108highest priority waiting thread should be awakened first. A thread
109may raise or lower its own priority at any time, but lowering its
110priority such that it no longer has the highest priority must cause it
111to immediately yield the CPU.
112</P>
113<P>
114
115Thread priorities range from <CODE>PRI_MIN</CODE> (0) to <CODE>PRI_MAX</CODE> (63).
116Lower numbers correspond to lower priorities, so that priority 0
117is the lowest priority and priority 63 is the highest.
118The initial thread priority is passed as an argument to
119<CODE>thread_create()</CODE>. If there's no reason to choose another
120priority, use <CODE>PRI_DEFAULT</CODE> (31). The <CODE>PRI_</CODE> macros are
121defined in <Q><TT>threads/thread.h</TT></Q>, and you should not change their
122values.
123</P>
124<P>
125
126One issue with priority scheduling is &quot;priority inversion&quot;. Consider
127high, medium, and low priority threads <VAR>H</VAR>, <VAR>M</VAR>, and <VAR>L</VAR>,
128respectively. If <VAR>H</VAR> needs to wait for <VAR>L</VAR> (for instance, for a
129lock held by <VAR>L</VAR>), and <VAR>M</VAR> is on the ready list, then <VAR>H</VAR>
130will never get the CPU because the low priority thread will not get any
131CPU time. A partial fix for this problem is for <VAR>H</VAR> to &quot;donate&quot;
132its priority to <VAR>L</VAR> while <VAR>L</VAR> is holding the lock, then recall
133the donation once <VAR>L</VAR> releases (and thus <VAR>H</VAR> acquires) the lock.
134</P>
135<P>
136
137Implement priority donation. You will need to account for all different
138situations in which priority donation is required. Be sure to handle
139multiple donations, in which multiple priorities are donated to a single
140thread. You must also handle nested donation: if <VAR>H</VAR> is waiting on
141a lock that <VAR>M</VAR> holds and <VAR>M</VAR> is waiting on a lock that <VAR>L</VAR>
142holds, then both <VAR>M</VAR> and <VAR>L</VAR> should be boosted to <VAR>H</VAR>'s
143priority. If necessary, you may impose a reasonable limit on depth of
144nested priority donation, such as 8 levels.
145</P>
146<P>
147
148You must implement priority donation for locks. You need not
149implement priority donation for the other Pintos synchronization
150constructs. You do need to implement priority scheduling in all
151cases.
152</P>
153<P>
154
155Finally, implement the following functions that allow a thread to
156examine and modify its own priority. Skeletons for these functions are
157provided in <Q><TT>threads/thread.c</TT></Q>.
158</P>
159<P>
160
161<A NAME="IDX2"></A>
162</P>
163<DL>
164<DT><U>Function:</U> void <B>thread_set_priority</B> (int <VAR>new_priority</VAR>)
165<DD>Sets the current thread's priority to <VAR>new_priority</VAR>. If the
166current thread no longer has the highest priority, yields.
167</DL>
168<P>
169
170<A NAME="IDX3"></A>
171</P>
172<DL>
173<DT><U>Function:</U> int <B>thread_get_priority</B> (void)
174<DD>Returns the current thread's priority. In the presence of priority
175donation, returns the higher (donated) priority.
176</DL>
177<P>
178
179You need not provide any interface to allow a thread to directly modify
180other threads' priorities.
181</P>
182<P>
183
184The priority scheduler is not a necessary for project 2.
185</P>
186<P>
187
188<A NAME="Project 1 FAQ"></A>
189<HR SIZE="6">
190<A NAME="SEC46"></A>
191<H2> 3.3 FAQ </H2>
192<!--docid::SEC46::-->
193<P>
194
195</P>
196<DL COMPACT>
197<DT><B>How much code will I need to write?</B>
198<DD><P>
199
200Here's a summary of our reference solution, produced by the
201<CODE>diffstat</CODE> program. The final row gives total lines inserted
202and deleted; a changed line counts as both an insertion and a deletion.
203</P>
204<P>
205
206The reference solution represents just one possible solution. Many
207other solutions are also possible and many of those differ greatly from
208the reference solution. Some excellent solutions may not modify all the
209files modified by the reference solution, and some may modify files not
210modified by the reference solution.
211</P>
212<P>
213
214<TABLE><tr><td>&nbsp;</td><td class=example><pre> threads/interrupt.c | 3 +-
215 threads/synch.c | 55 ++++++++++++++++++--
216 threads/synch.h | 2 +
217 threads/thread.c | 111 +++++++++++++++++++++++++++++++++++-----
218 threads/thread.h | 10 +++-
219 5 files changed, 160 insertions(+), 21 deletions(-)
220</pre></td></tr></table><P>
221
222</P>
223<DT><B>Doesn't priority scheduling lead to starvation?</B>
224<DD><P>
225
226Yes, strict priority scheduling can lead to starvation
227because a thread will not run if any higher-priority thread is runnable.
228The advanced scheduler introduces a mechanism for dynamically
229changing thread priorities.
230</P>
231<P>
232
233Strict priority scheduling is valuable in real-time systems because it
234offers the programmer more control over which jobs get processing
235time. High priorities are generally reserved for time-critical
236tasks. It's not &quot;fair,&quot; but it addresses other concerns not
237applicable to a general-purpose operating system.
238</P>
239<P>
240
241</P>
242<DT><B>What thread should run after a lock has been released?</B>
243<DD><P>
244
245When a lock is released, the highest priority thread waiting for that
246lock should be unblocked and put on the list of ready threads. The
247scheduler should then run the highest priority thread on the ready
248list.
249</P>
250<P>
251
252</P>
253<DT><B>If the highest-priority thread yields, does it continue running?</B>
254<DD><P>
255
256Yes. If there is a single highest-priority thread, it continues
257running until it blocks or finishes, even if it calls
258<CODE>thread_yield()</CODE>.
259If multiple threads have the same highest priority,
260<CODE>thread_yield()</CODE> should switch among them in &quot;round robin&quot; order.
261</P>
262<P>
263
264</P>
265<DT><B>What happens to the priority of a donating thread?</B>
266<DD><P>
267
268Priority donation only changes the priority of the donee
269thread. The donor thread's priority is unchanged.
270Priority donation is not additive: if thread <VAR>A</VAR> (with priority 5) donates
271to thread <VAR>B</VAR> (with priority 3), then <VAR>B</VAR>'s new priority is 5, not 8.
272</P>
273<P>
274
275</P>
276<DT><B>Can a thread's priority change while it is on the ready queue?</B>
277<DD><P>
278
279Yes. Consider a ready, low-priority thread <VAR>L</VAR> that holds a lock.
280High-priority thread <VAR>H</VAR> attempts to acquire the lock and blocks,
281thereby donating its priority to ready thread <VAR>L</VAR>.
282</P>
283<P>
284
285</P>
286<DT><B>Can a thread's priority change while it is blocked?</B>
287<DD><P>
288
289Yes. While a thread that has acquired lock <VAR>L</VAR> is blocked for any
290reason, its priority can increase by priority donation if a
291higher-priority thread attempts to acquire <VAR>L</VAR>. This case is
292checked by the <CODE>priority-donate-sema</CODE> test.
293</P>
294<P>
295
296</P>
297<DT><B>Can a thread added to the ready list preempt the processor?</B>
298<DD><P>
299
300Yes. If a thread added to the ready list has higher priority than the
301running thread, the correct behavior is to immediately yield the
302processor. It is not acceptable to wait for the next timer interrupt.
303The highest priority thread should run as soon as it is runnable,
304preempting whatever thread is currently running.
305</P>
306<P>
307
308</P>
309<DT><B>How does <CODE>thread_set_priority()</CODE> affect a thread receiving donations?</B>
310<DD><P>
311
312It sets the thread's base priority. The thread's effective priority
313becomes the higher of the newly set priority or the highest donated
314priority. When the donations are released, the thread's priority
315becomes the one set through the function call. This behavior is checked
316by the <CODE>priority-donate-lower</CODE> test.
317</P>
318<P>
319
320</P>
321<DT><B>Doubled test names in output make them fail.</B>
322<DD><P>
323
324Suppose you are seeing output in which some test names are doubled,
325like this:
326</P>
327<P>
328
329<TABLE><tr><td>&nbsp;</td><td class=example><pre>(alarm-priority) begin
330(alarm-priority) (alarm-priority) Thread priority 30 woke up.
331Thread priority 29 woke up.
332(alarm-priority) Thread priority 28 woke up.
333</pre></td></tr></table><P>
334
335What is happening is that output from two threads is being
336interleaved. That is, one thread is printing <CODE>&quot;(alarm-priority)
337Thread priority 29 woke up.\n&quot;</CODE> and another thread is printing
338<CODE>&quot;(alarm-priority) Thread priority 30 woke up.\n&quot;</CODE>, but the first
339thread is being preempted by the second in the middle of its output.
340</P>
341<P>
342
343This problem indicates a bug in your priority scheduler. After all, a
344thread with priority 29 should not be able to run while a thread with
345priority 30 has work to do.
346</P>
347<P>
348
349Normally, the implementation of the <CODE>printf()</CODE> function in the
350Pintos kernel attempts to prevent such interleaved output by acquiring
351a console lock during the duration of the <CODE>printf</CODE> call and
352releasing it afterwards. However, the output of the test name,
353e.g., <CODE>(alarm-priority)</CODE>, and the message following it is output
354using two calls to <CODE>printf</CODE>, resulting in the console lock being
355acquired and released twice.
356</DL>
357<A NAME="Project 2--Virtual Memory"></A>
358<HR SIZE="6">
359<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
360<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_3.html#SEC41"> &lt;&lt; </A>]</TD>
361<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_4.html#SEC47"> &gt;&gt; </A>]</TD>
362<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
363<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
364<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
365<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
366</TR></TABLE>
367<BR>
368<FONT SIZE="-1">
369This document was generated
370by on <I>March, 6 2012</I>
371using <A HREF="http://texi2html.cvshome.org"><I>texi2html</I></A>
372</FONT>
373
374</BODY>
375</HTML>
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-12 09:05:10 +0000