并發資料結構-1.1.4 複雜度測量&1.1.5 正确性

一個被廣泛研究的方向是在理想化模型，如并行随機存取機上分析并發資料結構和算法的漸進複雜度[35, 122, 135]。然而，很少有将這些資料結構放在一個真實的多處理器上進行模組化的。這裡有多種原因，大部分原因跟系統硬體架構與線程異步執行的互相作用有關。想想組合樹(combining tree)的例子，雖然我們能通過計算（指令數）得到o(p/logp)的加速比，但這無法反映在實證研究中[52, 129]。真實世界的行為是被上述其他因素支配的，如競争開銷，緩存行為，同步操作(例如cas)開銷，請求到達率，退避延時，資料結構在記憶體中的布局等等。這些因素很難用一個精确的涵蓋目前所有架構的模型來量化。

采集這些方面的複雜度（的）測量方法已經由dwork [28] ，anderson，yang [7]等人提出，雖然這些方法在算法設計上提供了有用的見解，但它們還是不能準确捕捉所有上述因素的影響。是以，并發資料結構的設計者通過在真實機器和模拟架構[9, 52, 97, 103]上運作微基準測試實證地比較他們的設計。在本章的剩餘部分，我們普遍地根據這些資料結構基于經驗觀察到的行為來評價他們，并且用簡單的複雜度變量來輔助直覺進行判斷。

很容易發現，簡單的基于鎖的計數器，其行為跟那些順序的實作是“相同”的。然而，很明顯我們更難看到對合并樹(combining tree)而言，同樣如此。一般情況下，并發資料結構的實作往往是很精細的，不正确的實作并不少見。是以，聲明并嚴格證明一個特定的設計正确地實作了所要求的并發資料結構是非常重要的。我們不希望達到這些而不精确地指明什麼是“正确”。

順序資料結構的資料結構規格描述通常更容易。例如，我們可以通過選擇一組狀态，并提供一個以狀态，操作名，以及該操作的參數作為函數參數，将新的狀态和操作傳回值作為函數傳回值的轉換函數(trainsition function)來指明一個順序資料結構的語義。加上指定的初始狀态，轉換函數(transition function)指定了該資料結構上所有可接受操作序列。計數器的順序語義定義如下：計數器的狀态是一組整數，初始狀态是0。fetch-and-inc操作的轉換函數在舊狀态上加一來擷取新狀态，傳回值是計數器的舊狀态。

順序資料結構上的操作是一次一個順序執行的，我們隻簡單要求順序操作的結果遵循如上讨論所指定的順序語義。然而，對并發資料結構來說，操作不一定完全按照順序。并發資料結構的正确性條件一般要求有些操作完全按照順序以滿足順序語義。不同正确性條件的差別在于對總順序的需求不同。

一個常見的正确性條件是lamport的順序一緻性(sequential consistency)[81]，這要求總順序上保證每個線程執行操作的順序。從軟體工程的角度來看順序一緻性有個缺點：使用順序一緻性元件實作的資料結構本身可能不是順序一緻的。

一個自然，廣泛使用且克服上述問題的正确性條件是herlihy, wing的可線性化(linearizability)[58]，它是一個用于資料庫事務的串行化條件的一個變種。可線性化需要（滿足兩個特性：(1)該資料結構是順序一緻的 ，(2)使其滿足順序一緻性的總體順序遵循操作執行的實時順序。遵循實時順序意味着如果操作o1在操作o2開始之前完成(操作之間不是并發的)，那麼o1必須排在o2之前。該正确性條件的另外一種了解方式是，它要求我們能夠确定每個操作執行時間間隔中的不同點，稱為可線性化點，這樣，如果我們根據可線性化點的順序來對操作排序，那麼排序結果會遵循順序一緻性語義。

很容易看到，基于鎖的計數器是可線性化的，計數器的狀态始終存儲在變量x中。我們将存儲增加後的值到變量x定義為fetch-and-inc操作的可線性化點。基于cas的無鎖(lock-free)實作的計數器的可線性化點同樣簡單，除了使用cas指令的語義而不是論證鎖語義，我們能得出結論，計數器每被修改一次就加一。

對于合并樹(combining tree)來說，很明顯我們更難看到它是可線性化的，因為計數器的狀态在同一時間不止加一，并且因為一個fetch-and-inc操作實際上可能由之前合并的另一個操作來執行。我們定義基于合并樹(combining tree)的計數器上的fetch-and-inc操作的可線性化點如下：當一個獲勝線程到達樹的根節點并将其累積值加到計數器上時，我們将其之前合并的操作線性化。這些操作根據之後被分發到對應操作的傳回值的順序線性化。雖然詳細的可線性化證明超出了我們讨論的範圍，但我們應該清楚即使是簡單并發資料結構的嚴格的正确性證明，也是相當具有挑戰性的。

直覺的吸引力和子產品化使可線性化(linearizability)成為一個廣受歡迎的正确性條件。在本章剩餘部分我們讨論的大部分并發資料結構實作都是可線性化的。然而，在某些情況下，性能和可擴充性可通過滿足較弱正确性得到提高。例如，靜态一緻性(quiescent consistency)條件[10]降低了對總操作順序滿足實時排序的要求，但要求所有靜态狀态(其中無任何操作執行)之後執行的操作必須排在該狀态之前執行的操作之後。一個滿足這種弱正确性條件的實作是否有用跟應用有關。相比之下，可線性化的實作始終是有用的，因為設計者可以将其視為具有原子性。