Explain Alorigthm waiting lines from Michael & Scott

Question

I am learning the queue algorithm without blocking Michael and Scott and trying to implement it in C ++.

But I made a race in my code and I think that there can be a race in the algorithm.

I read an article here: Simple, fast and practical locking and locking Parallel queuing algorithms and the original Dequeue pseudo-code are as follows:

dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean D1: loop // Keep trying until Dequeue is done D2: head = Q->Head // Read Head D3: tail = Q->Tail // Read Tail D4: next = head.ptr->next // Read Head.ptr->next D5: if head == Q->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(&Q->Tail, tail, <next.ptr, tail.count+1>) D11: else // No need to deal with Tail // Read value before CAS // Otherwise, another dequeue might free the next node D12: *pvalue = next.ptr->value // Try to swing Head to the next node D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>) 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 

In my opinion, the race is as follows:

• Theme 1 switched to D3 and then stopped.
• Thread 2 advanced to D3, read the same chapter as Thread 1.
• Topic 2, fortunately, progressed to D20, on D19 she freed head.ptr
• Thread 1 continues and advances to D4, trying to read head.ptr->next , but since head.ptr already freed by Thread 1, a crash occurs.

And my C ++ code always crashes in D4 for Thread 1.

Can someone point out my mistake and give some explanation?

Answer 1

Thank you, a very interesting topic! This definitely looks like a mistake, but one of the authors of the article claims that their free () is not the normal free () that we all live with, but some magic free (), so there are no errors. Fantastic.

See http://blog.shealevy.com/2015/04/23/use-after-free-bug-in-maged-m-michael-and-michael-l-scotts-non-blocking-concurrent-queue- algorithm /

I hope that no one will put this into production without a thorough analysis.

Answer 2

This is actually a non-blocking memory recovery problem that was explored many years ago when Maged Michael, one of the authors of the MS lineup, introduced hazard pointers [1].

Hazard pointers allow a thread to reserve blocks so that other threads do not actually return them until completion. However, this mechanism leads to non-trivial performance overheads.

There are also many epoch-based reclamation options, such as RCU [2,3], and more recently, interval-based reclamation (IBR) [4]. They avoid use after release, reserving ages, and are faster than hazard indicators. As far as I know, remediation of the era is widely used to solve this problem.

You can take a look at these documents below for more details. The article "Interval-based memory recovery" discusses a lot.

This is a common problem in non-blocking data structures, and we, as a rule, do not consider it as an error of the data structure itself - after all, this happens only in languages ​​that use manual memory management, such as C / C ++, but not in Java (by the way, Michael & Scott Queue has been used in Java Concurrency for many years).

Reference:

[1] Hazard statements: secure memory recovery for non-blocking objects, Maged M. Michael, IEEE Transactions in Parallel and Distributed Systems, 2004

[2] Memory recovery performance for synchronization without blocking, Thomas E. Hart et al., Journal of Parallel and Distributed Computing, 2007

[3] Read Copy Update, Paul E. McKenney et al., Ottawa Linux Symposium, 2002.

[4] Interval-based memory recovery, Khaosen Wen et al., Materials of the 23rd ACM SIGPLAN Symposium on the Principles and Practices of Parallel Programming (PPoPP), 2018.