Applying Hazard Pointers to More Concurrent Data Structures
Open Access
- 17 June 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 213-226
Abstract
Hazard pointers is a popular semi-manual memory reclamation scheme for concurrent data structures, where each accessing thread announces protection of each object to access and validates that the pointer is not already freed. Validation is typically done by over-approximating unreachability: if an object seems to be unreachable from the root of the data structure, the protecting thread decides not to access the object as it might have been freed. However, many efficient data structures are incompatible with validation by over-approximation as their optimistic traversal strategy intentionally ignores the warning of unreachability to achieve better performance. We design HP++, an extension to hazard pointers that supports optimistic traversal. The key idea is under-approximating unreachability during validation and patching up the potentially unsafe accesses arising from false-negatives. Thanks to optimistic traversal, data structures with HP++ outperform the same-purpose data structures with HP under contention, while consuming a similar amount of memory.Keywords
Funding Information
- Samsung Research Funding & Incubation Center of Samsung Electronics (SRFC-IT2201-06)
This publication has 38 references indexed in Scilit:
- Efficient Memory Management for Lock-Free Data Structures with Optimistic Access2015
- Asynchronized Concurrency2015
- A Fast Lock-Free Internal Binary Search Tree2015
- Fast concurrent lock-free binary search trees2014
- Scalable address spaces using RCU balanced trees2012
- 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
- High performance dynamic lock-free hash tables and list-based sets2002
- Safe memory reclamation for dynamic lock-free objects using atomic reads and writes2002
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990