多核編程中的線程隨機(jī)競爭模式的概率分析

這篇文章主要講解了“多核編程中的線程隨機(jī)競爭模式的概率分析”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“多核編程中的線程隨機(jī)競爭模式的概率分析”吧！

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供鞏義網(wǎng)站建設(shè)、鞏義做網(wǎng)站、鞏義網(wǎng)站設(shè)計(jì)、鞏義網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、鞏義企業(yè)網(wǎng)站模板建站服務(wù)，10多年鞏義做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

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

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

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

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

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

X1+X2+&hellip;+Xn = m                （方程1）

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

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

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

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

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

當(dāng)k=4（4核CPU）, m=6（6個(gè)線程）， P = [ 1+12(n+15)/((n+4)(n+5)) ] &times;[(n-1)(n-2)(n-3)]/ [(n+1)(n+2)(n+3)]   當(dāng)n＝8時(shí)，P=0.587; 當(dāng)n＝16時(shí), P=0.886; 當(dāng)n＝32時(shí)，P=0.978

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

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

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

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

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

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

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

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

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

感謝各位的閱讀，以上就是“多核編程中的線程隨機(jī)競爭模式的概率分析”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對多核編程中的線程隨機(jī)競爭模式的概率分析這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！

標(biāo)題名稱：多核編程中的線程隨機(jī)競爭模式的概率分析
鏈接URL：http://muchs.cn/article20/gdepco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、App開發(fā)、微信小程序、商城網(wǎng)站、電子商務(wù)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)