[nano_o]

I'm a bit skeptical about the code: it seems that it's using only the atomic fetch-and-add synchronization instruction, and not compare-and-swap. However, I think that whether queues are implementable with only fetch-and-add is an open problem in distributed computing (in technical terms, whether queues are in the Common2 family. See for example Afek et al., "Common2 Extended to Stacks and Unbounded Concurrency".)

[eloff]

I've seen many queues implemented similarly to this, and it works fine. Every thread that calls fetch and add receives a different result, therefore, wrapping asside, there can only be one thread with access to each slot. If there is only one consumer and one producer you don't need fetch and add at all (that is how fastflow is implemented.) You must check that your slot is populated by either comparing with the other index (producer if your the consumer), which is stupid because that cache line is highly contended. The better way is set a slot to null after you've consumed it, and if your the producer, you first check if the current slot is null before attempting to increment the index. A race condition exists where the slot can be null before incrementing but not afterward (e.g. only one slot free but several producers saw that and incremented.) In reality all that means is the producer can skip slots and the consumer must keep incrementing if it sees a null slot rather than assume an empty queue (can be tempered by checking x slots and then falling back to checking the producer index.) Consumer and producer indexes must be on seperate cache lines and some effort can be made to keep consumer and producer on sperate cache lines in the actual queue. e.g. each slot can be a whole cache line and pop() and push() can be batched to work with 8 elements at a time. In other words OP is a noob and I could write a queue that whoops his hiney (danger: attempt at humor.)

[nano_o]

Ok, so it is relatively easy to obtain a safe implementation and from there you can use a heuristic to prevent a thread from looping forever trying to find an available slot. Would that sum up the issue in practice?

[colanderman]

As far as I can tell, your "hiney-whooping" queue isn't lock-free (i.e., if one producer dies, all consumers will block waiting for that entry).

[colanderman]

Indeed, fetch-and-add can only solve consensus for up to 2 actors [1]. However, that only directly relates to wait-free (= guaranteed individual progress) data structures. I forget how that relates to lock-free data structures.

[1] http://en.wikipedia.org/wiki/Fetch-and-add