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