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

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

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

首 先m必須大于等于k，否則無法保證至少有k個任務(wù)在運(yùn)行。子數(shù)據(jù)結(jié)構(gòu)個數(shù)N也必須大于K，否則出現(xiàn)競爭的任務(wù)組數(shù)將少于k個，從而無法保證至少有k個任務(wù) 在運(yùn)行，當(dāng)然n越大，任務(wù)出現(xiàn)競爭的概率就越小，同時運(yùn)行的線程數(shù)量就越多，不妨設(shè)n大于等于m。在實(shí)際情況中，n并不是越大越好，當(dāng) n過大時，由于鎖的數(shù)量和n相等，會導(dǎo)致鎖占用過多的系統(tǒng)資源。

下面就來計(jì)算一下至少有k個線程在同時運(yùn)行的概率，考慮一種最壞情況的假設(shè)：假設(shè)有兩個線程在訪問同一個子數(shù)據(jù)結(jié)構(gòu) ，那么它們一定會發(fā)生鎖競爭。在這種最壞假設(shè)下，要保證至少有k個線程在同時運(yùn)行 ，實(shí)際上相當(dāng)于m個線程至少訪問了k個不同的子數(shù)據(jù)結(jié)構(gòu)。

假設(shè)訪問每個子數(shù)據(jù)結(jié)構(gòu)的線程數(shù)為Xi （ 0 <= Xi <= m, i∈{1,2,…n}）,這樣可以得到以下整數(shù)方程：

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

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

下面是對這個概率公式的一些實(shí)際計(jì)算結(jié)果：

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

當(dāng)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))   當(dāng)n=4時，P=0.83; 當(dāng)n＝8時，P=0.919; 當(dāng)n＝16時, P=0.954

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

當(dāng)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)]   當(dāng)n＝8時，P=0.587; 當(dāng)n＝16時, P=0.886; 當(dāng)n＝32時，P=0.978

從上面計(jì)算可以看出，當(dāng)CPU核數(shù)固定時，線程數(shù)m越多，則概率愈大 ，子數(shù)據(jù)結(jié)構(gòu)個數(shù)n越大，概率愈大。一般來說線程數(shù)***比核數(shù)大一倍，這樣得出的概率會大一些。

以上計(jì)算的是在最壞情況下的概率，實(shí)際情況中，由于兩個線程在競爭同一個子數(shù)據(jù)結(jié)構(gòu)時并不一定會發(fā)生競爭現(xiàn)象，因?yàn)榭赡馨l(fā)生線程A在進(jìn)行鎖操作時，線程B正在執(zhí)行不需要加鎖部分的代碼，因此實(shí)際的概率會大于上面計(jì)算出的最壞情況下的概率。

分布式數(shù)據(jù)結(jié)構(gòu)隨機(jī)鎖競爭和無鎖編程的性能比較

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

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

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

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

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

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

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