In a multithreaded

computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...

environment, hazard pointers are one approach to solving the problems posed by

dynamic memory management Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when ...

of the nodes in a

lock-free In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

. These problems generally arise only in environments that don't have

automatic garbage collection In computer science, garbage collection (GC) is a form of automatic memory management. The ''garbage collector'' attempts to reclaim memory which was allocated by the program, but is no longer referenced; such memory is called '' garbage''. ...

.Anthony Williams. ''C++ Concurrency in Action: Practical Multithreading.'' Manning:Shelter Island, 2012. See particularly Chapter 7.2, "Examples of lock-free data structures". Any lock-free data structure that uses the

compare-and-swap In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...

primitive must deal with the

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". However, another thread can execute be ...

. For example, in a lock-free stack represented as an intrusively linked list, one thread may be attempting to pop an item from the front of the stack (A → B → C). It remembers the second-from-top value "B", and then performs compare_and_swap(target=&head, newvalue=B, expected=A). Unfortunately, in the middle of this operation, another thread may have done two pops and then pushed A back on top, resulting in the stack (A → C). The compare-and-swap succeeds in swapping `head` with `B`, and the result is that the stack now contains garbage (a pointer to the freed element "B"). Furthermore, any lock-free algorithm containing code of the form Node* currentNode = this->head; // assume the load from "this->head" is atomic Node* nextNode = currentNode->next; // assume this load is also atomic suffers from another major problem, in the absence of automatic garbage collection. In between those two lines, it is possible that another thread may pop the node pointed to by this->head and deallocate it, meaning that the memory access through currentNode on the second line reads deallocated memory (which may in fact already be in use by some other thread for a completely different purpose). Hazard pointers can be used to address both of these problems. In a hazard-pointer system, each thread keeps a

list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby union ...

of hazard pointers indicating which nodes the thread is currently accessing. (In many systems this "list" may be probably limited to only one (C++ oriented article) or two elements.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread. When a thread wishes to remove a node, it places it on a list of nodes "to be freed later", but does not actually deallocate the node's memory until no other thread's hazard list contains the pointer. This manual garbage collection can be done by a dedicated garbage-collection thread (if the list "to be freed later" is shared by all the threads); alternatively, cleaning up the "to be freed" list can be done by each worker thread as part of an operation such as "pop" (in which case each worker thread can be responsible for its own "to be freed" list). In 2002, Maged Michael of IBM filed an application for a U.S. patent on the hazard pointer technique, but the application was abandoned in 2010. Alternatives to hazard pointers include reference counting.

References

*{{cite journal , author=Maged Michael , title=Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects , journal=IEEE Transactions on Parallel and Distributed Systems , volume=15 , issue=8 , year=2004 , pages=491–504 , url=http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf , doi=10.1109/TPDS.2004.8, citeseerx=10.1.1.130.8984 , s2cid=8373852 , archive-url=https://web.archive.org/web/20171104135736/http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf , archive-date=2017-11-04

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 Programming constructs

See also

References

External links