doc/charm++: startup text revisions
[charm.git] / doc / converse / threads.tex
1 \chapter{Threads}
2
3 The calls in this chapter can be used to put together runtime systems
4 for languages that support threads.
5 This threads package, like most thread packages, provides basic
6 functionality for creating threads, destroying threads, yielding, 
7 suspending, and awakening a suspended thread. In
8 addition, it provides facilities whereby you can write your own thread
9 schedulers.  
10
11 \section{Basic Thread Calls}
12
13 \function{typedef struct CthThreadStruct *CthThread;}
14 \index{CthThread}
15 \desc{This is an opaque type defined in {\tt converse.h}.  It represents
16 a first-class thread object.  No information is publicized about the
17 contents of a CthThreadStruct.}
18
19 \function{typedef void (CthVoidFn)();}
20 \index{CthVoidFn}
21 \desc{This is a type defined in {\tt converse.h}.  It represents
22 a function that returns nothing.}
23
24 \function{typedef CthThread (CthThFn)();}
25 \index{CthThFn}
26 \desc{This is a type defined in {\tt converse.h}.  It represents
27 a function that returns a CthThread.}
28
29 \function{CthThread CthSelf()}
30 \index{CthSelf}
31 \desc{Returns the currently-executing thread.  Note: even the initial
32 flow of control that inherently existed when the program began
33 executing {\tt main} counts as a thread.  You may retrieve that thread
34 object using {\tt CthSelf} and use it like any other.}
35
36 \function{CthThread CthCreate(CthVoidFn fn, void *arg, int size)}
37 \index{CthCreate}
38 \desc{Creates a new thread object.  The thread is not given control
39 yet.  To make the thread execute, you must push it into the
40 scheduler queue, using CthAwaken below.  When (and if) the thread
41 eventually receives control, it will begin executing the specified
42 function {\tt fn} with the specified argument.  The {\tt size}
43 parameter specifies the stack size in bytes, 0 means use the default
44 size.  Caution: almost all threads are created with CthCreate, but not
45 all.  In particular, the one initial thread of control that came into
46 existence when your program was first {\tt exec}'d was not created
47 with {\tt CthCreate}, but it can be retrieved (say, by calling {\tt
48 CthSelf} in {\tt main}), and it can be used like any other {\tt
49 CthThread}.}
50
51 \function{CthThread CthCreateMigratable(CthVoidFn fn, void *arg, int size)}
52 \index{CthCreateMigratable}
53 \desc{
54 Create a thread that can later be moved to other processors.
55 Otherwise identical to CthCreate.
56
57 This is only a hint to the runtime system; some threads
58 implementations cannot migrate threads, others always create
59 migratable threads.  In these cases, CthCreateMigratable is
60 equivalent to CthCreate.
61 }
62
63 \function{CthThread CthPup(pup\_er p,CthThread t)}
64 \index{CthPup}
65 \desc{
66 Pack/Unpack a thread.  This can be used to save a thread to disk,
67 migrate a thread between processors, or checkpoint the state of a thread.
68
69 Only a suspended thread can be Pup'd.  Only a thread created with
70 CthCreateMigratable can be Pup'd.
71 }
72
73 \function{void CthFree(CthThread t)}
74 \index{CthFree}
75 \desc{Frees thread {\tt t}.  You may ONLY free the
76 currently-executing thread (yes, this sounds strange, it's
77 historical).  Naturally, the free will actually be postponed until the
78 thread suspends.  To terminate itself, a thread calls
79 {\tt CthFree(CthSelf())}, then gives up control to another thread.}
80
81 \function{void CthSuspend()}
82 \index{CthSuspend}
83 \desc{Causes the current thread to stop executing.
84 The suspended thread will not start executing again until somebody
85 pushes it into the scheduler queue again, using CthAwaken below.  Control
86 transfers to the next task in the scheduler queue.}
87
88 \function{void CthAwaken(CthThread t)}
89 \index{CthAwaken}
90 \desc{Pushes a thread into the scheduler queue.  Caution: a thread
91 must only be in the queue once.  Pushing it in twice is a crashable
92 error.}
93
94 \function{void CthAwakenPrio(CthThread t, int strategy, int priobits, int *prio)}
95 \index{CthAwakenPrio}
96 \desc{Pushes a thread into the scheduler queue with priority specified by 
97 {\tt priobits} and {\tt prio} and queueing strategy {\tt strategy}.  
98 Caution: a thread
99 must only be in the queue once.  Pushing it in twice is a crashable
100 error. {\tt prio} is not copied internally, and is used when the scheduler 
101 dequeues the message, so it should not be reused until then.}
102
103 \function{void CthYield()}
104 \index{CthYield}
105 \desc{This function is part of the scheduler-interface.  It simply
106 executes {\tt \{ CthAwaken(CthSelf()); CthSuspend(); \} }.  This combination
107 gives up control temporarily, but ensures that control will eventually
108 return.}
109
110 \function{void CthYieldPrio(int strategy, int priobits, int *prio)}
111 \index{CthYieldPrio}
112 \desc{This function is part of the scheduler-interface.  It simply
113 executes \\
114 {\tt\{CthAwakenPrio(CthSelf(),strategy,priobits,prio);CthSuspend();\}}\\
115 This combination
116 gives up control temporarily, but ensures that control will eventually
117 return.}
118
119 \function{CthThread CthGetNext(CthThread t)}
120 \index{CthGetNext}
121 \desc{Each thread contains space for the user to store a ``next'' field (the
122 functions listed here pay no attention to the contents of this field).
123 This field is typically used by the implementors of mutexes, condition
124 variables, and other synchronization abstractions to link threads
125 together into queues.  This function returns the contents of the next field.}
126
127 \function{void CthSetNext(CthThread t, CthThread next)}
128 \index{CthGetNext}
129 \desc{Each thread contains space for the user to store a ``next'' field (the
130 functions listed here pay no attention to the contents of this field).
131 This field is typically used by the implementors of mutexes, condition
132 variables, and other synchronization abstractions to link threads
133 together into queues.  This function sets the contents of the next field.}
134
135 \section{Thread Scheduling and Blocking Restrictions}
136
137 \converse{} threads use a scheduler queue, like any other threads
138 package.  We chose to use the same queue as the one used for \converse{}
139 messages (see section \ref{schedqueue}).  Because of this, thread
140 context-switching will not work unless there is a thread polling for
141 messages.  A rule of thumb, with \converse{}, it is best to have a thread
142 polling for messages at all times.  In \converse{}'s normal mode (see
143 section \ref{initial}), this happens automatically.  However, in
144 user-calls-scheduler mode, you must be aware of it.
145
146 There is a second caution associated with this design.  There is a
147 thread polling for messages (even in normal mode, it's just hidden in
148 normal mode).  The continuation of your computation depends on that
149 thread --- you must not block it.  In particular, you must not call
150 blocking operations in these places:
151
152 \begin{itemize}
153
154 \item{In the code of a \converse{} handler (see sections \ref{handler1}
155 and \ref{handler2}).}
156
157 \item{In the code of the \converse{} start-function (see section
158 \ref{initial}).}
159
160 \end{itemize}
161
162 These restrictions are usually easy to avoid.  For example, if you
163 wanted to use a blocking operation inside a \converse{} handler, you
164 would restructure the code so that the handler just creates a new
165 thread and returns.  The newly-created thread would then do the work
166 that the handler originally did.
167
168 \section{Thread Scheduling Hooks}
169
170 Normally, when you CthAwaken a thread, it goes into the primary
171 ready-queue: namely, the main \converse{} queue described in section
172 \ref{schedqueue}.  However, it is possible to hook a thread to make
173 it go into a different ready-queue.  That queue doesn't have to be
174 priority-queue: it could be FIFO, or LIFO, or in fact it could handle
175 its threads in any complicated order you desire.  This is a powerful
176 way to implement your own scheduling policies for threads.
177
178 To achieve this, you must first implement a new kind of ready-queue.
179 You must implement a function that inserts threads into this queue.
180 The function must have this prototype:
181
182 {\bf void awakenfn(CthThread t, int strategy, int priobits, int *prio);}
183
184 When a thread suspends, it must choose a new thread to transfer control
185 to.  You must implement a function that makes the decision: which thread
186 should the current thread transfer to.  This function must have this
187 prototype:
188
189 {\bf CthThread choosefn();}
190
191 Typically, the choosefn would choose a thread from your ready-queue.
192 Alternately, it might choose to always transfer control to a central
193 scheduling thread.
194
195 You then configure individual threads to actually use this new
196 ready-queue.  This is done using CthSetStrategy:
197
198 \function{void CthSetStrategy(CthThread t, CthAwkFn awakenfn, CthThFn choosefn)}
199 \index{CthSetStrategy}
200 \desc{Causes the thread to use the specified \param{awakefn} whenever
201 you CthAwaken it, and the specified \param{choosefn} whenever you
202 CthSuspend it.}
203
204 CthSetStrategy alters the behavior of CthSuspend and CthAwaken.
205 Normally, when a thread is awakened with CthAwaken, it gets inserted
206 into the main ready-queue.  Setting the thread's {\tt awakenfn} will
207 cause the thread to be inserted into your ready-queue instead.
208 Similarly, when a thread suspends using CthSuspend, it normally
209 transfers control to some thread in the main ready-queue.  Setting the
210 thread's {\tt choosefn} will cause it to transfer control to a thread
211 chosen by your {\tt choosefn} instead.
212
213 You may reset a thread to its normal behavior using CthSetStrategyDefault:
214
215 \function{void CthSetStrategyDefault(CthThread t)}
216 \index{CthSetStrategyDefault}
217 \desc{Restores the value of \param{awakefn} and \param{choosefn} to
218 their default values.  This implies that the next time you CthAwaken
219 the specified thread, it will be inserted into the normal ready-queue.}
220
221 Keep in mind that this only resolves the issue of how threads get into
222 your ready-queue, and how those threads suspend.  To actually make
223 everything ``work out'' requires additional planning: you have to make
224 sure that control gets transferred to everywhere it needs to go.
225
226 Scheduling threads may need to use this function as well:
227
228 \function{void CthResume(CthThread t)}
229 \index{CthResume}
230 \desc{Immediately transfers control to thread {\tt t}.  This routine is
231 primarily intended for people who are implementing schedulers, not for
232 end-users.  End-users should probably call {\tt CthSuspend} or {\tt
233 CthAwaken} (see below).  Likewise, programmers implementing locks,
234 barriers, and other synchronization devices should also probably rely
235 on {\tt CthSuspend} and {\tt CthAwaken}.}
236
237 A final caution about the {\tt choosefn}: it may only return a thread
238 that wants the CPU, eg, a thread that has been awakened using the {\tt
239 awakefn}.  If no such thread exists, if the {\tt choosefn} cannot
240 return an awakened thread, then it must not return at all: instead, it
241 must wait until, by means of some pending IO event, a thread becomes
242 awakened (pending events could be asynchonous disk reads, networked
243 message receptions, signal handlers, etc).  For this reason, many
244 schedulers perform the task of polling the IO devices as a side
245 effect.  If handling the IO event causes a thread to be awakened, then
246 the choosefn may return that thread.  If no pending events exist, then
247 all threads will remain permanently blocked, the program is therefore
248 done, and the {\tt choosefn} should call {\tt exit}.
249
250 There is one minor exception to the rule stated above (``the scheduler
251 may not resume a thread unless it has been declared that the thread
252 wants the CPU using the {\tt awakefn}'').  If a thread {\tt t} is part
253 of the scheduling module, it is permitted for the scheduling module to
254 resume {\tt t} whenever it so desires: presumably, the scheduling
255 module knows when its threads want the CPU.
256
257 \zap{
258 \function{void CthSetVar(CthThread t, void **var, void *val)}
259 \desc{Specifies that the global variable pointed to by {\tt
260 var} should be set to value {\tt val} whenever thread {\tt t} is
261 executing.  {\tt var} should be of type {\tt void *}, or at least
262 should be coercible to a {\tt void *}.  This can be used to associate
263 thread-private data with thread {\tt t}.
264
265 it is intended that this function be used as follows:}
266
267 \begin{alltt}
268     /* User defines a struct th_info containing all the thread-private  */
269     /* data he wishes to associate with threads.  He also defines       */
270     /* a global variable 'current_thread_info' which will always hold   */
271     /* the th_info of the currently-executing thread.                   */
272     struct th_info \{ ... \} *current_thread_info;
273
274     /* User creates a thread 't', and allocates a block of memory       */
275     /* 'tinfo' to hold the thread's private data.  User tells the       */
276     /* system that whenever thread 't' is running, the global variable  */
277     /* 'current_thread_info' should be set to 'tinfo'.  Thus, thread    */
278     /* 't' can access its private data just by dereferencing            */
279     /* 'current_thread_info'.                                           */
280     t = CthCreate( ... );
281     tinfo = (struct th_info *)malloc(sizeof(struct th_info));
282     CthSetVar(t, &current_thread_info, tinfo);
283 \end{alltt}
284
285 \desc{Note: you can use CthSetVar multiple times on a thread, thereby
286 attaching multiple data items to it.  However, each data item slows
287 down context-switch to that thread by a tiny amount.  Therefore, a
288 module should ideally attach no more than one data item to a thread.
289 We allow multiple data items to be attached so that independent
290 modules can attach data to a thread without interfering with each
291 other.}
292
293 \function{void *CthGetVar(CthThread t, void **var)}
294 \desc{This makes it possible to retrieve values previously stored with
295 {\tt CthSetVar} when {\tt t} is {\it not} executing.  Returns the value
296 that {\tt var} will be set to when {\tt t} is running.}
297 }