Explain Michael & Scott lock-free queue alorigthm

This is actually the non-blocking memory reclamation problem that’s being explored years since Maged Michael, one of the authors of MS queue, introduced Hazard Pointers [1].

Hazard Pointers allow the thread to reserve blocks so that other threads won't really reclaim them before it finishes. However, this mechanism incurs nontrivial performance overhead.

There're also many epoch-based reclamation variants such as RCU [2,3], and most recently, interval-based reclamation (IBR) [4]. They avoid use-after-free by reserving epochs and are faster than Hazard Pointers. As far as I know, epoch-based reclamations are widely adopted to handle this problem.

You can take a look at these papers referred below for more details. The paper of Interval-Based Memory Reclamation has much background discussed.

This is a general problem in non-blocking data structures and we generally don't consider it as the bug of the data structure itself---after all it only occurs in languages using manual memory management like C/C++ but not in those like Java (BTW, Michael & Scott Queue has been adopted in Java Concurrency for years).

Reference:

[1] Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, Maged M. Michael, IEEE Transactions on Parallel and Distributed Systems, 2004.

[2] Performance of Memory Reclamation for Lockless Synchronization, 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 Reclamation, Haosen Wen et al., Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018.

Thank you, very interesting subject! It's definitely looks like a bug, but one of the authors of the paper assert that their free() is not normal free() we all live with, but some magic free(), so there is no bug. Fantastic.

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

Hope no one put this into production without thorough analysis.