npthread.html (14167B)
1 <html> 2 <body> 3 <a href="../djb.html">D. J. Bernstein</a> 4 <h1>The npthread library interface</h1> 5 The npthread library manages a collection of <b>threads</b>: 6 pointers to functions that should be called when specified conditions occur. 7 <p> 8 For example, 9 you can tell npthread 10 to call the handle0() function 11 whenever data is available to be read on descriptor 0, 12 and to call the handle6() function 13 whenever data is available to be read on descriptor 6. 14 If neither descriptor has data, 15 npthread will wait until data arrives. 16 <p> 17 The npthread library allows the following seven types of threads: 18 <ul> 19 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 20 as soon as possible. 21 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 22 if the current time is past <tt><i>t</i></tt>. 23 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 24 if UNIX signal <tt><i>s</i></tt> has just arrived. 25 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 26 if child process <tt><i>p</i></tt> has just exited. 27 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 28 if user-defined flag <tt><i>p</i></tt> has just been waved. 29 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 30 when file descriptor <tt><i>d</i></tt> is readable. 31 <li>Call <tt><i>f</i>(<i>n</i>)</tt> 32 when file descriptor <tt><i>d</i></tt> is writable. 33 </ul> 34 <h2><a name="preempt">Preemptive threads versus non-preemptive threads</a></h2> 35 Some thread libraries provide <b>preemptive threads</b>: 36 a function can be called even while another function is active. 37 <p> 38 The npthread library provides <b>non-preemptive threads</b>: 39 specifically, a function must return 40 before npthread calls another function. 41 For example, 42 say you've told npthread 43 to call the handle0() function 44 whenever data is available to be read on descriptor 0, 45 and to call the handle6() function 46 whenever data is available to be read on descriptor 6. 47 If descriptors 0 and 6 both have data, 48 npthread will call handle0() and then handle6(), 49 or it might instead call handle6() and then handle0(); 50 but it will not overlap handle0() and handle6(). 51 <p> 52 Other thread libraries provide <b>semi-preemptive threads</b>: 53 a function does not need to return 54 before another function is called, 55 but it does need to take some explicit action, 56 such as calling a yield() function. 57 (Semi-preemptive threads 58 are sometimes confusingly called non-preemptive threads. 59 The word <b>coroutines</b> can refer to either semi-preemptive threads 60 or non-preemptive threads.) 61 <p> 62 Basic issues to consider in deciding whether to use 63 a preemptive thread library, 64 a semi-preemptive thread library, 65 or a non-preemptive thread library: 66 <ul> 67 <li>With preemptive threads, 68 you have to go to extra effort whenever you read or write a global variable 69 (a variable that can interact with another thread). 70 If you fail to do this, 71 you may sporadically corrupt data. 72 <li>With non-preemptive and semi-preemptive threads, 73 you have to go to extra effort whenever you perform an operation 74 that can take lots of time, 75 such as calling the UNIX read() function. 76 If you fail to do this, 77 your program may freeze. 78 <li>Preemptive threads and semi-preemptive threads 79 tend to chew up much more memory than non-preemptive threads. 80 In theory, the <b>continuation</b> (stack and saved registers) 81 of a semi-preemptive thread should take the same space 82 as the equivalent structure in a non-preemptive thread; 83 in practice, it is inconvenient to allocate fewer than 4096 bytes for a stack, 84 while a non-preemptive thread typically fits into 64 bytes. 85 For similar reasons, 86 many preemptive thread systems do not allow more than 512 threads per process. 87 <li>With non-preemptive threads, 88 variables that might naturally be stored in a continuation 89 have to be stored somewhere else. 90 <li>Non-preemptive and semi-preemptive threads compete for one CPU, 91 even if the computer has another CPU available. 92 Two preemptive threads can run on two separate CPUs. 93 </ul> 94 Separate UNIX processes are always preemptive 95 and will take advantage of separate CPUs. 96 A common approach is to split tasks across several UNIX processes, 97 with non-preemptive threads inside each process. 98 <p> 99 The npthread library replaces my old sigsched library. 100 Other non-preemptive thread libraries: 101 Niels Provos's 102 <a href="http://www.monkey.org/~provos/libevent/">libevent</a>, 103 Dan Egnor's 104 <a href="http://liboop.org">liboop</a>, 105 libwww's 106 <a href="http://www.w3.org/Library/src/HTEvent.html">HTEvent</a>, 107 and 108 GLib's 109 <a href="http://developer.gnome.org/doc/API/glib/glib-the-main-event-loop.html">Main Event Loop</a>. 110 Some semi-preemptive thread libraries: 111 Keld Helsgaun's 112 <a href="http://www.dat.ruc.dk/~keld/research/COROUTINE/">COROUTINE</a>, 113 Ralf Engelschall's 114 <a href="http://www.gnu.org/software/pth/">Pth</a> 115 (formerly NPS), 116 and 117 Netscape's 118 <a href="http://state-threads.sourceforge.net">State Threads</a>. 119 The most common preemptive-thread interface 120 is the POSIX thread (Pthread) interface 121 supported by various libraries. 122 <hr> 123 <h2><a name="start">Starting threads</a></h2> 124 <pre> 125 #include "npthread.h" 126 int (*<i>f</i>)(int64); 127 int64 <i>n</i>; 128 npthread_add(<i>f</i>,<i>n</i>); 129 </pre> 130 <tt>npthread_add</tt> creates a new ``important'' thread 131 that will call <tt><i>f</i>(<i>n</i>)</tt> as soon as possible 132 (after <tt>npthread_start</tt> is called). 133 It returns 1 to indicate success. 134 <p> 135 If <tt>npthread_add</tt> runs out of memory, it returns 0 136 without changing the list of threads. 137 <hr> 138 <pre> 139 #include "npthread.h" 140 int (*<i>f</i>)(int64); 141 int64 <i>n</i>; 142 int <i>s</i>; 143 npthread_addsignal(<i>f</i>,<i>n</i>,<i>s</i>); 144 </pre> 145 <tt>npthread_addsignal</tt> creates a new ``unimportant'' thread 146 that will call <tt><i>f</i>(<i>n</i>)</tt> 147 when UNIX signal <tt><i>s</i></tt> is received 148 (after <tt>npthread_start</tt> is called). 149 It returns 1 to indicate success. 150 <p> 151 If <tt>npthread_addsignal</tt> runs out of memory, it returns 0 152 without changing the list of threads. 153 <p> 154 UNIX signals handled by npthread 155 are <i>not</i> an exception to the rule 156 that one thread does not preempt another. 157 For example, after 158 <pre> 159 npthread_add(compute,0); 160 npthread_addsignal(cleanup,0,SIGTERM); 161 npthread_start(); 162 </pre> 163 the function <tt>compute(0)</tt> will be called. 164 If a SIGTERM signal arrives while <tt>compute(0)</tt> is running, 165 it has no immediate effect; 166 <tt>cleanup(0)</tt> will be called <i>after</i> <tt>compute(0)</tt> returns. 167 <p> 168 Do not attempt to use UNIX signals as counters. 169 Two occurrences of a signal in quick succession 170 will be combined into a single occurrence of the signal; 171 a thread watching the signal will be called once, not twice. 172 <hr> 173 <pre> 174 #include "npthread.h" 175 npthread_start(void); 176 </pre> 177 <tt>npthread_start</tt> 178 looks for a thread whose call condition is satisfied, 179 calls the thread function, 180 and repeats, 181 as long as there is at least one ``important'' thread left. 182 It then returns 1. 183 <p> 184 A thread function is required to return one of the following numbers: 185 <ul> 186 <li>1: Continue this thread. 187 The thread will be called again later 188 if its call condition is again satisfied. 189 <li>0: Exit this thread. 190 <tt>npthread_start</tt> eliminates the thread. 191 <li>-1: Abort. 192 <tt>npthread_start</tt> immediately returns -1. 193 </ul> 194 <p> 195 If <tt>npthread_start</tt> has trouble preparing internal resources, 196 it returns 0, setting <tt>errno</tt> to indicate the error. 197 A failure of this type cannot happen once <tt>npthread_start</tt> 198 begins running threads. 199 <p> 200 <tt>npthread_start</tt> 201 does not check every call condition 202 every time it calls a thread function. 203 Its main loop checks many call conditions 204 and then calls many threads. 205 Specifically: 206 <ol> 207 <li>Top of the loop: 208 <tt>npthread_start</tt> checks whether any ``important'' threads are left. 209 It returns if not. 210 <li><tt>npthread_start</tt> checks which descriptors are readable and writable. 211 It marks as ``ready'' 212 every thread waiting for those descriptors. 213 <li><tt>npthread_start</tt> checks the current time. 214 It marks as ``ready'' 215 every thread to be called before this time. 216 It also marks as ``ready'' 217 every thread to be called as soon as possible. 218 <li><tt>npthread_start</tt> checks which UNIX signals have been received. 219 It marks as ``ready'' 220 every thread waiting for those signals. 221 <li><tt>npthread_start</tt> checks for newly exited children. 222 It marks as ``ready'' 223 every thread waiting for those children. 224 <li><tt>npthread_start</tt> 225 marks as ``run now'' each of the ``ready'' threads, 226 and removes all the ``ready'' marks. 227 <li>For each of the ``run now'' threads, in some order, 228 <tt>npthread_start</tt> calls the thread function. 229 User-defined flags may be waved at this time; 230 whenever a user-defined flag is waved, 231 every thread waiting for that flag is marked as ``ready.'' 232 <li><tt>npthread_start</tt> goes back to the top of the loop. 233 </ol> 234 Do not assume that UNIX signals, flag waves, readable descriptors, etc. 235 take effect immediately. 236 For example, if thread 1 waves a flag that thread 2 is watching, 237 it is possible for thread 1 to be called again before thread 2 is called. 238 </ul> 239 <hr> 240 <h2><a name="modify">Modifying threads</a></h2> 241 The following functions modify the current thread. 242 These functions cannot fail; 243 all necessary storage is preallocated by <tt>npthread_add</tt>. 244 <p> 245 These functions are for use solely in thread functions. 246 They must not be called outside <tt>npthread_start</tt>. 247 <hr> 248 <pre> 249 #include "npthread.h" 250 int (*<i>f</i>)(int64); 251 int64 <i>n</i>; 252 npthread_jump(<i>f</i>,<i>n</i>); 253 </pre> 254 <tt>npthread_jump</tt> tells the npthread library 255 that <tt><i>f</i>(<i>n</i>)</tt> 256 is the function to be called by the current thread. 257 <tt>npthread_jump</tt> is a jump, not a subroutine call: 258 it wipes out the previous function pointer. 259 <hr> 260 <pre> 261 #include "npthread.h" 262 npthread_unimportant(void); 263 npthread_important(void); 264 </pre> 265 <tt>npthread_unimportant</tt> changes the current thread 266 from ``important'' to ``unimportant.'' 267 If the thread is already ``unimportant,'' 268 <tt>npthread_unimportant</tt> leaves it alone. 269 <p> 270 <tt>npthread_important</tt> makes the opposite change. 271 <hr> 272 <pre> 273 #include "npthread.h" 274 tai6464 <i>t</i>; 275 npthread_sleepuntil(<i>t</i>); 276 </pre> 277 <tt>npthread_sleepuntil</tt> tells the npthread library 278 to call the current thread when the current time has passed <tt><i>t</i></tt>. 279 Any previous call conditions for the current thread are wiped out. 280 <hr> 281 <pre> 282 #include "npthread.h" 283 int64 <i>p</i>; 284 int <i>status</i>; 285 npthread_child(<i>p</i>); 286 <i>status</i> = npthread_childstatus(); 287 </pre> 288 <tt>npthread_child</tt> tells the npthread library 289 to call the current thread if child process <tt><i>p</i></tt> has just exited. 290 Any previous call conditions for the current thread are wiped out. 291 <p> 292 Once that call happens, 293 <tt>npthread_childstatus()</tt> 294 returns the child's exit status, in the following form: 295 <ul> 296 <li>If the child exited normally: 297 its exit code, between 0 and 255. 298 <li>If the child was terminated by a signal and didn't dump core 299 (or wasn't reported by the system to have dumped core): 300 1024 plus the signal, between 1024 and 1024+255. 301 <li>If the child was terminated by a signal and dumped core: 302 2048 plus the signal, between 2048 and 2048+255. 303 </ul> 304 <hr> 305 <pre> 306 #include "npthread.h" 307 int64 <i>p</i>; 308 npthread_watchflag(<i>p</i>); 309 npthread_waveflag(<i>p</i>); 310 <i>p</i> = npthread_newflag(); 311 </pre> 312 <tt>npthread_watchflag</tt> tells the npthread library 313 to call the current thread if user-defined flag number <tt><i>p</i></tt> 314 has just been waved. 315 Any previous call conditions for the current thread are wiped out. 316 <p> 317 <tt>npthread_waveflag</tt> waves user-defined flag number <tt><i>p</i></tt>. 318 <p> 319 <tt>npthread_newflag</tt> returns a new flag number each time it is called: 320 1, 2, 3, etc. 321 Libraries should use <tt>npthread_newflag</tt> to obtain their flag numbers 322 so that independent libraries do not bump into each other. 323 <p> 324 Do not attempt to use user-defined flag waves as counters. 325 If a thread is watching a flag, 326 and the flag is waved twice in quick succession 327 before the thread has a chance to wake up, 328 the thread will be called once, not twice. 329 <hr> 330 <pre> 331 #include "npthread.h" 332 int64 <i>d</i>; 333 npthread_read(<i>d</i>); 334 npthread_write(<i>d</i>); 335 </pre> 336 <tt>npthread_read</tt> tells the npthread library 337 to call the current thread 338 when file descriptor <tt><i>d</i></tt> is readable. 339 <tt>npthread_write</tt> tells the npthread library 340 to call the current thread 341 when file descriptor <tt><i>d</i></tt> is writable. 342 <p> 343 The descriptor must already be open 344 and known to the <a href="io.html">io library</a>; 345 you must use io_fd() to register descriptors not obtained from io_pipe() etc. 346 The descriptor must remain open until the call condition is changed. 347 <p> 348 Any previous call conditions for the current thread are wiped out. 349 For example, the <tt>npthread_sleepnutil</tt> in 350 <pre> 351 npthread_sleepuntil(tai6464_add(tai6464_now(),networktimeout)); 352 npthread_read(6); 353 return 1; 354 </pre> 355 has no effect. 356 If descriptor 6 is not readable, 357 the thread will not be called again, 358 even after <tt>networktimeout</tt> expires. 359 In contrast, 360 <pre> 361 io_timeout(6,tai6464_add(tai6464_now(),networktimeout)); 362 npthread_read(6); 363 return 1; 364 </pre> 365 will impose a time limit on the readability of descriptor 6. 366 <p> 367 Do not assume that data can actually be read or written 368 merely because of a previous <tt>npthread_read</tt> or <tt>npthread_write</tt>. 369 Data that is readable when <tt>npthread_start</tt> decides to call this thread 370 might be read a moment later by another process. 371 Buffer space available for writing when <tt>npthread_start</tt> decides to call this thread might be used a moment later by another process. 372 <p> 373 Do not assume that data has ever been readable or writable 374 merely because of a previous <tt>npthread_read</tt> or <tt>npthread_write</tt>. 375 The low-level UNIX routines used by 376 <tt>io_wait</tt> could have failed to allocate memory; 377 in this case, <tt>npthread_start</tt> has no 378 choice but to call all threads waiting for descriptors. 379 <hr> 380 <pre> 381 #include "npthread.h" 382 npthread_asap(); 383 </pre> 384 <tt>npthread_asap</tt> tells the npthread library 385 to call the current thread whenever possible. 386 This is how the thread starts out after <tt>npthread_add</tt>. 387 </body> 388 </html>