Automatic memory reclamation for lock-free data structures
Authors:
Open Access
- 23 October 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 260-279
Abstract
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.Keywords
Funding Information
- Israel Science Foundation (274/14)
This publication has 25 references indexed in Scilit:
- Efficient Memory Management for Lock-Free Data Structures with Optimistic Access2015
- SchismACM SIGPLAN Notices, 2010
- A Better x86 Memory Model: x86-TSO2009
- Performance of memory reclamation for lockless synchronizationJournal of Parallel and Distributed Computing, 2007
- Nonblocking memory management support for dynamic-sized data structuresACM Transactions on Computer Systems, 2005
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- Lock-free reference countingDistributed Computing, 2002
- A Pragmatic Implementation of Non-blocking Linked-lists2001
- Lock-free garbage collection for multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1992
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991