接上篇使用RCU技術實現(xiàn)讀寫線程無鎖，在沒有GC機制的語言中，要實現(xiàn)Lock free的算法，就免不了要自己處理內存回收的問題。
Hazard Pointer是另一種處理這個問題的算法，而且相比起來不但簡單，功能也很強大。鎖無關的數(shù)據(jù)結構與Hazard指針中講得很好，Wikipedia Hazard pointer也描述得比較清楚，所以我這里就不講那么細了。
一個簡單的實現(xiàn)可以參考我的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：一個讀線程要使用一個指針時，就會創(chuàng)建一個Hazard pointer包裝這個指針。一個Hazard pointer會被一個線程寫，多個線程讀。
struct HazardPointer {
void *real_ptr; // 包裝的指針
... // 不同的實現(xiàn)有不同的成員
};
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的具體實現(xiàn)，這就是Hazard Pointer的管理問題。
《鎖無關的數(shù)據(jù)結構與Hazard指針》文中創(chuàng)建了一個Lock free的鏈表來表示這個全局的Hazard Pointer List。每個Hazard Pointer有一個成員標識其是否可用。這個List中也就保存了已經被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合，當所有Hazard Pointer都被使用時，就會新分配一個加進這個List。當讀線程不使用指針時，需要歸還Hazard Pointer，直接設置可用成員標識即可。要gc()時，就直接遍歷這個List。
要實現(xiàn)一個Lock free的鏈表，并且僅需要實現(xiàn)頭插入，還是非常簡單的。本身Hazard Pointer標識某個指針時，都是用了后立即標識，所以這個實現(xiàn)直接支持了動態(tài)線程，支持線程的掛起等。
在nbds項目中也有一個Hazard Pointer的實現(xiàn)，相對要弱一點。它為每個線程都設置了自己的Hazard Pointer池，寫線程要釋放指針時，就訪問所有其他線程的Hazard Pointer池。
typedef struct haz_local {
// Free List
pending_t *pending; // to be freed
int pending_size;
int pending_count;
// Hazard Pointer 池，動態(tài)和靜態(tài)兩種
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技術實現(xiàn)讀寫線程無鎖中的一樣。這個實現(xiàn)為了支持線程動態(tài)創(chuàng)建，就需要一套線程ID的重用機制，相對復雜多了。
附錄
最后，附上一些并行編程中的一些概念。
Lock Free & Wait Free
常常看到Lock Free和Wait Free的概念，這些概念用于衡量一個系統(tǒng)或者說一段代碼的并行級別，并行級別可參考并行編程——并發(fā)級別。總之Wait Free是一個比Lock Free更牛逼的級別。
我自己的理解，例如《鎖無關的數(shù)據(jù)結構與Hazard指針》中實現(xiàn)的Hazard Pointer鏈表就可以說是Lock Free的，注意它在插入新元素到鏈表頭時，因為使用CAS，總免不了一個busy loop，有這個特征的情況下就算是Lock Free，雖然沒鎖，但某個線程的執(zhí)行情況也受其他線程的影響。
相對而言，Wait Free則是每個線程的執(zhí)行都是獨立的，例如《鎖無關的數(shù)據(jù)結構與Hazard指針》中的Scan函數(shù)。“每個線程的執(zhí)行時間都不依賴于其它任何線程的行為”
鎖無關(Lock-Free)意味著系統(tǒng)中總存在某個線程能夠得以繼續(xù)執(zhí)行；而等待無關(Wait-Free)則是一個更強的條件，它意味著所有線程都能往下進行。
ABA問題
在實現(xiàn)Lock Free算法的過程中，總是要使用CAS原語的，而CAS就會帶來ABA問題。
在進行CAS操作的時候，因為在更改V之前，CAS主要詢問“V的值是否仍然為A”，所以在第一次讀取V之后以及對V執(zhí)行CAS操作之前，如果將值從A改為B，然后再改回A，會使基于CAS的算法混亂。在這種情況下，CAS操作會成功。這類問題稱為ABA問題。
Wiki Hazard Pointer提到了一個ABA問題的好例子：在一個Lock free的棧實現(xiàn)中，現(xiàn)在要出棧，棧里的元素是[A, B, C]，head指向棧頂，那么就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在這個操作中，其他線程把A B都出棧，且刪除了B，又把A壓入棧中，即[A, C]。那么前一個線程的compare_and_swap能夠成功，此時head指向了一個已經被刪除的B。stackoverflow上也有個例子 Real-world examples for ABA in multithreading
對于CAS產生的這個ABA問題，通常的解決方案是采用CAS的一個變種DCAS。DCAS，是對于每一個V增加一個引用的表示修改次數(shù)的標記符。對于每個V，如果引用修改了一次，這個計數(shù)器就加1。然后再這個變量需要update的時候，就同時檢查變量的值和計數(shù)器的值。
但也早有人提出DCAS也不是ABA problem 的銀彈。