(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.

(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:

(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:

(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:

(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.

(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:

; 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.

; 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:

(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.

(mutex-name (make-mutex 'foo))  ⇒  foo

(mutex-tag mutex)

Returns the tag of the mutex.

(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

(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))))
⇒  (#<thread main: runnable> 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:

(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:

(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.