StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem is your algorithm: Consider this sequence of events:</p> <p>Thread 1 calls <code>list.Add(workItem1)</code>, which completes fully.</p> <p>Status is: </p> <pre><code>first=workItem1, workItem1.next = null </code></pre> <p>Then thread 1 calls <code>list.Add(workItem2)</code> and reaches the spot right before the second <code>Replace</code> (where you have the comment "//lets try").</p> <p>Status is: </p> <pre><code>first=workItem1, workItem1.next = null, nextItem=workItem1 </code></pre> <p>At this point thread 2 takes over and calls <code>list.Get()</code>. Assume <code>workItem1</code>'s executionTime is now, so the call succeeds and returns <code>workItem1</code>.</p> <p>After this status is: </p> <pre><code>first = null, workItem1.next = null </code></pre> <p>(and in the other thread, <code>nextItem</code> is still <code>workItem1</code>).</p> <p>Now we get back to the first thread, and it completes the <code>Add()</code> by setting <code>workItem1.next:=workItem2</code>.</p> <p>If we call <code>list.Get()</code> now, we will get <code>null</code>, even though the <code>Add()</code> completed successfully.</p> <p>You should probably look up a real peer-reviewed lock-free linked list algorithm. I think the standard one is <a href="ftp://ftp.cs.rpi.edu/pub/valoisj/podc95.ps.gz" rel="nofollow noreferrer">this</a> by John Valois. There is a C++ implementation <a href="http://www.cs.rpi.edu/~bushl2/portfolio/lockfree-grape/code/lockfreelist.h" rel="nofollow noreferrer">here</a>. <a href="http://www.cs.chalmers.se/~dcs/ConcurrentDataStructures/phd_chap5.pdf" rel="nofollow noreferrer">This</a> article on lock-free priority queues might also be of use.</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