# (lispkit thread) Library `(lispkit thread)` provides programming abstractions facilitating multi-threaded programming. LispKit's thread system offers mechanisms for creating new threads of execution and for synchronizing them. The abstractions provided by this library only offer low-level support for multi-threading and access control. Other libraries such as `(lispkit thread channel)` provide higher-level abstractions built on top of `(lispkit thread)`. Library `(lispkit thread)` defines the following data types: * Threads (a virtual processor which shares object space with all other threads) * Mutexes (a mutual exclusion device, also known as a lock and binary semaphore) * Condition variables (a set of blocked threads) Some exception datatypes related to multi-threading are also specified, and a general mechanism for handling such exceptions is provided. The design of this library as well as most of this documentation originates from SRFI 18 by Marc Feeley. ## Threads A thread in LispKit encapsulates a *thunk* which it eventually executes, a *name* identifying the thread, a *tag* for storing associated (thread-local) data, a list of mutexes it owns, as well as an end-result and end-exception field for eventually capturing the result of the executed thread. A thread is in exactly one of the following states: new, runnable, blocked, and terminated. ### Thread states A "running" thread is a thread that is currently executing. There can be more than one running thread on a multiprocessor machine. A "runnable" thread is a thread that is ready to execute or running. A thread is "blocked" if it is waiting for a mutex to become unlocked, the end of a "sleep" period, etc. A "new" thread is a thread that has not yet become runnable. A new thread becomes runnable when it is started explicitly. A "terminated" thread is a thread that can no longer become runnable. Deadlocked threads are not considered terminated. The only valid transitions between the thread states are from new to runnable, between runnable and blocked, and from any state to terminated:

The API of library `(lispkit thread)` provides procedures for triggering thread state transitions and for determining the current state of threads. ### Primordial thread The execution of a program is initially under the control of a single thread known as the "primordial thread". The primordial thread has name `main` and a tag referring to a mutable box for storing thread-local data. All threads are terminated when the primordial thread terminates. Expressions entered in the read-eval-print loop of LispKit are executed on the primordial thread. Whenever execution of an expression is finished, all threads (except for the primordial thread) are terminated automatically. ### Memory coherency Read and write operations on the store, such as reading and writing a variable, an element of a vector or a string, are not necessarily atomic. It is an error for a thread to write a location in the store while some other thread reads or writes that same location. It is the responsibility of the application to avoid write/read and write/write races through appropriate uses of the synchronization primitives. Concurrent reads and writes to ports are allowed, including input and output to the console. ### Dynamic environment The "dynamic environment" is a structure which allows the system to find the value returned by `current-input-port`, `current-output-port`, etc. The procedures `with-input-from-file`, `with-output-to-file`, etc. extend the dynamic environment to produce a new dynamic environment which is in effect for the duration of the call to the thunk passed as the last argument. LispKit provides procedures and special forms to define new "dynamic variables" and bind them in the dynamic environment via `make-parameter` and `parameterize`. Each thread has its own dynamic environment. When a thread's dynamic environment is extended this does not affect the dynamic environment of other threads. When a thread creates a continuation, the thread's dynamic environment and the dynamic-wind stack are saved within the continuation. When this continuation is invoked, the required dynamic-wind before and after thunks are called and the saved dynamic environment is reinstated as the dynamic environment of the current thread. During the call to each required dynamic-wind before and after thunk, the dynamic environment and the dynamic-wind stack in effect when the corresponding dynamic-wind was executed are reinstated. Note that this specification clearly defines the semantics of calling `call-with-current-continuation` or invoking a continuation within a before or after thunk. The semantics are well defined even when a continuation created by another thread is invoked. ### Thread-management API **(current-thread)**

Returns the current thread, i.e. the thread executing the current expression. **(thread? *****obj*****)**

Returns `#t` if *obj* is a thread object, otherwise `#f` is returned. ```scheme (thread? (current-thread)) ⇒ #t (thread? 12) ⇒ #f ``` **(make-thread *****thunk*****)**

\ \&#xNAN;**(make-thread *****thunk name*****)**\ \&#xNAN;**(make-thread *****thunk name tag*****)** Creates a new thread for executing *thunk*. Each thread has a thunk to execute as well as a *name* identifying the thread and a *tag* which can be used to associate arbitrary objects with a thread. Both *name* and *tag* can be arbitrary values. The default for *name* and *tag* is `#f`. New threads are not automatically made runnable; the procedure `thread-start!` must be used for that. Besides *name* and *tag*, a thread encapsulates an end-result, an end-exception, as well as a list of locked/owned mutexes. The thread's execution consists of a call to *thunk* with the "initial continuation". This continuation causes the (then) current thread to store the result in its end-result field, abandon all mutexes it owns, and finally terminate. The dynamic-wind stack of the initial continuation is empty. The thread inherits the dynamic environment from the current thread. Moreover, in this dynamic environment the exception handler is bound to the "initial exception handler" which is a unary procedure which causes the (then) current thread to store in its end-exception field an "uncaught exception" object whose "reason" is the argument of the handler, abandon all mutexes it owns, and finally terminate. **(thread *****stmt ...*****)**

Creates a new thread for executing the statements *stmt* ... . This statement is equivalent to: ```scheme (make-thread (thunk stmt ...)) ``` **(spawn *****thunk*****)**

\ \&#xNAN;**(spawn *****thunk name*****)**\ \&#xNAN;**(spawn *****thunk name tag*****)** Creates a new thread for executing *thunk* and starts it. Each thread has a thunk to execute as well as a *name* identifying the thread and a *tag* which can be used to associate arbitrary objects with a thread. Both *name* and *tag* can be arbitrary values. This statement is equivalent to: ```scheme (thread-start! (make-thread thunk name tag)) ``` **(go *****stmt ...*****)**

Creates a new thread for executing the statements *stmt* ... and starts it. This statement is equivalent to: ```scheme (thread-start! (make-thread (thunk stmt ...))) ``` **(parallel *****thunk0 thunk1 ...*****)**

Executes *thunk0* on the current thread, and spawns new threads for executing *thunk1 ...* in parallel. `parallel` only terminates when all parallel computations have terminated. It returns *n* results for *n* thunks provided as arguments. **(parallel/timeout *****timeout default thunk ...*****)**

Executes each *thunk* in parallel on a separate thread and terminates only if all parallel threads have terminated or the *timeout* has triggered. *timeout* is a number specifying the maximum time in seconds the computations are allowed to take. `parallel/timeout` returns *n* results for *n* thunks provided as arguments or *default* in case the timeout triggers. **(thread-name *****thread*****)**

Returns the name of the *thread*. **(thread-tag *****thread*****)**

Returns the tag of the *thread*. **(thread-runnable? *****thread*****)**

Returns `#t` if *thread* is in runnable state; otherwise `#f` is returned. **(thread-blocked? *****thread*****)**

Returns `#t` if *thread* is in runnable state; otherwise `#f` is returned. **(thread-terminated? *****thread*****)**

Returns `#t` if *thread* is in terminated state; otherwise `#f` is returned. **(thread-max-stack)**

\ \&#xNAN;**(thread-max-stack *****limit*****)**\ \&#xNAN;**(thread-max-stack *****thread*****)**\ \&#xNAN;**(thread-max-stack *****thread limit*****)** Returns the maximum stack size or sets it to a new limit. If no arguments are provided, the maximum stack size of the current thread is returned. If just fixnum *limit* is provided as an argument, the current thread's maximum stack size is set to *limit*. If just *thread* is provided as an argument, the maximum stack size of *thread* is returned. If both *thread* and *limit* are provided, then procedure `thread-max-stack` sets the maximum stack size of *thread* to *limit*. Changing the stack size while a thread is running is allowed, but it's not always possible to update the limit. The boolean returned by procedure `thread-max-stack` for forms where the maximum stack size is supposed to be updated, indicates whether the update worked. The return value is `#t` in this case. **(thread-start! *****thread*****)**

Makes *thread* runnable. The *thread* must be a new thread. `thread-start!` returns the *thread*. Executing the following code either prints `ba` or `ab`. ```scheme (let ((t (thread-start! (thread (write 'a))))) (write 'b) (thread-join! t)) ``` **(thread-yield!)**

The current thread exits the running state as if its quantum had expired. Here is an example how one could use `thread-yield`: ```scheme ; a busy loop that avoids being too wasteful of the CPU (let loop () ; try to lock m but don't block (if (mutex-try-lock! m) (begin (display "locked mutex m") (mutex-unlock! m)) (begin (do-something-else) (thread-yield!) ; relinquish rest of quantum (loop)))) ``` **(thread-sleep! *****timeout*****)**

The current thread waits for *timeout* seconds. This blocks the thread only if *timeout* is a positive number. ```scheme ; a clock with a gradual drift: (let loop ((x 1)) (thread-sleep! 1) (write x) (loop (+ x 1))) ; a clock with no drift: (let ((start (current-second))) (let loop ((x 1)) (thread-sleep! (- (+ start x) (current-second))) (write x) (loop (+ x 1)))) ``` **(thread-terminate! *****thread*****)**

\ \&#xNAN;**(thread-terminate! *****thread wait*****)** Causes an abnormal termination of the *thread*. If the *thread* is not already terminated, all mutexes owned by the *thread* become unlocked/abandoned and a "terminated thread exception" object is stored in the *thread*'s end-exception field. By default, the termination of the *thread* will occur before `thread-terminate!` returns, unless parameter *wait* is provided and set to `#f`. If *thread* is the current thread, `thread-terminate!` does not return. This operation must be used carefully because it terminates a thread abruptly and it is impossible for that thread to perform any kind of cleanup. This may be a problem if the thread is in the middle of a critical section where some structure has been put in an inconsistent state. However, another thread attempting to enter this critical section will raise an "abandoned mutex exception" because the mutex is unlocked/abandoned. This helps avoid observing an inconsistent state. **(thread-join! *****thread*****)**

\ \&#xNAN;**(thread-join! *****thread timeout*****)**\ \&#xNAN;**(thread-join! *****thread timeout default*****)** The current thread waits until the *thread* terminates (normally or not) or until the timeout is reached, if *timeout* is provided. *timeout* is a number in seconds relative to the time `thread-join!` is called. If the timeout is reached, *thread-join!* returns *default* if it is provided, otherwise a "join timeout exception" is raised. If the *thread* terminated normally, the content of the end-result field of *thread* is returned, otherwise the content of the end-exception field is raised. Example: ```scheme (let ((th (go (+ 1 2 3)))) (* 10 (thread-join! th))) ⇒ 60 (let ((th (go (error "broken thread")))) (* 10 (thread-join! th))) ⇒ raises: [uncaught] [error] broken thread ``` ## Mutexes A mutex is a synchronization abstraction, enforcing mutual exclusive access to a resource when there are many threads of execution. ### Mutex states A mutex can be in one of four states: *locked* (either *owned* or not *owned*) and *unlocked* (either *abandoned* or *not abandoned*). An attempt to lock a mutex only succeeds if the mutex is in an unlocked state, otherwise the current thread must wait. A mutex in the *locked/owned* state has an associated "owner" thread, which by convention is the thread that is responsible for unlocking the mutex. This case is typical of critical sections implemented as "lock mutex, perform operation, unlock mutex". A mutex in the *locked/not-owned* state is not linked to a particular thread. A mutex becomes locked when a thread locks it using the `mutex-lock!` primitive. A mutex becomes *unlocked/abandoned* when the owner of a *locked/owned* mutex terminates. A mutex becomes *unlocked/not-abandoned* when a thread unlocks it using the `mutex-unlock!` procedure. The mutexes provided by library `(lispkit thread)` do not implement "recursive" mutex semantics. An attempt to lock a mutex that is locked already implies that the current thread must wait, even if the mutex is owned by the current thread. This can lead to a deadlock if no other thread unlocks the mutex. ### Mutex state Upon creation, a mutex can be associated with a tag, which is an arbitrary object used in an application-specific way to associate data with the mutex. ### Mutex-management API **(mutex? *****obj*****)**

Returns `#t` if *obj* is a mutex, otherwise returns `#f`. **(make-mutex)**

\ \&#xNAN;**(make-mutex *****name*****)**\ \&#xNAN;**(make-mutex *****name tag*****)** Returns a new mutex in the *unlocked/not-abandoned* state. The optional *name* is an arbitrary object which identifies the mutex (for debugging purposes), defaulting to `#f`. It is also possible to provide a tag, which is an arbitrary object used in an application-specific way to associate data with the mutex. `#f` is used as a default if the tag is not provided. **(mutex-name *****mutex*****)**

Returns the name of the *mutex*. ```scheme (mutex-name (make-mutex 'foo)) ⇒ foo ``` **(mutex-tag *****mutex*****)**

Returns the tag of the *mutex*. ```scheme (mutex-tag (make-mutex 'id '(1 2 3))) ⇒ (1 2 3) ``` **(mutex-state *****mutex*****)**

Returns the state of the *mutex*. The possible results are: * *T*: the *mutex* is in the *locked/owned* state and thread *T* is the owner of the *mutex* * `not-owned`: the *mutex* is in the locked/not-owned state * `abandoned`: the *mutex* is in the unlocked/abandoned state * `not-abandoned`: the *mutex* is in the unlocked/not-abandoned state ```scheme (mutex-state (make-mutex)) ⇒ not-abandoned (let ((mutex (make-mutex))) (mutex-lock! mutex #f (current-thread)) (let ((state (mutex-state mutex))) (mutex-unlock! mutex) (list state (mutex-state mutex)))) ⇒ (# not-abandoned) ``` **(mutex-lock! *****mutex*****)**

\ \&#xNAN;**(mutex-lock! *****mutex timeout*****)**\ \&#xNAN;**(mutex-lock! *****mutex timeout thread*****)** Locks *mutex*. If *mutex* is already locked, the current thread waits until the *mutex* is unlocked, or until the timeout is reached if *timeout* is supplied. If the timeout is reached, `mutex-lock!` returns `#f`. Otherwise, the state of the *mutex* is changed as follows: * if *thread* is `#f`, the *mutex* becomes *locked/not-owned*, * otherwise, let *T* be *thread* (or the current thread if *thread* is not supplied): if *T* is terminated the *mutex* becomes *unlocked/abandoned*, otherwise *mutex* becomes *locked/owned* with *T* as the owner. After changing the state of the *mutex*, an "abandoned mutex exception" is raised if the *mutex* was *unlocked/abandoned* before the state change, otherwise `mutex-lock!` returns `#t`. It is not an error if the *mutex* is owned by the current thread, but the current thread will have to wait. **(mutex-try-lock! *****mutex*****)**

\ \&#xNAN;**(mutex-try-lock! *****mutex thread*****)** Locks *mutex* with owner *thread* and returns `#t` if *mutex* is not already locked. Otherwise, `#f` is returned. This is equivalent to: `(mutex-lock! mutex 0 thread)` **(mutex-unlock! *****mutex*****)**

\ \&#xNAN;**(mutex-unlock! *****mutex cvar*****)**\ \&#xNAN;**(mutex-unlock! *****mutex cvar timeout*****)** Unlocks the *mutex* by making it *unlocked/not-abandoned*. It is not an error to unlock an unlocked mutex and a mutex that is owned by any thread. If *cvar* is supplied, the current thread is blocked and added to the condition variable *cvar* before unlocking *mutex*. The thread can unblock at any time but no later than when an appropriate call to `condition-variable-signal!` or `condition-variable-broadcast!` is performed, and no later than the timeout (if *timeout* is supplied). If there are threads waiting to lock this *mutex*, the scheduler selects a thread, the mutex becomes *locked/owned* or *locked/not-owned*, and the thread is unblocked. `mutex-unlock!` returns `#f` when the timeout is reached, otherwise it returns `#t`. `mutex-unlock!` is related to the "wait" operation on condition variables available in other thread systems. The main difference is that "wait" automatically locks *mutex* just after the thread is unblocked. This operation is not performed by `mutex-unlock!` and so must be done by an explicit call to `mutex-lock!`. This has the advantages that a different timeout and exception handler can be specified on the mutex-lock! and mutex-unlock! and the location of all the mutex operations is clearly apparent. A typical use with a condition variable is this: ```scheme (let loop () (mutex-lock! m) (if (condition-is-true?) (begin (do-something-when-condition-is-true) (mutex-unlock! m)) (begin (mutex-unlock! m cv) (loop)))) ``` **(with-mutex *****mutex stmt0 stmt1 ...*****)**

`with-mutex` locks *mutex* and then executes statements *stmt0*, *stmt1*, ... After all statements are executed, *mutex* is being unlocked. `with-mutex` returns the result of evaluating the last statement. For locking and unlocking t *mutex*, `dynamic-wind` is used so that *mutex* is automatically unlocked if an error or new continuation exits the statements, and it is re-locked, if the statements are re-entered by a captured continuation. `(with-mutex m stmt0 stmt1 ...)` is equivalent to: ```scheme (dynamic-wind (lambda () (mutex-lock! m)) (lambda () (begin stmt0 stmt1 ...)) (lambda () (mutex-unlock! m))) ``` ## Condition variables ### Semantics A condition variable represents a set of blocked threads. These blocked threads are waiting for a certain condition to become true. When a thread modifies some program state that might make the condition true, the thread unblocks some number of threads 9one or all depending on the primitive used) so they can check the value of that condition. This allows complex forms of inter-thread synchronization to be expressed more conveniently than with mutexes alone. Each condition variable has a tag which can be used in an application specific way to associate data with the condition variable. ### Condition variable management **(condition-variable? *****obj*****)**

Returns `#t` if *obj* is a condition variable, otherwise returns `#f`. **(make-condition-variable)**

\ \&#xNAN;**(make-condition-variable *****name*****)**\ \&#xNAN;**(make-condition-variable *****name tag*****)** Returns a new empty condition variable. The optional *name* is an arbitrary object which identifies the condition variable for debugging purposes. It defaults to `#f`. It is also possible to provide a tag, which is an arbitrary object used in an application-specific way to associate data with the condition variable. `#f` is used as a default if the tag is not provided. **(condition-variable-name *****cvar*****)**

Returns the name of the condition variable *cvar*. **(condition-variable-tag *****cvar*****)**

Returns the tag of the condition variable *cvar*. **(condition-variable-wait! *****cvar mutex*****)**

\ \&#xNAN;**(condition-variable-wait! *****cvar mutex timeout*****)** `condition-variable-wait!` can be used to make the current thread wait on condition variable *cvar*. It is assumed the current thread has locked *mutex* when `condition-variable-wait!` is called. `condition-variable-wait!` will unlock *mutex* and wait on *cvar*, either until *cvar* unblocks the thread again or *timeout* (in seconds) triggers. When the current thread is woken up again, it reclaims the lock on *mutex*. `condition-variable-wait!` returns `#f` if the timeout triggers, otherwise `#t` is being returned. **(condition-variable-signal! *****cvar*****)**

If there are threads blocked on the condition variable *cvar*, the scheduler selects a thread and unblocks it. **(condition-variable-broadcast! *****cvar*****)**

Unblocks all the threads blocked on the condition variable *cvar*. ## Exception handling **(join-timeout-exception? *****obj*****)**

Returns `#t` if *obj* is a "join timeout exception" object, otherwise returns `#f`. A join timeout exception is raised when `thread-join!` is called, the timeout is reached and no *default* is supplied. **(abandoned-mutex-exception? *****obj*****)**

Returns `#t` if *obj* is an "abandoned mutex exception" object, otherwise returns `#f`. An abandoned mutex exception is raised when the current thread locks a mutex that was owned by a thread which terminated. **(terminated-thread-exception? *****obj*****)**

Returns `#t` if *obj* is a "terminated thread exception" object, otherwise returns `#f`. A terminated thread exception is raised when `thread-join!` is called and the target thread has terminated as a result of a call to `thread-terminate!`. **(uncaught-exception? *****obj*****)**

Returns `#t` if *obj* is an "uncaught exception" object, otherwise returns `#f`. An uncaught exception is raised when `thread-join!` is called and the target thread has terminated because it raised an exception that called the initial exception handler of that thread. **(uncaught-exception-reason *****exc*****)**

*exc* must be an "uncaught exception" object. `uncaught-exception-reason` returns the object which was passed to the initial exception handler of that thread. ## Hardware platform and debugging **(processor-count)**

\ \&#xNAN;**(processor-count *****active?*****)** Returns the number of processors provided by the underlying hardware. If *active?* is set to `#f` (the default), the number of physical processors is returned. If *active?* is set to `#t`, the number of active processors (i.e. available for executing code) is returned. **(runnable-thread-count)**

Returns the number of threads that are currently in runnable state. **(allocated-thread-count)**

Returns the number of allocated threads, i.e. threads in any state that are not garbage collected yet. **(abort-running-threads)**

Aborts all threads except for the primordial thread and waits until all threads are terminated. This procedure must only be invoked from the primordial thread. **(wait-threads-terminated)**

Waits until all threads except for the primordial thread are terminated. This procedure must only be invoked from the primordial thread. *** Large portions of this documentation: Copyright (c) 2001, Marc Feeley. All rights reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.