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

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

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

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

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

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

本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/drzhouweiming/archive/2007/09/27/1803695.aspx