使用互斥量、條件變量，以及“期望”來同步阻塞數(shù)據(jù)的算法和數(shù)據(jù)結(jié)構(gòu)。應(yīng)用調(diào)用庫函數(shù)，將會(huì)掛起一個(gè)執(zhí)行線程，直到其他線程完成某個(gè)特定的動(dòng)作。庫函數(shù)將調(diào)用阻塞操作來對線程進(jìn)行阻塞，在阻塞移除前，線程無法繼續(xù)自己的任務(wù)。通常，操作系統(tǒng)會(huì)完全掛起一個(gè)阻塞線程(并將其時(shí)間片交給其他線程)，直到其被其他線程“解阻塞”；“解阻塞”的方式很多，比如解鎖一個(gè)互斥鎖、通知條件變量達(dá)成，或讓“期望”就緒。

不使用阻塞庫的數(shù)據(jù)結(jié)構(gòu)和算法，被稱為無阻塞結(jié)構(gòu)。不過，無阻塞的數(shù)據(jù)結(jié)構(gòu)并非都是無鎖的，那么就讓我們見識一下各種各樣的無阻塞數(shù)據(jù)結(jié)構(gòu)吧！

7.1.1 非阻塞數(shù)據(jù)結(jié)構(gòu)

在第5章中，我們使用std::atomic_flag實(shí)現(xiàn)了一個(gè)簡單的自旋鎖。一起回顧一下這段代碼。

清單7.1 使用std::atomic_flag實(shí)現(xiàn)了一個(gè)簡單的自旋鎖

class spinlock_mutex
{
  std::atomic_flag flag;
public:
  spinlock_mutex():
    flag(ATOMIC_FLAG_INIT)
  {}
  void lock()
  {
    while(flag.test_and_set(std::memory_order_acquire));
  }
  void unlock()
  {
    flag.clear(std::memory_order_release);
  }
};

這段代碼沒有調(diào)用任何阻塞函數(shù)，lock()只是讓循環(huán)持續(xù)調(diào)用test_and_set()，并返回false。這就是為什么取名為“自旋鎖”的原因——代碼“自旋”于循環(huán)當(dāng)中。所以，這里沒有阻塞調(diào)用，任意代碼使用互斥量來保護(hù)共享數(shù)據(jù)都是非阻塞的。不過，自旋鎖并不是無鎖結(jié)構(gòu)。這里用了一個(gè)鎖，并且一次能鎖住一個(gè)線程。讓我們來看一下無鎖結(jié)構(gòu)的具體定義，這將有助于你判斷哪些類型的數(shù)據(jù)結(jié)構(gòu)是無鎖的。

7.1.2 無鎖數(shù)據(jù)結(jié)構(gòu)

作為無鎖結(jié)構(gòu)，就意味著線程可以并發(fā)的訪問這個(gè)數(shù)據(jù)結(jié)構(gòu)。線程不能做相同的操作；一個(gè)無鎖隊(duì)列可能允許一個(gè)線程進(jìn)行壓入數(shù)據(jù)，另一個(gè)線程彈出數(shù)據(jù)，當(dāng)有兩個(gè)線程同時(shí)嘗試添加元素時(shí)，這個(gè)數(shù)據(jù)結(jié)構(gòu)將被破壞。不僅如此，當(dāng)其中一個(gè)訪問線程被調(diào)度器中途掛起時(shí)，其他線程必須能夠繼續(xù)完成自己的工作，而無需等待掛起線程。

具有“比較/交換”操作的數(shù)據(jù)結(jié)構(gòu)，通常在“比較/交換”實(shí)現(xiàn)中都有一個(gè)循環(huán)。使用“比較/交換”操作的原因：當(dāng)有其他線程同時(shí)對指定數(shù)據(jù)的修改時(shí)，代碼將嘗試恢復(fù)數(shù)據(jù)。當(dāng)其他線程被掛起時(shí)，“比較/交換”操作執(zhí)行成功，那么這樣的代碼就是無鎖的。當(dāng)執(zhí)行失敗時(shí)，就需要一個(gè)自旋鎖了，且這個(gè)結(jié)構(gòu)就是“非阻塞-有鎖”的結(jié)構(gòu)。

無鎖算法中的循環(huán)會(huì)讓一些線程處于“饑餓”狀態(tài)。如有線程在“錯(cuò)誤”時(shí)間執(zhí)行，那么第一個(gè)線程將會(huì)不停得嘗試自己所要完成的操作(其他程序繼續(xù)執(zhí)行)?！盁o鎖-無等待”數(shù)據(jù)結(jié)構(gòu)，就為了避免這種問題存在的。

7.1.3 無等待數(shù)據(jù)結(jié)構(gòu)

無等待數(shù)據(jù)結(jié)構(gòu)就是：首先，是無鎖數(shù)據(jù)結(jié)構(gòu)；并且，每個(gè)線程都能在有限的步數(shù)內(nèi)完成操作，暫且不管其他線程是如何工作的。由于會(huì)和別的線程產(chǎn)生沖突，所以算法可以進(jìn)行無數(shù)次嘗試，因此并不是無等待的。

正確實(shí)現(xiàn)一個(gè)無鎖的結(jié)構(gòu)是十分困難的。因?yàn)?，要保證每一個(gè)線程都能在有限步驟里完成操作，就需要保證每一個(gè)操作可以被一次性執(zhí)行完成；當(dāng)有線程執(zhí)行某個(gè)操作時(shí)，不會(huì)讓其他線程的操作失敗。這就會(huì)讓算法中所使用到的操作變的相當(dāng)復(fù)雜。

考慮到獲取無鎖或無等待的數(shù)據(jù)結(jié)構(gòu)所有權(quán)都很困難，那么就有理由來寫一個(gè)數(shù)據(jù)結(jié)構(gòu)了；需要保證的是，所要得獲益要大于實(shí)現(xiàn)成本。那么，就先來找一下實(shí)現(xiàn)成本和所得獲益的平衡點(diǎn)吧！

7.1.4 無鎖數(shù)據(jù)結(jié)構(gòu)的利與弊

使用無鎖結(jié)構(gòu)的主要原因：將并發(fā)最大化。使用基于鎖的容器，會(huì)讓線程阻塞或等待；互斥鎖削弱了結(jié)構(gòu)的并發(fā)性。在無鎖數(shù)據(jù)結(jié)構(gòu)中，某些線程可以逐步執(zhí)行。在無等待數(shù)據(jù)結(jié)構(gòu)中，無論其他線程當(dāng)時(shí)在做什么，每一個(gè)線程都可以轉(zhuǎn)發(fā)進(jìn)度。這種理想的方式實(shí)現(xiàn)起來很難。結(jié)構(gòu)太簡單，反而不容易寫，因?yàn)槠渚褪且粋€(gè)自旋鎖。

使用無鎖數(shù)據(jù)結(jié)構(gòu)的第二個(gè)原因就是魯棒性。當(dāng)一個(gè)線程在獲取一個(gè)鎖時(shí)被殺死，那么數(shù)據(jù)結(jié)構(gòu)將被永久性的破壞。不過，當(dāng)線程在無鎖數(shù)據(jù)結(jié)構(gòu)上執(zhí)行操作，在執(zhí)行到一半死亡時(shí)，數(shù)據(jù)結(jié)構(gòu)上的數(shù)據(jù)沒有丟失(除了線程本身的數(shù)據(jù))，其他線程依舊可以正常執(zhí)行。

另一方面，當(dāng)不能限制訪問數(shù)據(jù)結(jié)構(gòu)的線程數(shù)量時(shí)，就需要注意不變量的狀態(tài)，或選擇替代品來保持不變量的狀態(tài)。同時(shí)，還需要注意操作的順序約束。為了避免未定義行為，及相關(guān)的數(shù)據(jù)競爭，就必須使用原子操作對修改操作進(jìn)行限制。不過，僅使用原子操作時(shí)不夠的；需要確定被其他線程看到的修改，是遵循正確的順序。

因?yàn)?，沒有任何鎖(有可能存在活鎖)，死鎖問題不會(huì)困擾無鎖數(shù)據(jù)結(jié)構(gòu)?；铈i的產(chǎn)生是，兩個(gè)線程同時(shí)嘗試修改數(shù)據(jù)結(jié)構(gòu)，但每個(gè)線程所做的修改操作都會(huì)讓另一個(gè)線程重啟，所以兩個(gè)線程就會(huì)陷入循環(huán)，多次的嘗試完成自己的操作。試想有兩個(gè)人要過獨(dú)木橋，當(dāng)兩個(gè)人從兩頭向中間走的時(shí)候，他們會(huì)在中間碰到，然后不得不再走回出發(fā)的地方，再次嘗試過獨(dú)木橋。這里，要打破僵局，除非有人先到獨(dú)木橋的另一端(或是商量好了，或是走的快，或純粹是運(yùn)氣)，要不這個(gè)循環(huán)將一直重復(fù)下去。不過活鎖的存在時(shí)間并不久，因?yàn)槠湟蕾囉诰€程調(diào)度。所以其只是對性能有所消耗，而不是一個(gè)長期的問題；但這個(gè)問題仍需要關(guān)注。根據(jù)定義，無等待的代碼不會(huì)被活鎖所困擾，因其操作執(zhí)行步驟是有上限的。換個(gè)角度，無等待的算法要比等待算法的復(fù)雜度高，且即使沒有其他線程訪問數(shù)據(jù)結(jié)構(gòu)，也可能需要更多步驟來完成對應(yīng)操作。

這就是“無鎖-無等待”代碼的缺點(diǎn)：雖然提高了并發(fā)訪問的能力，減少了單個(gè)線程的等待時(shí)間，但是其可能會(huì)將整體性能拉低。首先，原子操作的無鎖代碼要慢于無原子操作的代碼，原子操作就相當(dāng)于無鎖數(shù)據(jù)結(jié)構(gòu)中的鎖。不僅如此，硬件必須通過同一個(gè)原子變量對線程間的數(shù)據(jù)進(jìn)行同步。在第8章，你將看到與“乒乓”緩存相關(guān)的原子變量(多個(gè)線程訪問同時(shí)進(jìn)行訪問)，將會(huì)成為一個(gè)明顯的性能瓶頸。在提交代碼之前，無論是基于鎖的數(shù)據(jù)結(jié)構(gòu)，還是無鎖的數(shù)據(jù)結(jié)構(gòu)，對性能的檢查是很重要的(最壞的等待時(shí)間，平均等待時(shí)間，整體執(zhí)行時(shí)間，或者其他指標(biāo))。

讓我們先來看幾個(gè)例子。