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  is yes. The answer to  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.
<http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf> 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 -- <http://www.fmtc.be>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk