* Practical Considerations for Non-Blocking Concurrent Objects
* Authors: Brian N. Bershad
* Field: OS/Concurrency
* Reference: 13th Conference on Distributed Computing Systems, May 1993

Bershad discusses Compare-And-Swap (CAS) for non-blocking (optimistic)
concurrency on multiprocessors:

1. Since CAS not widely implemented in hardware, he demonstrates an
implementation based on "roll-back" which unlocks and restarts atomic
lock-based CAS if interrupted in crititcal section.

2. He shows that the usualy ways of implementing locks to prevent
contention don't work in this context: spinlocks and queuelocks.
Spinlocks keep on using TSL which incurs a penalty for the entire
system to synchronize.  Queuelocks have the waiters on a lock queued
up waiting on different cache lines so each processor only waits on
lock contention.  This fails for nonblocking objects because only one
process in the queue can succeed at a time: to succeed, all CAS before
it must fail and all after it will fail b/c it succeeded (assumptions
in this analysis?).

3. Proposes Compare-And-Compare-And-Swap, an advisory version of CAS
(i.e. may fail even if value hasn't changed) which tests the equality
condition while spinning for the lock and fails immediately if it's
changed.  Reading of the value occurs only local penalty (writes to
shared memory are broadcasted).  Demonstrates better throughput using
this scheme.