1.簡介
- non-blocking算法：一個(gè)線程的失敗或者暫停不會導(dǎo)致其他線程的失敗或暫停。
如果保證system-wide progress，則non-blocking算法是lock-free；
如果保證per-thread progress，則是wait-free。
2.為什么要引入non-blocking算法
傳統(tǒng)的加鎖方法有什么問題？
傳統(tǒng)的多線程編程方法是使用鎖來同步對共享資源的訪問。程序員使用同步原語機(jī)制（mutexes, semaphores, cirtical sections）來確保線程不會同時(shí)執(zhí)行，以確保共享數(shù)據(jù)結(jié)構(gòu)不會被損壞。
然而，很多情況下阻塞線程并不是我們期望的。
1）阻塞的線程一直在執(zhí)行高優(yōu)先級或?qū)崟r(shí)任務(wù)
2）鎖之間的交錯(cuò)可能導(dǎo)致deadlock, livelock, priority inversion
3）粗粒度鎖（coarse-grained locking）和細(xì)粒度鎖（fine-grained locking）之間的權(quán)衡，前者顯著減少并行，后者增加鎖的開銷并且更容易出錯(cuò)。non-blocking有什么優(yōu)勢？
1）不受上面的缺點(diǎn)影響
2）在中斷處理程序中也是安全的（interrupt handlers），即使被搶占的線程無法恢復(fù)，進(jìn)度可能依舊能夠保持（progress）。
但是使用鎖就不可以，因?yàn)椋o法恢復(fù)的）被強(qiáng)占的線程可能是鎖的持有者。但是這種問題可以通過在臨界區(qū)關(guān)閉中斷請求來避免。
3）lock-free 數(shù)據(jù)結(jié)構(gòu)可以提高性能，該類型的共享數(shù)據(jù)結(jié)構(gòu)不用保持串行訪問，可以在多核處理器上有更好的性能。
3.實(shí)現(xiàn)
- 除少數(shù)情況外，non-blocking算法使用原子的read-modify-write原語，該原語硬件必須提供，最出名的便是CAS。
關(guān)于read-modify-write(參考wiki)：代表一類原子操作（包括test-and-set、fetch-and-add、compare-and-swap，LL/SC），這些操作同時(shí)讀寫一個(gè)內(nèi)存位置。這些操作能夠在多線程應(yīng)用中防止數(shù)據(jù)競爭。一般用來實(shí)現(xiàn)mutexes或者semaphores，也經(jīng)常用在non-blocking同步中。 - 臨界區(qū)基本上都是使用基于這些原語的標(biāo)準(zhǔn)接口實(shí)現(xiàn)的。（一般情況下，即使是用這些原語實(shí)現(xiàn)的臨界區(qū)也是會發(fā)生阻塞）。
- software transactional memory承諾提供寫高效non-blocking代碼的標(biāo)準(zhǔn)抽象。
關(guān)于STM（參考wiki）：是一種類似于數(shù)據(jù)庫事務(wù)的并發(fā)控制機(jī)制，用于在并發(fā)計(jì)算中對共享內(nèi)存訪問的控制。是基于鎖同步的一種替代方案。一個(gè)事務(wù)是指對共享內(nèi)存一些列的讀和寫邏輯上發(fā)生在一個(gè)瞬間，其中間的狀態(tài)對于其他事務(wù)是不可見的。 - stacks queues sets 及 hash tables的non-blocking版本，可以保證在程序之間以異步的方式交換數(shù)據(jù)。
Herb Sutter關(guān)于queue
Herb Sutter關(guān)于queue - 有些數(shù)據(jù)結(jié)構(gòu)不需要特殊的原子原語就可以實(shí)現(xiàn)non-blocking，包括：
1）a single-reader single-writer ring buffer FIFO
使用內(nèi)存屏障實(shí)現(xiàn)（memory barrier）
2）Read-copy-update with a single writer and any number of readers
讀者是wait-free；寫者是lock-free，直到需要回收內(nèi)存
關(guān)于Read-copy-update（參考wiki）：用在讀取性能很關(guān)鍵的地方，也是space-time tradeoff的一個(gè)例子，用更多的空間換取更好的性能。（更新后的reader能夠讀取到新值）對于被RCU保護(hù)的共享數(shù)據(jù)結(jié)構(gòu)，讀操作不需要獲得任何鎖就可以訪問，但寫操作在訪問它時(shí)首先拷貝一個(gè)副本，然后對副本進(jìn)行修改，最后在適當(dāng)?shù)臅r(shí)機(jī)把指向原來數(shù)據(jù)的指針重新指向新的被修改的數(shù)據(jù)。這個(gè)時(shí)機(jī)就是所有引用該數(shù)據(jù)的CPU都退出對共享數(shù)據(jù)的操作。Linux內(nèi)核中內(nèi)存管理大量的運(yùn)用到了RCU機(jī)制。為每個(gè)內(nèi)存對象增加了一個(gè)原子計(jì)數(shù)器用來繼續(xù)該對象當(dāng)前訪問數(shù)。當(dāng)沒有其他進(jìn)程在訪問該對象時(shí)（計(jì)數(shù)器為0），才允許回收該內(nèi)存。
3）Read-copy-update with multiple writers and any number of readers.
讀者是wait-free；寫者通常用一個(gè)lock來穿行，并且不是obstruction-free - 有一些庫使用了lock-free技巧
C++ libcds
liblfds
Concurrency Kit
4.并發(fā)的級別
4.1 wait-freedom 無等待并發(fā)（non-blocking）
- 是最強(qiáng)級別的演進(jìn)（progress）保證，并保證system-wide throughput with starvation-freedom.
Wait-freedom 指的是每一個(gè)線程都一直運(yùn)行下去而無須等待外部條件，整個(gè)流程中任何操作都能在一個(gè)有限的步驟內(nèi)完成，這是最高的并發(fā)級別，沒有任何阻塞。
對實(shí)時(shí)系統(tǒng)很關(guān)鍵。 - 可以簡單認(rèn)為能夠直接調(diào)用一個(gè)原子操作實(shí)現(xiàn)的算法或程序就屬于Wait-free，比如下面的 increment_reference_counter 函數(shù)就是wait-free的，它封裝了atomic_increment這個(gè)原子自增原語，多個(gè)線程可以同時(shí)調(diào)用這個(gè)函數(shù)對同一個(gè)內(nèi)存變量進(jìn)行自增，而無須任何阻塞（其實(shí)也是有阻塞的，是總線鎖級別）。
CAS類的調(diào)用就不是wait-free的，注意wait-free的原語都不能包含內(nèi)部循環(huán)，CAS原語使用時(shí)通常包含在“循環(huán)直到成功”的循環(huán)內(nèi)部。 - wait-free的最新實(shí)現(xiàn)
Kogan, Alex; Petrank, Erez (2011). *Wait-free queues with multiple enqueuers and dequeuers*. Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/1941553.1941585](https://doi.org/10.1145/1941553.1941585). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-0119-0](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-0119-0 "Special:BookSources/978-1-4503-0119-0").
Kogan, Alex; Petrank, Erez (2012). *A method for creating fast wait-free data structures*. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/2145816.2145835](https://doi.org/10.1145/2145816.2145835). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-1160-1](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-1160-1 "Special:BookSources/978-1-4503-1160-1").
Kogan, Alex; Petrank, Erez (2012). *A method for creating fast wait-free data structures*. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/2145816.2145835](https://doi.org/10.1145/2145816.2145835). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-1160-1](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-1160-1 "Special:BookSources/978-1-4503-1160-1").
4.2 lock-freedom 無鎖并發(fā)（non-blocking）
- 允許單個(gè)線程starve，但是保證system-wide throughput.
對于運(yùn)行足夠長時(shí)間的線程中，至少有一個(gè)線程能夠演進(jìn)（make progress），則是lock-free。
Lock-freedom 指的是整個(gè)系統(tǒng)作為一個(gè)整體一直運(yùn)行下去，系統(tǒng)內(nèi)部單個(gè)線程某段時(shí)間內(nèi)可能會饑餓，這是比wait-freedom弱的并發(fā)級別，但系統(tǒng)整體上看依然是沒有阻塞的。所有wait-free的算法顯然都滿足lock-free的要求。
Lock-free算法通?？梢酝ㄟ^同步原語 CAS實(shí)現(xiàn)。 - 當(dāng)一個(gè)線程被掛起時(shí)，lock-free算法可以保證其余線程仍然可以演進(jìn)。
因此，如果兩個(gè)線程競爭相同的mutex lock 或 spinlock時(shí)，算法不是lock-free，因?yàn)楂@得鎖的線程掛起時(shí)，另一個(gè)線程會阻塞。 - 一些無限的操作可以在某些處理器上可以有限步完成，則算法是lock-free。wait-free要求所有處理都在有限步完成，lock-free要求部分在有限步完成。
- 無鎖算法可以運(yùn)行在四個(gè)階段：
完成自己的操作；
assisting an obstructing 操作；
abort obstructing 操作；
等待。
assist, abort or wait的時(shí)機(jī)是由爭用管理器決定，可以進(jìn)行優(yōu)化以保證更好的吞吐量（throughput），或者高優(yōu)先級操作的低延時(shí)。
4.3 obstruction-freedom （non-blocking）
- 在任何時(shí)間點(diǎn)，一個(gè)單獨(dú)隔離的線程（所有obstrcting 線程都掛起了）在有限步驟能夠完成其操作，則是obstruction-free。
bstruction-free 是指在任何時(shí)間點(diǎn)，一個(gè)孤立運(yùn)行線程的每一個(gè)操作可以在有限步之內(nèi)結(jié)束。只要沒有競爭，線程就可以持續(xù)運(yùn)行，一旦共享數(shù)據(jù)被修改，Obstruction-free 要求中止已經(jīng)完成的部分操作，并進(jìn)行回滾，obstruction-free 是并發(fā)級別更低的非阻塞并發(fā)，該算法在不出現(xiàn)沖突性操作的情況下提供單線程式的執(zhí)行進(jìn)度保證，所有 Lock-Free 的算法都是 Obstruction-free 的。 - obstruction-freedom要求可以中止任何部分完成的操作并且能夠回滾已做的更改。
丟棄并發(fā)協(xié)助可以實(shí)現(xiàn)更簡單的算法，且更容易驗(yàn)證。
競爭管理器需要防止持續(xù)的live-locking。 - 一些obstruction-freedom算法在數(shù)據(jù)結(jié)構(gòu)中使用一對“一致性標(biāo)記”。
讀取數(shù)據(jù)結(jié)構(gòu)的進(jìn)行首先讀取一個(gè)一致性標(biāo)記，然后將相關(guān)的數(shù)據(jù)讀入一個(gè)內(nèi)部緩沖區(qū)；
然后讀取另一個(gè)標(biāo)記，并且比較這兩個(gè)標(biāo)記。
如果標(biāo)記相同，則數(shù)據(jù)是一致的；標(biāo)記可能不一致，因?yàn)楫?dāng)前的讀過程可能被另外一個(gè)更新該數(shù)據(jù)結(jié)構(gòu)的進(jìn)程中斷，這種情況下，該進(jìn)程丟棄掉內(nèi)部緩沖區(qū)的數(shù)據(jù)并重試。
