In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have automatic garbage collection. 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 — Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Hazard pointer (en)
- 冒险指针 (zh)
|
| rdfs:comment
| - In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have automatic garbage collection. 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 — Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers (en)
- 在多线程环境中， 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法。 这些问题通常仅在没有自动垃圾收集的环境中出现。 使用比较和交换原语的任何无锁数据结构都必须处理ABA问题。 例如，在使用链表实现的无锁堆栈中，一个线程可能正在尝试从堆栈的前面弹出项目（A→B→C）。 它会记住自栈顶而下的第二个值“B”，然后执行 <span class="n">compare_and_swap</span><span class="p">(</span><span class="n">target</span><span class="o">=&</span><span class="n">head</span><span class="p">,</span><span class="w"> </span><span class="n">newvalue</span><span class="o">=</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">expected</span><span class="o">=</span><span class="n">A</span><span class="p">)</span><span class="w"></span> 不幸的是，在此操作正在执行时，另一个线程可能执行了两次弹出操作，然后将A推回顶部，从而导致堆栈（A→C）。 比较并交换成功将“ head”与“ B”交换，结果是堆栈现在包含垃圾数据（指向已经被释放的元素“ B”的指针）。 (zh)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have automatic garbage collection. 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 <span class="n">compare_and_swap</span><span class="p">(</span><span class="n">target</span><span class="o">=&</span><span class="n">head</span><span class="p">,</span><span class="w"> </span><span class="n">newvalue</span><span class="o">=</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">expected</span><span class="o">=</span><span class="n">A</span><span class="p">)</span><span class="w"></span>. 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 of hazard pointers indicating which nodes the thread is currently accessing. (In many systems this "list" may be probably limited to only one or two elements.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread. 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 deleteing hands off it." — Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers 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, 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. (en)
- 在多线程环境中， 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法。 这些问题通常仅在没有自动垃圾收集的环境中出现。 使用比较和交换原语的任何无锁数据结构都必须处理ABA问题。 例如，在使用链表实现的无锁堆栈中，一个线程可能正在尝试从堆栈的前面弹出项目（A→B→C）。 它会记住自栈顶而下的第二个值“B”，然后执行 <span class="n">compare_and_swap</span><span class="p">(</span><span class="n">target</span><span class="o">=&</span><span class="n">head</span><span class="p">,</span><span class="w"> </span><span class="n">newvalue</span><span class="o">=</span><span class="n">B</span><span class="p">,</span><span class="w"> </span><span class="n">expected</span><span class="o">=</span><span class="n">A</span><span class="p">)</span><span class="w"></span> 不幸的是，在此操作正在执行时，另一个线程可能执行了两次弹出操作，然后将A推回顶部，从而导致堆栈（A→C）。 比较并交换成功将“ head”与“ B”交换，结果是堆栈现在包含垃圾数据（指向已经被释放的元素“ B”的指针）。 此外，任何包含以下形式代码的无锁算法 Node* currentNode = this->head; // assume the load from "this->head" is atomic Node* nextNode = currentNode->next; // assume this load is also atomic 在没有自动垃圾收集的情况下，它还面临另一个主要问题。 在这两行之间，另一个线程可能会弹出this->head指向的节点并对其进行内存分配，这意味着通过第二行上的currentNode进行的内存访问读取了已释放的内存（实际上可能已经被另外一部分程序用在了不同的地方）。 冒险指针可用于同时解决这两个问题。 在使用冒险指针的系统中，每个线程都保留一个冒险指针的列表 ，这些指针指示该线程当前正在访问的节点。 （在许多系统中，此“列表”可能只限于一个 或两个元素。 ）冒险指针列表上的节点不得被任何其他线程修改或释放。 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 deleteing hands off it." ——Andrei Alexandrescu and Maged Michael，Lock-Free Data Structures with Hazard Pointers 当线程希望删除一个节点时，它将其放置在“稍后释放”的节点列表上，但实际上直到其他线程的危险列表中没有包含指针时才真正释放该节点的内存。 可以通过专用的垃圾回收线程来完成此手动垃圾回收（如果所有线程共享“稍后释放”的列表）；或者，可以由每个工作线程自行清除“待释放”列表，作为诸如“ pop”之类的操作的一部分（在这种情况下，每个工作线程可以负责其自己的“待释放”列表）。 在2002年， IBM的 Maged Michael提出了关于冒险指针技术的美国专利申请， 但该申请在2010年被放弃。 冒险指针的替代方法包括引用计数 。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)