冒險指針
在多線程環境中， 冒險指針是一種解決由無鎖 數據結構中的節點動態內存管理引起的問題的方法。 這些問題通常僅在沒有自動垃圾收集的環境中出現。 [1]
使用比較和交換原語的任何無鎖數據結構都必須處理ABA問題。 例如，在使用鍊表實現的無鎖堆疊中，一個線程可能正在嘗試從堆疊的前面彈出項目（A→B→C）。 它會記住自棧頂而下的第二個值「B」，然後執行 compare_and_swap(target=&head, newvalue=B, expected=A) 不幸的是，在此操作正在執行時，另一個線程可能執行了兩次彈出操作，然後將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進行的內存訪問讀取了已釋放的內存（實際上可能已經被另外一部分程序用在了不同的地方）。
冒險指針可用於同時解決這兩個問題。 在使用冒險指針的系統中，每個線程都保留一個冒險指針的列表 ，這些指針指示該線程當前正在訪問的節點。 （在許多系統中，此「列表」可能只限於一個[1] [2]或兩個元素。 ）冒險指針列表上的節點不得被任何其他線程修改或釋放。
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[2]
當線程希望刪除一個節點時，它將其放置在「稍後釋放」的節點列表上，但實際上直到其他線程的危險列表中沒有包含指針時才真正釋放該節點的內存。 可以通過專用的垃圾回收線程來完成此手動垃圾回收（如果所有線程共享「稍後釋放」的列表）；或者，可以由每個工作線程自行清除「待釋放」列表，作為諸如「 pop」之類的操作的一部分（在這種情況下，每個工作線程可以負責其自己的「待釋放」列表）。
在2002年， IBM的 Maged Michael提出了關於冒險指針技術的美國專利申請， [3]但該申請在2010年被放棄。
參見
[編輯]- 並發數據結構
- 冒險(計算機體系結構)
參考文獻
[編輯]- ^ 1.0 1.1 1.2 Anthony Williams. C++ Concurrency in Action: Practical Multithreading. Manning:Shelter Island, 2012. See particularly Chapter 7.2, "Examples of lock-free data structures".
- ^ 2.0 2.1 Andrei Alexandrescu and Maged Michael. Lock-Free Data Structures with Hazard Pointers. Dr. Dobb's. 2004 [2020-01-17]. （原始內容存檔於2019-07-19）.
- ^ US application 20040107227 Maged M. Michael, "Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation." Filed on 3 December 2002.
- Maged Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (PDF). IEEE Transactions on Parallel and Distributed Systems. 2004, 15 (8): 491–504 [2020-01-17]. Bibcode:10.1.1.130.8984 請檢查
|bibcode=值 (幫助). doi:10.1109/TPDS.2004.8. （原始內容存檔 (PDF)於2017-05-06）.