Re: [boost] [thread] Some thoughts about "atomic"

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? 
[1]
> 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.)
[2]

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. 
<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
-- 
Peter Soetens -- FMTC -- <http://www.fmtc.be>