timeouts for WITH-MUTEX and WITH-RECURSIVE-LOCK

[sbcl.git] / doc / manual / threading.texinfo

@node  Threading
@comment  node-name,  next,  previous,  up
@chapter Threading

SBCL supports a fairly low-level threading interface that maps onto
the host operating system's concept of threads or lightweight
processes.  This means that threads may take advantage of hardware
multiprocessing on machines that have more than one CPU, but it does
not allow Lisp control of the scheduler.  This is found in the
SB-THREAD package.

Threads are part of the default build on x86[-64] Linux only.

They are also experimentally supported on: x86[-64] Darwin (Mac OS X),
x86[-64] FreeBSD, x86 SunOS (Solaris), and PPC Linux. On these platforms
threads must be explicitly enabled at build-time, see @file{INSTALL} for
directions.

@menu
* Threading basics::            
* Special Variables::           
* Atomic Operations::           
* Mutex Support::               
* Semaphores::                  
* Waitqueue/condition variables::  
* Barriers::                    
* Sessions/Debugging::          
* Foreign threads::             
* Implementation (Linux x86/x86-64)::  
@end menu

@node Threading basics
@comment  node-name,  next,  previous,  up
@section Threading basics

@lisp
(make-thread (lambda () (write-line "Hello, world")))
@end lisp

@subsection Thread Objects

@include struct-sb-thread-thread.texinfo
@include var-sb-thread-star-current-thread-star.texinfo
@include fun-sb-thread-list-all-threads.texinfo
@include fun-sb-thread-thread-alive-p.texinfo
@include fun-sb-thread-thread-name.texinfo
@include fun-sb-thread-main-thread-p.texinfo
@include fun-sb-thread-main-thread.texinfo

@subsection Making, Returning From, Joining, and Yielding Threads

@include fun-sb-thread-make-thread.texinfo
@include macro-sb-thread-return-from-thread.texinfo
@include fun-sb-thread-abort-thread.texinfo
@include fun-sb-thread-join-thread.texinfo
@include fun-sb-thread-thread-yield.texinfo

@subsection Asynchronous Operations

@include fun-sb-thread-interrupt-thread.texinfo
@include fun-sb-thread-terminate-thread.texinfo

@subsection Miscellaneous Operations

@include fun-sb-thread-symbol-value-in-thread.texinfo

@subsection Error Conditions

@include condition-sb-thread-thread-error.texinfo
@include fun-sb-thread-thread-error-thread.texinfo

@c @include condition-sb-thread-symbol-value-in-thread-error.texinfo
@include condition-sb-thread-interrupt-thread-error.texinfo
@include condition-sb-thread-join-thread-error.texinfo

@node Special Variables
@comment  node-name,  next,  previous,  up
@section Special Variables

The interaction of special variables with multiple threads is mostly
as one would expect, with behaviour very similar to other
implementations.

@itemize
@item
global special values are visible across all threads;
@item
bindings (e.g. using LET) are local to the thread;
@item
threads do not inherit dynamic bindings from the parent thread
@end itemize

The last point means that

@lisp
(defparameter *x* 0)
(let ((*x* 1))
  (sb-thread:make-thread (lambda () (print *x*))))
@end lisp

prints @code{0} and not @code{1} as of 0.9.6.

@node Atomic Operations
@comment  node-name,  next,  previous,  up
@section Atomic Operations

Following atomic operations are particularly useful for implementing
lockless algorithms.

@include macro-sb-ext-atomic-decf.texinfo
@include macro-sb-ext-atomic-incf.texinfo
@include macro-sb-ext-atomic-pop.texinfo
@include macro-sb-ext-atomic-push.texinfo
@include macro-sb-ext-atomic-update.texinfo
@include macro-sb-ext-compare-and-swap.texinfo

@unnumberedsubsec CAS Protocol

Our @code{compare-and-swap} is user-extensible using a protocol
similar to @code{setf}, allowing users to add CAS support to new
places via eg. @code{defcas}.

At the same time, new atomic operations can be built on top of CAS
using @code{get-cas-expansion}. See @code{atomic-update},
@code{atomic-push}, and €@code{atomic-pop} for example of how to do
this.

@include macro-sb-ext-cas.texinfo
@include macro-sb-ext-define-cas-expander.texinfo
@include macro-sb-ext-defcas.texinfo
@include fun-sb-ext-get-cas-expansion.texinfo

@node Mutex Support
@comment  node-name,  next,  previous,  up
@section Mutex Support

Mutexes are used for controlling access to a shared resource. One
thread is allowed to hold the mutex, others which attempt to take it
will be made to wait until it's free. Threads are woken in the order
that they go to sleep.

@lisp
(defpackage :demo (:use "CL" "SB-THREAD" "SB-EXT"))

(in-package :demo)

(defvar *a-mutex* (make-mutex :name "my lock"))

(defun thread-fn ()
  (format t "Thread ~A running ~%" *current-thread*)
  (with-mutex (*a-mutex*)
    (format t "Thread ~A got the lock~%" *current-thread*)
    (sleep (random 5)))
  (format t "Thread ~A dropped lock, dying now~%" *current-thread*))

(make-thread #'thread-fn)
(make-thread #'thread-fn)
@end lisp

@include struct-sb-thread-mutex.texinfo

@include macro-sb-thread-with-mutex.texinfo
@include macro-sb-thread-with-recursive-lock.texinfo

@include fun-sb-thread-make-mutex.texinfo
@include fun-sb-thread-mutex-name.texinfo
@include fun-sb-thread-mutex-owner.texinfo
@include fun-sb-thread-mutex-value.texinfo
@include fun-sb-thread-grab-mutex.texinfo
@include fun-sb-thread-release-mutex.texinfo

@node Semaphores
@comment  node-name,  next,  previous,  up
@section Semaphores

Semaphores are among other things useful for keeping track of a
countable resource, eg. messages in a queue, and sleep when the
resource is exhausted.

@include struct-sb-thread-semaphore.texinfo
@include fun-sb-thread-make-semaphore.texinfo
@include fun-sb-thread-signal-semaphore.texinfo
@include fun-sb-thread-wait-on-semaphore.texinfo
@include fun-sb-thread-try-semaphore.texinfo
@include fun-sb-thread-semaphore-count.texinfo
@include fun-sb-thread-semaphore-name.texinfo

@include struct-sb-thread-semaphore-notification.texinfo
@include fun-sb-thread-make-semaphore-notification.texinfo
@include fun-sb-thread-semaphore-notification-status.texinfo
@include fun-sb-thread-clear-semaphore-notification.texinfo

@node Waitqueue/condition variables
@comment  node-name,  next,  previous,  up
@section Waitqueue/condition variables

These are based on the POSIX condition variable design, hence the
annoyingly CL-conflicting name. For use when you want to check a
condition and sleep until it's true. For example: you have a shared
queue, a writer process checking ``queue is empty'' and one or more
readers that need to know when ``queue is not empty''. It sounds
simple, but is astonishingly easy to deadlock if another process runs
when you weren't expecting it to.

There are three components:

@itemize
@item
the condition itself (not represented in code)

@item
the condition variable (a.k.a waitqueue) which proxies for it

@item
a lock to hold while testing the condition
@end itemize

Important stuff to be aware of:

@itemize
@item
when calling condition-wait, you must hold the mutex. condition-wait
will drop the mutex while it waits, and obtain it again before
returning for whatever reason;

@item
likewise, you must be holding the mutex around calls to
condition-notify;

@item
a process may return from condition-wait in several circumstances: it
is not guaranteed that the underlying condition has become true. You
must check that the resource is ready for whatever you want to do to
it.

@end itemize

@lisp
(defvar *buffer-queue* (make-waitqueue))
(defvar *buffer-lock* (make-mutex :name "buffer lock"))

(defvar *buffer* (list nil))

(defun reader ()
  (with-mutex (*buffer-lock*)
    (loop
     (condition-wait *buffer-queue* *buffer-lock*)
     (loop
      (unless *buffer* (return))
      (let ((head (car *buffer*)))
        (setf *buffer* (cdr *buffer*))
        (format t "reader ~A woke, read ~A~%"
                *current-thread* head))))))

(defun writer ()
  (loop
   (sleep (random 5))
   (with-mutex (*buffer-lock*)
     (let ((el (intern
                (string (code-char
                         (+ (char-code #\A) (random 26)))))))
       (setf *buffer* (cons el *buffer*)))
     (condition-notify *buffer-queue*))))

(make-thread #'writer)
(make-thread #'reader)
(make-thread #'reader)
@end lisp

@include struct-sb-thread-waitqueue.texinfo
@include fun-sb-thread-make-waitqueue.texinfo
@include fun-sb-thread-waitqueue-name.texinfo
@include fun-sb-thread-condition-wait.texinfo
@include fun-sb-thread-condition-notify.texinfo
@include fun-sb-thread-condition-broadcast.texinfo

@node Barriers
@comment  node-name,  next,  previous,  up
@section Barriers

These are based on the Linux kernel barrier design, which is in turn
based on the Alpha CPU memory model.  They are presently implemented for
x86, x86-64, and PPC systems, and behave as compiler barriers on all
other CPUs.

In addition to explicit use of the @code{sb-thread:barrier} macro, the
following functions and macros also serve as @code{:memory} barriers:

@itemize
@item
@code{sb-ext:atomic-decf}, @code{sb-ext:atomic-incf}, @code{sb-ext:atomic-push},
and @code{sb-ext:atomic-pop}.
@item
@code{sb-ext:compare-and-swap}.
@item
@code{sb-thread:grab-mutex}, @code{sb-thread:release-mutex},
@code{sb-thread:with-mutex} and @code{sb-thread:with-recursive-lock}.
@item
@code{sb-thread:signal-semaphore}, @code{sb-thread:try-semaphore} and
@code{sb-thread:wait-on-semaphore}.
@item
@code{sb-thread:condition-wait}, @code{sb-thread:condition-notify} and
@code{sb-thread:condition-broadcast}.
@end itemize

@include macro-sb-thread-barrier.texinfo

@node Sessions/Debugging
@comment  node-name,  next,  previous,  up
@section Sessions/Debugging

If the user has multiple views onto the same Lisp image (for example,
using multiple terminals, or a windowing system, or network access)
they are typically set up as multiple @dfn{sessions} such that each
view has its own collection of foreground/background/stopped threads.
A thread which wishes to create a new session can use
@code{sb-thread:with-new-session} to remove itself from the current
session (which it shares with its parent and siblings) and create a
fresh one.
# See also @code{sb-thread:make-listener-thread}.

Within a single session, threads arbitrate between themselves for the
user's attention.  A thread may be in one of three notional states:
foreground, background, or stopped.  When a background process
attempts to print a repl prompt or to enter the debugger, it will stop
and print a message saying that it has stopped.  The user at his
leisure may switch to that thread to find out what it needs.  If a
background thread enters the debugger, selecting any restart will put
it back into the background before it resumes.  Arbitration for the
input stream is managed by calls to @code{sb-thread:get-foreground}
(which may block) and @code{sb-thread:release-foreground}.

@node Foreign threads
@comment  node-name,  next,  previous,  up
@section Foreign threads

Direct calls to @code{pthread_create} (instead of @code{MAKE-THREAD})
create threads that SBCL is not aware of, these are called foreign
threads. Currently, it is not possible to run Lisp code in such
threads. This means that the Lisp side signal handlers cannot work.
The best solution is to start foreign threads with signals blocked,
but since third party libraries may create threads, it is not always
feasible to do so. As a workaround, upon receiving a signal in a
foreign thread, SBCL changes the thread's sigmask to block all signals
that it wants to handle and resends the signal to the current process
which should land in a thread that does not block it, that is, a Lisp
thread.

The resignalling trick cannot work for synchronously triggered signals
(SIGSEGV and co), take care not to trigger any. Resignalling for
synchronously triggered signals in foreign threads is subject to
@code{--lose-on-corruption}, see @ref{Runtime Options}.

@node Implementation (Linux x86/x86-64)
@comment  node-name,  next,  previous,  up
@section Implementation (Linux x86/x86-64)

Threading is implemented using pthreads and some Linux specific bits
like futexes.

On x86 the per-thread local bindings for special variables is achieved
using the %fs segment register to point to a per-thread storage area.
This may cause interesting results if you link to foreign code that
expects threading or creates new threads, and the thread library in
question uses %fs in an incompatible way. On x86-64 the r12 register
has a similar role.

Queues require the @code{sys_futex()} system call to be available:
this is the reason for the NPTL requirement.  We test at runtime that
this system call exists.

Garbage collection is done with the existing Conservative Generational
GC.  Allocation is done in small (typically 8k) regions: each thread
has its own region so this involves no stopping. However, when a
region fills, a lock must be obtained while another is allocated, and
when a collection is required, all processes are stopped.  This is
achieved by sending them signals, which may make for interesting
behaviour if they are interrupted in system calls.  The streams
interface is believed to handle the required system call restarting
correctly, but this may be a consideration when making other blocking
calls e.g. from foreign library code.

Large amounts of the SBCL library have not been inspected for
thread-safety.  Some of the obviously unsafe areas have large locks
around them, so compilation and fasl loading, for example, cannot be
parallelized.  Work is ongoing in this area.

A new thread by default is created in the same POSIX process group and
session as the thread it was created by.  This has an impact on
keyboard interrupt handling: pressing your terminal's intr key
(typically @kbd{Control-C}) will interrupt all processes in the
foreground process group, including Lisp threads that SBCL considers
to be notionally `background'.  This is undesirable, so background
threads are set to ignore the SIGINT signal.

@code{sb-thread:make-listener-thread} in addition to creating a new
Lisp session makes a new POSIX session, so that pressing
@kbd{Control-C} in one window will not interrupt another listener -
this has been found to be embarrassing.