多核系統(tǒng)中三種典型鎖競爭的加速比分析
1.1 引言
在多核系統(tǒng)中，衡量程序性能的一個重要指標就是加速比，加速比定義如下：
S(n) ＝ 單處理器上最優(yōu)串行化算法計算時間 / 使用n個處理器并行計算時間
眾所周知，關于加速比有一個阿姆達爾定律，說的是加速比方面的事情，即加速比S(n)和串行部分所占比例f有關，而與CPU核數(shù)n無關，也就是說
當處理器個數(shù)n趨近于無窮大時，有以下等式。
阿姆達爾定律的提出讓整個軟件界灰心了許多年，因為只要串行比例為5％，那么不論增加多少處理器，加速比最多也只能達到20。
若干年后一個叫Gustafson的人提出了和阿姆達爾定律不同的意見，得到了一個新的加速比公式如下：
其中的K是一個常數(shù)，表示串行執(zhí)行時間所占的比例。
按照Gustafson定律，加速比顯然和CPU核數(shù)n是成正比的，CPU核數(shù)越大，加速比也越大。
Gustafson定律的前提條件假設串行化代碼的規(guī)模是固定的，計算規(guī)模是隨CPU核數(shù)增加而增加的。實際情況中，共享資源訪問的計算量和程序的計算規(guī)模是成正比的，如果共享資源通過鎖保護操作而變成串行化執(zhí)行的話，那么串行化代碼的規(guī)模將隨程序規(guī)模的增加而線性增加，這樣將導致不符合Gustafson定律的前提條件，而是符合阿姆達爾定律的前提條件。最終得出的加速比將是按照阿姆達爾定律計算出結果。
因此如何消除鎖競爭造成的串行化執(zhí)行就成了程序員需要解決的問題，下面就來先看一下幾種不同類型的鎖競爭形式對加速比指標的具體影響，在鎖競爭的情況中，任務粒度因子和鎖粒度因子是影響加速比的重要因素之一，因此需要先看一下任務粒度因子和鎖粒度因子的概念。
1.2 任務粒度因子與鎖粒度因子
在一個有鎖保護操作的程序中，每個任務中的計算可以分為如下圖所示的幾部分：
圖1：任務內的計算分類
其中
ts － 表示鎖內計算時間，大小由共享資源的操作時間決定，與共享資源類型有關，并且與程序員的程序設計有關。
tl － 表示 Lock操作和Unlock操作耗費的時間，如果CPU核的速度固定，那么它為一常量。
tp － 表示鎖外可并行計算部分耗費的時間，大小與具體的應用類型及程序員的分解有關
為了形象地表示出各段計算間的比例關系，引入兩個概念：任務粒度因子和鎖粒度因子。
1.任務粒度因子
任務粒度因子主要是用來反映一個任務的計算量大小，由tl是常量，因此把任務內的有效計算和tl的比值叫做任務粒度因子，記為：
2.鎖粒度因子
鎖粒度因子反映了一個任務內鎖操作的粒度關系，用鎖內計算和tl的比值來表示鎖粒度因子，記為：
1.3 固定式鎖競爭中的加速比分析
在一個固定式鎖競爭情況中，是由若干個同 時創(chuàng)建的對等任務競爭同一把鎖，在這種固定式競爭環(huán)境中，假設每個任務都執(zhí)行一次鎖內操作，鎖競爭一定會發(fā)生并因鎖競爭而導致任務排隊串行執(zhí)行鎖操作及鎖 內計算。固定式鎖競爭屬于實際情況中的常見現(xiàn)象，比如使用前面提到過的OpenMP來創(chuàng)建任務，如果在任務中使用了鎖操作的話，那么它就是一種固定式鎖競 爭。
固定式鎖競爭的情況在這篇文章：多核編程中的鎖競爭難題里做過分析，如果用前面的任務粒度因子和鎖粒度因子代入的話，可以得到固定式鎖競爭的加速比如下：
1.4 隨機鎖競爭中的加速比分析
在實際情況中，除了上節(jié)講過的固定式鎖競爭情況外，鎖競爭還有一種隨機競爭的形式，在多核編程中的任務隨機競爭模式的概率分析 一文中對隨機鎖競爭做過分析。
在隨機鎖競爭中，各個對等任務運行鎖計算的時間是隨機的。比如在服務器軟件中，各個任務創(chuàng)建后，每個任務都在循環(huán)地做同樣的計算，而各個任務的運行時間受網絡客戶端的影響，其處理時間不是固定的，而是隨機的，這樣將導致各個任務在競爭同一把鎖時出現(xiàn)隨機競爭現(xiàn)象。
隨機鎖競爭情況下的加速比期望值如下：
n 隨機鎖競爭最壞情況下的加速比
上面計算出的加速比是期望值，在最壞情況下，實際上有 
的概率所有的任務都處于鎖內計算狀態(tài)，在這種最壞情況下，只有一個任務在運行，因此加速比為1，如果考慮鎖計算開銷，那么加速比為
在最壞的情況下，加速比將小于1。
#p#
1.5 分布式鎖競爭的加速比分析
在一個分布式鎖競爭環(huán)境中，有多個任務競爭多把不同的鎖，不妨設有m個任務競爭r把不同的鎖。
如果任務數(shù)量m足夠大的話，那么運行鎖外計算的任務數(shù)量將會大于CPU核數(shù)，導致每個CPU核上都有任務在運行，此時的多CPU效率為 
，
可以看出這種情況下的加速比和CPU核數(shù)成正比，并和任務粒度因子有關，任務粒度因子越大，那么加速比也越大。此時加速比和鎖粒度沒有任何關系。這是分布式鎖競爭和普通鎖競爭的最大區(qū)別。
如果任務數(shù)量m不夠大，運行鎖外計算的任務數(shù)量小于CPU核數(shù)的話，那么需要計算在有多少個進行鎖競爭的任務在運行。
為方便起見 ，令k為運行鎖內計算的任務數(shù)量，那么這k個任務在競爭r把鎖，假設有 1把鎖上有任務在競爭，可以求出q的期望值為：
實際上q表示了這些鎖競爭的任務中，最多可能有q個任務在運行，最大運行鎖內計算的任務數(shù)為沒有運行鎖外計算的CPU核數(shù)。
如果q小于n-m+k，那么有m-k個任務在運行鎖外計算，有q個任務在運行q把鎖上的鎖內計算，此時多CPU效率為 
，求出加速比的期望值為：
加速比的大小完全取決于q的大小，而q的大小與任務數(shù)k和鎖的數(shù)量r有關，r保持不變情況下，任務數(shù)愈大，則q愈大；任務數(shù)k保持不變情況下，r愈大則q愈大。
如果q大于等于n-m+k，那么將至少有n個任務在運行，所有的CPU核都處于運行狀態(tài)，考慮加鎖解鎖增加的開銷后，多CPU效率期望值為 
，可以求出此時的加速比期望值為：
所以在隨機分布式鎖競爭的情況下，加速比只和四個因素有關，CPU核數(shù)、任務粒度因子、任務數(shù)量、鎖的數(shù)量。
只要選取合適的任務數(shù)量、鎖的數(shù)量，那么就可以使加速比和CPU核數(shù)成正比關系。
n分布式鎖競爭在最壞情況下的概率計算
分布式鎖競爭情況下，考慮一種最壞的情況，所有的任務都在運行鎖內計算，此時可以
只要選擇合適的任務數(shù)m，鎖數(shù)量r，那么可以將概率P控制在一個比較大的值，這樣在最壞情況下也不會出現(xiàn)問題。
1.6 結論
以上三種鎖競爭形式中，固定式鎖競爭所得 到的加速比是很糟糕的，和阿姆達爾定律相當，隨機式鎖競爭所得到的加速比比固定式好了許多，但最壞情況下仍然不容樂觀。分布式鎖競爭所得到的加速比是最好 的，加速比和CPU核數(shù)成正比，和Gustafson定律描述的相當。因此在多核系統(tǒng)中使用分布式鎖競爭的話，可以取得和單核系統(tǒng)中多任務編程差不多的性 能。分布式鎖競爭形式將是多核編程的發(fā)展方向。
