summaryrefslogtreecommitdiffstats
path: root/doc/pintos_7.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_7.html
downloadprogos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.gz
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.bz2
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.zip
initial pintos checkin
Diffstat (limited to 'doc/pintos_7.html')
-rw-r--r--doc/pintos_7.html238
1 files changed, 238 insertions, 0 deletions
diff --git a/doc/pintos_7.html b/doc/pintos_7.html
new file mode 100644
index 0000000..e7ac7b5
--- /dev/null
+++ b/doc/pintos_7.html
@@ -0,0 +1,238 @@
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 Documentation</TITLE>
16
17<META NAME="description" CONTENT="Pintos Projects: Project Documentation">
18<META NAME="keywords" CONTENT="Pintos Projects: Project Documentation">
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="SEC93"></A>
28<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
29<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_6.html#SEC89"> &lt;&lt; </A>]</TD>
30<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_8.html#SEC96"> &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> C. Project Documentation </H1>
39<!--docid::SEC93::-->
40<P>
41
42This chapter presents a sample assignment and a filled-in design
43document for one possible implementation. Its purpose is to give you an
44idea of what we expect to see in your own design documents.
45</P>
46<P>
47
48<A NAME="Sample Assignment"></A>
49<HR SIZE="6">
50<A NAME="SEC94"></A>
51<H2> C.1 Sample Assignment </H2>
52<!--docid::SEC94::-->
53<P>
54
55Implement <CODE>thread_join()</CODE>.
56</P>
57<P>
58
59<A NAME="IDX160"></A>
60</P>
61<DL>
62<DT><U>Function:</U> void <B>thread_join</B> (tid_t <VAR>tid</VAR>)
63<DD>Blocks the current thread until thread <VAR>tid</VAR> exits. If <VAR>A</VAR> is
64the running thread and <VAR>B</VAR> is the argument, then we say that
65&quot;<VAR>A</VAR> joins <VAR>B</VAR>.&quot;
66<P>
67
68Incidentally, the argument is a thread id, instead of a thread pointer,
69because a thread pointer is not unique over time. That is, when a
70thread dies, its memory may be, whether immediately or much later,
71reused for another thread. If thread <VAR>A</VAR> over time had two children
72<VAR>B</VAR> and <VAR>C</VAR> that were stored at the same address, then
73<CODE>thread_join(<VAR>B</VAR>)</CODE> and <CODE>thread_join(<VAR>C</VAR>)</CODE> would be
74ambiguous.
75</P>
76<P>
77
78A thread may only join its immediate children. Calling
79<CODE>thread_join()</CODE> on a thread that is not the caller's child should
80cause the caller to return immediately. Children are not &quot;inherited,&quot;
81that is, if <VAR>A</VAR> has child <VAR>B</VAR> and <VAR>B</VAR> has child <VAR>C</VAR>,
82then <VAR>A</VAR> always returns immediately should it try to join <VAR>C</VAR>,
83even if <VAR>B</VAR> is dead.
84</P>
85<P>
86
87A thread need not ever be joined. Your solution should properly free
88all of a thread's resources, including its <CODE>struct thread</CODE>,
89whether it is ever joined or not, and regardless of whether the child
90exits before or after its parent. That is, a thread should be freed
91exactly once in all cases.
92</P>
93<P>
94
95Joining a given thread is idempotent. That is, joining a thread
96multiple times is equivalent to joining it once, because it has already
97exited at the time of the later joins. Thus, joins on a given thread
98after the first should return immediately.
99</P>
100<P>
101
102You must handle all the ways a join can occur: nested joins (<VAR>A</VAR>
103joins <VAR>B</VAR>, then <VAR>B</VAR> joins <VAR>C</VAR>), multiple joins (<VAR>A</VAR>
104joins <VAR>B</VAR>, then <VAR>A</VAR> joins <VAR>C</VAR>), and so on.
105</P>
106</DL>
107<P>
108
109<A NAME="Sample Design Document"></A>
110<HR SIZE="6">
111<A NAME="SEC95"></A>
112<H2> C.2 Sample Design Document </H2>
113<!--docid::SEC95::-->
114<P>
115
116<TABLE><tr><td>&nbsp;</td><td class=example><pre>
117 +-----------------+
118 | CS 140 |
119 | SAMPLE PROJECT |
120 | DESIGN DOCUMENT |
121 +-----------------+
122
123---- GROUP ----
124
125Ben Pfaff &lt;blp@stanford.edu&gt;
126
127---- PRELIMINARIES ----
128
129&gt;&gt; If you have any preliminary comments on your submission, notes for
130&gt;&gt; the TAs, or extra credit, please give them here.
131
132(This is a sample design document.)
133
134&gt;&gt; Please cite any offline or online sources you consulted while
135&gt;&gt; preparing your submission, other than the Pintos documentation,
136&gt;&gt; course text, and lecture notes.
137
138None.
139
140 JOIN
141 ====
142
143---- DATA STRUCTURES ----
144
145&gt;&gt; Copy here the declaration of each new or changed `struct' or `struct'
146&gt;&gt; member, global or static variable, `typedef', or enumeration.
147&gt;&gt; Identify the purpose of each in 25 words or less.
148
149A &quot;latch&quot; is a new synchronization primitive. Acquires block
150until the first release. Afterward, all ongoing and future
151acquires pass immediately.
152
153 /* Latch. */
154 struct latch
155 {
156 bool released; /* Released yet? */
157 struct lock monitor_lock; /* Monitor lock. */
158 struct condition rel_cond; /* Signaled when released. */
159 };
160
161Added to struct thread:
162
163 /* Members for implementing thread_join(). */
164 struct latch ready_to_die; /* Release when thread about to die. */
165 struct semaphore can_die; /* Up when thread allowed to die. */
166 struct list children; /* List of child threads. */
167 list_elem children_elem; /* Element of `children' list. */
168
169---- ALGORITHMS ----
170
171&gt;&gt; Briefly describe your implementation of thread_join() and how it
172&gt;&gt; interacts with thread termination.
173
174thread_join() finds the joined child on the thread's list of
175children and waits for the child to exit by acquiring the child's
176ready_to_die latch. When thread_exit() is called, the thread
177releases its ready_to_die latch, allowing the parent to continue.
178
179---- SYNCHRONIZATION ----
180
181&gt;&gt; Consider parent thread P with child thread C. How do you ensure
182&gt;&gt; proper synchronization and avoid race conditions when P calls wait(C)
183&gt;&gt; before C exits? After C exits? How do you ensure that all resources
184&gt;&gt; are freed in each case? How about when P terminates without waiting,
185&gt;&gt; before C exits? After C exits? Are there any special cases?
186
187C waits in thread_exit() for P to die before it finishes its own
188exit, using the can_die semaphore &quot;down&quot;ed by C and &quot;up&quot;ed by P as
189it exits. Regardless of whether whether C has terminated, there
190is no race on wait(C), because C waits for P's permission before
191it frees itself.
192
193Regardless of whether P waits for C, P still &quot;up&quot;s C's can_die
194semaphore when P dies, so C will always be freed. (However,
195freeing C's resources is delayed until P's death.)
196
197The initial thread is a special case because it has no parent to
198wait for it or to &quot;up&quot; its can_die semaphore. Therefore, its
199can_die semaphore is initialized to 1.
200
201---- RATIONALE ----
202
203&gt;&gt; Critique your design, pointing out advantages and disadvantages in
204&gt;&gt; your design choices.
205
206This design has the advantage of simplicity. Encapsulating most
207of the synchronization logic into a new &quot;latch&quot; structure
208abstracts what little complexity there is into a separate layer,
209making the design easier to reason about. Also, all the new data
210members are in `struct thread', with no need for any extra dynamic
211allocation, etc., that would require extra management code.
212
213On the other hand, this design is wasteful in that a child thread
214cannot free itself before its parent has terminated. A parent
215thread that creates a large number of short-lived child threads
216could unnecessarily exhaust kernel memory. This is probably
217acceptable for implementing kernel threads, but it may be a bad
218idea for use with user processes because of the larger number of
219resources that user processes tend to own.
220</pre></td></tr></table><A NAME="Debugging Tools"></A>
221<HR SIZE="6">
222<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
223<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_7.html#SEC93"> &lt;&lt; </A>]</TD>
224<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_8.html#SEC96"> &gt;&gt; </A>]</TD>
225<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>
226<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
227<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
228<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
229</TR></TABLE>
230<BR>
231<FONT SIZE="-1">
232This document was generated
233by on <I>March, 6 2012</I>
234using <A HREF="http://texi2html.cvshome.org"><I>texi2html</I></A>
235</FONT>
236
237</BODY>
238</HTML>
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-12 06:04:07 +0000