s48-refman/thread/optimism.texi

@node Optimistic concurrency
@section 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.

@cindex proposals
@cindex logs
@cindex transaction logs
@cindex optimistic concurrency proposals
@cindex optimistic concurrency logs
In the Scheme48 system, every thread has its own log of transactions,
called a @dfn{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 @emph{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.

@stindex proposals
All of the names described in this section are exported by the
@code{proposals} structure.

@subsection High-level optimistic concurrency

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

@deffn procedure call-ensuring-atomicity thunk @returns{} values
@deffnx procedure call-ensuring-atomicity! thunk @returns{} unspecified
These ensure that the operation of @var{thunk} is atomic.  If there is
already a current proposal in place, these are equivalent to calling
@var{thunk}.  If there is not a current proposal in place, these
install a new proposal, call @var{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.
@code{Call-ensuring-atomicity} returns the values that @var{thunk}
returned when the commit succeeded; @code{call-ensuring-atomicity!}
returns zero values --- it is intended for when @var{thunk} is used for
its effects only.
@end deffn

@deffn procedure call-atomically thunk @returns{} values
@deffnx procedure call-atomically! thunk @returns{} unspecified
These are like @var{call-ensuring-atomicity} and
@var{call-ensuring-atomicity!}, respectively, except that they always
install a new proposal (saving the old one and restoring it when they
are done).
@end deffn

@deffn syntax ensure-atomicity body @returns{} values
@deffnx syntax ensure-atomicity! body @returns{} unspecified
@deffnx syntax atomically body @returns{} values
@deffnx syntax atomically! body @returns{} unspecified
These are syntactic sugar over @code{call-ensuring-atomicity},
@code{call-ensuring-atomicity!}, @code{call-atomically}, and
@code{call-atomically!}, respectively.
@end deffn

Use these high-level optimistic concurrency operations to make the
body atomic.  @code{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.  @code{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 @code{call-ensuring-atomicity} @etc{} or
@code{call-atomically} @etc{} should @emph{not} explicitly commit the
current proposal; those operations above @emph{automatically} commit
the current proposal when the atomic transaction is completed.  (In
the case of @code{call-atomically} @etc{}, this is when the procedure
passed returns; in the case of @code{call-ensuring-atomicity} @etc{},
this is when the outermost enclosing atomic transaction completes, or
the same as @code{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 @embedref{Custom thread synchronization, customized thread
synchronization} facilities that commit the current proposal after
their regular function, or the operations on @embedref{Higher-level
synchronization, condition variables} that operate on the condition
variable and then commit the current proposal ---, one must use the
@code{with-new-proposal} syntax as described below, not these
operations.

@subsection Logging variants of Scheme procedures

@cindex logging operations
@cindex optimistic concurrency logging operations
@deffn procedure provisional-car pair @returns{} value
@deffnx procedure provisional-cdr pair @returns{} value
@deffnx procedure provisional-set-car! pair value @returns{} unspecified
@deffnx procedure provisional-set-cdr! pair value @returns{} unspecified
@deffnx procedure provisional-cell-ref cell @returns{} value
@deffnx procedure provisional-cell-set! cell value @returns{} unspecified
@deffnx procedure provisional-vector-ref vector index @returns{} value
@deffnx procedure provisional-vector-set! vector index value @returns{} unspecified
@deffnx procedure provisional-string-ref string index @returns{} char
@deffnx procedure provisional-string-set! string index value @returns{} unspecified
@deffnx procedure provisional-byte-vector-ref byte-vector index @returns{} char
@deffnx procedure provisional-byte-vector-set! byte-vector index byte @returns{} unspecified
@deffnx 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.  @code{Attempt-copy-bytes!} copies a sequence of
@var{count} bytes from the byte vector or string @var{from}, starting
at the index @var{fstart}, to the byte vector or string @var{to},
starting at the index @var{tstart}.
@end deffn

@subsection Synchronized records

@cindex optimistically concurrent record types
@deffn syntax define-synchronized-record-type
@lisp
(define-synchronized-record-type @var{tag} @var{type-name}
  (@var{constructor-name} @var{parameter-field-tag} @dots{})
  [(@var{sync-field-tag} @dots{})]
  @var{predicate-name}
  (@var{field-tag} @var{accessor-name} [@var{modifier-name}])
  @dots{})@end lisp
This is exactly like @code{define-record-type} from the
@code{define-record-types} structure, except that the accessors &
modifiers for each field in @var{sync-field-tag} @dots{} 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.
@end deffn

@stindex define-sync-record-types
The @code{proposals} structure also exports
@code{define-record-discloser} (@pxref{Records}).  Moreover, the
@code{define-sync-record-types} structure, too, exports
@code{define-synchronized-record-type}, though it does not export
@code{define-record-discloser}.

@subsection 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:

@lisp
(define (make-counter value)
  (lambda ()
    (let ((v value))
      (set! value (+ v 1))
      v)))@end lisp

This has a problem: between obtaining the value of the closure's slot
for @code{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:

@lisp
(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))))))@end lisp

This poses another problem, however.  Suppose we wish to write an
atomic @code{(step-counters! @var{counter @dots{}})} procedure that
increments each of the supplied counters by one; supplying a counter
@var{n} times should have the effect of incrementing it by @var{n}.
The na@"{@dotless{i}}ve definition of it is this:

@lisp
(define (step-counters! . counters)
  (for-each (lambda (counter) (counter))
            counters))@end 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:

@lisp
(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)))))))@end 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 @embedref{Cells, cell}, in order to use a provisional accessor &
modifier, as is necessary to make use of optimistic concurrency, and
we surround with @code{call-ensuring-atomicity} any regions we wish to
be atomic:

@lisp
(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))))@end lisp

@noindent
This approach has a number of advantages:

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

@item Composition of transactions is entirely transparent; it is
accomplished automatically simply by @code{call-ensuring-atomicity}.

@item 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.

@item 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.
@end itemize

@subsection Low-level optimistic concurrency

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

@cindex proposals
@deffn procedure make-proposal @returns{} proposal
@deffnx procedure current-proposal @returns{} proposal
@deffnx procedure set-current-proposal! proposal @returns{} unspecified
@deffnx procedure remove-current-proposal! @returns{} unspecified
@code{Make-proposal} creates a fresh proposal.  @code{Current-proposal}
returns the current thread's proposal.  @code{Set-current-proposal!}
sets the current thread's proposal to @var{proposal}.
@code{Remove-current-proposal!} sets the current thread's proposal to
@code{#f}.
@end deffn

@cindex committing proposals
@cindex proposals, committing
@deffn procedure maybe-commit @returns{} boolean
@deffnx procedure invalidate-current-proposal! @returns{} unspecified
@code{Maybe-commit} checks that the current thread's proposal is still
valid.  If it is, the proposal's writes are committed, and
@code{maybe-commit} returns @code{#t}; if not, the current thread's
proposal is set to @code{#f} and @code{maybe-commit} returns @code{#f}.
@code{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.
@end deffn

@cindex installing proposals
@cindex proposals, installing
@deffn syntax with-new-proposal (lose) body @returns{} values
Convenience for repeating a transaction.  @code{With-new-proposal}
saves the current proposal and will reinstates it when everything is
finished.  After saving the current proposal, it binds @var{lose} to a
nullary procedure that installs a fresh proposal and that evaluates
@var{body}; it then calls @var{lose}.  Typically, the last thing, or
close to last thing, that @var{body} will do is attempt to commit the
current proposal, and, if that fails, call @var{lose} to retry.
@code{With-new-proposal} expands to a form that returns the values
that @var{body} returns.

This @code{retry-at-most} example tries running the transaction of
@var{thunk}, and, if it fails to commit, retries at most @var{n}
times.  If the transaction is successfully committed before @var{n}
repeated attempts, it returns true; otherwise, it returns false.

@lisp
(define (retry-at-most n thunk)
  (with-new-proposal (lose)
    (thunk)
    (cond ((maybe-commit) #t)
          ((zero? n)      #f)
          (else (set! n (- n 1))
                (lose)))))@end lisp
@end deffn