859
並發數據結構-1.1 並發的數據結構的設計
隨著多個處理器共享同一內存的機器在商業上的廣泛使用，並發編程的藝術也產生了巨大的變化。當前的趨勢向著低功耗芯片級多線程（CMT）發展，所以這樣的機器一定會更加廣泛的被使用。
共享內存多處理器是指並發的執行多個線程的係統，這些線程在共享的內存中通過數據結構通訊和同步。這些數據結構的效率對於性能是很關鍵的，而目前熟練掌握為多處理器機器設計高效數據結構這一技術的人並不多。對大多數人來說，設計並發的數據結構比設計單線程的難多了，因為並發執行的線程可能會多種方式地交錯運行他們的指令，每一種方式會帶來不同的，甚至不符合預期的輸出。這就要求設計者改變他們對運算的認識，理解新的設計方法，采用新的編程工具集。此外，設計可擴展的並發數據結構，使得當機器執行越來越多的並發線程時依舊表現良好也是新的挑戰。本文主要介紹設計並發數據結構的相關挑戰，和一些重要的數據結構相關內容的總結。我們的總結絕不是全麵的；相反，我們特意選取了一些能說明設計的關鍵問題的流行的數據結構，希望我們提供了足夠的背景和知識，讓有興趣的讀者接觸那些我們沒有提到的內容。
1.1 並發的數據結構的設計
共享內存多處理器的一些特性使得並發數據結構的設計和校驗比相對應的單線程結構難度顯著增加。
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 右半部分所示，我們能通過鎖機製得到一個正確的順序實現。我們通過阻止所有的交錯來預防壞的交錯。這樣很容易得到一個正確的共享計數器，然而這種簡單是有代價的：鎖機製引發了許多關於性能和軟件工程上的問題。
文章轉自 並發編程網-ifeve.com
最後更新：2017-05-23 12:02:35