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
|
<!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 Documentation</TITLE>
<META NAME="description" CONTENT="Pintos Projects: Project Documentation">
<META NAME="keywords" CONTENT="Pintos Projects: Project Documentation">
<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="SEC93"></A>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_6.html#SEC89"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_8.html#SEC96"> >> </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> C. Project Documentation </H1>
<!--docid::SEC93::-->
<P>
This chapter presents a sample assignment and a filled-in design
document for one possible implementation. Its purpose is to give you an
idea of what we expect to see in your own design documents.
</P>
<P>
<A NAME="Sample Assignment"></A>
<HR SIZE="6">
<A NAME="SEC94"></A>
<H2> C.1 Sample Assignment </H2>
<!--docid::SEC94::-->
<P>
Implement <CODE>thread_join()</CODE>.
</P>
<P>
<A NAME="IDX160"></A>
</P>
<DL>
<DT><U>Function:</U> void <B>thread_join</B> (tid_t <VAR>tid</VAR>)
<DD>Blocks the current thread until thread <VAR>tid</VAR> exits. If <VAR>A</VAR> is
the running thread and <VAR>B</VAR> is the argument, then we say that
"<VAR>A</VAR> joins <VAR>B</VAR>."
<P>
Incidentally, the argument is a thread id, instead of a thread pointer,
because a thread pointer is not unique over time. That is, when a
thread dies, its memory may be, whether immediately or much later,
reused for another thread. If thread <VAR>A</VAR> over time had two children
<VAR>B</VAR> and <VAR>C</VAR> that were stored at the same address, then
<CODE>thread_join(<VAR>B</VAR>)</CODE> and <CODE>thread_join(<VAR>C</VAR>)</CODE> would be
ambiguous.
</P>
<P>
A thread may only join its immediate children. Calling
<CODE>thread_join()</CODE> on a thread that is not the caller's child should
cause the caller to return immediately. Children are not "inherited,"
that is, if <VAR>A</VAR> has child <VAR>B</VAR> and <VAR>B</VAR> has child <VAR>C</VAR>,
then <VAR>A</VAR> always returns immediately should it try to join <VAR>C</VAR>,
even if <VAR>B</VAR> is dead.
</P>
<P>
A thread need not ever be joined. Your solution should properly free
all of a thread's resources, including its <CODE>struct thread</CODE>,
whether it is ever joined or not, and regardless of whether the child
exits before or after its parent. That is, a thread should be freed
exactly once in all cases.
</P>
<P>
Joining a given thread is idempotent. That is, joining a thread
multiple times is equivalent to joining it once, because it has already
exited at the time of the later joins. Thus, joins on a given thread
after the first should return immediately.
</P>
<P>
You must handle all the ways a join can occur: nested joins (<VAR>A</VAR>
joins <VAR>B</VAR>, then <VAR>B</VAR> joins <VAR>C</VAR>), multiple joins (<VAR>A</VAR>
joins <VAR>B</VAR>, then <VAR>A</VAR> joins <VAR>C</VAR>), and so on.
</P>
</DL>
<P>
<A NAME="Sample Design Document"></A>
<HR SIZE="6">
<A NAME="SEC95"></A>
<H2> C.2 Sample Design Document </H2>
<!--docid::SEC95::-->
<P>
<TABLE><tr><td> </td><td class=example><pre>
+-----------------+
| CS 140 |
| SAMPLE PROJECT |
| DESIGN DOCUMENT |
+-----------------+
---- GROUP ----
Ben Pfaff <blp@stanford.edu>
---- PRELIMINARIES ----
>> If you have any preliminary comments on your submission, notes for
>> the TAs, or extra credit, please give them here.
(This is a sample design document.)
>> Please cite any offline or online sources you consulted while
>> preparing your submission, other than the Pintos documentation,
>> course text, and lecture notes.
None.
JOIN
====
---- DATA STRUCTURES ----
>> 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.
A "latch" is a new synchronization primitive. Acquires block
until the first release. Afterward, all ongoing and future
acquires pass immediately.
/* Latch. */
struct latch
{
bool released; /* Released yet? */
struct lock monitor_lock; /* Monitor lock. */
struct condition rel_cond; /* Signaled when released. */
};
Added to struct thread:
/* Members for implementing thread_join(). */
struct latch ready_to_die; /* Release when thread about to die. */
struct semaphore can_die; /* Up when thread allowed to die. */
struct list children; /* List of child threads. */
list_elem children_elem; /* Element of `children' list. */
---- ALGORITHMS ----
>> Briefly describe your implementation of thread_join() and how it
>> interacts with thread termination.
thread_join() finds the joined child on the thread's list of
children and waits for the child to exit by acquiring the child's
ready_to_die latch. When thread_exit() is called, the thread
releases its ready_to_die latch, allowing the parent to continue.
---- SYNCHRONIZATION ----
>> Consider parent thread P with child thread C. How do you ensure
>> proper synchronization and avoid race conditions when P calls wait(C)
>> before C exits? After C exits? How do you ensure that all resources
>> are freed in each case? How about when P terminates without waiting,
>> before C exits? After C exits? Are there any special cases?
C waits in thread_exit() for P to die before it finishes its own
exit, using the can_die semaphore "down"ed by C and "up"ed by P as
it exits. Regardless of whether whether C has terminated, there
is no race on wait(C), because C waits for P's permission before
it frees itself.
Regardless of whether P waits for C, P still "up"s C's can_die
semaphore when P dies, so C will always be freed. (However,
freeing C's resources is delayed until P's death.)
The initial thread is a special case because it has no parent to
wait for it or to "up" its can_die semaphore. Therefore, its
can_die semaphore is initialized to 1.
---- RATIONALE ----
>> Critique your design, pointing out advantages and disadvantages in
>> your design choices.
This design has the advantage of simplicity. Encapsulating most
of the synchronization logic into a new "latch" structure
abstracts what little complexity there is into a separate layer,
making the design easier to reason about. Also, all the new data
members are in `struct thread', with no need for any extra dynamic
allocation, etc., that would require extra management code.
On the other hand, this design is wasteful in that a child thread
cannot free itself before its parent has terminated. A parent
thread that creates a large number of short-lived child threads
could unnecessarily exhaust kernel memory. This is probably
acceptable for implementing kernel threads, but it may be a bad
idea for use with user processes because of the larger number of
resources that user processes tend to own.
</pre></td></tr></table><A NAME="Debugging Tools"></A>
<HR SIZE="6">
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_7.html#SEC93"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_8.html#SEC96"> >> </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>
|
