StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>Why is E7 needed?</p> </blockquote> <p>Its more for optimization. </p> <p>Consider two threads trying to enqueue at the same time. They all get to E5 but before thread 1 gets to E7 thread 2 successfully queues. When thread 1 gets to E7 it will observer t == tail to be false then retries. This will avoid a costly CAS. Of course its not full proof because E7 can succeed before thread 2 enqueues and eventually fails the CAS and has to retry anyway. </p> <blockquote> <p>why D5 is needed</p> </blockquote> <p>Similar to D5</p> <p>Again, both functions without E7 and D5 would work. There was probably some benchmarking going on and found that under moderate contention the double check increases throughput (this is more of an observation and less of fact).</p> <p>Edit: </p> <p>I went and read the paper on this queue a bit more. The check is also there for correctness of a lock free algorithm and less of the data structure's state.</p> <blockquote> <p>The lock-free algorithm is non-blocking because if there are non-delayed processes attempting to perform operations on the queue, an operation is guaranteed to complete within finite time. An enqueue operation loops only if the condition in line E7 fails, the condition in line E8 fails, or the compare and swap in line E9 fails. A dequeue operation loops only if the condition in line D5 fails, the condition in line D6 holds (and the queue is not empty), or the compare and swap in line D13 fails. We show that the algorithm is non-blocking by showing that a process loops beyond a finite number of times only if another process completes an operation on the queue.</p> </blockquote> <p><a href="http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf" rel="nofollow">http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload