7.1 定義和意義

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

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

7.1.1 非阻塞數據結構

在第5章中，我們使用std::atomic_flag實現了一個簡單的自旋鎖。一起回顧一下這段代碼。

清單7.1 使用std::atomic_flag實現了一個簡單的自旋鎖

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);
  }
};

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

7.1.2 無鎖數據結構

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

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

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

7.1.3 無等待數據結構

無等待數據結構就是：首先，是無鎖數據結構；并且，每個線程都能在有限的步數內完成操作，暫且不管其他線程是如何工作的。由于會和別的線程產生沖突，所以算法可以進行無數次嘗試，因此并不是無等待的。

正確實現一個無鎖的結構是十分困難的。因為，要保證每一個線程都能在有限步驟里完成操作，就需要保證每一個操作可以被一次性執(zhí)行完成；當有線程執(zhí)行某個操作時，不會讓其他線程的操作失敗。這就會讓算法中所使用到的操作變的相當復雜。

考慮到獲取無鎖或無等待的數據結構所有權都很困難，那么就有理由來寫一個數據結構了；需要保證的是，所要得獲益要大于實現成本。那么，就先來找一下實現成本和所得獲益的平衡點吧！

7.1.4 無鎖數據結構的利與弊

使用無鎖結構的主要原因：將并發(fā)最大化。使用基于鎖的容器，會讓線程阻塞或等待；互斥鎖削弱了結構的并發(fā)性。在無鎖數據結構中，某些線程可以逐步執(zhí)行。在無等待數據結構中，無論其他線程當時在做什么，每一個線程都可以轉發(fā)進度。這種理想的方式實現起來很難。結構太簡單，反而不容易寫，因為其就是一個自旋鎖。

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

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

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

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

讓我們先來看幾個例子。