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

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

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

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

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

• 等待無線程對數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問時，刪除所有等待刪除的對象。

• 使用風(fēng)險指針來標(biāo)識正在被線程訪問的對象。

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

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

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

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

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

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

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

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

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

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