Scheme 48 Manual | Contents | In Chapter: Threads
Previous: Optimistic concurrency | Next: Optimistic concurrency

Optimistic concurrency

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 ensuring-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 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!.

The following procedures give access to the low-level proposal mechanism.

Maybe-commit verifies that any reads logged in proposal are still valid and, if so, performs any writes that proposal 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.

With-proposal saves the current proposal, installs proposal as the current proposal, and then calls thunk. When thunk returns the saved proposal is reinstalled as the current proposal and the value(s) returned by thunk are returned. 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.

Previous: Optimistic concurrency | Next: Optimistic concurrency