*** empty log message ***
[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 In this section, we refer to the ``scheduler queue''.  By this, we mean
14 the priority queue described in section \ref{schedqueue}.
15
16
17 \function{typedef struct CthThreadStruct *CthThread;}
18 \index{CthThread}
19 \desc{This is an opaque type defined in {\tt converse.h}.  It represents
20 a first-class thread object.  No information is publicized about the
21 contents of a CthThreadStruct.}
22
23 \function{typedef void (CthVoidFn)();}
24 \index{CthVoidFn}
25 \desc{This is a type defined in {\tt threads.h}.  It represents
26 a function that returns nothing.}
27
28 \function{typedef CthThread (CthThFn)();}
29 \index{CthThFn}
30 \desc{This is a type defined in {\tt threads.h}.  It represents
31 a function that returns a CthThread.}
32
33 \function{CthThread CthSelf()}
34 \index{CthSelf}
35 \desc{Returns the currently-executing thread.  Note: even the initial
36 flow of control that inherently existed when the program began
37 executing {\tt main} counts as a thread.  You may retrieve that thread
38 object using {\tt CthSelf} and use it like any other.}
39
40 \function{CthThread CthCreate(CthVoidFn fn, void *arg, int size)}
41 \index{CthCreate}
42 \desc{Creates a new thread object.  The thread is not given control
43 yet.  To make the thread execute, you must push it into the
44 scheduler queue, using CthAwaken below.  When (and if) the thread
45 eventually receives control, it will begin executing the specified
46 function {\tt fn} with the specified argument.  The {\tt size}
47 parameter specifies the stack size in bytes, 0 means use the default
48 size.  Caution: almost all threads are created with CthCreate, but not
49 all.  In particular, the one initial thread of control that came into
50 existence when your program was first {\tt exec}'d was not created
51 with {\tt CthCreate}, but it can be retrieved (say, by calling {\tt
52 CthSelf} in {\tt main}), and it can be used like any other {\tt
53 CthThread}.}
54
55 \function{void CthFree(CthThread t)}
56 \index{CthFree}
57 \desc{Frees thread {\tt t}.  You may ONLY free the
58 currently-executing thread (yes, this sounds strange, it's
59 historical).  Naturally, the free will actually be postponed until the
60 thread suspends.  To terminate itself, a thread calls
61 {\tt CthFree(CthSelf())}, then gives up control to another thread.}
62
63 \function{void CthSuspend()}
64 \index{CthSuspend}
65 \desc{Causes the current thread to stop executing.
66 The suspended thread will not start executing again until somebody
67 pushes it into the scheduler queue again, using CthAwaken below.  Control
68 transfers to the thread running CsdScheduler.  This has the effect of
69 polling for messages, and possibly transferring control to a
70 thread in the scheduler queue.}
71
72 \function{void CthAwaken(CthThread t)}
73 \index{CthAwaken}
74 \desc{Pushes a thread into the scheduler queue.  Caution: a thread
75 must only be in the queue once.  Pushing it in twice is a crashable
76 error.}
77
78 \function{void CthYield()}
79 \index{CthYield}
80 \desc{This function is part of the scheduler-interface.  It simply
81 executes {\tt \{ CthAwaken(CthSelf()); CthSuspend(); \} }.  This combination
82 gives up control temporarily, but ensures that control will eventually
83 return.}
84
85 \function{CthThread CthGetNext(CthThread t)}
86 \index{CthGetNext}
87 \desc{Each thread contains space for the user to store a ``next'' field (the
88 functions listed here pay no attention to the contents of this field).
89 This field is typically used by the implementors of mutexes, condition
90 variables, and other synchronization abstractions to link threads
91 together into queues.  This function returns the contents of the next field.}
92
93 \function{void CthSetNext(CthThread t, CthThread next)}
94 \index{CthGetNext}
95 \desc{Each thread contains space for the user to store a ``next'' field (the
96 functions listed here pay no attention to the contents of this field).
97 This field is typically used by the implementors of mutexes, condition
98 variables, and other synchronization abstractions to link threads
99 together into queues.  This function sets the contents of the next field.}
100
101 \section{Thread Scheduling Hooks}
102
103 Normally, when you CthAwaken a thread, it goes into the primary
104 ready-queue: namely, the main Converse queue described in section
105 \ref{schedqueue}.  However, it is possible to hook a thread to make
106 it go into a different ready-queue.  That queue doesn't have to be
107 priority-queue: it could be FIFO, or LIFO, or in fact it could handle
108 its threads in any complicated order you desire.  This is a powerful
109 way to implement your own scheduling policies for threads.
110
111 To achieve this, you must first implement a new kind of ready-queue.
112 You must implement a function that inserts threads into this queue.
113 The function must have this prototype:
114
115 {\bf void awakenfn(CthThread t);}
116
117 When a thread suspends, it must choose a new thread to transfer control
118 to.  You must implement a function that makes the decision: which thread
119 should the current thread transfer to.  This function must have this
120 prototype:
121
122 {\bf CthThread choosefn();}
123
124 Typically, the choosefn would choose a thread from your ready-queue.
125 Alternately, it might choose to always transfer control to a central
126 scheduling thread.
127
128 You then configure individual threads to actually use this new
129 ready-queue.  This is done using CthSetStrategy:
130
131 \function{void CthSetStrategy(CthThread t, CthVoidFn awakenfn, CthThFn choosefn)}
132 \index{CthSetStrategy}
133 \desc{Causes the thread to use the specified \param{awakefn} whenever
134 you CthAwaken it, and the specified \param{choosefn} whenever you
135 CthSuspend it.}
136
137 CthSetStrategy alters the behavior of CthSuspend and CthAwaken.
138 Normally, when a thread is awakened with CthAwaken, it gets inserted
139 into the main ready-queue.  Setting the thread's {\tt awakenfn} will
140 cause the thread to be inserted into your ready-queue instead.
141 Similarly, when a thread suspends using CthSuspend, it normally
142 transfers control to some thread in the main ready-queue.  Setting the
143 thread's {\tt choosefn} will cause it to transfer control to a thread
144 chosen by your {\tt choosefn} instead.
145
146 You may reset a thread to its normal behavior using CthSetStrategyDefault:
147
148 \function{void CthSetStrategyDefault(CthThread t)}
149 \index{CthSetStrategyDefault}
150 \desc{Restores the value of \param{awakefn} and \param{choosefn} to
151 their default values.  This implies that the next time you CthAwaken
152 the specified thread, it will be inserted into the normal ready-queue.}
153
154 Keep in mind that this only resolves the issue of how threads get into
155 your ready-queue, and how those threads suspend.  To actually make
156 everything ``work out'' requires additional planning: you have to make
157 sure that control gets transferred to everywhere it needs to go.
158
159 Scheduling threads may need to use this function as well:
160
161 \function{void CthResume(CthThread t)}
162 \index{CthResume}
163 \desc{Immediately transfers control to thread {\tt t}.  This routine is
164 primarily intended for people who are implementing schedulers, not for
165 end-users.  End-users should probably call {\tt CthSuspend} or {\tt
166 CthAwaken} (see below).  Likewise, programmers implementing locks,
167 barriers, and other synchronization devices should also probably rely
168 on {\tt CthSuspend} and {\tt CthAwaken}.}
169
170 A final caution about the {\tt choosefn}: it may only return a thread
171 that wants the CPU, eg, a thread that has been awakened using the {\tt
172 awakefn}.  If no such thread exists, if the {\tt choosefn} cannot
173 return an awakened thread, then it must not return at all: instead, it
174 must wait until, by means of some pending IO event, a thread becomes
175 awakened (pending events could be asynchonous disk reads, networked
176 message receptions, signal handlers, etc).  For this reason, many
177 schedulers perform the task of polling the IO devices as a side
178 effect.  If handling the IO event causes a thread to be awakened, then
179 the choosefn may return that thread.  If no pending events exist, then
180 all threads will remain permanently blocked, the program is therefore
181 done, and the {\tt choosefn} should call {\tt exit}.
182
183 There is one minor exception to the rule stated above (``the scheduler
184 may not resume a thread unless it has been declared that the thread
185 wants the CPU using the {\tt awakefn}'').  If a thread {\tt t} is part
186 of the scheduling module, it is permitted for the scheduling module to
187 resume {\tt t} whenever it so desires: presumably, the scheduling
188 module knows when its threads want the CPU.
189
190 \internal{
191 \function{void CthSetVar(CthThread t, void **var, void *val)}
192 \desc{Specifies that the global variable pointed to by {\tt
193 var} should be set to value {\tt val} whenever thread {\tt t} is
194 executing.  {\tt var} should be of type {\tt void *}, or at least
195 should be coercible to a {\tt void *}.  This can be used to associate
196 thread-private data with thread {\tt t}.
197
198 it is intended that this function be used as follows:}
199
200 \begin{verbatim}
201     /* User defines a struct th_info containing all the thread-private  */
202     /* data he wishes to associate with threads.  He also defines       */
203     /* a global variable 'current_thread_info' which will always hold   */
204     /* the th_info of the currently-executing thread.                   */
205     struct th_info { ... } *current_thread_info;
206
207     /* User creates a thread 't', and allocates a block of memory       */
208     /* 'tinfo' to hold the thread's private data.  User tells the       */
209     /* system that whenever thread 't' is running, the global variable  */
210     /* 'current_thread_info' should be set to 'tinfo'.  Thus, thread    */
211     /* 't' can access its private data just by dereferencing            */
212     /* 'current_thread_info'.                                           */
213     t = CthCreate( ... );
214     tinfo = (struct th_info *)malloc(sizeof(struct th_info));
215     CthSetVar(t, &current_thread_info, tinfo);
216 \end{verbatim}
217
218 \desc{Note: you can use CthSetVar multiple times on a thread, thereby
219 attaching multiple data items to it.  However, each data item slows
220 down context-switch to that thread by a tiny amount.  Therefore, a
221 module should ideally attach no more than one data item to a thread.
222 We allow multiple data items to be attached so that independent
223 modules can attach data to a thread without interfering with each
224 other.}
225
226 \function{void *CthGetVar(CthThread t, void **var)}
227 \desc{This makes it possible to retrieve values previously stored with
228 {\tt CthSetVar} when {\tt t} is {\it not} executing.  Returns the value
229 that {\tt var} will be set to when {\tt t} is running.}
230 }