Next: , Previous: Basic thread operations, Up: Multithreading


5.2 Optimistic concurrency

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.

5.2.1 High-level optimistic concurrency

There are several high-level operations that abstract the manipulation of the current thread's proposal.

— procedure: call-ensuring-atomicity thunk –> values
— procedure: call-ensuring-atomicity! thunk –> unspecified

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.

— procedure: call-atomically thunk –> values
— procedure: call-atomically! thunk –> unspecified

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

— syntax: ensure-atomicity body –> values
— syntax: ensure-atomicity! body –> unspecified
— syntax: atomically body –> values
— syntax: atomically! body –> unspecified

These are syntactic sugar over call-ensuring-atomicity, call-ensuring-atomicity!, call-atomically, and call-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.

5.2.2 Logging variants of Scheme procedures

— procedure: provisional-car pair –> value
— procedure: provisional-cdr pair –> value
— procedure: provisional-set-car! pair value –> unspecified
— procedure: provisional-set-cdr! pair value –> unspecified
— procedure: provisional-cell-ref cell –> value
— procedure: provisional-cell-set! cell value –> unspecified
— procedure: provisional-vector-ref vector index –> value
— procedure: provisional-vector-set! vector index value –> unspecified
— procedure: provisional-string-ref string index –> char
— procedure: provisional-string-set! string index value –> unspecified
— procedure: provisional-byte-vector-ref byte-vector index –> char
— procedure: provisional-byte-vector-set! byte-vector index byte –> unspecified
— procedure: attempt-copy-bytes! from fstart to tstart count –> unspecified

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.

5.2.3 Synchronized records

— syntax: define-synchronized-record-type
          (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 the define-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.

5.2.4 Optimistic concurrency example

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:

5.2.5 Low-level optimistic concurrency

Along with the higher-level operations described above, there are some lower-level primitives for finer control over optimistic concurrency.

— procedure: make-proposal –> proposal
— procedure: current-proposal –> proposal
— procedure: set-current-proposal! proposal –> unspecified
— procedure: remove-current-proposal! –> unspecified

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.

— procedure: maybe-commit –> boolean
— procedure: invalidate-current-proposal! –> unspecified

Maybe-commit checks that the current thread's proposal is still valid. If it is, the proposal's writes are committed, and maybe-commit returns #t; if not, the current thread's proposal is set to #f and maybe-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.

— syntax: with-new-proposal (lose) body –> values

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