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

王文義,王興啟

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

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

王文義,王興啟

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

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

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

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

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

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

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

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

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

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

1 鎖競爭導(dǎo)致的串行化

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

1.1 復(fù)制獨占訪問資源

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

1.2 有鎖編程——競爭多把鎖

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

圖1 將樹的訪問化為對子結(jié)構(gòu)的訪問以化解競爭

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

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

圖2 線程分組競爭示意圖

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

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

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

要保證至少有k個線程在競爭,就要保證上述方程中至少有k個大于0的解,則能保證至少有 k個線程在并行運行.

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

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

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

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

……

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

1.3 非阻塞算法

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

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

2 鎖與無鎖編程分析

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

圖3 鎖競爭引起的線程阻塞

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

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

3 結(jié) 語

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

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

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

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

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

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

[6] 武華北,孫濟洲,王文義.面向混合并行計算系統(tǒng)編程環(huán)境的研究與實現(xiàn)[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è)計技術(shù)——通過軟件多線程提升性能[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ù)研究項目(082300410300)

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