Hazard pointer

In a multithreaded computing environment, a hazard pointer is an element used by a method that allows the memory allocated to the nodes of lock-free dynamic shared objects to be reclaimed.

The typical problem with modifying dynamically allocated nodes is the ABA problem: other threads may modify nodes while you are working on them. In this solution, each thread keeps a list of hazard pointers indicating which nodes the thread is currently accessing. This list can only be written to by the owning thread but can be read by any thread. When a thread wishes to remove a node, it places it on a private list and periodically scans the lists of all other threads for pointers referencing that node. If no such pointers are found the memory occupied by the node can be safely freed.

Hazard pointer basically is a mechanism for a thread to declare to other threads it has to 'look-out' for them. Dr. Michael analyzed a large number of lock-free data structures and found all requires one or two hazard pointers per thread only.

References

• Maged Michael (2004). "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects". IEEE Transactions on Parallel and Distributed Systems 15 (8): 491–504. doi:10.1109/TPDS.2004.8. 
• Andrei Alexandrescu and Maged Michael (2004). "Lock-Free Data Structures with Hazard Pointers". Dr Dobbs.  (C++ oriented article).

External links

• Concurrent Building Blocks - C++ implementation of Hazard Pointer (called "SMR") and other lock-free data structures. Also has Java interfaces.
• Concurrency Kit - C implementation of Hazard Pointer and lock-free data structures
• Atomic Ptr Plus - C/C++ library that has a Hazard Pointer implementation
• The parallelism shift and C++'s memory model - Contains C++ implementation for Windows in appendices
• libcds - C++ library of lock-free containers and Hazard Pointer implementation