Boost logo

Boost :

From: Peter Soetens (peter.soetens_at_[hidden])
Date: 2006-12-05 04:03:22

On Friday 01 December 2006 11:33, Roland Schwarz wrote:
> 4) Does there exist a canonical set of atomic primitives, from which
> others can be built?
> E.g. given atomic_test_and_set, atomic_load and
> atomic_store is it possible to emulate atomic_compare_and_swap? (without
> use of system mutices of course.)

The answer to [1] is yes. The answer to [2] is no. The reference work which
has prooven this is written by M. Herlihy (1991) "Wait-free synchronization".
ACM Trans. Program. Lang. Syst. 13 (1), 124–149.
<> This paper is not
easy. One of the things he proves is that
there is an 'ordering' (using the 'consensus number') of atomic operations,
where a higher consensus number indicates that it can be used to implement a
lower consensus number. Well, only Compare-And-Swap and Memory-Move have a
consensusnumber of infinity. Read-Write has order '1', Atomic fetch-and-add
only has '2'. (The ordering collapses on uni-processor systems though.) See
page '126' of the above link.

The main idea is: if your processor does not have the compare-and-swap
instruction, it is not very useful for multicore or SMP systems.

I believe 'lock-free' algorithms (which use CAS) have been discussed earlier
on this list.


Peter Soetens -- FMTC -- <>

Boost list run by bdawes at, gregod at, cpdaniel at, john at