Applying Hazard Pointers to More Concurrent Data Structures
Jaehwang Jung, Janggun Lee, Jeonghyeon Kim, Jeehoon Kang
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.
Topics & Concepts
Computer sciencePointer (user interface)Data structureThread (computing)Tree traversalLinked listConcurrent data structureProgramming languageParallel computingDistributed computingArtificial intelligenceDistributed systems and fault toleranceSecurity and Verification in ComputingParallel Computing and Optimization Techniques