Explain Michael & Scott lock-free queue alorigthm : <p>I am studying Michael &amp; Scott's lock-free queue algorithm and trying to implemented it in C++.</p>

<p>But I produced a race in my code and think there may be a race in the algorithm.</p>

<p>I read the paper here:
<a href="https://www.research.ibm.com/people/m/michael/podc-1996.pdf" rel="noreferrer">Simple, Fast, and Practical Non-Blocking and Blocking
Concurrent Queue Algorithms</a>
and the original Dequeue pseudo-code is as following:</p>

<pre><code>dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1:   loop                          // Keep trying until Dequeue is done
D2:      head = Q-&gt;Head             // Read Head
D3:      tail = Q-&gt;Tail             // Read Tail
D4:      next = head.ptr-&gt;next      // Read Head.ptr-&gt;next
D5:      if head == Q-&gt;Head         // Are head, tail, and next consistent?
D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
D7:            if next.ptr == NULL  // Is queue empty?
D8:               return FALSE      // Queue is empty, couldn't dequeue
D9:            endif
                // Tail is falling behind.  Try to advance it
D10:            CAS(&amp;Q-&gt;Tail, tail, &lt;next.ptr, tail.count+1&gt;)
D11:         else                    // No need to deal with Tail
               // Read value before CAS
               // Otherwise, another dequeue might free the next node
D12:            *pvalue = next.ptr-&gt;value
               // Try to swing Head to the next node
D13:            if CAS(&amp;Q-&gt;Head, head, &lt;next.ptr, head.count+1&gt;)
D14:               break             // Dequeue is done.  Exit loop
D15:            endif
D16:         endif
D17:      endif
D18:   endloop
D19:   free(head.ptr)                // It is safe now to free the old node
D20:   return TRUE                   // Queue was not empty, dequeue succeeded
</code></pre>

<p>In my view, the race is like this:</p>

<ol>
<li>Thread 1 advanced to D3 and then stop.</li>
<li>Thread 2 advanced to D3, read the same head as Thread 1.</li>
<li>Thread 2 luckily advanced all the way to D20, at D19 it freed head.ptr</li>
<li>Thread 1 continues and advanced to D4, trying to read <code>head.ptr-&gt;next</code>, but as <code>head.ptr</code> is already freed by Thread 1, crash happens.</li>
</ol>

<p>And my C++ code really always crashes at D4 for Thread 1.</p>

<p>Can anyone please point out my mistake and give some explanation ?</p>
