Every Data Structure Deserves Lock-Free Memory Reclamation
Author:
- Nachshon CohenNCNachshon Cohen
Preprint
Abstract
Memory-management support for lock-free data structures is well known to be a tough problem. Recent work has successfully reduced the overhead of such schemes. However, applying memory-management support to a data structure remains complex and, in many cases, requires redesigning the data structure. In this paper, we present the first lock-free memory-management scheme that is applicable to general (arbitrary) lock-free data structures and that can be applied automatically via a compiler plug-in. In addition to the simplicity of incorporating to data structures, this scheme provides low overhead and does not rely on the lock freedom of any OS services.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- CBPQ: High Performance Lock-Free Priority Queue2016
- Wait-free linked-lists2012
- A methodology for creating fast wait-free data structures2012
- A highly-efficient wait-free universal construction2011
- Wait-free queues with multiple enqueuers and dequeuers2011
- A study of concurrent real-time garbage collectorsACM SIGPLAN Notices, 2008
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- 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