7.3 對(duì)于設(shè)計(jì)無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的指導(dǎo)建議

本章中的例子中，看到了一些復(fù)雜的代碼可讓無(wú)鎖結(jié)構(gòu)工作正常。如果要設(shè)計(jì)自己的數(shù)據(jù)結(jié)構(gòu)，一些指導(dǎo)建議可以幫助你找到設(shè)計(jì)重點(diǎn)。第6章中關(guān)于并發(fā)通用指導(dǎo)建議還適用，不過(guò)這里需要更多的建議。我從例子中抽取了幾個(gè)實(shí)用的指導(dǎo)建議，在你設(shè)計(jì)無(wú)鎖結(jié)構(gòu)數(shù)據(jù)的時(shí)候就可以直接引用。

7.3.1 指導(dǎo)建議：使用std::memory_order_seq_cst的原型

std::memory_order_seq_cst比起其他內(nèi)存序要簡(jiǎn)單的多，因?yàn)樗胁僮鞫紝⑵渥鳛榭傂?。本章的所有例子，都是?code>std::memory_order_seq_cst開(kāi)始，只有當(dāng)基本操作正常工作的時(shí)候，才放寬內(nèi)存序的選擇。在這種情況下，使用其他內(nèi)存序就是進(jìn)行優(yōu)化(早起可以不用這樣做)。通常，當(dāng)你看整套代碼對(duì)數(shù)據(jù)結(jié)構(gòu)的操作后，才能決定是否要放寬該操作的內(nèi)存序選擇。所以，嘗試放寬選擇，可能會(huì)讓你輕松一些。在測(cè)試后的時(shí)候，工作的代碼可能會(huì)很復(fù)雜(不過(guò)，不能完全保證內(nèi)存序正確)。除非你有一個(gè)算法檢查器，可以系統(tǒng)的測(cè)試，線(xiàn)程能看到的所有可能性組合，這樣就能保證指定內(nèi)存序的正確性(這樣的測(cè)試的確存在)，僅是執(zhí)行實(shí)現(xiàn)代碼是遠(yuǎn)遠(yuǎn)不夠的。

7.3.2 指導(dǎo)建議：對(duì)無(wú)鎖內(nèi)存的回收策略

這里與無(wú)鎖代碼最大的區(qū)別就是內(nèi)存管理。當(dāng)有其他線(xiàn)程對(duì)節(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn)的時(shí)候，節(jié)點(diǎn)無(wú)法被任一線(xiàn)程刪除；為避免過(guò)多的內(nèi)存使用，還是希望這個(gè)節(jié)點(diǎn)在能刪除的時(shí)候盡快刪除。本章中介紹了三種技術(shù)來(lái)保證內(nèi)存可以被安全的回收：

• 等待無(wú)線(xiàn)程對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪(fǎng)問(wèn)時(shí)，刪除所有等待刪除的對(duì)象。

• 使用風(fēng)險(xiǎn)指針來(lái)標(biāo)識(shí)正在被線(xiàn)程訪(fǎng)問(wèn)的對(duì)象。

• 對(duì)對(duì)象進(jìn)行引用計(jì)數(shù)，當(dāng)沒(méi)有線(xiàn)程對(duì)對(duì)象進(jìn)行引用時(shí)，將其刪除。

在所有例子中，主要的想法都是使用一種方式去跟蹤指定對(duì)象上的線(xiàn)程訪(fǎng)問(wèn)數(shù)量，當(dāng)沒(méi)有現(xiàn)成對(duì)對(duì)象進(jìn)行引用的時(shí)候，將對(duì)象刪除。當(dāng)然，在無(wú)鎖數(shù)據(jù)結(jié)構(gòu)中，還有很多方式可以用來(lái)回收內(nèi)存。例如，理想情況下使用一個(gè)垃圾收集器。比起算法來(lái)說(shuō)，其實(shí)現(xiàn)更容易一些。只需要讓回收器知道，當(dāng)節(jié)點(diǎn)沒(méi)被引用的時(shí)候，回收節(jié)點(diǎn)，就可以了。

其他替代方案就是循環(huán)使用節(jié)點(diǎn)，只在數(shù)據(jù)結(jié)構(gòu)被銷(xiāo)毀的時(shí)候才將節(jié)點(diǎn)完全刪除。因?yàn)楣?jié)點(diǎn)能被復(fù)用，那么就不會(huì)有非法的內(nèi)存，所以這就能避免未定義行為的發(fā)生。這種方式的缺點(diǎn)：產(chǎn)生“ABA問(wèn)題”。

7.3.3 指導(dǎo)建議：小心ABA問(wèn)題

在“基于比較/交換”的算法中要格外小心“ABA問(wèn)題”。其流程是:

1. 線(xiàn)程1讀取原子變量x，并且發(fā)現(xiàn)其值是A。
2. 線(xiàn)程1對(duì)這個(gè)值進(jìn)行一些操作，比如，解引用(當(dāng)其是一個(gè)指針的時(shí)候)，或做查詢(xún)，或其他操作。
3. 操作系統(tǒng)將線(xiàn)程1掛起。
4. 其他線(xiàn)程對(duì)x執(zhí)行一些操作，并且將其值改為B。
5. 另一個(gè)線(xiàn)程對(duì)A相關(guān)的數(shù)據(jù)進(jìn)行修改(線(xiàn)程1持有)，讓其不再合法。可能會(huì)在釋放指針指向的內(nèi)存時(shí)，代碼產(chǎn)生劇烈的反應(yīng)(大問(wèn)題)；或者只是修改了相關(guān)值而已(小問(wèn)題)。
6. 再來(lái)一個(gè)線(xiàn)程將x的值改回為A。如果A是一個(gè)指針，那么其可能指向一個(gè)新的對(duì)象，只是與舊對(duì)象共享同一個(gè)地址而已。
7. 線(xiàn)程1繼續(xù)運(yùn)行，并且對(duì)x執(zhí)行“比較/交換”操作，將A進(jìn)行對(duì)比。這里，“比較/交換”成功(因?yàn)槠渲颠€是A)，不過(guò)這是一個(gè)錯(cuò)誤的A(the wrong A value)。從第2步中讀取的數(shù)據(jù)不再合法，但是線(xiàn)程1無(wú)法言明這個(gè)問(wèn)題，并且之后的操作將會(huì)損壞數(shù)據(jù)結(jié)構(gòu)。

本章提到的算法不存在這個(gè)問(wèn)題，不過(guò)在無(wú)鎖的算法中，這個(gè)問(wèn)題很常見(jiàn)。解決這個(gè)問(wèn)題的一般方法是，讓變量x中包含一個(gè)ABA計(jì)數(shù)器?！氨容^/交換”會(huì)對(duì)加入計(jì)數(shù)器的x進(jìn)行操作。每次的值都不一樣，計(jì)數(shù)隨之增長(zhǎng)，所以在x還是原值的前提下，即使有線(xiàn)程對(duì)x進(jìn)行修改，“比較/交換”還是會(huì)失敗。

“ABA問(wèn)題”在使用釋放鏈表和循環(huán)使用節(jié)點(diǎn)的算法中很是普遍，而將節(jié)點(diǎn)返回給分配器，則不會(huì)引起這個(gè)問(wèn)題。

7.3.4 指導(dǎo)建議：識(shí)別忙等待循環(huán)和幫助其他線(xiàn)程

在最終隊(duì)列的例子中，已經(jīng)見(jiàn)識(shí)到線(xiàn)程在執(zhí)行push操作時(shí)，必須等待另一個(gè)push操作流程的完成。等待線(xiàn)程就會(huì)被孤立，將會(huì)陷入到忙等待循環(huán)中，當(dāng)線(xiàn)程嘗試失敗的時(shí)候，會(huì)繼續(xù)循環(huán)，這樣就會(huì)浪費(fèi)CPU的計(jì)算周期。當(dāng)忙等待循環(huán)結(jié)束時(shí)，就像一個(gè)阻塞操作解除，和使用互斥鎖的行為一樣。通過(guò)對(duì)算法的修改，當(dāng)之前的線(xiàn)程還沒(méi)有完成操作前，讓等待線(xiàn)程執(zhí)行未完成的步驟，就能讓忙等待的線(xiàn)程不再被阻塞。在隊(duì)列例中，需要將一個(gè)數(shù)據(jù)成員轉(zhuǎn)換為一個(gè)原子變量，而不是使用非原子變量和使用“比較/交換”操作來(lái)做這件事；要是在更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中，這將需要更加多的變化來(lái)滿(mǎn)足需求。