王文義,王興啟

(中原工學(xué)院,鄭州 450007)

基于多核處理器的有鎖編程與非阻塞算法研究

王文義,王興啟

(中原工學(xué)院,鄭州 450007)

對(duì)在多核環(huán)境下的鎖的使用以及因硬件發(fā)展所帶來(lái)的無(wú)鎖編程模式進(jìn)行了研究.

多核處理器;鎖競(jìng)爭(zhēng);非阻塞算法;并行程序設(shè)計(jì)

并發(fā)事件與并行處理技術(shù)歷來(lái)是諸如氣象、材料、核物理、地質(zhì)勘探和航空航天等許多重要應(yīng)用領(lǐng)域中的核心工作.經(jīng)過(guò)長(zhǎng)期的研究與積累,傳統(tǒng)的并行程序設(shè)計(jì)方法已日趨成熟并已普遍被人們所接受[1].但當(dāng)今多核處理器(Chip M ultiProcesso r,CM P)的出現(xiàn)卻對(duì)這些傳統(tǒng)方法提出了嚴(yán)峻挑戰(zhàn),使這些算法要么失效,要么可用性大為降低.單核處理器由于受限于自身?xiàng)l件,其性能已達(dá)到極限,而多核處理器卻能夠以更低的頻率(低功耗)去處理更高的工作負(fù)載,既提高了處理器性能,又大幅降低了功耗,這恰恰是當(dāng)今所謂的綠色計(jì)算 GC(Green Computing)對(duì)計(jì)算機(jī)提出的目標(biāo)要求.問(wèn)題是:在盡最大可能承襲傳統(tǒng)方法的同時(shí)(無(wú)人希望耗資巨大開(kāi)發(fā)出的并行應(yīng)用程序因硬件的更新而報(bào)廢),我們?nèi)绾文軌虮M快找到可行的與多核技術(shù)相配的并行編程模式.

Am dahl將程序分為可加速與不可加速兩大部分[2].程序的加速比是同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間的比率,用它來(lái)衡量并行系統(tǒng)或程序并行化的性能和效果.加速比為:

式中:p為不可加速部分所占的比例;n為處理器的個(gè)數(shù).

由公式(1)可知,當(dāng) n→∞時(shí),S(n)=1/p,所以加速比的極限值為1/p,與處理器的個(gè)數(shù)無(wú)關(guān).就此而言,似乎多核處理器對(duì)提高加速比的前景并不被看好.

Gustafson定律提出了不同的假設(shè),用以證明加速系數(shù)可以超越Amdahl的限制.Gustafson認(rèn)為可以把軟件中的串行部分 p視為是固定的,并假設(shè)在單處理器上執(zhí)行 p所需要的時(shí)間為t,則在多核處理器上執(zhí)行時(shí)間為tm=pt+(1-p)t/n,所以加速比[2]為:

由公式(2)可知,因?yàn)榇胁糠?p不變,所以加速比S(n)將隨著 n的增加而增加.倘若現(xiàn)實(shí)情況的確與Gustafson的上述假設(shè)吻合的話(huà),那么軟件的性能可以隨著處理器個(gè)數(shù)的增加而增加.運(yùn)用Amdahl與Gustafson所提出的兩公式所得到的加速比差異如此之大,那么到底用哪一個(gè)更接近實(shí)際呢?

實(shí)際上在多核程序中,串行部分所占的比例并非是一成不變的,而加鎖保護(hù)導(dǎo)致的串行化便是其中重要的組成部分.在并行程序中,通過(guò)一定的算法,任務(wù)被劃分成多個(gè)子任務(wù),以便在各個(gè)節(jié)點(diǎn)上運(yùn)行.但對(duì)于各個(gè)節(jié)點(diǎn)來(lái)說(shuō),鎖的使用使程序只能在一個(gè)核上運(yùn)行,于是失去了多核的意義.通常處理器的個(gè)數(shù)越多,任務(wù)數(shù)量越大,加鎖保護(hù)所帶來(lái)的串行化就越嚴(yán)重.本文側(cè)重從鎖競(jìng)爭(zhēng)問(wèn)題入手,對(duì)程序加鎖問(wèn)題進(jìn)行分析,并對(duì)可用于多核環(huán)境中的并行編程模式進(jìn)行探討.

1 鎖競(jìng)爭(zhēng)導(dǎo)致的串行化

在雙核系統(tǒng)中,假如有2個(gè)線(xiàn)程A、B要使用同一把鎖,那么當(dāng)線(xiàn)程A獲取鎖后,在A(yíng)未解鎖前線(xiàn)程B將處于阻塞狀態(tài),這時(shí)只有線(xiàn)程A在運(yùn)行,2個(gè)CPU核中將只有一個(gè)得到利用,而另一個(gè)核則處于空閑狀態(tài).這里只是2個(gè)線(xiàn)程的情況,實(shí)際上在多核處理器中會(huì)有很多線(xiàn)程[3-4],如果這些線(xiàn)程都去競(jìng)爭(zhēng)同一把鎖,則會(huì)使問(wèn)題的復(fù)雜度大為增加.擬考慮使用3種方法來(lái)解決這個(gè)問(wèn)題.

1.1 復(fù)制獨(dú)占訪(fǎng)問(wèn)資源

要避免鎖競(jìng)爭(zhēng),最好的方法就是對(duì)資源進(jìn)行復(fù)制,讓每個(gè)線(xiàn)程都擁有一個(gè)私有的副本,讓線(xiàn)程對(duì)獨(dú)占資源的訪(fǎng)問(wèn)變成對(duì)自己副本的訪(fǎng)問(wèn).如果需要的話(huà),在程序最后可以將這些副本合并成一個(gè)單一的共享資源副本.例如,如果獨(dú)占資源是一個(gè)計(jì)數(shù)器,就可以讓每個(gè)線(xiàn)程都有一個(gè)私有的計(jì)數(shù)器,最后如果需要計(jì)算計(jì)數(shù)值總和,就可以在所有線(xiàn)程都完成計(jì)數(shù)以后,再將各私有計(jì)數(shù)器的結(jié)果累加起來(lái).

1.2 有鎖編程——競(jìng)爭(zhēng)多把鎖

如果某個(gè)資源上的鎖無(wú)法消除,就可以考慮將資源劃分成若干個(gè)部分,然后用彼此獨(dú)立的鎖分別給予保護(hù).通過(guò)這種方法可以將一個(gè)數(shù)據(jù)結(jié)構(gòu)或散列表劃分成多個(gè)子結(jié)構(gòu)或子表,將原來(lái)對(duì)整個(gè)結(jié)構(gòu)或表的競(jìng)爭(zhēng)轉(zhuǎn)變?yōu)楦?jìng)爭(zhēng)多個(gè)子鎖.如圖1所示,在對(duì)一棵樹(shù)進(jìn)行訪(fǎng)問(wèn)時(shí),若有2個(gè)線(xiàn)程需要訪(fǎng)問(wèn),傳統(tǒng)的方法是線(xiàn)程1在執(zhí)行時(shí),首先獲得訪(fǎng)問(wèn)的鎖,然后才能進(jìn)行訪(fǎng)問(wèn),當(dāng)訪(fǎng)問(wèn)結(jié)束的時(shí)候,就釋放鎖,然后再進(jìn)行線(xiàn)程2訪(fǎng)問(wèn).可以把整個(gè)樹(shù)分成3個(gè)鎖,即對(duì)根節(jié)點(diǎn)下的3個(gè)節(jié)點(diǎn)分別上鎖,而對(duì)整個(gè)樹(shù)則不加鎖,這樣如果線(xiàn)程1在對(duì)子樹(shù)節(jié)點(diǎn)1進(jìn)行訪(fǎng)問(wèn)的時(shí)候,而線(xiàn)程2則可以對(duì)其余2節(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn),于是就可以實(shí)現(xiàn)線(xiàn)程的并行,從而大大減少訪(fǎng)問(wèn)的時(shí)間.

圖1 將樹(shù)的訪(fǎng)問(wèn)化為對(duì)子結(jié)構(gòu)的訪(fǎng)問(wèn)以化解競(jìng)爭(zhēng)

競(jìng)爭(zhēng)多把鎖又稱(chēng)為分布式鎖競(jìng)爭(zhēng),相關(guān)的設(shè)計(jì)模式有2種:多核編程中的線(xiàn)程分組競(jìng)爭(zhēng)模式和線(xiàn)程隨機(jī)競(jìng)爭(zhēng)模式 .

(1)線(xiàn)程分組競(jìng)爭(zhēng)模式.如圖2所示,有2個(gè)線(xiàn)程需要執(zhí)行.在線(xiàn)程執(zhí)行中,對(duì)同一線(xiàn)程不能同時(shí)執(zhí)行添加和刪除動(dòng)作.圖2中的4個(gè)線(xiàn)程動(dòng)作分成2組執(zhí)行:添加線(xiàn)程1(或刪除線(xiàn)程1)和添加線(xiàn)程2(或刪除線(xiàn)程2)之間不存在鎖競(jìng)爭(zhēng),可以并行執(zhí)行.這只是2組線(xiàn)程的分組競(jìng)爭(zhēng).在n個(gè)CPU核的情況下,如果將線(xiàn)程組數(shù)控制在≥n的時(shí)候,則至少在同一時(shí)間有 n個(gè)線(xiàn)程在執(zhí)行.這樣就可以保證CPU不會(huì)產(chǎn)生閑置現(xiàn)象.

圖2 線(xiàn)程分組競(jìng)爭(zhēng)示意圖

(2)線(xiàn)程隨機(jī)競(jìng)爭(zhēng)模式.分組競(jìng)爭(zhēng)模式雖然能避免鎖的競(jìng)爭(zhēng),但并不是任意的共享數(shù)據(jù)都能夠采用這種模式,比如在數(shù)據(jù)結(jié)構(gòu)和圖中,對(duì)于不同的子結(jié)構(gòu)或子圖來(lái)說(shuō),分組競(jìng)爭(zhēng)模式雖然可以有效避免鎖的競(jìng)爭(zhēng),但是對(duì)于同一個(gè)子結(jié)構(gòu)或子圖,如果查找的數(shù)據(jù)恰好位于同一個(gè)子結(jié)構(gòu)或子圖中,則鎖競(jìng)爭(zhēng)仍不可避免.

在這種分布式數(shù)據(jù)結(jié)構(gòu)的隨機(jī)鎖競(jìng)爭(zhēng)中,需要掌握的是在一個(gè)有 k個(gè)CPU核的機(jī)器上,線(xiàn)程數(shù) m和劃分的子數(shù)據(jù)結(jié)構(gòu)個(gè)數(shù)n究竟為多少時(shí),才能保證至少有k個(gè)線(xiàn)程在并行運(yùn)行時(shí)的概率不低于給定的概率P.在通常情況下,n越大,各子任務(wù)出現(xiàn)競(jìng)爭(zhēng)的概率就越小,而運(yùn)行的線(xiàn)程數(shù)量就越多,所以可以設(shè)n≥m.在實(shí)際情況中,n并不是越大越好,因?yàn)楫?dāng) n過(guò)大時(shí),由于鎖的數(shù)量和 n相等,它會(huì)占用過(guò)多的系統(tǒng)資源,而這是我們所不希望的.

在計(jì)算至少有k個(gè)線(xiàn)程在同時(shí)(并行)運(yùn)行的概率P的時(shí)候,如果發(fā)生鎖競(jìng)爭(zhēng),則對(duì)于同一個(gè)子數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō),至少在同一時(shí)刻有2個(gè)線(xiàn)程需要訪(fǎng)問(wèn)它.這時(shí)就至少有k個(gè)不同的子數(shù)據(jù)結(jié)構(gòu)被所有的m個(gè)線(xiàn)程訪(fǎng)問(wèn).假設(shè)訪(fǎng)問(wèn)每個(gè)子數(shù)據(jù)結(jié)構(gòu)的線(xiàn)程數(shù)為 Xi(0≤Xi≤m,i∈{1,2,…,n}),則有整數(shù)方程:

要保證至少有k個(gè)線(xiàn)程在競(jìng)爭(zhēng),就要保證上述方程中至少有k個(gè)大于0的解,則能保證至少有 k個(gè)線(xiàn)程在并行運(yùn)行.

方程(3)的解的總個(gè)數(shù)為 Cn-1m+n-1,方程至少有 k個(gè)線(xiàn)程在運(yùn)行的概率為故概率

通過(guò)前面的分析可知,子數(shù)據(jù)結(jié)構(gòu)越多,則線(xiàn)程對(duì)于同一個(gè)子數(shù)據(jù)結(jié)構(gòu)競(jìng)爭(zhēng)的概率就越小.當(dāng)然,CPU的核數(shù)越多,可同時(shí)并行處理的子數(shù)據(jù)結(jié)構(gòu)也就越多,故線(xiàn)程競(jìng)爭(zhēng)同一把鎖的概率也就越小.例如:

當(dāng) k=2,m=4,n=4時(shí),則 P=0.886;

當(dāng)k=4,m=4,n=4時(shí),則 P=0.03;

……

由數(shù)據(jù)可知:在CPU的核數(shù)固定且子數(shù)據(jù)結(jié)構(gòu)相同的情況下,線(xiàn)程數(shù) m越大,則線(xiàn)程競(jìng)爭(zhēng)同一把鎖的概率也就越大.

1.3 非阻塞算法

鎖競(jìng)爭(zhēng)導(dǎo)致了程序的串行化,那么能不能不使用鎖呢?不使用鎖的算法稱(chēng)為非阻塞算法(nonblocking),也叫無(wú)鎖編程模式.多數(shù)非阻塞算法都包含一個(gè)循環(huán),該循環(huán)試圖執(zhí)行由一個(gè)或多個(gè)由比較并交換(Compare-and-sw ap,CAS)操作組成的動(dòng)作,如果某次CAS操作失敗,就重新執(zhí)行整個(gè)動(dòng)作.例如,若要對(duì)一指定的變量m進(jìn)行加1操作,則其有鎖代碼如下:

這種算法,避免了鎖的使用,同時(shí)也就消除了競(jìng)爭(zhēng),線(xiàn)程可以持續(xù)執(zhí)行.

2 鎖與無(wú)鎖編程分析

對(duì)于復(fù)制獨(dú)占訪(fǎng)問(wèn)資源這種方法來(lái)說(shuō),如果任務(wù)可以拆分的話(huà),這無(wú)疑是一種很好的方法.這種方法比較簡(jiǎn)單而且易于理解.然而現(xiàn)實(shí)中的許多問(wèn)題并不能通過(guò)簡(jiǎn)單的拆分來(lái)解決.所以不得不使用有鎖編程和非阻塞算法2種方法[7—8].對(duì)于前者而言,由于以前的程序都基于單核,程序員對(duì)于鎖的使用比較容易,同時(shí)這種編程難度比較小,易于理解和掌握.但由于無(wú)鎖編程是發(fā)生在線(xiàn)程掛起的情況下,其他線(xiàn)程并沒(méi)有受到影響,這無(wú)疑可以加快程序的運(yùn)行.而在有鎖編程中,一旦持有該鎖的線(xiàn)程被掛起,其他線(xiàn)程將被阻塞.如果鎖的獲得是按照先來(lái)先服務(wù)的順序,那么這種情況將會(huì)更加糟糕,因?yàn)橐坏┣懊娴囊粋€(gè)線(xiàn)程被掛起,那么后面等待獲取該鎖的線(xiàn)程都將被阻塞,如圖3所示.

圖3 鎖競(jìng)爭(zhēng)引起的線(xiàn)程阻塞

在無(wú)鎖編程中,由于使用了串行化的原子操作,所以單從執(zhí)行效率上來(lái)說(shuō)它可以被視為是一種速度更快的鎖.這種方法相對(duì)于等價(jià)的有鎖算法來(lái)說(shuō)要復(fù)雜的多,往往還需要考慮更多額外的因素.例如,在線(xiàn)程的安全載入操作(fetch-and-op)中,假如要讀取一個(gè)數(shù)(存儲(chǔ)單元為 m),并對(duì)它進(jìn)行計(jì)算,最后存儲(chǔ)該值.代碼如下:

由此可以看出,從代碼行數(shù)量上來(lái)說(shuō),無(wú)鎖編程較之于單線(xiàn)程編程,程序量顯然是增加了,同時(shí),它還增加了計(jì)算量,而且計(jì)算要遵從阿姆爾達(dá)定律,因此其加速比性能會(huì)隨著CPU核數(shù)的增加而降低[9].特別地,若在m_old=m和InterlockedCompareExchange之間有另一處理器要對(duì)其進(jìn)行fetch-and-op操作,若原處理器讀到的m的初值為A,而另一處理器先將其修改為B,然后又改回A.此時(shí)原處理器在執(zhí)行的時(shí)候,它所看到的m值并沒(méi)有發(fā)生變化,盡管對(duì)此我們可以采用內(nèi)存垃圾回收機(jī)制來(lái)解決,但這卻加大了程序出錯(cuò)的風(fēng)險(xiǎn).

3 結(jié) 語(yǔ)

與單核計(jì)算機(jī)相比,多核計(jì)算機(jī)能夠以較低的頻率和能耗去處理更多的任務(wù),但它的出現(xiàn)卻也帶來(lái)了諸多新的問(wèn)題,因?yàn)樗沟孟到y(tǒng)變得更加復(fù)雜,同時(shí)也使編程難度大為增加.本文主要從多核環(huán)境所帶來(lái)的編程模式問(wèn)題入手,側(cè)重對(duì)多核環(huán)境下因鎖的使用所帶來(lái)的程序串行化問(wèn)題進(jìn)行了深入分析,希望所述問(wèn)題能對(duì)從事多核編程的讀者有所啟發(fā).

[1] Hwang Kai.高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)——并行性、可擴(kuò)展性、可編程性[M].王鼎興,譯.北京:清華大學(xué)出版社,1995.

[2] 周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢:華中科技出版社,2009.

[3] 李寶峰,富弘毅,李韜譯.多核程序設(shè)計(jì)技術(shù)——通過(guò)軟件多線(xiàn)程提升性能[M].北京:電子工業(yè)出版社,2007.

[4] 湯彬,李培耀.Window s下多線(xiàn)程編程技術(shù)[J].上海工程技術(shù)大學(xué)學(xué)報(bào),2002,16(4):320-328.

[5] 伊君翰.基于多核處理器的并行編程模型[J].計(jì)算機(jī)工程,2009,35(8):62-65.

[6] 武華北,孫濟(jì)洲,王文義.面向混合并行計(jì)算系統(tǒng)編程環(huán)境的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué),2010(4):143-145.

[7] Rajwar R,Goodman J.Transactional Lock-free execution of Lock-based Program s[C]//Proc.10thInt.Conf.A rchitectural Support fo r Programming Languages and Operating System s.San Jose,California:ACM p ress,2002:5-17.

[8] Philippas Hang Y.Integrating Non-blocking Synchronisation in Parallel App lications:Perfo rmance Advantages and Methodologics[C]//.Proc.Of the 3rdACM Wo rkshop on Software and Perfo rmance.San Jose,California:ACM Press,2002:55-67.

[9] Shameem A,Jason R.多核程序設(shè)計(jì)技術(shù)——通過(guò)軟件多線(xiàn)程提升性能[M].北京:電子工業(yè)出版社,2007.

Study of the Lock’s Programm ing and Non-lock Algorithm Based on M ulti-core Processors

WANGWen-yi,WANG Xing-qi
(Zhongyuan U niversity of Technology,Zhengzhou 450007,China)

This paper focused on the use of the lock in the M ulti-core environment and the non-lock p rogramming mode w hich caused by the development of hardware.

multi-co re p rocesso r;lock competition;non-block algo rithm;parallel p rogramm ing

TP301

A DO I:10.3969/j.issn.1671-6906.2010.04.004

1671-6906(2010)04-0015-04

2010-07-13

河南省基礎(chǔ)與前沿技術(shù)研究項(xiàng)目(082300410300)

王文義(1947-),男,河南洛陽(yáng)人,教授.