前一篇多核編程中的線程分組競爭模式中談到了讓線程分組競爭以解決多核CPU遇到的鎖競爭導致的饑餓問題。

并 不是任意的共享數據都能夠設計成進行分組競爭的模式，比如最常用的需要用于查找的數據結構，當數據結構分成多個子數據結構后，每次查找時，不能指定查找某 個特定的子數據結構，而必須進行二級查找，先在整個數據結構內找到對應的子數據結構（不加鎖），然后再在子數據結構中查找（加鎖）。如果同時多個線程進行 查找，有可能查找的數據分布在不同的子數據結構里，也可能分布在同一子數據結構中。當查找分布在同一子數據結構時，這時就有可能發生鎖競爭現象，從而引起 CPU饑餓的發生。

在這種分布式數據結構的隨機鎖競爭中，需要知道的是在一個k個核的CPU上，需要的線程數m和劃分的子數據結構個數n為多少時，才能保證至少有k個線程在同時運行的概率不低于給定的概率P。

首 先m必須大于等于k，否則無法保證至少有k個任務在運行。子數據結構個數N也必須大于K，否則出現競爭的任務組數將少于k個，從而無法保證至少有k個任務 在運行，當然n越大，任務出現競爭的概率就越小，同時運行的線程數量就越多，不妨設n大于等于m。在實際情況中，n并不是越大越好，當 n過大時，由于鎖的數量和n相等，會導致鎖占用過多的系統資源。

下面就來計算一下至少有k個線程在同時運行的概率，考慮一種最壞情況的假設：假設有兩個線程在訪問同一個子數據結構 ，那么它們一定會發生鎖競爭。在這種最壞假設下，要保證至少有k個線程在同時運行 ，實際上相當于m個線程至少訪問了k個不同的子數據結構。

假設訪問每個子數據結構的線程數為Xi （ 0 <= Xi <= m, i∈{1,2,…n}）,這樣可以得到以下整數方程：

X1+X2+…+Xn = m                （方程1）

要保證至少有k組線程在競爭，實際上相當于X1,X2…Xn中必須至少有k個大于0，這樣至少有k個線程在運行的概率相當于上述方程滿足,X2…Xn中必須至少有k個大于0的解的個數和所有可能解的個數的比值。

下面是對這個概率公式的一些實際計算結果：

當k=2（2核CPU）, m=2（2個線程）， P=(n-1) / (n+1)    當n=4時，P=0.6; 當n＝8時，P=7/9 =0.7778; 當n＝16時, P=15/17=0.882

當k=2（2核CPU）, m=4（4個線程）， P=(n-1) (n＋3)/ ((n+1)(n+2)) + 9 (n-1)/((n+3)(n+2)(n+1))   當n=4時，P=0.83; 當n＝8時，P=0.919; 當n＝16時, P=0.954

當k=4（4核CPU）, m=4（4個線程）， P=(n-1) (n-2)(n-3)/ ((n+1)(n+2)(n+3))   當n=4時，P=0.0286; 當n＝8時，P=0.212; 當n＝16時, P=0.47; 當n＝32時，P=0.687

當k=4（4核CPU）, m=6（6個線程）， P = [ 1+12(n+15)/((n+4)(n+5)) ] ×[(n-1)(n-2)(n-3)]/ [(n+1)(n+2)(n+3)]   當n＝8時，P=0.587; 當n＝16時, P=0.886; 當n＝32時，P=0.978

從上面計算可以看出，當CPU核數固定時，線程數m越多，則概率愈大 ，子數據結構個數n越大，概率愈大。一般來說線程數***比核數大一倍，這樣得出的概率會大一些。

以上計算的是在最壞情況下的概率，實際情況中，由于兩個線程在競爭同一個子數據結構時并不一定會發生競爭現象，因為可能發生線程A在進行鎖操作時，線程B正在執行不需要加鎖部分的代碼，因此實際的概率會大于上面計算出的最壞情況下的概率。

分布式數據結構隨機鎖競爭和無鎖編程的性能比較

在 使用了隨機鎖競爭的分布式數據結構中，并行化的加速比期望值等于前面所計算出的概率×CPU核數，因此只要將概率保持大于一定的值，那么加速比是可以得到 保證的，并且只要加大線程個數和子數據結構個數，那么加速比的期望值就會增加。另外分布式數據結構中相比于單線程的數據結構其操作要復雜一些，增加了一些 計算開銷，另外加上鎖的計算開銷，因此加速比要打一個較大的折扣。但是分布式數據結構的好處在于它的加速比系數不會隨CPU核數的增加而降低，程序的性能 是隨著核數的增加而線形增加的（前提是在數據 結構中的元素個數足夠多的情況下）。

在 無鎖編程中，由于使用了原子操作，原子操作是串行化的，雖然原子操作占的比重很小，但是這種串行化反映到加速比計算上需要按照阿姆爾達定律來計算，因此其 性能同樣不容樂觀，會隨著CPU核數的增加而降低。以一個無鎖的FIFO隊列為例，在進隊操作時需要使用一條CAS原子操作，由于隊列操作本身就很簡單， 因此昂貴的CAS操作所占的比例也不容小覷，在這種隊列操作中，CAS所占的比例估計要達到20％左右（具體的數據需要通過測試才能確定），按照阿姆爾達 定律，在一個8核的 CPU上的加速比系數將為3.33, 在一個64核CPU上，其加速比將小于5，當然這是只考慮隊列操作沒有考慮程序中其他并行操作的極端情況，但是不管怎么說，采用無鎖編程的話，加速比系數 會隨CPU核數的增加而降低。

另外無鎖編程相比于單線程編程，其代碼也變復雜了，也增加了額外的計算開銷，加速比也需要另外打一個折扣。

如 果將分布式數據結構和單核時的多線程編程相比，則分布式數據結構中，僅僅增加了定位到子數據結構的開銷，如果是查找類型的數據結構，子表的查找時間縮小 了，實際上增加的開銷小于定位子數據結構的開銷。因此分布式數據結構增加的開銷所占的比例是非常小的，其性能近似（略低）于單核時的多線程編程。

在 CPU核數較少時，無鎖編程的性能可能會優于分布式數據結構，并且優于單核多線程編程的性能，但是當CPU核數增加到一定程度時，分布式數據結構的性能優 勢就體現出來了。采用分布式數據結構可以復用部分單線程時的數據結構代碼，采用加鎖機制容易被程序員理解，并且實現的功能不受限制。而無鎖編程則難度非常 高，遠非普通程序員所能掌握，并且實現的功能受到限制，比如實現一個無鎖的隊列，如果想要給隊列加一個計數來掌握隊列中有多少元素，采用無鎖編程實現估計 就很難行得通了，而這在有鎖編程中只是一個簡單得不能再簡單的東西。因此對程序員來說，分布式數據結構是多核時代必需掌握的技術，而無鎖編程也許可以用在 某些無法使用分布式數據結構的特定場合。

需 要說明的是前面對概率的計算隱含了一個前提，就是每個線程在訪問各個子數據結構時的概率是相同的，這要求各個子數據結構必須是負載均衡的，否則如果訪問各 個子數據結構的概率不相同的話，計算出的結果會小于前面的計算結果，考慮一種最極端的情況，所有的數據都在一個子數據結構里，那么所有的線程都將競爭同一 個子數據結構，那么問題倒退回多核編程中的鎖競爭難題一文中描述一樣的情況，這是一種可能比阿姆爾達定律更糟糕的情況。100％的負載均衡是做不到的，所 幸可以通過一定的手段來使數據盡量變得均衡，使得數據能夠相對較均勻地分布在各個子數據結構中，這樣就不會對最終的概率產生較大影響。

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