無(wú)鎖編程與分布式編程那個(gè)更適合多核CPU？
 
前一篇文章多核系統(tǒng)中三種典型鎖競(jìng)爭(zhēng)的加速比分析講過(guò)了三種典型鎖競(jìng)爭(zhēng)情況下的加速比情況，特別是分布式鎖競(jìng)爭(zhēng)的加速比和CPU核數(shù)成正比，有很好的加速比性能。由于近些年在學(xué)術(shù)界中，無(wú)鎖編程屬于研究熱點(diǎn)。那么使用無(wú)鎖編程是不是可以取得更好的加速比性能呢？或者說(shuō)無(wú)鎖編程是不是更適合多核CPU系統(tǒng)呢？
無(wú)鎖編程主要是使用原子操作替代鎖來(lái)實(shí)現(xiàn)對(duì)共享資源的訪問(wèn)保護(hù)，舉個(gè)例子，要對(duì)某個(gè)整數(shù)變量進(jìn)行加1操作的話，用鎖保護(hù)操作的代碼如下：
int a = 0;
Lock();
a+= 1;
Unlock();
 
如果對(duì)上述代碼反編譯可以發(fā)現(xiàn) a+=1;被翻譯成了以下三條匯編指令：
mov         eax,dword ptr [a]
add         eax,1
mov         dword ptr [a],eax
 
 
如果在單核系統(tǒng)中,由于在上述三條指令的任何一條執(zhí)行完后都可能發(fā)生任務(wù)切換，比如執(zhí)行完第1條指令后就發(fā)生了任務(wù)切換，這時(shí)如果有其他任務(wù)來(lái)對(duì)a進(jìn)行操作的話，當(dāng)任務(wù)切換回來(lái)后，將繼續(xù)對(duì)a進(jìn)行操作，很可能出現(xiàn)不可預(yù)測(cè)的結(jié)果，因此上述三條指令必須使用鎖來(lái)保護(hù)，以使這段時(shí)間內(nèi)其他任務(wù)無(wú)法對(duì)a進(jìn)行操作。
需要注意的是，在多核系統(tǒng)中，因?yàn)槎鄠€(gè)CPU核在物理上是并行的，可能發(fā)生同時(shí)寫的現(xiàn)象；所以必須保證一個(gè)CPU核在對(duì)共享內(nèi)存進(jìn)行寫操作時(shí)，其他CPU核不能寫這塊內(nèi)存。因此在多核系統(tǒng)中和單核有區(qū)別，即使只有一條指令，也需要要加鎖保護(hù)。
如果使用原子操作來(lái)實(shí)現(xiàn)上述加1操作的話，例如使用VC里的InterlockedIncrement來(lái)操作的話，那么對(duì)a的加1操作需要以下語(yǔ)句
InterlockedIncrement (&a);
這條語(yǔ)句最終的實(shí)際加1操作會(huì)被翻譯成以下一條帶lock前綴的匯編指令：
lock xadd   dword ptr [ecx],eax
 
使用原子操作時(shí)，在進(jìn)行實(shí)際的寫操作時(shí)，使用了lock指令，這樣就可以阻止其他任務(wù)寫這塊內(nèi)存，避免出現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)現(xiàn)象。原子操作速度比鎖快，一般要快一倍以上。
使用lock前綴的指令實(shí)際上在系統(tǒng)中是使用了內(nèi)存柵障（memory barrier），當(dāng)原子操作在進(jìn)行時(shí)，其他任務(wù)都不能對(duì)內(nèi)存操作，會(huì)影響其他任務(wù)的執(zhí)行。因此這種原子操作實(shí)際上屬于一種激烈競(jìng)爭(zhēng)的鎖，不過(guò)由于它的操作時(shí)間很快，因此可以看成是一種極細(xì)粒度鎖。
在無(wú)鎖(Lock－free)編程環(huán)境中，主要使用的原子操作為CAS（Compare and Swap）操作，在VC里對(duì)應(yīng)的操作為InterlockedCompareExchange或者InterlockedCompareExchangeAcquire；如果是64位的操作，需要使用InterlockedCompareExchange64或者InterlockedCompareExchangeAcquire64。使用這種原子操作替代鎖的最大的一個(gè)好處是它是非阻塞的。
按照微軟MSDN的說(shuō)明，InterlockedCompareExchange帶有全局的內(nèi)存柵障(full memory barrier)，在使用了full memory barrier的情況下，即使不是訪問(wèn)同一內(nèi)存變量的原子操作也會(huì)發(fā)生競(jìng)爭(zhēng)，從競(jìng)爭(zhēng)形式上來(lái)講，會(huì)發(fā)生固定式鎖競(jìng)爭(zhēng)或隨機(jī)鎖競(jìng)爭(zhēng)現(xiàn)象，并且無(wú)法實(shí)現(xiàn)分布式鎖競(jìng)爭(zhēng)的競(jìng)爭(zhēng)模式，比起使用普通鎖的競(jìng)爭(zhēng)會(huì)更激烈，因此最終得到的加速比會(huì)比上一篇文章里講的固定式鎖競(jìng)爭(zhēng)還要糟糕。
對(duì)于象InterlockedCompareExchangeAcquire這類的原子操作，沒(méi)有使用full memory barrier，因此性能理論上會(huì)比使用full memory barrier的原子操作好很多（由于目前這類原子操作只有在特定的機(jī)器才支持，具體性能到底如何沒(méi)有測(cè)試過(guò)，微軟的MSDN里也對(duì)性能方面作出說(shuō)明）。但是如果采用固定式鎖競(jìng)爭(zhēng)形式，其加速比仍然是按照前面的固定式鎖競(jìng)爭(zhēng)的加速比公式來(lái)計(jì)算：

由于原子操作速度比鎖快，其實(shí)相比于普通鎖操作，相當(dāng)于加鎖解鎖時(shí)間 1減少了2～3倍左右，不妨以2倍來(lái)計(jì)算，對(duì)應(yīng)的任務(wù)粒度會(huì)增大一倍，為 ，另外由于原子操作內(nèi)的鎖內(nèi)計(jì)算通常只是簡(jiǎn)單一兩條指令，因此其鎖粒度很小，可以近似看成為0，因此加速比為：

因此在固定式鎖競(jìng)爭(zhēng)情況下，加速比的極限值約等于使用普通鎖時(shí)的2倍任務(wù)粒度大小，大約比使用 普通鎖時(shí)的加速比大一倍左右。加速比并不能隨CPU核數(shù)增長(zhǎng)而線性增加。
對(duì)于隨機(jī)式鎖競(jìng)爭(zhēng)情況，加速比為：
如果講普通鎖操作改成原子操作，將鎖粒度近似看成0，那么 ，對(duì)于任務(wù)粒度非常大的情況，概率p的增加并不大；對(duì)于任務(wù)粒度非常小的情況，概率p最大可以增大近似一倍，加速比相比于普通鎖也可以獲得一定程度的提高。
對(duì)于普通鎖隨機(jī)競(jìng)爭(zhēng)情況下的最壞情況，加速比為：

改成原子操作后，加速比為：

只是相對(duì)于普通鎖競(jìng)爭(zhēng)情況提高了一些，并不能隨CPU核數(shù)增加而增加。
注意上面沒(méi)有考慮無(wú)鎖編程的算法開銷，采用無(wú)鎖編程時(shí)，要完成一個(gè)CAS操作需要在一個(gè)循環(huán)里來(lái)完成，有可能要循環(huán)很多次才能完成一次寫操作，因此實(shí)際性能并達(dá)不到上面的計(jì)算結(jié)果。
因此即使使用無(wú)鎖編程，如果鎖競(jìng)爭(zhēng)形式仍然是固定式競(jìng)爭(zhēng)或隨機(jī)競(jìng)爭(zhēng)的形式，加速比性能仍然是不樂(lè)觀的，仍然跟分布式鎖競(jìng)爭(zhēng)的加速比差很遠(yuǎn)，因?yàn)榉植际芥i競(jìng)爭(zhēng)在最壞情況下加速比也可以做到接近CPU核數(shù)。
當(dāng)然有人也會(huì)提出，既然分布式鎖競(jìng)爭(zhēng)的加速比性能這么好，那么將原子操作替代普通鎖來(lái)進(jìn)行分布式競(jìng)爭(zhēng)，豈不是可以取得更好的加速比性能？理論上來(lái)說(shuō)，如果以不帶full memory barrier的原子操作來(lái)替代普通鎖進(jìn)行分布式競(jìng)爭(zhēng)，是可以取得比普通鎖進(jìn)行分布式競(jìng)爭(zhēng)更好的加速比，分布式加速比為 ，使用原子操作后，任務(wù)粒度將會(huì)增大2~3倍，對(duì)于任務(wù)粒度非常小的情況，比如任務(wù)粒度小于0.5（這種情況實(shí)際中很難出現(xiàn)），加速比將比使用普通鎖時(shí)增大一倍左右，對(duì)于任務(wù)粒度較大的情況，加速比增加并不明顯。
對(duì)于任務(wù)粒度的大小，很大程度上取決于程序員對(duì)任務(wù)的劃分，只要程序員在劃分任務(wù)時(shí)不要將任務(wù)粒度劃得太小，這樣就可以降低任務(wù)粒度對(duì)加速比造成的影響。
但是使用分布式鎖競(jìng)爭(zhēng)時(shí)，性能已經(jīng)可以和單核多任務(wù)時(shí)的程序性能接近了，使用無(wú)鎖編程難度非常高，程序復(fù)雜度也非常高，非專業(yè)人士難以掌握，普通程序員想要進(jìn)行無(wú)鎖編程幾乎是不可能的事情。而分布式編程的難度和以前單核多任務(wù)時(shí)代的數(shù)據(jù)結(jié)構(gòu)算法編程難度差不多，普通程序員都可以掌握。因此在實(shí)際情況中只要任務(wù)粒度不是太小，就沒(méi)有必要過(guò)于追求性能，使用普通鎖的分布式鎖競(jìng)爭(zhēng)已經(jīng)足夠了。
從目前無(wú)鎖編程的發(fā)展來(lái)看，已經(jīng)實(shí)現(xiàn)了的無(wú)鎖算法很有限，并且功能也很有限，并且無(wú)鎖編程是獨(dú)立于以前的單核時(shí)代的編程的，使用無(wú)鎖編程幾乎無(wú)法復(fù)用以前的成果。分布式編程是在原有的單核多任務(wù)編程基礎(chǔ)上發(fā)展而來(lái)，可以繼承以前單核時(shí)代的成果，比如隊(duì)列池便可以繼承已有的隊(duì)列算法，因此采用分布式編程可以大大減輕將現(xiàn)有單核程序移植到多核系統(tǒng)中的工作量，只要對(duì)現(xiàn)有程序進(jìn)行一些重構(gòu)即可完全支持多核CPU系統(tǒng)。
綜上所述，可以得到下表所示的結(jié)論
  比較項(xiàng)目 無(wú)鎖編程 分布式編程
1 加速比性能 取決于競(jìng)爭(zhēng)方式，除非也采用分布式競(jìng)爭(zhēng)，否則不如分布式鎖競(jìng)爭(zhēng)的性能 加速比和CPU核數(shù)成正比關(guān)系，接近于單核多任務(wù)時(shí)的性能
2 實(shí)現(xiàn)的功能 有限 不受限制
3 程序員掌握難易程度 難度太高，過(guò)于復(fù)雜，普通程序員無(wú)法掌握，目前世界上只有少數(shù)幾個(gè)人掌握。 和單核時(shí)代的數(shù)據(jù)結(jié)構(gòu)算法難度差不多，普通程序員可以掌握
4 現(xiàn)有軟件的移植 使用無(wú)鎖算法后，以往的算法需要廢棄掉，無(wú)法復(fù)用 可以繼承已有的算法，在已有程序基礎(chǔ)上重構(gòu)即可。

 
從上表的四個(gè)方面的綜合比較可以看出，無(wú)鎖編程的實(shí)用價(jià)值是遠(yuǎn)遠(yuǎn)不如分布式編程的，因此分布式編程比無(wú)鎖編程更適合多核CPU系統(tǒng)。         

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/drzhouweiming/archive/2007/09/27/1803695.aspx