在前一篇講解多核編程的幾個難題及其對策（難題一）的文章中提到了鎖競爭會讓串行化隨CPU的核數增多而加劇的現象，這篇文章就來對多核編程的鎖競爭進行深入的分析。

為了簡化起見，我們先看一個簡單的情況，假設有4個對等的任務同時啟動運行，假設每個任務剛開始時有一個需要鎖保護的操作，耗時為1，每個任務其他部分的耗時為25。這幾個任務啟動運行后的運行情況如下圖所示：

                                               圖1：對等任務的鎖競爭示意圖

在上圖中，可以看出第1個任務直接執行到結束，中間沒有等待，第2個任務等待了1個時間單位，第3個任務等待了2個時間單位，第3個任務等待了3個時間單位。

這樣有3個CPU總計等待了6個時間單位，如果這幾個任務是采用OpenMP里的所有任務都在同一點上進行等待到全部任務執行完再向下執行時，那么總的運行時間將和第四個任務一樣為29個時間單位，加速系數為：（1＋4×25）/ 29 ＝ 3.48

即使以4個任務的平均時間27.5來進行計算，加速系數＝101/27.5 = 3.67

按 照阿姆爾達定律來計算加速系數的話，上述應用中，串行時間為1，并行處理的總時間轉化為串行后為100個時間單位，如果放在4核CPU上運行的話，加速系 數＝p / (1 + (p-1)*f) ＝ 4/(1+(4-1)*1/101) = 404/104 = 3.88

這就產生了一個奇怪的問題，使用了鎖之后，加速系數連阿姆爾達定律計算出來的加速系數都不如，更別說用Gustafson定律計算的加速系數了。

其實可以將上面4個任務的鎖競爭情況推廣到更一般的情況，假設有鎖保護的串行化時間為1，可并行化部分在單核CPU上的運行時間為t，CPU核數為p，那么在p個對成任務同時運行情況下，鎖競爭導致的總等待時間為：1＋2＋…＋p ＝ p*(p-1)/2

耗時最多的一個任務所用時間為： p + t/p

使用耗時最多的一個任務所用時間來當作并行運行時間的話，加速系數如下

S(p) = (t+1) / (p + t/p) = p*(t+1) / (p*p+t)       （鎖競爭下的加速系數公式）

這個公式表明在有鎖競爭情況下，如果核數固定情況下，可并行化部分越大，那么加速系數將越大。在并行化時間固定的情況下，如果CPU核數越多，那么加速系數將越小。

還是計算幾個實際的例子來說明上面公式的效果：

令t=100, p=4, 加速系數＝4×(100 +1)/ (4*4+100) = 3.48

令t=100, p=16, 加速系數＝16×(100+1) / (16*16+100) = 4.54

令t=100, p=64, 加速系數＝64×(100+1) / (64*64+100) = 1.54

令t=100, p=128, 加速系數＝128×(100+1) / (128*128+100) = 0.78

從以上計算可以看出，當核數多到一定的時候，加速系數不僅不增加反而下降，核數增加到128時，加速系數只有0.78，還不如在單核CPU上運行的速度。

上面的例子中，鎖保護導致的串行代碼是在任務啟動時調用的，其實對等任務中在其他地方調用的鎖保護的串行代碼也是一樣的。

對等型任務的鎖競爭現象在實際情況中是很常見的，比如服務器軟件，通常各個客戶端處理任務都是對等的，如果在里面使用了鎖的話，那么很容易造成上面說的加速系數隨CPU核數增多而下降的現象。

以前的服務器軟件一般運行在雙CPU或四CPU機器上，所以鎖競爭導致的加速系數下降現象不明顯，進入多核時代后，隨著CPU核數的增多，這個問題將變得很嚴重，所以多核時代對程序設計提出了新的挑戰。以前的多任務下的編程思想放到多核編程上不一定行得通。

所以簡單地認為多核編程和以前的多任務編程或并行計算等同的話是不切實際的，在講串行化難題的那篇文章中提出了一些解決方面的對策，但是那些對策還有待業界繼續努力才能做得到。

當然由于目前市面上銷售的多核CPU還是雙核和四核的，等到16核以上的CPU大規模進入市場可能還有幾年時間，相信業界在未來的幾年內能夠對于上面對等任務上的鎖競爭問題找到更好的解決方案。

原文鏈接：http://blog.csdn.net/drzhouweiming/article/details/1559718