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