857
並行編程中的內存回收Hazard Pointer
接上篇使用RCU技術實現讀寫線程無鎖，在沒有GC機製的語言中，要實現Lock free的算法，就免不了要自己處理內存回收的問題。
Hazard Pointer是另一種處理這個問題的算法，而且相比起來不但簡單，功能也很強大。鎖無關的數據結構與Hazard指針中講得很好，Wikipedia Hazard pointer也描述得比較清楚，所以我這裏就不講那麼細了。
一個簡單的實現可以參考我的github haz_ptr.c
原理
基本原理無非也是讀線程對指針進行標識，指針(指向的內存)要釋放時都會緩存起來延遲到確認沒有讀線程了才對其真正釋放。
<Lock-Free Data Structures with Hazard Pointers>中的描述：
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.”
關鍵的結構包括：Hazard pointer、Thread Free list
Hazard pointer：一個讀線程要使用一個指針時，就會創建一個Hazard pointer包裝這個指針。一個Hazard pointer會被一個線程寫，多個線程讀。
struct HazardPointer {
void *real_ptr; // 包裝的指針
... // 不同的實現有不同的成員
};
void func() {
HazardPointer *hp = accquire(_real_ptr);
... // use _real_ptr
release(hp);
}Thread Free List：每個線程都有一個這樣的列表，保存著將要釋放的指針列表，這個列表僅對應的線程讀寫
void defer_free(void *ptr) {
_free_list.push_back(ptr);
}當某個線程要嚐試釋放Free List中的指針時，例如指針ptr，就檢查所有其他線程使用的Hazard pointer，檢查是否存在包裝了ptr的Hazard pointer，如果沒有則說明沒有讀線程正在使用ptr，可以安全釋放ptr。
void gc() {
for(ptr in _free_list) {
conflict = false
for (hp in _all_hazard_pointers) {
if (hp->_real_ptr == ptr) {
confilict = true
break
}
}
if (!conflict)
delete ptr
}
}以上，其實就是Hazard Pointer的主要內容。
Hazard Pointer的管理
上麵的代碼中沒有提到_all_hazard_pointers及accquire的具體實現，這就是Hazard Pointer的管理問題。
《鎖無關的數據結構與Hazard指針》文中創建了一個Lock free的鏈表來表示這個全局的Hazard Pointer List。每個Hazard Pointer有一個成員標識其是否可用。這個List中也就保存了已經被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合，當所有Hazard Pointer都被使用時，就會新分配一個加進這個List。當讀線程不使用指針時，需要歸還Hazard Pointer，直接設置可用成員標識即可。要gc()時，就直接遍曆這個List。
要實現一個Lock free的鏈表，並且僅需要實現頭插入，還是非常簡單的。本身Hazard Pointer標識某個指針時，都是用了後立即標識，所以這個實現直接支持了動態線程，支持線程的掛起等。
在nbds項目中也有一個Hazard Pointer的實現，相對要弱一點。它為每個線程都設置了自己的Hazard Pointer池，寫線程要釋放指針時，就訪問所有其他線程的Hazard Pointer池。
typedef struct haz_local {
// Free List
pending_t *pending; // to be freed
int pending_size;
int pending_count;
// Hazard Pointer 池，動態和靜態兩種
haz_t static_haz[STATIC_HAZ_PER_THREAD];
haz_t **dynamic;
int dynamic_size;
int dynamic_count;
} __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;
static haz_local_t haz_local_[MAX_NUM_THREADS] = {};每個線程當然就涉及到haz_local_索引(ID)的分配，就像使用RCU技術實現讀寫線程無鎖中的一樣。這個實現為了支持線程動態創建，就需要一套線程ID的重用機製，相對複雜多了。
附錄
最後，附上一些並行編程中的一些概念。
Lock Free & Wait Free
常常看到Lock Free和Wait Free的概念，這些概念用於衡量一個係統或者說一段代碼的並行級別，並行級別可參考並行編程——並發級別。總之Wait Free是一個比Lock Free更牛逼的級別。
我自己的理解，例如《鎖無關的數據結構與Hazard指針》中實現的Hazard Pointer鏈表就可以說是Lock Free的，注意它在插入新元素到鏈表頭時，因為使用CAS，總免不了一個busy loop，有這個特征的情況下就算是Lock Free，雖然沒鎖，但某個線程的執行情況也受其他線程的影響。
相對而言，Wait Free則是每個線程的執行都是獨立的，例如《鎖無關的數據結構與Hazard指針》中的Scan函數。“每個線程的執行時間都不依賴於其它任何線程的行為”
鎖無關(Lock-Free)意味著係統中總存在某個線程能夠得以繼續執行；而等待無關(Wait-Free)則是一個更強的條件，它意味著所有線程都能往下進行。
ABA問題
在實現Lock Free算法的過程中，總是要使用CAS原語的，而CAS就會帶來ABA問題。
在進行CAS操作的時候，因為在更改V之前，CAS主要詢問“V的值是否仍然為A”，所以在第一次讀取V之後以及對V執行CAS操作之前，如果將值從A改為B，然後再改回A，會使基於CAS的算法混亂。在這種情況下，CAS操作會成功。這類問題稱為ABA問題。
Wiki Hazard Pointer提到了一個ABA問題的好例子：在一個Lock free的棧實現中，現在要出棧，棧裏的元素是[A, B, C]，head指向棧頂，那麼就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在這個操作中，其他線程把AB都出棧，且刪除了B，又把A壓入棧中，即[A, C]。那麼前一個線程的compare_and_swap能夠成功，此時head指向了一個已經被刪除的B。stackoverflow上也有個例子Real-world examples for ABA in multithreading
對於CAS產生的這個ABA問題，通常的解決方案是采用CAS的一個變種DCAS。DCAS，是對於每一個V增加一個引用的表示修改次數的標記符。對於每個V，如果引用修改了一次，這個計數器就加1。然後再這個變量需要update的時候，就同時檢查變量的值和計數器的值。
但也早有人提出DCAS也不是ABA problem 的銀彈。
原文地址： https://codemacro.com/2015/05/03/hazard-pointer/
written by Kevin Lynx posted athttps://codemacro.com
最後更新：2017-05-22 16:37:24