并發資料結構-1.1 并發的資料結構的設計

随着多個處理器共享同一記憶體的機器在商業上的廣泛使用，并發程式設計的藝術也産生了巨大的變化。目前的趨勢向着低功耗晶片級多線程（cmt）發展，是以這樣的機器一定會更加廣泛的被使用。

共享記憶體多處理器是指并發的執行多個線程的系統，這些線程在共享的記憶體中通過資料結構通訊和同步。這些資料結構的效率對于性能是很關鍵的，而目前熟練掌握為多處理器機器設計高效資料結構這一技術的人并不多。對大多數人來說，設計并發的資料結構比設計單線程的難多了，因為并發執行的線程可能會多種方式地交錯運作他們的指令，每一種方式會帶來不同的，甚至不符合預期的輸出。這就要求設計者改變他們對運算的認識，了解新的設計方法，采用新的程式設計工具集。此外，設計可擴充的并發資料結構，使得當機器執行越來越多的并發線程時依舊表現良好也是新的挑戰。本文主要介紹設計并發資料結構的相關挑戰，和一些重要的資料結構相關内容的總結。我們的總結絕不是全面的；相反，我們特意選取了一些能說明設計的關鍵問題的流行的資料結構，希望我們提供了足夠的背景和知識，讓有興趣的讀者接觸那些我們沒有提到的内容。

共享記憶體多處理器的一些特性使得并發資料結構的設計和校驗比相對應的單線程結構難度顯著增加。

<code></code>

acquire(lock);

oldval = x;                                                                                      oldval = x;

x = oldval + 1;                                                                                x = oldval + 1;

return oldval;                                                                                 release(lock);

return oldval;

圖1.1：順序的和基于鎖機制的fetch-and-inc操作代碼片段

難點的根源在于并發：因為線程是在不同的處理器上并發的執行，而且受作業系統的排程決策、缺頁、中斷等等影響，我們必須按照全部異步的想法來思考，以保證不同的線程能夠随意交錯的運作。這顯著提升了正确設計并發資料結構的複雜度。

為多處理器系統設計并發的資料結構在性能和可擴充性上也有大量的挑戰。在現代的機器上，處理器和記憶體的布局、資料在記憶體中的布局、多處理器體系結構中各個元素間的通信負載全都對性能有影響。此外，正确性和性能兩者聯系非常的緊密：算法的改進在提高性能的同時經常使其更加難以設計和檢驗正确的資料結構實作。

下面的例子闡述了影響資料結構設計的各個多處理器特征。假設我們想要實作一個共享的計數器資料結構，用于支援fetch-and-inc操作，即計數器加一然後傳回增加前的值。一個普通的順序fetch-and-inc實作的代碼就如圖1.1中左邊部分所展示的那樣。

如果我們允許多個線程并發地調用fetch-and-inc操作，上述實作運作起來并不正确。來看看原因，注意大多數編譯器會把這份源代碼轉換成機器指令：把 x 的值裝進一個寄存器，然後把寄存器中的值加一，然後再把這個寄存器的值存回 x 。假如計數器初始化為 0 ，兩個不同的處理器并發的執行兩個fetch-and-inc操作。然後就有可能兩個操作都從 x 中讀出 0 ，然後都把 1 存回 x 并且傳回 0 。這顯然是不正确的：兩個操作中有一個應該傳回 1 。

如上所述，兩個fetch-and-inc操作不正确的交錯結果導緻了不正确的行為。一個自然并且普通的方法來阻止這樣的交錯就是用互斥鎖（也被叫做 mutex 或者 lock）。鎖是一個在任意時間點，都是不被（其他線程）擷取，隻被一個線程所擷取的構造。如果一個線程 t1 希望擷取已經被另一個線程 t2 所擷取到的鎖，那麼 t1 必須等到 t2 釋放這個鎖。

如圖 1.1 右半部分所示，我們能通過鎖機制得到一個正确的順序實作。我們通過阻止所有的交錯來預防壞的交錯。這樣很容易得到一個正确的共享計數器，然而這種簡單是有代價的：鎖機制引發了許多關于性能和軟體工程上的問題。