Don't hardcode the number of gencgc generations.
[sbcl.git] / doc / manual / threading.texinfo
1 @node  Threading
2 @comment  node-name,  next,  previous,  up
3 @chapter Threading
4
5 SBCL supports a fairly low-level threading interface that maps onto
6 the host operating system's concept of threads or lightweight
7 processes.  This means that threads may take advantage of hardware
8 multiprocessing on machines that have more than one CPU, but it does
9 not allow Lisp control of the scheduler.  This is found in the
10 SB-THREAD package.
11
12 Threads are part of the default build on x86[-64] Linux only.
13
14 They are also experimentally supported on: x86[-64] Darwin (Mac OS X),
15 x86[-64] FreeBSD, x86 SunOS (Solaris), and PPC Linux. On these platforms
16 threads must be explicitly enabled at build-time, see @file{INSTALL} for
17 directions.
18
19 @menu
20 * Threading basics::            
21 * Special Variables::           
22 * Atomic Operations::           
23 * Mutex Support::               
24 * Semaphores::                  
25 * Waitqueue/condition variables::  
26 * Barriers::                    
27 * Sessions/Debugging::          
28 * Foreign threads::             
29 * Implementation (Linux x86/x86-64)::  
30 @end menu
31
32 @node Threading basics
33 @comment  node-name,  next,  previous,  up
34 @section Threading basics
35
36 @lisp
37 (make-thread (lambda () (write-line "Hello, world")))
38 @end lisp
39
40 @subsection Thread Objects
41
42 @include struct-sb-thread-thread.texinfo
43 @include var-sb-thread-star-current-thread-star.texinfo
44 @include fun-sb-thread-list-all-threads.texinfo
45 @include fun-sb-thread-thread-alive-p.texinfo
46 @include fun-sb-thread-thread-name.texinfo
47 @include fun-sb-thread-main-thread-p.texinfo
48 @include fun-sb-thread-main-thread.texinfo
49
50 @subsection Making, Returning From, Joining, and Yielding Threads
51
52 @include fun-sb-thread-make-thread.texinfo
53 @include macro-sb-thread-return-from-thread.texinfo
54 @include fun-sb-thread-abort-thread.texinfo
55 @include fun-sb-thread-join-thread.texinfo
56 @include fun-sb-thread-thread-yield.texinfo
57
58 @subsection Asynchronous Operations
59
60 @include fun-sb-thread-interrupt-thread.texinfo
61 @include fun-sb-thread-terminate-thread.texinfo
62
63 @subsection Miscellaneous Operations
64
65 @include fun-sb-thread-symbol-value-in-thread.texinfo
66
67 @subsection Error Conditions
68
69 @include condition-sb-thread-thread-error.texinfo
70 @include fun-sb-thread-thread-error-thread.texinfo
71
72 @c @include condition-sb-thread-symbol-value-in-thread-error.texinfo
73 @include condition-sb-thread-interrupt-thread-error.texinfo
74 @include condition-sb-thread-join-thread-error.texinfo
75
76 @node Special Variables
77 @comment  node-name,  next,  previous,  up
78 @section Special Variables
79
80 The interaction of special variables with multiple threads is mostly
81 as one would expect, with behaviour very similar to other
82 implementations.
83
84 @itemize
85 @item
86 global special values are visible across all threads;
87 @item
88 bindings (e.g. using LET) are local to the thread;
89 @item
90 threads do not inherit dynamic bindings from the parent thread
91 @end itemize
92
93 The last point means that
94
95 @lisp
96 (defparameter *x* 0)
97 (let ((*x* 1))
98   (sb-thread:make-thread (lambda () (print *x*))))
99 @end lisp
100
101 prints @code{0} and not @code{1} as of 0.9.6.
102
103 @node Atomic Operations
104 @comment  node-name,  next,  previous,  up
105 @section Atomic Operations
106
107 Following atomic operations are particularly useful for implementing
108 lockless algorithms.
109
110 @include macro-sb-ext-atomic-decf.texinfo
111 @include macro-sb-ext-atomic-incf.texinfo
112 @include macro-sb-ext-atomic-pop.texinfo
113 @include macro-sb-ext-atomic-push.texinfo
114 @include macro-sb-ext-atomic-update.texinfo
115 @include macro-sb-ext-compare-and-swap.texinfo
116
117 @unnumberedsubsec CAS Protocol
118
119 Our @code{compare-and-swap} is user-extensible using a protocol
120 similar to @code{setf}, allowing users to add CAS support to new
121 places via e.g. @code{defcas}.
122
123 At the same time, new atomic operations can be built on top of CAS
124 using @code{get-cas-expansion}. See @code{atomic-update},
125 @code{atomic-push}, and €@code{atomic-pop} for example of how to do
126 this.
127
128 @include macro-sb-ext-cas.texinfo
129 @include macro-sb-ext-define-cas-expander.texinfo
130 @include macro-sb-ext-defcas.texinfo
131 @include fun-sb-ext-get-cas-expansion.texinfo
132
133 @node Mutex Support
134 @comment  node-name,  next,  previous,  up
135 @section Mutex Support
136
137 Mutexes are used for controlling access to a shared resource. One
138 thread is allowed to hold the mutex, others which attempt to take it
139 will be made to wait until it's free. Threads are woken in the order
140 that they go to sleep.
141
142 @lisp
143 (defpackage :demo (:use "CL" "SB-THREAD" "SB-EXT"))
144
145 (in-package :demo)
146
147 (defvar *a-mutex* (make-mutex :name "my lock"))
148
149 (defun thread-fn ()
150   (format t "Thread ~A running ~%" *current-thread*)
151   (with-mutex (*a-mutex*)
152     (format t "Thread ~A got the lock~%" *current-thread*)
153     (sleep (random 5)))
154   (format t "Thread ~A dropped lock, dying now~%" *current-thread*))
155
156 (make-thread #'thread-fn)
157 (make-thread #'thread-fn)
158 @end lisp
159
160 @include struct-sb-thread-mutex.texinfo
161
162 @include macro-sb-thread-with-mutex.texinfo
163 @include macro-sb-thread-with-recursive-lock.texinfo
164
165 @include fun-sb-thread-make-mutex.texinfo
166 @include fun-sb-thread-mutex-name.texinfo
167 @include fun-sb-thread-mutex-owner.texinfo
168 @include fun-sb-thread-mutex-value.texinfo
169 @include fun-sb-thread-grab-mutex.texinfo
170 @include fun-sb-thread-release-mutex.texinfo
171
172 @node Semaphores
173 @comment  node-name,  next,  previous,  up
174 @section Semaphores
175
176 Semaphores are among other things useful for keeping track of a
177 countable resource, e.g. messages in a queue, and sleep when the
178 resource is exhausted.
179
180 @include struct-sb-thread-semaphore.texinfo
181 @include fun-sb-thread-make-semaphore.texinfo
182 @include fun-sb-thread-signal-semaphore.texinfo
183 @include fun-sb-thread-wait-on-semaphore.texinfo
184 @include fun-sb-thread-try-semaphore.texinfo
185 @include fun-sb-thread-semaphore-count.texinfo
186 @include fun-sb-thread-semaphore-name.texinfo
187
188 @include struct-sb-thread-semaphore-notification.texinfo
189 @include fun-sb-thread-make-semaphore-notification.texinfo
190 @include fun-sb-thread-semaphore-notification-status.texinfo
191 @include fun-sb-thread-clear-semaphore-notification.texinfo
192
193 @node Waitqueue/condition variables
194 @comment  node-name,  next,  previous,  up
195 @section Waitqueue/condition variables
196
197 These are based on the POSIX condition variable design, hence the
198 annoyingly CL-conflicting name. For use when you want to check a
199 condition and sleep until it's true. For example: you have a shared
200 queue, a writer process checking ``queue is empty'' and one or more
201 readers that need to know when ``queue is not empty''. It sounds
202 simple, but is astonishingly easy to deadlock if another process runs
203 when you weren't expecting it to.
204
205 There are three components:
206
207 @itemize
208 @item
209 the condition itself (not represented in code)
210
211 @item
212 the condition variable (a.k.a. waitqueue) which proxies for it
213
214 @item
215 a lock to hold while testing the condition
216 @end itemize
217
218 Important stuff to be aware of:
219
220 @itemize
221 @item
222 when calling condition-wait, you must hold the mutex. condition-wait
223 will drop the mutex while it waits, and obtain it again before
224 returning for whatever reason;
225
226 @item
227 likewise, you must be holding the mutex around calls to
228 condition-notify;
229
230 @item
231 a process may return from condition-wait in several circumstances: it
232 is not guaranteed that the underlying condition has become true. You
233 must check that the resource is ready for whatever you want to do to
234 it.
235
236 @end itemize
237
238 @lisp
239 (defvar *buffer-queue* (make-waitqueue))
240 (defvar *buffer-lock* (make-mutex :name "buffer lock"))
241
242 (defvar *buffer* (list nil))
243
244 (defun reader ()
245   (with-mutex (*buffer-lock*)
246     (loop
247      (condition-wait *buffer-queue* *buffer-lock*)
248      (loop
249       (unless *buffer* (return))
250       (let ((head (car *buffer*)))
251         (setf *buffer* (cdr *buffer*))
252         (format t "reader ~A woke, read ~A~%"
253                 *current-thread* head))))))
254
255 (defun writer ()
256   (loop
257    (sleep (random 5))
258    (with-mutex (*buffer-lock*)
259      (let ((el (intern
260                 (string (code-char
261                          (+ (char-code #\A) (random 26)))))))
262        (setf *buffer* (cons el *buffer*)))
263      (condition-notify *buffer-queue*))))
264
265 (make-thread #'writer)
266 (make-thread #'reader)
267 (make-thread #'reader)
268 @end lisp
269
270 @include struct-sb-thread-waitqueue.texinfo
271 @include fun-sb-thread-make-waitqueue.texinfo
272 @include fun-sb-thread-waitqueue-name.texinfo
273 @include fun-sb-thread-condition-wait.texinfo
274 @include fun-sb-thread-condition-notify.texinfo
275 @include fun-sb-thread-condition-broadcast.texinfo
276
277 @node Barriers
278 @comment  node-name,  next,  previous,  up
279 @section Barriers
280
281 These are based on the Linux kernel barrier design, which is in turn
282 based on the Alpha CPU memory model.  They are presently implemented for
283 x86, x86-64, and PPC systems, and behave as compiler barriers on all
284 other CPUs.
285
286 In addition to explicit use of the @code{sb-thread:barrier} macro, the
287 following functions and macros also serve as @code{:memory} barriers:
288
289 @itemize
290 @item
291 @code{sb-ext:atomic-decf}, @code{sb-ext:atomic-incf}, @code{sb-ext:atomic-push},
292 and @code{sb-ext:atomic-pop}.
293 @item
294 @code{sb-ext:compare-and-swap}.
295 @item
296 @code{sb-thread:grab-mutex}, @code{sb-thread:release-mutex},
297 @code{sb-thread:with-mutex} and @code{sb-thread:with-recursive-lock}.
298 @item
299 @code{sb-thread:signal-semaphore}, @code{sb-thread:try-semaphore} and
300 @code{sb-thread:wait-on-semaphore}.
301 @item
302 @code{sb-thread:condition-wait}, @code{sb-thread:condition-notify} and
303 @code{sb-thread:condition-broadcast}.
304 @end itemize
305
306 @include macro-sb-thread-barrier.texinfo
307
308 @node Sessions/Debugging
309 @comment  node-name,  next,  previous,  up
310 @section Sessions/Debugging
311
312 If the user has multiple views onto the same Lisp image (for example,
313 using multiple terminals, or a windowing system, or network access)
314 they are typically set up as multiple @dfn{sessions} such that each
315 view has its own collection of foreground/background/stopped threads.
316 A thread which wishes to create a new session can use
317 @code{sb-thread:with-new-session} to remove itself from the current
318 session (which it shares with its parent and siblings) and create a
319 fresh one.
320 # See also @code{sb-thread:make-listener-thread}.
321
322 Within a single session, threads arbitrate between themselves for the
323 user's attention.  A thread may be in one of three notional states:
324 foreground, background, or stopped.  When a background process
325 attempts to print a repl prompt or to enter the debugger, it will stop
326 and print a message saying that it has stopped.  The user at his
327 leisure may switch to that thread to find out what it needs.  If a
328 background thread enters the debugger, selecting any restart will put
329 it back into the background before it resumes.  Arbitration for the
330 input stream is managed by calls to @code{sb-thread:get-foreground}
331 (which may block) and @code{sb-thread:release-foreground}.
332
333 @node Foreign threads
334 @comment  node-name,  next,  previous,  up
335 @section Foreign threads
336
337 Direct calls to @code{pthread_create} (instead of @code{MAKE-THREAD})
338 create threads that SBCL is not aware of, these are called foreign
339 threads. Currently, it is not possible to run Lisp code in such
340 threads. This means that the Lisp side signal handlers cannot work.
341 The best solution is to start foreign threads with signals blocked,
342 but since third party libraries may create threads, it is not always
343 feasible to do so. As a workaround, upon receiving a signal in a
344 foreign thread, SBCL changes the thread's sigmask to block all signals
345 that it wants to handle and resends the signal to the current process
346 which should land in a thread that does not block it, that is, a Lisp
347 thread.
348
349 The resignalling trick cannot work for synchronously triggered signals
350 (SIGSEGV and co), take care not to trigger any. Resignalling for
351 synchronously triggered signals in foreign threads is subject to
352 @code{--lose-on-corruption}, see @ref{Runtime Options}.
353
354 @node Implementation (Linux x86/x86-64)
355 @comment  node-name,  next,  previous,  up
356 @section Implementation (Linux x86/x86-64)
357
358 Threading is implemented using pthreads and some Linux specific bits
359 like futexes.
360
361 On x86 the per-thread local bindings for special variables is achieved
362 using the %fs segment register to point to a per-thread storage area.
363 This may cause interesting results if you link to foreign code that
364 expects threading or creates new threads, and the thread library in
365 question uses %fs in an incompatible way. On x86-64 the r12 register
366 has a similar role.
367
368 Queues require the @code{sys_futex()} system call to be available:
369 this is the reason for the NPTL requirement.  We test at runtime that
370 this system call exists.
371
372 Garbage collection is done with the existing Conservative Generational
373 GC.  Allocation is done in small (typically 8k) regions: each thread
374 has its own region so this involves no stopping. However, when a
375 region fills, a lock must be obtained while another is allocated, and
376 when a collection is required, all processes are stopped.  This is
377 achieved by sending them signals, which may make for interesting
378 behaviour if they are interrupted in system calls.  The streams
379 interface is believed to handle the required system call restarting
380 correctly, but this may be a consideration when making other blocking
381 calls e.g. from foreign library code.
382
383 Large amounts of the SBCL library have not been inspected for
384 thread-safety.  Some of the obviously unsafe areas have large locks
385 around them, so compilation and fasl loading, for example, cannot be
386 parallelized.  Work is ongoing in this area.
387
388 A new thread by default is created in the same POSIX process group and
389 session as the thread it was created by.  This has an impact on
390 keyboard interrupt handling: pressing your terminal's intr key
391 (typically @kbd{Control-C}) will interrupt all processes in the
392 foreground process group, including Lisp threads that SBCL considers
393 to be notionally `background'.  This is undesirable, so background
394 threads are set to ignore the SIGINT signal.
395
396 @code{sb-thread:make-listener-thread} in addition to creating a new
397 Lisp session makes a new POSIX session, so that pressing
398 @kbd{Control-C} in one window will not interrupt another listener -
399 this has been found to be embarrassing.