In message <20070313161735.GA5993@polynum.com>,
tlaronde@polynum.com writes:

>On Tue, Mar 13, 2007 at 08:26:51AM -0700, Jason Thorpe wrote:
[...]
>>
>> Hm, if it is compare-and-swap, then great... but I thought it was  
>> compare-and-set.  Anyway, if you could double-check for me, that would  
>> be great -- m68k is one of the platforms I was thinking of when I went  
>> with "compare-and-store"
>
>cas is "compare and swap" from Solaris Internals, second edition, page
>820.

CAS meaning "compare and swap" goes back to the IBM 370.  Usage on
sparcv9 and 68040+ is, IIRC, compatible.

The three arguments are: address, expected value, new value.  The
value at the address is atomically overwritten by the new value if and
only if the value at the address (atomically) matches the expected value.

CAS with boolean result (swapped, or not) lets algorithm designers
refetch the current value and restart their atomic operation. You
don't strictly need to atomically return the old value when it differs
from the expected value.

Typically, effort goes into avoiding the so-called "A/B/A" problem,
where one thread reads value A at address L, a second thread reads A
from L, modifies L to B, and then back to A; whereupon the first
thread reads "A" (with a CAS) and presume that the location value
hasn' changed since its prior read.  (Consider "A" being a pointer
which has been freed, then reallocated as an object of a different type).

But for data structures with simple semantics like counters,
that doesn't matter.