On 2015-10-22 03:03, Gavin Lambert wrote:
On 22/10/2015 20:57, Giovanni Piero Deretta wrote:
It seems to me then it is not really lock free then, right?
There's a difference between "lock free" and "wait free" (though I haven't examined the code to see which most correctly applies here).
Wait-free is better than lock-free, of course, but it's also incredibly hard to achieve in an MPMC problem.
Strictly speaking it is not wait-free, because all writers in push() have to wait for the writer before them to complete (increment trail edge index by 1) before they can complete (increase the trail edge index by 1). However, this is the only waiting part, they don't have to wait to write their item into the queue (assuming there are empty slots in the queue). The readers behave symmetrically. The one advantage of this queue (assuming the implementation is correct) is that there is lower contention than methods that use compare_exchange (and therefore spend more time colliding and waiting).