Hazard pointer
Encyclopedia
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.
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
computing
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
environment, a hazard pointer is an element used by a method that allows the memory allocated to the nodes
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
of lock-free
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
dynamic shared objects
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
to be reclaimed.
The typical problem with modifying dynamically allocated nodes is the ABA problem
ABA problem
In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed"...
: other threads may modify nodes while you are working on them. In this solution, each thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
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.
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