Title

Real-time multithreading support

Author

Marc Feeley

Status

This SRFI is currently in ``final'' status. To see an explanation of each status that a SRFI can hold, see here. You can access the discussion via the archive of the mailing list.

Abstract

This SRFI is a real-time extension to SRFI 18, "Multithreading support". It defines the following multithreading datatypes for Scheme

It also defines a mechanism to handle exceptions and some multithreading exception datatypes.

Rationale

Multithreading is a paradigm that is well suited for building complex systems such as: servers, GUIs, and high-level operating systems. All thread systems, including the one proposed here, offer mechanisms for creating new threads of execution and for synchronizing them. Mechanisms for controlling access privileges for various operations are also usually provided by thread systems. This SRFI does not include such access control mechanisms because it aims to provide basic mechanisms on top of which higher-level abstractions can be built. Features which are useful in a real-time context, such as priorities and priority inheritance, are specified in this SRFI.

This SRFI also specifies a datatype for time which is useful on its own but is also required for specifying absolute synchronization timeouts. Mechanisms to handle exceptions and some multithreading exception datatypes are also provided because exceptions are closely tied to the multithreading model.

Specification

The thread system provides the following data types:

Some multithreading exception datatypes are also specified, and a general mechanism for handling exceptions.

Threads

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, an I/O operation to become possible, 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. A "terminated" thread is a thread that can no longer become runnable (but "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:

                         unblock
       start            <-------
  NEW -------> RUNNABLE -------> BLOCKED
    \             |      block  /
     \            v            /
      +-----> TERMINATED <----+

Each thread has a "base priority", which is a real number (where a higher numerical value means a higher priority), a "priority boost", which is a non-negative real number representing the priority increase applied to a thread when it blocks, and a "quantum", which is a non-negative real number representing a duration in seconds.

Each thread has a "specific" field which can be used in an application specific way to associate data with the thread (some thread systems call this "thread local storage").

Mutexes

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! primitive. The mutex primitives specified in this SRFI do not implement "recursive" mutex semantics; an attempt to lock a mutex that is locked 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).

Each mutex has a "specific" field which can be used in an application specific way to associate data with the mutex.

Condition variables

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 (one or all depending on the primitive used) so they can check the value of the condition. This allows complex forms of interthread synchronization to be expressed more conveniently than with mutexes alone.

Each condition variable has a "specific" field which can be used in an application specific way to associate data with the condition variable.

Fairness

In various situations the scheduler must select one thread from a set of threads (e.g. which thread to run when a running thread blocks or expires its quantum, which thread to unblock when a mutex unlocks or a condition variable is signaled). The constraints on the selection process determine the scheduler's "fairness". Typically the selection depends on the order in which threads become runnable or blocked and on some "priority" attached to the threads.

The fairness specified by this SRFI requires a notion of time ordering, i.e. "event A occured before event B". For the purpose of establishing time ordering, the system may use a clock with a discrete, possibly variable, resolution (a "tick"). Events occuring in a given tick can be considered to be simultaneous (i.e. if event A occured before event B in real time, then the system can claim that event A occured before event B or, if the events fall within the same tick, that they occured at the same time).

Each thread T has three priorities which affect fairness; the "base priority", the "boosted priority", and the "effective priority".

  1. The base priority is the value contained in T's "base priority" field (which is set with the thread-base-priority-set! primitive).
  2. T's "boosted flag" field contains a boolean that affects T's boosted priority. When the boosted flag field is false, the boosted priority is equal to the base priority, otherwise the boosted priority is equal to the base priority plus the value contained in T's "priority boost" field (which is set with the thread-priority-boost-set! primitive). The boosted flag field is set to false when a thread is created, when its quantum expires, and when thread-yield! is called. The boosted flag field is set to true when a thread blocks. By carefully choosing the base priority and priority boost it is possible to set up an interactive thread so that it has good I/O response time without being a CPU hog when it performs long computations.
  3. The effective priority is equal to the maximum of T's boosted priority and the effective priority of all the threads that are blocked on a mutex owned by T. This "priority inheritance" avoids priority inversion problems that would prevent a high priority thread blocked at the entry of a critical section to progress because a low priority thread inside the critical section is preempted for an arbitrary long time by a medium priority thread.

Let P(T) be the effective priority of thread T and let R(T) be the most recent time when one of the following events occurred for thread T, thus making it runnable: T was started by calling thread-start!, T called thread-yield!, T expired its quantum, or T was unblocked. Let the relation NL(T1,T2), "T1 no later than T2", be true if P(T1)<P(T2) or P(T1)=P(T2) and R(T1)>R(T2), and false otherwise. The system must schedule the execution of threads in such a way that whenever there is at least one runnable thread, 1) within a finite time at least one thread will be running, and 2) there is never a pair of runnable threads T1 and T2 for which NL(T1,T2) is true and T1 is not running and T2 is running.

A thread T expires its quantum when an amount of time equal to T's quantum has elapsed since T entered the running state and T did not block, terminate or call thread-yield!. At that point T exits the running state to allow other threads to run. A thread's quantum is thus an indication of the rate of progress of the thread relative to the other threads of the same priority. Moreover, the resolution of the timer measuring the running time may cause a certain deviation from the quantum, so a thread's quantum should only be viewed as an approximation of the time it can run before yielding to another thread.

Threads blocked on a given mutex or condition variable will unblock in an order which is consistent with decreasing priority and increasing blocking time (i.e. the highest priority thread unblocks first, and among equal priority threads the one that blocked first unblocks first).

Memory coherency and lack of atomicity

Read and write operations on the store (such as reading and writing a variable, an element of a vector or a string) are not required to be 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. It is the responsibility of the implementation to serialize accesses to a given port using the appropriate synchronization primitives.

Dynamic environments, continuations and dynamic-wind

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. Some Scheme systems generalize the dynamic environment by providing procedures and special forms to define new "dynamic variables" and bind them in the dynamic environment (e.g. 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 (an alternate but equivalent point of view is that the dynamic-wind stack is part of the dynamic environment). 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. Below is an example exercising the subtleties of this semantics.

    (with-output-to-file
     "foo"
     (lambda ()
       (let ((k (call-with-current-continuation
                 (lambda (exit)
                   (with-output-to-file
                    "bar"
                    (lambda ()
                      (dynamic-wind
                       (lambda () (write '(b1)))
                       (lambda ()
                         (let ((x (call-with-current-continuation
                                   (lambda (cont) (exit cont)))))
                           (write '(t1))
                           x))
                       (lambda () (write '(a1))))))))))
         (if k
             (dynamic-wind
              (lambda () (write '(b2)))
              (lambda ()
                (with-output-to-file
                 "baz"
                 (lambda ()
                   (write '(t2))
                   ; go back inside (with-output-to-file "bar" ...)
                   (k #f))))
              (lambda () (write '(a2))))))))

In an implementation of Scheme where with-output-to-file only closes the port it opened when the thunk returns normally, then the following actions will occur: (b1)(a1) is written to "bar", (b2) is written to "foo", (t2) is written to "baz", (a2) is written to "foo", and (b1)(t1)(a1) is written to "bar".

When the scheduler stops the execution of a running thread T1 (whether because it blocked, expired its quantum, was terminated, etc) and then resumes the execution of a thread T2, there is in a sense a transfer of control between T1's current continuation and the continuation of T2. This transfer of control by the scheduler does not cause any dynamic-wind before and after thunks to be called. It is only when a thread itself transfers control to a continuation that dynamic-wind before and after thunks are called.

Time objects and timeouts

A time object represents a point on the time line. Its resolution is implementation dependent (implementations are encouraged to implement at least millisecond resolution so that precise timing is possible). Using time->seconds and seconds->time, a time object can be converted to and from a real number which corresponds to the number of seconds from a reference point on the time line. The reference point is implementation dependent and does not change for a given execution of the program (e.g. the reference point could be the time at which the program started).

All synchronization primitives which take a timeout parameter accept three types of values as a timeout, with the following meaning:

When a timeout denotes the current time or a time in the past, the synchronization primitive claims that the timeout has been reached only after the other synchronization conditions have been checked. Moreover the thread remains running (it does not enter the blocked state). For example, (mutex-lock! m 0) will lock mutex m and return #t if m is currently unlocked, otherwise #f is returned because the timeout is reached.

Primitives and exceptions

When one of the primitives defined in this SRFI raises an exception defined in this SRFI, the exception handler is called with the same continuation as the primitive (i.e. it is a tail call to the exception handler). This requirement avoids having to use call-with-current-continuation to get the same effect in some situations.

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 an unspecified base priority, priority boost, boosted flag, quantum, name, specific field, dynamic environment, dynamic-wind stack, and exception handler. All threads are terminated when the primordial thread terminates (normally or not).

Procedures

(current-thread)                                      ;procedure

Returns the current thread.

    (eq? (current-thread) (current-thread))  ==>  #t
(thread? obj)                                         ;procedure

Returns #t if obj is a thread, otherwise returns #f.

    (thread? (current-thread))  ==>  #t
    (thread? 'foo)              ==>  #f

(make-thread thunk [name])                            ;procedure

Returns a new thread. This thread is not automatically made runnable (the procedure thread-start! must be used for this). A thread has the following fields: base priority, priority boost, boosted flag, quantum, name, specific, end-result, end-exception, and a list of locked/owned mutexes it owns. 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 optional name is an arbitrary Scheme object which identifies the thread (useful for debugging); it defaults to an unspecified value. The specific field is set to an unspecified value. The base priority, priority boost, and quantum of the thread are set to the same value as the current thread and the boosted flag is set to false. 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.

    (make-thread (lambda () (write 'hello)))  ==>  a thread
(thread-name thread)                                  ;procedure

Returns the name of the thread.

    (thread-name (make-thread (lambda () #f) 'foo))  ==>  foo
(thread-specific thread)                              ;procedure

Returns the content of the thread's specific field.

(thread-specific-set! thread obj)                     ;procedure

Stores obj into the thread's specific field. thread-specific-set! returns an unspecified value.

    (thread-specific-set! (current-thread) "hello")  ==>  unspecified
    (thread-specific (current-thread))               ==>  "hello"
(thread-base-priority thread)                         ;procedure

Returns a real number which corresponds to the base priority of the thread.

(thread-base-priority-set! thread priority)           ;procedure

Changes the base priority of the thread to priority. The priority must be a real number. thread-base-priority-set! returns an unspecified value.

    (thread-base-priority-set! (current-thread) 12.3)  ==>  unspecified
    (thread-base-priority (current-thread))            ==>  12.3
(thread-priority-boost thread)                        ;procedure

Returns a real number which corresponds to the priority boost of the thread.

(thread-priority-boost-set! thread priority-boost)    ;procedure

Changes the priority boost of the thread to priority-boost. The priority-boost must be a non-negative real. thread-priority-boost-set! returns an unspecified value.

    (thread-priority-boost-set! (current-thread) 2.5)  ==>  unspecified
    (thread-priority-boost (current-thread))           ==>  2.5
(thread-quantum thread)                               ;procedure

Returns a real number which corresponds to the quantum of the thread.

(thread-quantum-set! thread quantum)                  ;procedure

Changes the quantum of the thread to quantum. The quantum must be a non-negative real. A value of zero selects the smallest quantum supported by the implementation. thread-quantum-set! returns an unspecified value.

    (thread-quantum-set! (current-thread) 1.5)  ==>  unspecified
    (thread-quantum (current-thread))           ==>  1.5
    (thread-quantum-set! (current-thread) 0)    ==>  unspecified
    (thread-quantum (current-thread))           ==>  .01
(thread-start! thread)                                 ;procedure

Makes thread runnable. The thread must be a new thread. thread-start! returns the thread.

    (let ((t (thread-start! (make-thread (lambda () (write 'a))))))
      (write 'b)
      (thread-join! t))             ==>  unspecified
                                         after writing ab or ba

NOTE: It is useful to separate thread creation and thread activation to avoid the race condition that would occur if the created thread tries to examine a table in which the current thread stores the created thread. See the last example of thread-terminate! which contains mutually recursive threads.

(thread-yield!)                                        ;procedure

The current thread exits the running state as if its quantum had expired. thread-yield! returns an unspecified value.

    ; a busy loop that avoids being too wasteful of the CPU

    (let loop ()
      (if (mutex-lock! m 0) ; try to lock m but don't block
          (begin
            (display "locked mutex m")
            (mutex-unlock! m))
          (begin
            (do-something-else)
            (thread-yield!) ; relinquish rest of quantum
            (loop))))
(thread-sleep! timeout)                                ;procedure

The current thread waits until the timeout is reached. This blocks the thread only if timeout represents a point in the future. It is an error for timeout to be #f. thread-sleep! returns an unspecified value.

    ; 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 (time->seconds (current-time)))
      (let loop ((x 1))
        (thread-sleep! (seconds->time (+ x start)))
        (write x)
        (loop (+ x 1))))
(thread-terminate! thread)                             ;procedure

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. If thread is the current thread, thread-terminate! does not return. Otherwise thread-terminate! returns an unspecified value; the termination of the thread will occur before thread-terminate! returns.

    (thread-terminate! (current-thread))  ==>  does not return

    (define (amb thunk1 thunk2)
      (let ((result #f)
            (result-mutex (make-mutex))
            (done-mutex (make-mutex)))
        (letrec ((child1
                  (make-thread
                    (lambda ()
                      (let ((x (thunk1)))
                        (mutex-lock! result-mutex #f #f)
                        (set! result x)
                        (thread-terminate! child2)
                        (mutex-unlock! done-mutex)))))
                 (child2
                  (make-thread
                    (lambda ()
                      (let ((x (thunk2)))
                        (mutex-lock! result-mutex #f #f)
                        (set! result x)
                        (thread-terminate! child1)
                        (mutex-unlock! done-mutex))))))
          (mutex-lock! done-mutex #f #f)
          (thread-start! child1)
          (thread-start! child2)
          (mutex-lock! done-mutex #f #f)
          result)))

NOTE: 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. Clean termination can be obtained by polling, as shown in the example below.

    (define (spawn thunk)
      (let ((t (make-thread thunk)))
        (thread-specific-set! t #t)
        (thread-start! t)
        t))

    (define (stop! thread)
      (thread-specific-set! thread #f)
      (thread-join! thread))

    (define (keep-going?)
      (thread-specific (current-thread)))

    (define count!
      (let ((m (make-mutex))
            (i 0))
        (lambda ()
          (mutex-lock! m)
          (let ((x (+ i 1)))
            (set! i x)
            (mutex-unlock! m)
            x))))

    (define (increment-forever!)
      (let loop () (count!) (if (keep-going?) (loop))))

    (let ((t1 (spawn increment-forever!))
          (t2 (spawn increment-forever!)))
      (thread-sleep! 1)
      (stop! t1)
      (stop! t2)
      (count!))  ==>  377290
(thread-join! thread [timeout [timeout-val]])         ;procedure

The current thread waits until the thread terminates (normally or not) or until the timeout is reached if timeout is supplied. If the timeout is reached, thread-join! returns timeout-val if it is supplied, otherwise a "join timeout exception" is raised. If the thread terminated normally, the content of the end-result field is returned, otherwise the content of the end-exception field is raised.

    (let ((t (thread-start! (make-thread (lambda () (expt 2 100))))))
      (do-something-else)
      (thread-join! t))  ==>  1267650600228229401496703205376

    (let ((t (thread-start! (make-thread (lambda () (raise 123))))))
      (do-something-else)
      (with-exception-handler
        (lambda (exc)
          (if (uncaught-exception? exc)
              (* 10 (uncaught-exception-reason exc))
              99999))
        (lambda ()
          (+ 1 (thread-join! t)))))  ==>  1231

    (define thread-alive?
      (let ((unique (list 'unique)))
        (lambda (thread)
          ; Note: this procedure raises an exception if
          ; the thread terminated abnormally.
          (eq? (thread-join! thread 0 unique) unique))))

    (define (wait-for-termination! thread)
      (let ((eh (current-exception-handler)))
        (with-exception-handler
          (lambda (exc)
            (if (not (or (terminated-thread-exception? exc)
                         (uncaught-exception? exc)))
                (eh exc))) ; unexpected exceptions are handled by eh
          (lambda ()
            ; The following call to thread-join! will wait until the
            ; thread terminates.  If the thread terminated normally
            ; thread-join! will return normally.  If the thread
            ; terminated abnormally then one of these two exceptions
            ; is raised by thread-join!:
            ;   - terminated thread exception
            ;   - uncaught exception
            (thread-join! thread)
            #f)))) ; ignore result of thread-join!
(mutex? obj)                                          ;procedure

Returns #t if obj is a mutex, otherwise returns #f.

    (mutex? (make-mutex))  ==>  #t
    (mutex? 'foo)          ==>  #f
(make-mutex [name])                                   ;procedure

Returns a new mutex in the unlocked/not-abandoned state. The optional name is an arbitrary Scheme object which identifies the mutex (useful for debugging); it defaults to an unspecified value. The mutex's specific field is set to an unspecified value.

    (make-mutex)       ==>  an unlocked/not-abandoned mutex
    (make-mutex 'foo)  ==>  an unlocked/not-abandoned mutex named foo
(mutex-name mutex)                                    ;procedure

Returns the name of the mutex.

    (mutex-name (make-mutex 'foo))  ==>  foo
(mutex-specific mutex)                                ;procedure

Returns the content of the mutex's specific field.

(mutex-specific-set! mutex obj)                       ;procedure

Stores obj into the mutex's specific field. mutex-specific-set! returns an unspecified value.

    (define m (make-mutex))
    (mutex-specific-set! m "hello")  ==>  unspecified
    (mutex-specific m)               ==>  "hello"

    (define (mutex-lock-recursively! mutex)
      (if (eq? (mutex-state mutex) (current-thread))
          (let ((n (mutex-specific mutex)))
            (mutex-specific-set! mutex (+ n 1)))
          (begin
            (mutex-lock! mutex)
            (mutex-specific-set! mutex 0))))

    (define (mutex-unlock-recursively! mutex)
      (let ((n (mutex-specific mutex)))
        (if (= n 0)
            (mutex-unlock! mutex)
            (mutex-specific-set! mutex (- n 1)))))
(mutex-state mutex)                                   ;procedure

Returns information about the state of the mutex. The possible results are:

    (mutex-state (make-mutex))  ==>  not-abandoned

    (define (thread-alive? thread)
      (let ((mutex (make-mutex)))
        (mutex-lock! mutex #f thread)
        (let ((state (mutex-state mutex)))
          (mutex-unlock! mutex) ; avoid space leak
          (eq? state thread))))
(mutex-lock! mutex [timeout [thread]])                ;procedure

If the mutex is currently 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:

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

    ; an implementation of a mailbox object of depth one; this
    ; implementation does not behave well in the presence of forced
    ; thread terminations using thread-terminate! (deadlock can occur
    ; if a thread is terminated in the middle of a put! or get! operation)

    (define (make-empty-mailbox)
      (let ((put-mutex (make-mutex)) ; allow put! operation
            (get-mutex (make-mutex))
            (cell #f))

        (define (put! obj)
          (mutex-lock! put-mutex #f #f) ; prevent put! operation
          (set! cell obj)
          (mutex-unlock! get-mutex)) ; allow get! operation

        (define (get!)
          (mutex-lock! get-mutex #f #f) ; wait until object in mailbox
          (let ((result cell))
            (set! cell #f) ; prevent space leaks
            (mutex-unlock! put-mutex) ; allow put! operation
            result))

        (mutex-lock! get-mutex #f #f) ; prevent get! operation

        (lambda (msg)
          (case msg
            ((put!) put!)
            ((get!) get!)
            (else (error "unknown message"))))))

    (define (mailbox-put! m obj) ((m 'put!) obj))
    (define (mailbox-get! m) ((m 'get!)))

    ; an alternate implementation of thread-sleep!

    (define (sleep! timeout)
      (let ((m (make-mutex)))
        (mutex-lock! m #f #f)
        (mutex-lock! m timeout #f)))

    ; a procedure that waits for one of two mutexes to unlock

    (define (lock-one-of! mutex1 mutex2)
      ; this procedure assumes that neither mutex1 or mutex2
      ; are owned by the current thread
      (let ((ct (current-thread))
            (done-mutex (make-mutex)))
        (mutex-lock! done-mutex #f #f)
        (let ((t1 (thread-start!
                   (make-thread
                    (lambda ()
                      (mutex-lock! mutex1 #f ct)
                      (mutex-unlock! done-mutex)))))
              (t2 (thread-start!
                   (make-thread
                    (lambda ()
                      (mutex-lock! mutex2 #f ct)
                      (mutex-unlock! done-mutex))))))
          (mutex-lock! done-mutex #f #f)
          (thread-terminate! t1)
          (thread-terminate! t2)
          (if (eq? (mutex-state mutex1) ct)
              (begin
                (if (eq? (mutex-state mutex2) ct)
                    (mutex-unlock! mutex2)) ; don't lock both
                mutex1)
              mutex2))))
(mutex-unlock! mutex [condition-variable [timeout]])  ;procedure

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 condition-variable is supplied, the current thread is blocked and added to the condition-variable 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 (see below), 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.

NOTE: The reason the thread can unblock at any time (when condition-variable is supplied) is to allow extending this SRFI with primitives that force a specific blocked thread to become runnable. For example a primitive to interrupt a thread so that it performs a certain operation, whether the thread is blocked or not, may be useful to handle the case where the scheduler has detected a serious problem (such as a deadlock) and it must unblock one of the threads (such as the primordial thread) so that it can perform some appropriate action. After a thread blocked on a condition-variable has handled such an interrupt it would be wrong for the scheduler to return the thread to the blocked state, because any calls to condition-variable-broadcast! during the interrupt will have gone unnoticed. It is necessary for the thread to remain runnable and return from the call to mutex-unlock! with a result of #t.

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

    (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))))
(condition-variable? obj)                             ;procedure

Returns #t if obj is a condition variable, otherwise returns #f.

    (condition-variable? (make-condition-variable))  ==>  #t
    (condition-variable? 'foo)                       ==>  #f
(make-condition-variable [name])                      ;procedure

Returns a new empty condition variable. The optional name is an arbitrary Scheme object which identifies the condition variable (useful for debugging); it defaults to an unspecified value. The condition variable's specific field is set to an unspecified value.

    (make-condition-variable)  ==>  an empty condition variable
(condition-variable-name condition-variable)          ;procedure

Returns the name of the condition-variable.

    (condition-variable-name (make-condition-variable 'foo))  ==>  foo
(condition-variable-specific condition-variable)      ;procedure

Returns the content of the condition-variable's specific field.

(condition-variable-specific-set! condition-variable obj) ;procedure

Stores obj into the condition-variable's specific field. condition-variable-specific-set! returns an unspecified value.

    (define cv (make-condition-variable))
    (condition-variable-specific-set! cv "hello")  ==>  unspecified
    (condition-variable-specific cv)               ==>  "hello"
(condition-variable-signal! condition-variable)       ;procedure

If there are threads blocked on the condition-variable, the scheduler selects a thread and unblocks it. condition-variable-signal! returns an unspecified value.

    ; an implementation of a mailbox object of depth one; this
    ; implementation behaves gracefully when threads are forcibly
    ; terminated using thread-terminate! (the "abandoned mutex"
    ; exception will be raised when a put! or get! operation is attempted
    ; after a thread is terminated in the middle of a put! or get!
    ; operation)

    (define (make-empty-mailbox)
      (let ((mutex (make-mutex))
            (put-condvar (make-condition-variable))
            (get-condvar (make-condition-variable))
            (full? #f)
            (cell #f))

        (define (put! obj)
          (mutex-lock! mutex)
          (if full?
              (begin
                (mutex-unlock! mutex put-condvar)
                (put! obj))
              (begin
                (set! cell obj)
                (set! full? #t)
                (condition-variable-signal! get-condvar)
                (mutex-unlock! mutex))))

        (define (get!)
          (mutex-lock! mutex)
          (if (not full?)
              (begin
                (mutex-unlock! mutex get-condvar)
                (get!))
              (let ((result cell))
                (set! cell #f) ; avoid space leaks
                (set! full? #f)
                (condition-variable-signal! put-condvar)
                (mutex-unlock! mutex))))

        (lambda (msg)
          (case msg
            ((put!) put!)
            ((get!) get!)
            (else (error "unknown message"))))))

    (define (mailbox-put! m obj) ((m 'put!) obj))
    (define (mailbox-get! m) ((m 'get!)))
(condition-variable-broadcast! condition-variable)    ;procedure

Unblocks all the threads blocked on the condition-variable. condition-variable-broadcast! returns an unspecified value.

    (define (make-semaphore n)
      (vector n (make-mutex) (make-condition-variable)))

    (define (semaphore-wait! sema)
      (mutex-lock! (vector-ref sema 1))
      (let ((n (vector-ref sema 0)))
        (if (> n 0)
            (begin
              (vector-set! sema 0 (- n 1))
              (mutex-unlock! (vector-ref sema 1)))
            (begin
              (mutex-unlock! (vector-ref sema 1) (vector-ref sema 2))
              (semaphore-wait! sema))))

    (define (semaphore-signal-by! sema increment)
      (mutex-lock! (vector-ref sema 1))
      (let ((n (+ (vector-ref sema 0) increment)))
        (vector-set! sema 0 n)
        (if (> n 0)
            (condition-variable-broadcast! (vector-ref sema 2)))
        (mutex-unlock! (vector-ref sema 1))))
(current-time)                                        ;procedure

Returns the time object corresponding to the current time.

    (current-time)  ==>  a time object
(time? obj)                                           ;procedure

Returns #t if obj is a time object, otherwise returns #f.

    (time? (current-time))  ==>  #t
    (time? 123)             ==>  #f
(time->seconds time)                                  ;procedure

Converts the time object time into an exact or inexact real number representing the number of seconds elapsed since some implementation dependent reference point.

    (time->seconds (current-time))  ==>  955039784.928075
(seconds->time x)                                     ;procedure

Converts into a time object the exact or inexact real number x representing the number of seconds elapsed since some implementation dependent reference point.

    (seconds->time (+ 10 (time->seconds (current-time)))
       ==>  a time object representing 10 seconds in the future
(current-exception-handler)                           ;procedure

Returns the current exception handler.

    (current-exception-handler)  ==>  a procedure
(with-exception-handler handler thunk)                ;procedure

Returns the result(s) of calling thunk with no arguments. The handler, which must be a procedure, is installed as the current exception handler in the dynamic environment in effect during the call to thunk.

    (with-exception-handler
      list
      current-exception-handler)  ==>  the procedure list
(raise obj)                                           ;procedure

Calls the current exception handler with obj as the single argument. obj may be any Scheme object.

    (define (f n)
      (if (< n 0) (raise "negative arg") (sqrt n))))

    (define (g)
      (call-with-current-continuation
        (lambda (return)
          (with-exception-handler
            (lambda (exc)
              (return
                (if (string? exc)
                    (string-append "error: " exc)
                    "unknown error")))
            (lambda ()
              (write (f 4.))
              (write (f -1.))
              (write (f 9.)))))))

    (g)  ==>  writes 2. and returns "error: negative arg"
(join-timeout-exception? obj)                         ;procedure

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 timeout-val is supplied.

(abandoned-mutex-exception? obj)                      ;procedure

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 (see mutex-lock!).

(terminated-thread-exception? obj)                    ;procedure

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)                             ;procedure

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)                       ;procedure

exc must be an "uncaught exception" object. uncaught-exception-reason returns the object which was passed to the initial exception handler of that thread.

Acknowledgements

Much of this design has been influenced by other thread systems. Here are the main contributions:

Implementation

The implementation will be provided at a later time.

Copyright

Copyright (C) Marc Feeley (2001). 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.


Editor: Mike Sperber