并發資料結構- 1.1.1 性能

一個運作在p個處理上的應用程式的加速度是它在單個處理器上的執行時間和在p個處理器的執行時間的比值。這是一種評價應用程式對于機器資源利用程度的衡量。理想情況下，我們想要的結果是線性加速度：當我們使用p個處理器的時候,我們希望可以獲得p的加速度(譯者注:例如一個應用程式在單處理器的執行時間是10秒,那麼在雙處理的執行時間理想情況下是5秒)。加速度随着p一起增加的資料結構我們稱之為可擴充的資料結構。在設計可擴充的資料結構的時候,我們必須注意：為了同步使用簡單的方法會嚴重破壞擴充性。

回到基于鎖的計數器，我們會發現鎖會帶來順序性的瓶頸：在任何時間點，最多隻有一個fetch-and-inc操作是有用的，例如：遞增變量x。這種順序性的瓶頸會對本來能夠到達的加速度造成令人驚訝的影響。順序執行部分代碼對性能帶來的影響已經在基于amdahl’s law的一個簡單公式中闡明了。假設b是一個程式中順序性瓶頸所占的百分比。假設在單處理器中運作這個程式需要1個時間機關，那麼在p個處理器的環境中，執行順序運作部分的代碼需要b個時間機關，同時在最好的情況下，并發部分的代碼消耗(1-b)/p個時間機關，那麼加速度最多等于 1/(b+(1-b)/p) 。這意味中如果程式中隻有10%是屬于順序性瓶頸的部分，那麼在一個10個處理器的環境中，程式能達到的加速度最多隻有5.3：我們的應用隻利用了機器的一半性能。減少順序性執行代碼塊的數量和長度對性能是至關重要的。在基于鎖的上下文中，這意味着減少申請鎖的次數，降低鎖的粒度：一種用來表示在持有鎖時，執行指令數目的衡量。

我們的簡單計數器實作碰到的第二個問題是記憶體競争：這是底層硬體為了多線程并發嘗試通路相同的記憶體位址所造成的流量的開銷。隻有當你了解普通的共享記憶體多處理器架構一些方面，你才能意識到記憶體競争。如果保護着我們計數器的鎖就像很多簡單鎖一樣，是使用單一位址實作的話，那麼為了請求鎖，線程必須重複嘗試修改這個位址。以緩存一緻性多處理器為例，包含着鎖的cache line的獨占所有權必須重複的從一個處理器傳輸到别的處理器上，這會導緻每次嘗試修改記憶體位址的操作都需要長時間的等待，失敗的嘗試擷取鎖的操作會進一步加重相應的記憶體流量。在1.1.7中我們會讨論針對不同類型的共享記憶體架構實作相應的鎖，避免類似這樣的問題.

基于鎖的實作的計數器的第三個問題是：當持有鎖的線程被延期了，那麼所有嘗試擷取鎖的線程都會被延期。這種現象稱為阻塞，阻塞是多道程式設計（multiprogrammed）中特有的問題，每個處理器都有多個線程，作業系統會給擁有鎖的線程優先權。對于很多的資料結構來說，這個問題可以通過設計非阻塞的算法來解決，在非阻塞算法中一個線程的延期不會導緻其他線程的延期。根據定義而言，這些算法不能使用鎖。

下面我們繼續讨論我們的共享計數器的例子，分别讨論阻塞和非阻塞技術；我們會引入更多和性能相關的話題.