[Go to first, previous, next page;   contents;   index]

Chapter 7

Threads

This chapter describes Scheme 48’s thread system: Scheme 48 threads are fully preemptive; all threads (currently) run within a single operating system process. Scheme 48 allows writing customized, nested schedulers, and provides numerous facilities for the synchronization of shared-memory programs, most importantly proposals for optimistic concurrency.

7.1  Creating and controlling threads

The bindings described in this section are part of the threads structure.

Spawn creates a new thread, passes that thread to the current scheduler, and instructs the scheduler to run thunk in that thread. The name argument (a symbol) associates a symbolic name with the thread; it is purely for debugging purposes.

Relinquish-timeslice instructs the scheduler to run another thread, thus relinquishing the timeslice of the current thread. Sleep does the same and asks the scheduler to suspend the current thread for at least time-in-milliseconds milliseconds before resuming it. Finally, terminate-current-thread terminates the current thread.

Each thread is represented by a thread object. The following procedures operate on that object:

Current-thread returns the thread object associated with the currently running thread. Thread? is the predicate for thread objects. Thread-name extracts the name of the thread, if one was specified in the call to spawn, #f otherwise. Thread-uid returns the uid of the thread, a unique integer assigned by the thread system.

7.2  Advanced thread handling

The following bindings are part of the threads-internal structure:

Terminate-thread! unwinds the thread associated with thread, running any pending dynamic-wind after thunks (in that thread), after which the thread terminates. Kill-thread! causes the thread associated with thread to terminate immediately without unwinding its continuation.

7.3  Debugging multithreaded programs

Debugging multithreaded programs can be difficult.

As described in section 3.11, when any thread signals an error, Scheme 48 stops running all of the threads at that command level.

The following procedure (exported by the structure debug-messages) is useful in debugging multi-threaded programs.

Debug-message prints the elements to ‘stderr’, followed by a newline. The only types of values that debug-message prints in full are small integers (fixnums), strings, characters, symbols, booleans, and the empty list. Values of other types are abbreviated as follows:

pair (...)
vector #(...)
procedure #{procedure}
record #{<name of record type>}
all others ???
The great thing about debug-message is that it bypasses Scheme 48’s I/O and thread handling. The message appears immediately, with no delays or errors.

7.4  Optimistic concurrency

Most of the bindings described in this section are part of the proposals structure—the low-level bindings described at the very end of the section are part of the low-proposals structure.

A proposal is a record of reads from and and writes to locations in memory. Each thread has an associated current proposal (which may be #f). The logging operations listed below record any values read or written in the current proposal. A reading operation, such as provisional-vector-ref, first checks to see if the current proposal contains a value for the relevent location. If so, that value is returned as the result of the read. If not, the current contents of the location are stored in the proposal and then returned as the result of the read. A logging write to a location stores the new value as the current contents of the location in the current proposal; the contents of the location itself remain unchanged.

Committing to a proposal verifies that any reads logged in the proposal are still valid and, if so, performs any writes that the proposal contains. A logged read is valid if, at the time of the commit, the location contains the same value it had at the time of the original read (note that this does not mean that no change occured, simply that the value now is the same as the value then). If a proposal has an invalid read then the effort to commit fails; no change is made to the value of any location. The verifications and subsequent writes to memory are performed atomically with respect to other proposal commit attempts.

If there is a proposal in place call-ensuring-atomicity and call-ensuring-atomicity! simply make a (tail-recursive) call to thunk. If the current proposal is #f they create a new proposal, install it, call thunk, and then try to commit to the proposal. This process repeats, with a new proposal on each iteration, until the commit succeeds. Call-ensuring-atomicity returns whatever values are returned by thunk on its final invocation, while ensure-atomicity! discards any such values and returns nothing.

Ensure-Atomicity and ensure-atomicity! are macro versions of call-ensuring-atomicity and call-ensuring-atomicity!: (ensure-atomicity exp ...) expands into (call-ensuring-atomicity (lambda () exp ...)); likewise for ensure-atomicity! and call-ensuring-atomicity!.

These are all logging versions of their Scheme counterparts. Reads are checked when the current proposal is committed and writes are delayed until the commit succeeds. If the current proposal is #f these perform exactly as their Scheme counterparts.

The following implementation of a simple counter may not function properly when used by multiple threads. 

(define (make-counter)
  (let ((value 0))
    (lambda ()
      (set! value (+ value 1))
      value)))

Here is the same procedure using a proposal to ensure that each increment operation happens atomically. The value of the counter is kept in a cell (see section 5.6) to allow the use of logging operations. 

(define (make-counter)
  (let ((value (make-cell 0)))
    (lambda ()
      (ensure-atomicity
        (lambda ()
          (let ((v (+ (provisional-cell-ref value)
                      1)))
            (provisional-cell-set! value v)
            v))))))

Because ensure-atomicity creates a new proposal only if there is no existing proposal in place, multiple atomic actions can be merged into a single atomic action. For example, the following procedure increments an arbitrary number of counters at the same time. This works even if the same counter appears multiple times; (step-counters! c0 c0) would add two to the value of counter c0. 

(define (step-counters! . counters)
  (ensure-atomicity
    (lambda ()
      (for-each (lambda (counter)
                  (counter))
                counters))))


(define-synchronized-record-type tag type-name
  (constructor-name field-tag ...)
  [(field-tag ...)]
  predicate-name
  (field-tag accessor-name [modifier-name])
  ...)

This is the same as define-record-type except all field reads and writes are logged in the current proposal. If the optional list of field tags is present then only those fields will be logged.

Call-atomically and call-atomically! are identical to call-ensuring-atomicity and call-ensuring-atomicity! except that they always install a new proposal before calling thunk. The current proposal is saved and then restored after thunk returns. Call-atomically and Call-atomically! are useful if thunk contains code that is not to be combined with any other operation.

Atomically and atomically! are macro versions of call-atomically and call-atomically!: (atomically exp ...) expands into (call-atomically (lambda () exp ...)); likewise for atomically! and call-atomically!.

With-new-proposal saves the current proposal, installs a new one, executes the forms in the body, and returns whatever they returns. It also binds lose to a thunk repeating the procedure of installing a new procedure and running the body. Typically, the body will call maybe-commit and, if that fails, call lose to try again.

The following procedures give access to the low-level proposal mechanism. They are defined in the low-proposals structure.

Maybe-commit verifies that any reads logged in the current proposal are still valid and, if so, performs any writes that it contains. A logged read is valid if, at the time of the commit, the location read contains the same value it had at the time of the original read (note that this does not mean that no change occured, simply that the value now is the same as the value then). Maybe-commit returns #t if the commit succeeds and #f if it fails.

Make-proposal creates a new proposal. Current-proposal and set-current-proposal access and set the current thread’s proposal. It is an error to pass to set-current-proposal! a proposal that is already in use.

7.5  Condition variables

Condition variables (defined in the condvars structure) allow threads perform condition synchronization: It allows threads to block, waiting for a specified condition—associated with a condition variable—to occur, and other threads to wake up the waiting threads when the condition is fulfilled.

Note that, in Scheme 48, condition variables work in conjunction with proposals, not with mutex locks or semaphores, as in most other implementations of this concept.

Make-condvar creates a condition variable. (The optional id argument is only for debugging purposes; the discloser for condition variables prints it out if present.) Condvar? is the predicate for condition variables.

Each condition variable has an associated value and a flag has-value? signalling if the condition has already occured. The accessor for flag is condvar-has-value?; set-condvar-has-value?! sets it. Both are provisional operations and go through the current proposal. Set-condvar-value! sets the value of the condition variable (provisionally), and condvar-value extracts it.

Maybe-commit-and-wait-for-condvar attempts to commit the current proposal. If the commit succeeds, it suspends the current thread and registers it with the condvar condition variable. Upon waking up again maybe-commit-and-wait-for-condvar returns #t, If the commit fails, maybe-commit-and-set-condvar returns #f.

Maybe-commit-and-set-condvar! sets the value of the condvar condition variable to value, (provisionally) sets the has-value? flag to #t, and then attempt to commit the current proposal. Upon success, it wakes up all suspended threads registered with condvar and returns #t, otherwise, it returns #f.

7.6  Mutual exclusion

Scheme 48 also has more traditional mutual-exclusion synchronization abstractions, specifically mutex locks and placeholders. Note that typically synchronization via optimistic concurrency is usually preferable: Mutual exclusion often puts the running program into an inconsistent state for the time of the inclusion, which has adverse effects on modularity and interruptibility.

7.6.1  Locks

The locks structure contains bindings that implement standard mutex locks:

Make-lock creates a lock in the “released” state. Lock? is the predicate for locks.

Obtain-lock atomically checks if lock is in the “released” state. If it is, the lock is put into the “obtained” state, and obtain-lock returns immediately. If the lock is in the “obtained” state, the current thread is suspended and registered with the lock. Maybe-obtain-lock, like obtain-lock, checks the state of lock: if it is “released,” the lock is put into the “obtained” state, if it is “obtained,” maybe-obtain-lock returns immediately. Maybe-obtain-lock returns #t if it was able to obtain the lock, and #f otherwise.

Release-lock does nothing if lock is in the “released” state. If it is in the “obtained” state, release-lock causes one of the threads suspended on an obtain-lock lock operation to continue execution. If that thread is the last thread registered with the lock, the lock is transferred to the “released” state. In any case, release-lock returns immediately.

7.6.2  Placeholders

The placeholders structure contains bindings for placeholders—thread-safe, write-once variables, akin to ID-90 I-structures or CML I-variables.

The typical scenario for placeholders is that, say, a thread A computes a value needed by another thread B at some unspecified time. Both threads share access to a placeholder; when A has computed the value, it places it into the placeholder. When B needs the value, it extracts it from placeholder, blocking if necessary.

Make-placeholder creates an empty placeholder. (The optional id argument is only for debugging purposes; the discloser for placeholders prints it out if present.) Placeholder? is the predicate for placeholders.

Placeholder-set! places a value into a placeholder. Doing this more than once signals an error. Placeholder-value extracts the value from the placeholder and returns it. If the placeholder is empty, it blocks the current thread until it becomes full.

7.7  Writing custom synchronization abstractions

The bindings explained in this section are part of the threads-internal structure. They are concerned with suspending threads and making them runnable again upon some later event.

Typically, a suspended thread needs to be recorded in a queue somewhere for later waking-up. To allow a thread to be recorded in multiple queues (say, when it waits for one of a number of events), such thread queues are ordinary queues containing cells that, in turn, contain the thread objects themselves. Each thread has at most one such cell associated with it which is shared among all queues (or other data structures) holding on to the suspended thread. The cell is cleared when the thread is woken up.

Thread-queue-empty? atomically checks whether the thread-queue thread queue is empty, i.e., if it does not contain non-empty cells. Maybe-dequeue-thread! provisionally dequeues a thread from thread-queue if it contains one. It returns the dequeued thread or #f if the queue is empty.

Maybe-commit-and-block attempts to commit the current proposal. If this succeeds, the current thread is blocked, the thread’s cell is set to cell, and #t is returned. Otherwise, #f is returned. Maybe-commit-and-block-on-queue is like maybe-commit-and-block, excepts that it creates a fresh cell for the thread and enqueues it in thread-queue if the commit succeeds.

Maybe-commit-and-make-ready accepts either a thread object or a thread queue as an argument. In either case, maybe-commit-and-make-ready tries to commit the current proposal. If that succeeds, it maybe-commit-and-make-ready makes its argument runnable: if thread-or-queue is a thread, that thread is made runnable, if it is a thread queue, all threads on the queue are made runnable. (In the latter case, none of the threads actually runs until all have been made runnable.) Marybe-commit-and-make-ready returns #t if it succeeded, and #f otherwise.

7.8  Concurrent ML abstractions

The interface to the Concurrent ML abstractions in Scheme 48 is mostly analogous to the original implementation shipped with SML/NJ [9]. Note that both the interface and implementation are new and may change in future releases.

The main terminological difference is that CML events are called rendezvous in Scheme 48. For more information on programming with the CML abstractions, Reppy’s book [9] is recommended.

7.8.1  Basic rendezvous combinators

The basic rendezvous combinators live in the rendezvous structure.

Never-rv is a rendezvous that is never enabled for synchronization. (It is the same as the never event in CML.) Always-rv returns a rendezvous that is elways enabled for synchronization, and always yields the same value value. (This is the same as the alwaysEvt function in CML.)

Choose creates a rendezvous representing the choice of its arguments: Synchronization on the resulting rendezvous will synchronize on one of the arguments to choose, depending on which becomes enabled first. (This is the same as the choose function in CML.)

Wrap wraps a post-synchronization procedure around rendezvous: When the resulting rendezvous is synchronized, rendezvous is synchronized, and the value it yields is passed to proc; the value returned by proc then is the result of the synchronization. (This is the same as the CML wrap function.)

Guard delays the creation of a rendezvous until synchronization time: It returns a rendezvous that will, upon synchronization, turn into the rendezvous returned by thunk. Guard can be used to perform pre-synchronization actions such as resource allocation. (This is the same as the CML guard function.)

With-nack, like guard, creates a delayed rendezvous: Upon synchronization, the rendezvous actually used is the one returned by proc. In addition to the functionality offered by guard, proc receives, as an argument, another rendezvous which becomes enabled when another rendezvous involved in the synchronization (via choose) is picked instead of the one produced by proc. (This is the same as the CML withNack function.)

Sync synchronizes the current thread on rendezvous rendezvous, returning the value it yields. Select synchronizes on the choice of its argument; (select r1 ...rn) is semantically equivalent to (sync (choose select r1 ...rn)), but may be implemented more efficiently. (These are the same as the CML functions sync and select.)

7.8.2  Synchronous channels

The rendezvous-channels structure contains abstractions for bidirectional, synchronous channels for communicating between two threads.

Make-channel creates a new synchronous channel. (This is the same as the CML channel function.) Channel? is the predicate for synchronous channels.

Send-rv creates a rendezvous that, upon synchronization, sends message value on the synchronous channel channel. The synchronization suceeds only when another thread attempts to receive a message from channel. (This is the same as the CML sendEvt function.) Send directly sends a message value on channel channel; (send c v) is equivalent to (sync (send-rv c v)). (Send is the same as the CML send function.)

Receive-rv creates a rendezvous which, upon synchronization, receives a message on channel channel. (This is the same as the CML recEvt function.) Receive directly receives a message on channel channel; (receive c v) is equivalent to (sync (receive-rv c v)). (Receive is the same as the CML recv function.)

7.8.3  Synchronous variables

Two structures contain abstractions for synchronous variables: the rendezvous-placeholders structure for so-called placeholders (write-once variables), and the rendezvous-jars structure for jars (which allow multiple updates.)

7.8.3.1  Placeholders

Placeholders are write-once variables. The placeholders implemented by the rendezvous-placeholders structure offer equivalent functionality to the placeholders implemented by the placeholders structure (see Section 7.6.2), but additionally allow converting a placeholder into a rendezvous. Note, however, that placeholders from placeholders are different from and not interchangable with placeholders from rendezvous-placeholders.

Make-placeholder creates an empty placeholder. (The optional id argument is only for debugging purposes; the discloser for placeholders prints it out if present.) (This is the same as the CML iVar function.) Placeholder? is the predicate for placeholders.

Placeholder-set! places a value into a placeholder. Doing this more than once signals an error. (This is the same as the CML iPut function.)

Placeholder-value extracts the value from the placeholder and returns it. If the placeholder is empty, it blocks the current thread until it becomes full. (This is the same as the CML iGet function.) Placeholder-value-rv creates a rendezvous that will, upon synchronization, extrasct the value from the placeholder and yield it as a result. (This is the same as the CML iGetEvt function.)

7.8.3.2  Jars

A jar is a synchronous variable which can have two states: full and empty. It becomes full when a value it put into it; putting a value into a full jar is an error. Conversely, it becomes empty when a value is taken out of it. Trying to take a value out of an empty jar blocks until it becomes full. (Jars are similar to ID-90 M-structures.) Jars live in the rendezvous-jars structure.

Make-jar creates an empty jar. (The optional id argument is only for debugging purposes; the discloser for jars prints it out if present.) (This is the same as the CML mVar function.) Jar? is the predicate for jars.

Jar-put! places a value into a jar if it is empty. Applying jar-put! to a full jar is an error. (This is the same as the CML mPut function.)

Jar-take takes a value from a full jar, emptying it in the process. If the jar is empty, jar-take blocks until it becomes full. (This is the same as the CML mTake function.) Jar-take-rv creates a rendezvous that, upon synchronization, will extract the value from a jar and empty it in the process. (This is the same as the CML mTakeEvt function.)

7.8.4  Timeouts

The rendezvous-time structure allows creating rendezvous for alarms and timeouts:

After-time-rv creates a rendezvous that becomes enabled at time interval milliseconds after synchronization. (Actually, milliseconds is a minimum waiting time; the actual delay may be longer.) (This is the same as the CML timeOutEvt function.) At-real-time-rv creates a rendezvous that becomes enabled at an absolute time specified by time; this absolute time is specified in the same way as the return value real-time from the time structure. (This is the same as the CML atTimeEvt function.)

7.8.5  CML to Scheme correspondence

The following table lists the Scheme names that correspond to particular CML names.

CML name Scheme name
rendezvous
never never-rv
alwaysEvt always-rv
choose choose
wrap wrap
guard guard
withNack with-nack
sync sync
select select
rendezvous-channels
channel make-channel
sendEvt send-rv
send send
recEvt receive-rv
rec receive
rendezvous-placeholders
iVar make-placeholder
iPut placeholder-set!
iGet placeholder-value
iGetEvt placeholder-value-rv
rendezvous-jars
mVar make-jar
mTake jar-take
mTakeEvt jar-take-rv
mPut jar-put!
rendezvous-time
timeOutEvt after-time-rv
atTimeEvt at-real-time-rv

[Go to first, previous, next page;   contents;   index]