實(shí)現(xiàn)無鎖的棧與隊(duì)列(5)：Hazard Pointer
兩年多以前隨手寫了點(diǎn)與 lock free 相關(guān)的筆記：1,2,3,4，質(zhì)量都不是很高其實(shí)(讀者見諒)，但兩年來陸陸續(xù)續(xù)竟也有些閱讀量了(可見劍走偏鋒的技巧是多容易吸引眼球)。筆記當(dāng)中在解決內(nèi)存釋放和 ABA 問題時(shí)提到了 Hazard Pointer 這個(gè)東西，有兩三個(gè)讀者來信問這是什么，讓詳細(xì)講一下，我想了想，反正以前在看這東西的時(shí)候也記了些東西，干脆整理一下發(fā)出來。
前面寫的那幾篇筆記都來源于 Maged Michael 的學(xué)術(shù)論文，Hazard pointer 也是他的創(chuàng)想，academic paper 的特點(diǎn)之一就是經(jīng)常有些美好的假設(shè)，關(guān)于 hazard pointer 也同樣如此，以下的討論均假設(shè)內(nèi)存模型是 sequential consistent 的，否則還是問題多多。
核心問題
Hazard Pointer(以下簡(jiǎn)稱為 HP) 要解決的核心問題是怎樣安全地釋放內(nèi)存，該問題的解決在實(shí)現(xiàn)無鎖算法時(shí)有兩個(gè)關(guān)鍵的影響：
- 保證了關(guān)鍵節(jié)點(diǎn)的訪問是合法的，不會(huì)導(dǎo)致程序嘗試去讀取已經(jīng)釋放了的內(nèi)存。
- 保證了 ABA 問題不會(huì)出現(xiàn)，程序邏輯正確的前提。
這兩個(gè)問題在寫無鎖代碼時(shí)基本是無法避免的，走這條路終會(huì)遇上，多少人因此費(fèi)盡心力窮盡技巧各種花樣，只為把這問題徹底解決。HP 就是這眾多花樣各種技巧中的一種，它的做法以我的愚見也不是很完美，但實(shí)現(xiàn)上比較簡(jiǎn)單，不依賴具體系統(tǒng)，也不對(duì)硬件有特殊要求(當(dāng)然 CAS 操作還是要的)，從效果上看也湊和，因此無論怎樣是值得參考學(xué)習(xí)的。
具體實(shí)現(xiàn)
在無鎖算法中釋放內(nèi)存之所以難，主要原因在于，當(dāng)一個(gè)線程準(zhǔn)備釋放一塊內(nèi)存時(shí)，它無法知道是否另有別的線程也同時(shí)持有該塊內(nèi)存的指針并需要訪問，因此解決這個(gè)難點(diǎn)的一個(gè)直接想法就是，在每個(gè)線程獲取了一個(gè)關(guān)鍵內(nèi)存的指針后，該線程將設(shè)置一個(gè)標(biāo)志，表明"我正在操作這個(gè)關(guān)鍵數(shù)據(jù)，你們誰都別給我隨便就釋放了"。當(dāng)然，這個(gè)標(biāo)志需要放在一個(gè)公共區(qū)域，使得任何線程都可以去讀。當(dāng)另一個(gè)線程想要釋放一塊內(nèi)存時(shí)，它就去把每個(gè)線程的標(biāo)志都看一下，看看是否有別的線程也在操作這塊內(nèi)存，從而決定是否馬上釋放該內(nèi)存：如果有別的線程在操作該內(nèi)存，則暫時(shí)不釋放，等下次。具體實(shí)現(xiàn)如下：
- 建立一個(gè)全局?jǐn)?shù)組 HP hp[N]，數(shù)組中的元素為指針，稱為 Hazard pointer，數(shù)組的大小為線程的數(shù)目，即每個(gè)線程擁有一個(gè) HP。
- 約定每個(gè)線程只能修改自己的 HP，而不允許修改別的線程的 HP，但可以去讀別的線程的 HP 值。
- 當(dāng)線程嘗試去訪問一個(gè)關(guān)鍵數(shù)據(jù)節(jié)點(diǎn)時(shí)，它得先把該節(jié)點(diǎn)的指針賦給自己的 HP，即告訴別人不要釋放這個(gè)節(jié)點(diǎn)。
- 每個(gè)線程維護(hù)一個(gè)私有鏈表(free list)，當(dāng)該線程準(zhǔn)備釋放一個(gè)節(jié)點(diǎn)時(shí)，把該節(jié)點(diǎn)放入自己的鏈表中，當(dāng)鏈表數(shù)目達(dá)到一個(gè)設(shè)定數(shù)目 R 后，遍歷該鏈表把能釋放的節(jié)點(diǎn)通通釋放。
- 當(dāng)一個(gè)線程要釋放某個(gè)節(jié)點(diǎn)時(shí)，它需要檢查全局的 HP 數(shù)組，確定如果沒有任何一個(gè)線程的 HP 值與當(dāng)前節(jié)點(diǎn)的指針相同，則釋放之，否則不釋放，仍舊把該節(jié)點(diǎn)放回自己的鏈表中。
HP 算法主要用在實(shí)現(xiàn)無鎖的隊(duì)列上，因此前面的具體步驟其實(shí)基于以下幾個(gè)假設(shè)：
- 隊(duì)列上的元素任何時(shí)候，只可能被其中一個(gè)線程成功地從隊(duì)列上取下來，因此每個(gè)線程的 free list 中的元素肯定是唯一的。
- 線程在操作無鎖隊(duì)列時(shí)，任何時(shí)候基本只需要處理一個(gè)節(jié)點(diǎn)，因此每個(gè)線程只需要一個(gè) HP 就夠了，如果有特殊需求，當(dāng)然 HP 的數(shù)目也可以相應(yīng)擴(kuò)展。
- 對(duì)于某個(gè)節(jié)點(diǎn)來說，多個(gè)線程同時(shí)持有該節(jié)點(diǎn)的指針這個(gè)現(xiàn)象，在時(shí)間上是非常短暫有限的，只有當(dāng)這幾個(gè)線程同時(shí)嘗試去取下該節(jié)點(diǎn)，它們才可能同時(shí)持有該節(jié)點(diǎn)的指針，一旦某個(gè)線程成功地將節(jié)點(diǎn)取下，其它線程很快就會(huì)發(fā)現(xiàn)，并嘗試?yán)^續(xù)去操作下一下節(jié)點(diǎn)，而后續(xù)再來取節(jié)點(diǎn)的線程則不再可能獲得已經(jīng)不在無瑣隊(duì)列上的節(jié)點(diǎn)的指針，因此：當(dāng)某個(gè)線程嘗試去檢查其它線程的 HP 時(shí)，它只需要將 HP 數(shù)組遍歷一遍就夠了，不用擔(dān)心各線程 HP 值的變化。
以下為我從論文里翻譯過來的偽代碼，入隊(duì)列的函數(shù)不涉及刪除節(jié)點(diǎn)因此不會(huì)操作 HP，難點(diǎn)都在處理出隊(duì)列的函數(shù)上：
using hp_t = void*;
hp_t hp[N] = {0};
// 以下為隊(duì)列的頭指針。
node_t* top;
data_t* Pop()
{
node_t* t = null;
while (true)
{
t = top;
if (t == null) break;
// 設(shè)置當(dāng)前線程的 HP
hp[this_thread] = t;
// 以下這步是必須的，確認(rèn)了當(dāng)前 HP 在 t 被釋放前已經(jīng)被設(shè)置到當(dāng)前線程的 HP 中。
if (t != top) continue;
node_t* next = t->next;
if (CAS(&top, t, next)) break;
}
// 已經(jīng)不再持有任何節(jié)點(diǎn)，需將自己的 HP 設(shè)為空.
hp[this_thread] = null;
if (t == null) return null
data_t* data = t->data;
// 嘗試釋放節(jié)點(diǎn)
DeleteNode(t);
return data;
}
以上是出隊(duì)列的代碼，顯然，所做的事情非常直白：線程拿到一個(gè)節(jié)點(diǎn)后將數(shù)據(jù)取出，并嘗試釋放節(jié)點(diǎn)。釋放節(jié)點(diǎn)是另一個(gè)關(guān)鍵點(diǎn)，具體實(shí)現(xiàn)參看如下偽代碼：
thread_local vector<hp_t> free_list;
void DeleteNode(node_t* t)
{
free_list.push_back(t);
if (free_list.size() > R) FreeNode();
}
void FreeNode()
{
vector<hp_t> hp_list;
hp_list.reserve(N);
// 獲取所有線程的 HP，如非空則保存到 hp_list 中。
for (int i = 0; i < N; ++i)
{
if (hp[i] == null) continue;
hp_list.push_back(hp[i]);
}
std::sort(hp_list);
vector<hp_t> not_free;
not_free.reserve(free_list.size());
// 把當(dāng)前線程的 free_list 遍歷遂一進(jìn)行釋放。
for (int i = 0;i < free_list.size(); ++i)
{
if (std::binary_search(hp_list.begin(), hp_list.end(), free_list[i]))
{
// 某個(gè)線程持有當(dāng)前節(jié)點(diǎn)，故不能刪除，還是保留在隊(duì)列里。
not_free.push_back(free_list[i]);
continue;
}
// 確認(rèn)沒有任何線程持有該節(jié)點(diǎn)，刪除之。
delete free_list[i];
}
free_list.swap(not_free);
}
存在的問題
看到這里相信讀者對(duì) Hazard Pointer 的原理已經(jīng)大概了解了，那么我們來簡(jiǎn)單總結(jié)一下上面的實(shí)現(xiàn)。
首先是效率問題，它夠快嗎？根據(jù)前面的偽代碼，顯然影響效率的關(guān)鍵點(diǎn)在FreeNode()這個(gè)函數(shù)上，該函數(shù)有一個(gè)雙重循環(huán)，但還好第二重循環(huán)用了二分查找，因此刪除 R 個(gè)節(jié)點(diǎn)總的時(shí)間效率理論上是 O(R*logN)，R 可以設(shè)置， N 是線程數(shù)目，通常也不會(huì)太大，因此均攤下來應(yīng)該還好？我只能說不知道，看使用場(chǎng)景吧，用無瑣一般有很高的效率需求，這里加個(gè)這樣復(fù)雜度的處理是否會(huì)比加瑣更快呢？也說不準(zhǔn)，實(shí)現(xiàn)上復(fù)雜了是肯定的，想用的話得好好測(cè)試測(cè)試看看劃不劃得來。
其次是易用性，HP 釋放節(jié)點(diǎn)是累進(jìn)制的，只有當(dāng)一個(gè)線程積累到了一定數(shù)量的節(jié)點(diǎn)才批量進(jìn)行釋放，而生產(chǎn)環(huán)境里通常情況復(fù)雜，會(huì)不會(huì)某個(gè)線程積累了幾個(gè)節(jié)點(diǎn)后，就不再去隊(duì)列里 pop 數(shù)據(jù)了呢？豈不是總有些節(jié)點(diǎn)不能釋放？心里有些疙瘩。。除此，現(xiàn)代操作系統(tǒng)里線程創(chuàng)建銷毀其實(shí)很頻繁，某個(gè)線程如果要退出了，還得記得把自己頭上的節(jié)點(diǎn)釋放一下，也是件麻煩事。有人可能會(huì)覺得為什么刪除節(jié)點(diǎn)時(shí)要把節(jié)點(diǎn)放到隊(duì)列里再刪？多此一舉！直接遍歷 HP 數(shù)組直到?jīng)]有線程持有該節(jié)點(diǎn)不就好了 --- 放到隊(duì)列里其實(shí)是為效率，否則每 pop 一次就遍歷一遍 HP list，而且搞不好還要反復(fù)等待某個(gè)線程釋放節(jié)點(diǎn)，均攤下來效率太低。
最后，還有一個(gè)問題，相信讀者忍了很久了，HP 數(shù)組那里，各個(gè)線程怎么 index 進(jìn)去取出自己的 HP 呢？ thread id 嗎？那這個(gè)數(shù)組不得很大很大很大？
一點(diǎn)改進(jìn)
關(guān)于 HP 數(shù)組的實(shí)現(xiàn)上，作者其實(shí)也看到了問題，提出可以用 list 來管理 HP，因?yàn)椴皇敲總€(gè)線程都必須固定分配一個(gè) HP，事實(shí)上只有當(dāng)該線程正在進(jìn)行 pop 操作的時(shí)候它才需要，pop 完了馬上就可以把 HP 還回去了，因此數(shù)組可以用鏈表來替換，當(dāng)然這個(gè)鏈表也得是 Lock free 的，但這個(gè)鏈表可以不用考慮回收和釋放實(shí)現(xiàn)上容易多了，和我在本系列文章的第四篇里提到的思路是一致的。
但這樣用 List 來代替數(shù)組在一定程度也增加了效率負(fù)擔(dān)，因?yàn)槊總€(gè)線程取出 HP 變得更慢了(首先是很容易引起多個(gè)線程沖突，其次用到了 CAS 以及函數(shù)調(diào)用的開銷)，當(dāng)然具體有多少效率損失還得看使用場(chǎng)景，需要好好測(cè)量一下---寫無瑣代碼不能少做的事情。
無瑣編程很難，但這并不代表它們因此只能是理論游戲，Maged Michael 的無瑣系列文章啟發(fā)了很多人，這其中也包括 c++ 里的大腕 Andrei Alexandrescu，吶吶，看這里。
浙公網(wǎng)安備 33010602011771號(hào)