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>