1.1 引言

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

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

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

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

阿姆達(dá)爾定律的提出讓整個(gè)軟件界灰心了許多年，因?yàn)橹灰斜壤秊?％，那么不論增加多少處理器，加速比最多也只能達(dá)到20。

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

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

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

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

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

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

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

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

其中

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

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

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

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

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

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

2.鎖粒度因子

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

1.3 固定式鎖競(jìng)爭(zhēng)中的加速比分析

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

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

1.4 隨機(jī)鎖競(jìng)爭(zhēng)中的加速比分析

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

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

隨機(jī)鎖競(jìng)爭(zhēng)情況下的加速比期望值如下：

n 隨機(jī)鎖競(jìng)爭(zhēng)最壞情況下的加速比

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

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

#p#

1.5 分布式鎖競(jìng)爭(zhēng)的加速比分析

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

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

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

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

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

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

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

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

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

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

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

n分布式鎖競(jìng)爭(zhēng)在最壞情況下的概率計(jì)算

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

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

1.6 結(jié)論

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