Off-Topic :: Wait-Free/Lock-less synchronization crash course

Well, results are not that good as I have hoped. (In depth info at Wikipedia. Read the first reference on the page written by Maurice Herlihy in 1993.)

1. Rule of thumb: lock-less can only be data structures which synchronize using single datum.
2. Compare-And-Swap( ptr, old, new ) can be used for implementation of atomic counters. The operation is supported by all high performance platforms (e.g. PowerPC & IA-32).
   
3. One cannot make lock-less FIFO for N:M (N readers/M writers) nor for 1:M (1 reader/M writers) configurations. Seems that 1:1 (1 read and 1 writer) only possible configuration and in fact it doesn't require any special support at CPU level. (Reference to rule of thumb: FIFO requires two data items for implementation - head/tail (or next/prev).)
   
4. Stack (LIFO) can be implemented wait-free/lock-less using Compare-And-Swap() op, since it needs only single pointer for implementation - head - pointing to first element to remove/last element inserted.

Conclusion:

1. Unixes were 100% right putting pipes at foundation of I/O: pipe can be implemented as couple of FIFOs and as long as pipe isn't shared between more than 2 applications, it can be completely lock free.
   
2. Stack (along with Compare-And-Swap op) allows to implement memory management (for static block size) very efficiently. (Edit1. In preemptive SMP OS, that might lead to situation when Compare-And-Swap would succeed despite fact that state of queue already changed. Proper implementation for multiple CPUs would use several (at minimum 2) stacks. Allocations are made from one stack, freeing is done on next stack. Allocation function rotates stacks when detects that current stack is empty. Allocation is failed when all stacks were queried at least once and all are empty. Alternatively, one can introduce additional counter: generation counter. That way Compare-And-Swap needs to be able to write double word. When element is allocated, generation counter is incremented. When element is freed, we put on stack pair - pointer and generation counter - which would be with high probability unique.)
   
3. Message passing systems suck big time because (i) 1:1 FIFOs are inapplicable and (ii) it is impossible to optimize memory allocation with lock-less stack since it is impossible to tell where the message would end up. (The later can only be implemented in worst case scenario of shared memory.)