1.1 引言

在多核系統(tǒng)中，衡量程序性能的一個重要指標就是加速比，加速比定義如下：

S(n) ＝ 單處理器上最優(yōu)串行化算法計算時間 / 使用n個處理器并行計算時間

眾所周知，關(guān)于加速比有一個阿姆達爾定律，說的是加速比方面的事情，即加速比S(n)和串行部分所占比例f有關(guān)，而與CPU核數(shù)n無關(guān)，也就是說

當(dāng)處理器個數(shù)n趨近于無窮大時，有以下等式。

阿姆達爾定律的提出讓整個軟件界灰心了許多年，因為只要串行比例為5％，那么不論增加多少處理器，加速比最多也只能達到20。

若干年后一個叫Gustafson的人提出了和阿姆達爾定律不同的意見，得到了一個新的加速比公式如下：

其中的K是一個常數(shù)，表示串行執(zhí)行時間所占的比例。

按照Gustafson定律，加速比顯然和CPU核數(shù)n是成正比的，CPU核數(shù)越大，加速比也越大。

Gustafson定律的前提條件假設(shè)串行化代碼的規(guī)模是固定的，計算規(guī)模是隨CPU核數(shù)增加而增加的。實際情況中，共享資源訪問的計算量和程序的計算規(guī)模是成正比的，如果共享資源通過鎖保護操作而變成串行化執(zhí)行的話，那么串行化代碼的規(guī)模將隨程序規(guī)模的增加而線性增加，這樣將導(dǎo)致不符合Gustafson定律的前提條件，而是符合阿姆達爾定律的前提條件。最終得出的加速比將是按照阿姆達爾定律計算出結(jié)果。

因此如何消除鎖競爭造成的串行化執(zhí)行就成了程序員需要解決的問題，下面就來先看一下幾種不同類型的鎖競爭形式對加速比指標的具體影響，在鎖競爭的情況中，任務(wù)粒度因子和鎖粒度因子是影響加速比的重要因素之一，因此需要先看一下任務(wù)粒度因子和鎖粒度因子的概念。

1.2 任務(wù)粒度因子與鎖粒度因子

在一個有鎖保護操作的程序中，每個任務(wù)中的計算可以分為如下圖所示的幾部分：

圖1：任務(wù)內(nèi)的計算分類

其中

t_s － 表示鎖內(nèi)計算時間，大小由共享資源的操作時間決定，與共享資源類型有關(guān)，并且與程序員的程序設(shè)計有關(guān)。

t_l － 表示 Lock操作和Unlock操作耗費的時間，如果CPU核的速度固定，那么它為一常量。

t_p － 表示鎖外可并行計算部分耗費的時間，大小與具體的應(yīng)用類型及程序員的分解有關(guān)

為了形象地表示出各段計算間的比例關(guān)系，引入兩個概念：任務(wù)粒度因子和鎖粒度因子。

1.任務(wù)粒度因子

任務(wù)粒度因子主要是用來反映一個任務(wù)的計算量大小，由t_l是常量，因此把任務(wù)內(nèi)的有效計算和t_l的比值叫做任務(wù)粒度因子，記為：

2.鎖粒度因子

鎖粒度因子反映了一個任務(wù)內(nèi)鎖操作的粒度關(guān)系，用鎖內(nèi)計算和t_l的比值來表示鎖粒度因子，記為：

1.3 固定式鎖競爭中的加速比分析

在一個固定式鎖競爭情況中，是由若干個同 時創(chuàng)建的對等任務(wù)競爭同一把鎖，在這種固定式競爭環(huán)境中，假設(shè)每個任務(wù)都執(zhí)行一次鎖內(nèi)操作，鎖競爭一定會發(fā)生并因鎖競爭而導(dǎo)致任務(wù)排隊串行執(zhí)行鎖操作及鎖 內(nèi)計算。固定式鎖競爭屬于實際情況中的常見現(xiàn)象，比如使用前面提到過的OpenMP來創(chuàng)建任務(wù)，如果在任務(wù)中使用了鎖操作的話，那么它就是一種固定式鎖競 爭。

固定式鎖競爭的情況在這篇文章：多核編程中的鎖競爭難題里做過分析，如果用前面的任務(wù)粒度因子和鎖粒度因子代入的話，可以得到固定式鎖競爭的加速比如下：

1.4 隨機鎖競爭中的加速比分析

在實際情況中，除了上節(jié)講過的固定式鎖競爭情況外，鎖競爭還有一種隨機競爭的形式，在多核編程中的任務(wù)隨機競爭模式的概率分析 一文中對隨機鎖競爭做過分析。

在隨機鎖競爭中，各個對等任務(wù)運行鎖計算的時間是隨機的。比如在服務(wù)器軟件中，各個任務(wù)創(chuàng)建后，每個任務(wù)都在循環(huán)地做同樣的計算，而各個任務(wù)的運行時間受網(wǎng)絡(luò)客戶端的影響，其處理時間不是固定的，而是隨機的，這樣將導(dǎo)致各個任務(wù)在競爭同一把鎖時出現(xiàn)隨機競爭現(xiàn)象。

隨機鎖競爭情況下的加速比期望值如下：

n 隨機鎖競爭最壞情況下的加速比

上面計算出的加速比是期望值，在最壞情況下，實際上有 的概率所有的任務(wù)都處于鎖內(nèi)計算狀態(tài)，在這種最壞情況下，只有一個任務(wù)在運行，因此加速比為1，如果考慮鎖計算開銷，那么加速比為

在最壞的情況下，加速比將小于1。

#p#

1.5 分布式鎖競爭的加速比分析

在一個分布式鎖競爭環(huán)境中，有多個任務(wù)競爭多把不同的鎖，不妨設(shè)有m個任務(wù)競爭r把不同的鎖。

如果任務(wù)數(shù)量m足夠大的話，那么運行鎖外計算的任務(wù)數(shù)量將會大于CPU核數(shù)，導(dǎo)致每個CPU核上都有任務(wù)在運行，此時的多CPU效率為 ，

可以看出這種情況下的加速比和CPU核數(shù)成正比，并和任務(wù)粒度因子有關(guān)，任務(wù)粒度因子越大，那么加速比也越大。此時加速比和鎖粒度沒有任何關(guān)系。這是分布式鎖競爭和普通鎖競爭的最大區(qū)別。

如果任務(wù)數(shù)量m不夠大，運行鎖外計算的任務(wù)數(shù)量小于CPU核數(shù)的話，那么需要計算在有多少個進行鎖競爭的任務(wù)在運行。

為方便起見 ，令k為運行鎖內(nèi)計算的任務(wù)數(shù)量，那么這k個任務(wù)在競爭r把鎖，假設(shè)有 1把鎖上有任務(wù)在競爭，可以求出q的期望值為：

實際上q表示了這些鎖競爭的任務(wù)中，最多可能有q個任務(wù)在運行，最大運行鎖內(nèi)計算的任務(wù)數(shù)為沒有運行鎖外計算的CPU核數(shù)。

如果q小于n-m+k，那么有m-k個任務(wù)在運行鎖外計算，有q個任務(wù)在運行q把鎖上的鎖內(nèi)計算，此時多CPU效率為 ，求出加速比的期望值為：

加速比的大小完全取決于q的大小，而q的大小與任務(wù)數(shù)k和鎖的數(shù)量r有關(guān)，r保持不變情況下，任務(wù)數(shù)愈大，則q愈大；任務(wù)數(shù)k保持不變情況下，r愈大則q愈大。

如果q大于等于n-m+k，那么將至少有n個任務(wù)在運行，所有的CPU核都處于運行狀態(tài)，考慮加鎖解鎖增加的開銷后，多CPU效率期望值為 ，可以求出此時的加速比期望值為：

所以在隨機分布式鎖競爭的情況下，加速比只和四個因素有關(guān)，CPU核數(shù)、任務(wù)粒度因子、任務(wù)數(shù)量、鎖的數(shù)量。

只要選取合適的任務(wù)數(shù)量、鎖的數(shù)量，那么就可以使加速比和CPU核數(shù)成正比關(guān)系。

n分布式鎖競爭在最壞情況下的概率計算

分布式鎖競爭情況下，考慮一種最壞的情況，所有的任務(wù)都在運行鎖內(nèi)計算，此時可以

只要選擇合適的任務(wù)數(shù)m，鎖數(shù)量r，那么可以將概率P控制在一個比較大的值，這樣在最壞情況下也不會出現(xiàn)問題。

1.6 結(jié)論

以上三種鎖競爭形式中，固定式鎖競爭所得 到的加速比是很糟糕的，和阿姆達爾定律相當(dāng)，隨機式鎖競爭所得到的加速比比固定式好了許多，但最壞情況下仍然不容樂觀。分布式鎖競爭所得到的加速比是最好 的，加速比和CPU核數(shù)成正比，和Gustafson定律描述的相當(dāng)。因此在多核系統(tǒng)中使用分布式鎖競爭的話，可以取得和單核系統(tǒng)中多任務(wù)編程差不多的性 能。分布式鎖競爭形式將是多核編程的發(fā)展方向。