Automatic Memory Reclamation for Lock-Free Data Structures

作者：Cohen Nachshon^*; Petrank Erez

来源：ACM Sigplan Notices, 2015, 50(10): 260-279.

DOI：10.1145/2814270.2814298

• Algorithms
• Design
• Theory
• Memory Management
• Concurrent Data Structures
• Non-blocking
• Lock-free
• Hazard Pointers

Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are "manual" in the sense that the developer has to specify when nodes have retired and may be reclaimed. Retiring nodes adequately is non-trivial and often requires the modification of the original lock-free algorithm. In this paper we present an automatic lock-free reclamation scheme for lock-free data-structures in the spirit of a mark-sweep garbage collection. The proposed algorithm works with any normalized lock-free algorithm and with no need for the programmer to retire nodes or make changes to the algorithm. Evaluation of the proposed scheme on a linked-list and a hash table shows that it performs similarly to the best manual (lock-free) memory reclamation scheme.

• 出版日期2015-10