Practical considerations for non-blocking concurrent objects
Bershad
1993
Summary by Ed Swierk

Paper describes problems with implementing Compare-and-Set using primitive
instructions like Test-and-Set as part of a spinlock or queueing lock, and
presents a way of solving these problems.

non-blocking concurrent objects:
concurrent objects whose operations are not contained within mutually
exclusive critical sections

Why non-blocking?  Avoids problems with blocking:
- scheduling convoys: other processors have to wait for a descheduled
  thread that is holding a lock
- priority inversion: low priority thread holds a lock needed by a high
  priority thread, but low priority thread is preempted by a medium
  priority thread
- deadlock: processors hold locks while waiting for locks held by other
  processors

Compare-and-Swap(address, old value, new value):
  acquire lock
  if address contents == old value:
    address contents := new value
    release lock
    return SUCCESS
  else:
    release lock
    return FAILURE

(shouldn't this be called Compare-and-Copy?)

To be non-blocking, a thread can be preempted while in the Compare-and-Swap
critical section, releasing the lock.  Two ways of proceeding:

roll-out mode: resume at beginning if assignment did not take place,
otherwise resume at end

roll-forward mode: continue executing until assignment completes, resume
at end; more complex but necessary if pathological scheduling prevents
processors from making progress in roll-out mode