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.

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 returns values
 -- procedure: call-ensuring-atomicity! thunk returns 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 returns values
 -- procedure: call-atomically! thunk returns 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 returns values
 -- syntax: ensure-atomicity! body returns unspecified
 -- syntax: atomically body returns values
 -- syntax: atomically! body returns 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 etc simply ensure that the transaction will be atomic, and may `fuse' it with an enclosing atomic transaction if there already is one, ie use the proposal for that transaction already in place, creating one only if there is not already one.  Call-atomically etc 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 etc or call-atomically etc 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 etc, this is when the procedure passed returns; in the case of call-ensuring-atomicity etc, 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 Custom thread synchronization, customized thread synchronization facilities that commit the current proposal after their regular function, or the operations on Higher-level synchronization, 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.

Logging variants of Scheme procedures
-------------------------------------

 -- procedure: provisional-car pair returns value
 -- procedure: provisional-cdr pair returns value
 -- procedure: provisional-set-car! pair value returns unspecified
 -- procedure: provisional-set-cdr! pair value returns unspecified
 -- procedure: provisional-cell-ref cell returns value
 -- procedure: provisional-cell-set! cell value returns unspecified
 -- procedure: provisional-vector-ref vector index returns value
 -- procedure: provisional-vector-set! vector index value returns unspecified
 -- procedure: provisional-string-ref string index returns char
 -- procedure: provisional-string-set! string index value returns unspecified
 -- procedure: provisional-byte-vector-ref byte-vector index returns char
 -- procedure: provisional-byte-vector-set! byte-vector index byte returns unspecified
 -- procedure: attempt-copy-bytes! from fstart to tstart count returns 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.

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])
            ...) lisp
          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, ie to log in the current proposal.  If the list of
          synchronized fields is absent, all of the fields are synchronized,
          ie 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.

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

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

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

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

                    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 Cells, 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)))) lisp

                         This approach has a number of advantages:

                           * The original control structure is preserved, only with
                              provisional operators for shared memory access that we explicitly wish
                              to be synchronized and with call-ensuring-atomicity wrapping
                              the portions of code that we explicitly want to be atomic.

                           * Composition of transactions is entirely transparent; it is
                              accomplished automatically simply by call-ensuring-atomicity.

                           * Transactions can be nested arbitrarily deeply, and there is no
                              problem of accidentally locking the same resource again at a deeper
                              nesting level to induce deadlock.

                           * No explicit mutual exclusion or blocking is necessary.  Threads
                              proceed without heed to others, but do not actually write data to the
                              shared memory until its validity is ensured.  There is no deadlock at
                              all.

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 returns proposal
 -- procedure: current-proposal returns proposal
 -- procedure: set-current-proposal! proposal returns unspecified
 -- procedure: remove-current-proposal! returns 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 returns boolean
 -- procedure: invalidate-current-proposal! returns 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 returns 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))))) lisp