Brief Announcement
Authors:
Open Access
- 24 July 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 367-369
Abstract
For non-blocking data-structures, only memory reclamation with pointer-based techniques can maintain non-blocking progress, but there can be high overhead associated to these techniques, with the most notable example being Hazard Pointers. We present a new algorithm we named Hazard Eras, which allows for efficient lock-free or wait-free memory reclamation in concurrent data structures and can be used as drop-in replacement to Hazard Pointers. Results from our microbenchmark show that when applied to a lock-free linked list, Hazard Eras will match the throughput of Hazard Pointers in the worst-case, and can outperform Hazard Pointers by a factor of 5x. Hazard Eras provides the same progress conditions as Hazard Pointers and can equally be implemented with the C11/C++11 memory model and atomics, making it portable across multiple systems.Keywords
This publication has 17 references indexed in Scilit:
- Fast non-intrusive memory reclamation for highly-concurrent data structures2016
- Can parallel data structures rely on automatic memory managers?2012
- Performance of memory reclamation for lockless synchronizationJournal of Parallel and Distributed Computing, 2007
- Stopless2007
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- High performance dynamic lock-free hash tables and list-based sets2002
- A Pragmatic Implementation of Non-blocking Linked-lists2001
- Sapphire2001
- Lock-free linked lists using compare-and-swap1995
- Lock-free garbage collection for multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1992