imported>Oceanicscope2 at 03:04, 23 June 2025

2025-06-23T03:04:37Z

← Previous revision		Revision as of 03:04, 23 June 2025
Line 27:		Line 27:
	*[[Hazard (computer architecture)]]		*[[Hazard (computer architecture)]]
	*[[Finalizer]]		*[[Finalizer]]
			*[[C++26]] - Adds <code><hazard_pointer></code> to [[C++ Standard Library]]

	==References==		==References==

imported>Frap at 18:15, 31 October 2024

2024-10-31T18:15:16Z

New page

{{Short description|Programming concept}}
{{too technical|date=January 2014}}
In a [[Thread (computer science)|multithreaded]] [[computer science|computing]] environment, '''hazard pointers''' are one approach to solving the problems posed by [[dynamic memory management]] of the nodes in a [[non-blocking algorithm|lock-free]] [[data structure]]. These problems generally arise only in environments that don't have [[automatic garbage collection]].<ref name="Williams12">Anthony Williams. ''C++ Concurrency in Action: Practical Multithreading.'' Manning:Shelter Island, 2012. See particularly Chapter 7.2, "Examples of lock-free data structures".</ref>

Any lock-free data structure that uses the [[compare-and-swap]] primitive must deal with the [[ABA problem]]. 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 <syntaxhighlight lang="c" inline>
compare_and_swap(target=&head, newvalue=B, expected=A)</syntaxhighlight>. 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
<syntaxhighlight lang="c">
Node* currentNode = this->head; // assume the load from "this->head" is atomic
Node* nextNode = currentNode->next; // assume this load is also atomic
</syntaxhighlight>
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 <code>this->head</code> and deallocate it, meaning that the memory access through <code>currentNode</code> 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 (computer science)|thread]] keeps a [[List (computing)|list]] of hazard pointers indicating which nodes the thread is currently accessing. (In many systems this "list" may be probably limited to only one<ref name="Williams12"/><ref name="Alexandrescu04">{{Cite news| author=Andrei Alexandrescu and Maged Michael | title=Lock-Free Data Structures with Hazard Pointers | url=http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890 | journal=Dr. Dobb's | year=2004}} (C++ oriented article)</ref> or two elements.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread.

{{quote|1=Each reader thread owns a single-writer/multi-reader shared pointer called "hazard pointer." When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), "I am reading this map. You can replace it if you want, but don't change its contents and certainly keep your <code>delete</code>ing hands off it."|2=[[Andrei Alexandrescu]] and Maged Michael|3=Lock-Free Data Structures with Hazard Pointers<ref name="Alexandrescu04"/>}}

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,<ref name="USPTO">{{patent|US|20040107227|application|Maged M. Michael, "Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation." Filed on 3 December 2002.}}</ref> but the application was abandoned in 2010.

Alternatives to hazard pointers include [[reference counting]].<ref name="Williams12"/>

==See also==
*[[Concurrent data structure]]
*[[Hazard (computer architecture)]]
*[[Finalizer]]

==References==
<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==
*[http://amino-cbbs.sourceforge.net/ Concurrent Building Blocks] - C++ implementation of Hazard Pointer (called "SMR") and other lock-free data structures. Also has Java interfaces.
*[http://concurrencykit.org/ Concurrency Kit] {{Webarchive|url=https://web.archive.org/web/20140601032152/http://concurrencykit.org/ |date=2014-06-01 }} - C implementation of Hazard Pointer and lock-free data structures
*[http://atomic-ptr-plus.sourceforge.net/ Atomic Ptr Plus] - C/C++ library that has a Hazard Pointer implementation
*[http://www.johantorp.com/ The parallelism shift and C++'s memory model] - Contains C++ implementation for Windows in appendices
*[http://libcds.sourceforge.net/ libcds] - C++ library of lock-free containers and Hazard Pointer implementation

[[Category:Programming constructs]]

Hazard pointer - Revision history

imported>Oceanicscope2 at 03:04, 23 June 2025

imported>Frap at 18:15, 31 October 2024