Next: Higher-level synchronization, Previous: Basic thread operations, Up: Multithreading
Scheme48's fundamental thread synchronization mechanism is based on a device often used in high-performance database systems: optimistic concurrency. The basic principle of optimistic concurrency is that, rather than mutually excluding other threads from data involved in one thread's transaction, a thread keeps a log of its transaction, not actually modifying the data involved, only touching the log. When the thread is ready to commit its changes, it checks that all of the reads from memory retained their integrity — that is, all of the memory that was read from during the transaction has remained the same, and is consistent with what is there at the time of the commit. If, and only if, all of the reads remained valid, the logged writes are committed; otherwise, the transaction has been invalidated. While a thread is transacting, any number of other threads may be also transacting on the same resource. All that matters is that the values each transaction read are consistent with every write that was committed during the transaction. This synchronization mechanism allows for wait-free, lockless systems that easily avoid confusing problems involving careful sequences of readily deadlock-prone mutual exclusion.
In the Scheme48 system, every thread has its own log of transactions, called a proposal. There are variants of all data accessors & modifiers that operate on the current thread's proposal, rather than actual memory: after the initial read of a certain part of memory — which does perform a real read —, the value from that location in memory is cached in the proposal, and thenceforth reads from that location in memory will actually read the cache; modifications touch only the proposal, until the proposal is committed.
All of the names described in this section are exported by the
proposals
structure.
There are several high-level operations that abstract the manipulation of the current thread's proposal.
These ensure that the operation of thunk is atomic. If there is already a current proposal in place, these are equivalent to calling thunk. If there is not a current proposal in place, these install a new proposal, call thunk, and attempt to commit the new proposal. If the commit succeeded, these return. If it failed, these retry with a new proposal until they do succeed.
Call-ensuring-atomicity
returns the values that thunk returned when the commit succeeded;call-ensuring-atomicity!
returns zero values — it is intended for when thunk is used for its effects only.
These are like call-ensuring-atomicity and call-ensuring-atomicity!, respectively, except that they always install a new proposal (saving the old one and restoring it when they are done).
These are syntactic sugar over
call-ensuring-atomicity
,call-ensuring-atomicity!
,call-atomically
, andcall-atomically!
, respectively.
Use these high-level optimistic concurrency operations to make the
body atomic. Call-ensuring-atomicity
&c. simply ensure that
the transaction will be atomic, and may `fuse' it with an enclosing
atomic transaction if there already is one, i.e. use the proposal for
that transaction already in place, creating one only if there is not
already one. Call-atomically
&c. are for what might be
called `subatomic' transactions, which cannot be fused with other
atomic transactions, and for which there is always created a new
proposal.
However, code within call-ensuring-atomicity
&c. or
call-atomically
&c. should not explicitly commit the
current proposal; those operations above automatically commit
the current proposal when the atomic transaction is completed. (In
the case of call-atomically
&c., this is when the procedure
passed returns; in the case of call-ensuring-atomicity
&c.,
this is when the outermost enclosing atomic transaction completes, or
the same as call-atomically
if there was no enclosing atomic
transaction.) To explicitly commit the current proposal — for
example, to perform some particular action if the commit fails rather
than just to repeatedly retry the transaction, or to use operations
from the customized thread synchronization facilities that commit the current proposal after
their regular function, or the operations on condition variables that operate on the condition
variable and then commit the current proposal —, one must use the
with-new-proposal
syntax as described below, not these
operations.
These are variants of most basic Scheme memory accessors & modifiers that log in the current proposal, rather than performing the actual memory access/modification. All of these do perform the actual memory access/modification, however, if there is no current proposal in place when they are called.
Attempt-copy-bytes!
copies a sequence of count bytes from the byte vector or string from, starting at the index fstart, to the byte vector or string to, starting at the index tstart.
(define-synchronized-record-type tag type-name (constructor-name parameter-field-tag ...) [(sync-field-tag ...)] predicate-name (field-tag accessor-name [modifier-name]) ...)This is exactly like
define-record-type
from thedefine-record-types
structure, except that the accessors & modifiers for each field in sync-field-tag ... are defined to be provisional, i.e. to log in the current proposal. If the list of synchronized fields is absent, all of the fields are synchronized, i.e. it is as if all were specified in that list.
The proposals
structure also exports
define-record-discloser
(see Records). Moreover, the
define-sync-record-types
structure, too, exports
define-synchronized-record-type
, though it does not export
define-record-discloser
.
Here is a basic example of using optimistic concurrency to ensure the synchronization of memory. We first present a simple mechanism for counting integers by maintaining internal state, which is expressed easily with closures:
(define (make-counter value) (lambda () (let ((v value)) (set! value (+ v 1)) v)))
This has a problem: between obtaining the value of the closure's slot
for value
and updating that slot, another thread might be given
control and modify the counter, producing unpredictable results in
threads in the middle of working with the counter. To remedy this, we
might add a mutual exclusion lock to counters to prevent threads from
simultaneously accessing the cell:
(define (make-counter value) (let ((lock (make-lock))) (lambda () (dynamic-wind (lambda () (obtain-lock lock)) (lambda () (let ((v value)) (set! value (+ v 1)) v)) (lambda () (release-lock lock))))))
This poses another problem, however. Suppose we wish to write an
atomic (step-counters!
counter ...)
procedure that
increments each of the supplied counters by one; supplying a counter
n times should have the effect of incrementing it by n.
The naïve definition of it is this:
(define (step-counters! . counters) (for-each (lambda (counter) (counter)) counters))
Obviously, though, this is not atomic, because each individual counter is locked when it is used, but not the whole iteration across them. To work around this, we might use an obfuscated control structure to allow nesting the locking of counters:
(define (make-counter value) (let ((lock (make-lock))) (lambda args (dynamic-wind (lambda () (obtain-lock lock)) (lambda () (if (null? args) (let ((v value)) (set! value (+ v 1)) v) ((car args)))) (lambda () (release-lock lock)))))) (define (step-counters! . counters) (let loop ((cs counters)) (if (null? cs) (for-each (lambda (counter) (counter)) counters) ((car cs) (lambda () (loop (cdr cs)))))))
Aside from the obvious matter of the obfuscation of the control structures used here, however, this has another problem: we cannot step one counter multiple times atomically. Though different locks can be nested, nesting is very dangerous, because accidentally obtaining a lock that is already obtained can cause deadlock, and there is no modular, transparent way to avoid this in the general case.
Instead, we can implement counters using optimistic concurrency to
synchronize the shared data. The state of counters is kept explicitly
in a cell, in order to use a provisional accessor &
modifier, as is necessary to make use of optimistic concurrency, and
we surround with call-ensuring-atomicity
any regions we wish to
be atomic:
(define (make-counter initial) (let ((cell (make-cell initial))) (lambda () (call-ensuring-atomicity (lambda () (let ((value (provisional-cell-ref cell))) (provisional-cell-set! cell (+ value 1)) value)))))) (define (step-counters! . counters) (call-ensuring-atomicity! (lambda () (for-each (lambda (counter) (counter)) counters))))
This approach has a number of advantages:
call-ensuring-atomicity
wrapping
the portions of code that we explicitly want to be atomic.
call-ensuring-atomicity
.
Along with the higher-level operations described above, there are some lower-level primitives for finer control over optimistic concurrency.
Make-proposal
creates a fresh proposal.Current-proposal
returns the current thread's proposal.Set-current-proposal!
sets the current thread's proposal to proposal.Remove-current-proposal!
sets the current thread's proposal to#f
.
Maybe-commit
checks that the current thread's proposal is still valid. If it is, the proposal's writes are committed, andmaybe-commit
returns#t
; if not, the current thread's proposal is set to#f
andmaybe-commit
returns#f
.Invalidate-current-proposal!
causes an inconsistency in the current proposal by caching a read and then directly writing to the place that read was from.
Convenience for repeating a transaction.
With-new-proposal
saves the current proposal and will reinstates it when everything is finished. After saving the current proposal, it binds lose to a nullary procedure that installs a fresh proposal and that evaluates body; it then calls lose. Typically, the last thing, or close to last thing, that body will do is attempt to commit the current proposal, and, if that fails, call lose to retry.With-new-proposal
expands to a form that returns the values that body returns.This
retry-at-most
example tries running the transaction of thunk, and, if it fails to commit, retries at most n times. If the transaction is successfully committed before n repeated attempts, it returns true; otherwise, it returns false.(define (retry-at-most n thunk) (with-new-proposal (lose) (thunk) (cond ((maybe-commit) #t) ((zero? n) #f) (else (set! n (- n 1)) (lose)))))