On Wed, Jan 04, 2006 at 03:20:03PM +0100, zvrba@globalnet.hr wrote:
> Non-blocking data structures have an upper bound to latency. Achievable
> latency is O(n) where n is the number of processes contending for the
> data structure. It's very different from one thread acquiring a spinlock
> and others indefinetly burning CPU cycles until the spinlock is released.

This is incorrect. You are confusing non-blocking with wait-free.
Non-block algorithms guaranty that at least one instance is mkaing
progress, e.g. can insert an element. It does not mean you can predict
*which* instance it is. This means in a NUMA system a remote CPU can
starve. A wait-free algorithm (which is much harder) gives you an upper
bound on the time of an operation for any single instance. It does
effectively prevent starvation.

Joerg