王磊曹龍漢,2

（1.重慶郵電大學(xué)通信工程學(xué)院，重慶 400065 2.重慶通信學(xué)院控制工程重點(diǎn)實(shí)驗(yàn)室，重慶 400035）

引言：近年來(lái)，隨著 GNU（GNU's Not Unix）旗下的linux操作系統(tǒng)的蓬勃發(fā)展，GNU發(fā)布的C庫(kù)--Glibc的使用幾乎無(wú)處不在。與此同時(shí)，由于CPU性能的提高特別是多核技術(shù)的出現(xiàn)，無(wú)論在服務(wù)器級(jí)應(yīng)用還是嵌入式程序中都普遍使用了多線程技術(shù)，而互斥鎖正是解決多線程技術(shù)中同步與資源互斥問(wèn)題的常用手段。Glibc庫(kù)提供的互斥鎖為pthread_mutex_t，一方面，互斥鎖提供了資源互斥和任務(wù)同步的功能[1][2]；另一方面，濫用互斥鎖也會(huì)導(dǎo)致應(yīng)用程式出現(xiàn)死鎖與程序性能低下等問(wèn)題。一個(gè)有效地互斥鎖統(tǒng)計(jì)工具應(yīng)具有以下功能：（1）記錄互斥鎖的最近操作，以便程序發(fā)生死鎖時(shí)進(jìn)行分析；（2）統(tǒng)計(jì)程序運(yùn)行后互斥鎖的各種操作次數(shù)，特別是阻塞發(fā)生次數(shù)，以便應(yīng)用程序性能優(yōu)化時(shí)使用。

目前，針對(duì)C庫(kù)進(jìn)行互斥鎖統(tǒng)計(jì)的軟件并不多，主要原因是：（1）在用戶態(tài)對(duì)C庫(kù)互斥鎖統(tǒng)計(jì)準(zhǔn)確度不高；（2）互斥鎖一般使用在多線程環(huán)境，此時(shí)資源競(jìng)爭(zhēng)狀況往往十分頻繁，添加不適宜的統(tǒng)計(jì)操作會(huì)嚴(yán)重影響應(yīng)用程序的效率，甚至改變線程間的執(zhí)行順序；（3）由于統(tǒng)計(jì)是在多線程環(huán)境執(zhí)行，必然會(huì)遇到資源競(jìng)爭(zhēng)，如果再使用互斥手段避免沖突，就會(huì)陷入循環(huán)統(tǒng)計(jì)。

由于使用互斥鎖不當(dāng)導(dǎo)致的死鎖和效率低下問(wèn)題幾乎在每一個(gè)軟件中都出現(xiàn)過(guò)，所以開(kāi)發(fā)一種互斥鎖統(tǒng)計(jì)工具，對(duì)于排查應(yīng)用程序故障特別是在項(xiàng)目的開(kāi)發(fā)測(cè)試階段進(jìn)行排查是非常有意義的。本文提出一種統(tǒng)計(jì)互斥鎖使用情況的方法，程序員可以根據(jù)統(tǒng)計(jì)結(jié)果優(yōu)化或排查應(yīng)用程序的互斥鎖使用情況，從而減小使用互斥鎖帶來(lái)的負(fù)面效應(yīng)。

2 互斥鎖統(tǒng)計(jì)算法的原理。本文使用哈希算法查詢技術(shù)查找mutex統(tǒng)計(jì)對(duì)象，使用循環(huán)隊(duì)列技術(shù)記錄mutex近期的操作，使用原子操作解決資源沖突的情況。

2.1 哈希算法簡(jiǎn)介。用來(lái)產(chǎn)生一些數(shù)據(jù)片段（例如消息或會(huì)話項(xiàng)）的哈希值的算法叫哈希算法[3][4][5]，它是信息存儲(chǔ)和查詢所用的一項(xiàng)基本技術(shù)，基于Hash函數(shù)的文件構(gòu)造方法，可實(shí)現(xiàn)對(duì)記錄的快速隨機(jī)存取。哈希算法把給定的任意長(zhǎng)關(guān)鍵字映射為一個(gè)固定長(zhǎng)度的哈希值，一般用于鑒權(quán)、認(rèn)證、加密、索引等。使用好的哈希算法，在輸入數(shù)據(jù)中所做的更改就可以更改結(jié)果哈希值中的所有位。

哈希算法也稱為"哈希函數(shù)"。主要優(yōu)點(diǎn)是運(yùn)算簡(jiǎn)單，預(yù)處理時(shí)間較短，內(nèi)存消耗低，匹配查找速度比較快，便于維護(hù)和刷新，支持匹配規(guī)則數(shù)多等。好的Hash算法具有以下三個(gè)性質(zhì)：

(1)單向性。給定一個(gè)輸入數(shù)，容易計(jì)算出它的哈希值，但是已知一個(gè)哈希值根據(jù)同樣的算法不能得到原輸入數(shù)。

(2)弱抗碰撞性。給定一個(gè)輸入數(shù)，要找到另一個(gè)得到給定數(shù)的哈希值，在使用同一種方法時(shí)，在計(jì)算上不可行。

(3)強(qiáng)抗碰撞性。對(duì)于任意兩個(gè)不同的輸入數(shù)，根據(jù)同樣的算法計(jì)算出相同的哈希值，在計(jì)算上不可行。

然而，要實(shí)現(xiàn)哈希算法，完全滿足上述三個(gè)性質(zhì)幾乎是不可能的。實(shí)際上，哈希算法用于分類時(shí)，需要考慮不同關(guān)鍵字之間哈希值可能發(fā)生的地址沖突。當(dāng)發(fā)生沖突時(shí)，一般采用開(kāi)放定址法來(lái)解決沖突，即建立沖突解除區(qū)，并使用鏈表在沖突解除區(qū)中存放沖突的關(guān)鍵字。如圖1所示，當(dāng)不同的輸入產(chǎn)生相同的Hash值時(shí)，后輸入的數(shù)將被以鏈表的形式存放在沖突解除區(qū)(哈希桶)中。沖突的數(shù)越多，該Hash值后面的鏈表越長(zhǎng)。在進(jìn)行信息檢索時(shí)，如果所需的信息存放在沖突解除區(qū)，就需要遍歷沖突解除區(qū)中的鏈表。

2.2 互斥鎖統(tǒng)計(jì)對(duì)象的哈希表查找方法。本統(tǒng)計(jì)中的哈希表是根據(jù)哈希算法由C語(yǔ)言實(shí)現(xiàn)的，為了達(dá)到統(tǒng)計(jì)算法的要求，我們使用了以下幾個(gè)關(guān)鍵技術(shù)：

圖1 哈希表結(jié)構(gòu)

1 )使用面向?qū)ο蠹夹g(shù)，針對(duì)每個(gè)哈希表對(duì)象封裝了一套自定義的哈希算法、哈希表遍歷操作；

2 )使用除余法來(lái)構(gòu)建哈希函數(shù)。由于使用mutex對(duì)象的指針對(duì)作為鍵值，考慮到程序?qū)嶋H運(yùn)行時(shí)mutex指針前兩個(gè)字節(jié)變化較少后兩個(gè)字節(jié)變化頻繁的特點(diǎn)，讓其前后兩個(gè)字節(jié)的異或做除余法。即，異或值除以哈希表的桶數(shù)（哈希表的容量）作為哈希值；

3 )使用開(kāi)放定址法來(lái)處理沖突。如圖1，當(dāng)出現(xiàn)哈希值沖突的情況，在桶中建立一個(gè)鏈表，解決沖突。

2.3 互斥鎖近期操作的循環(huán)隊(duì)列記錄方法。循環(huán)隊(duì)列[6]是指循環(huán)利用的隊(duì)列，具有隊(duì)列的先進(jìn)先出特性，同時(shí)在隊(duì)列被寫滿后循環(huán)到隊(duì)列首部保存下一次數(shù)據(jù)。由于記錄互斥鎖操作只關(guān)心最近N次的操作內(nèi)容，所以循環(huán)隊(duì)列完全可以滿足要求，并且還可以節(jié)約軟件的空間消耗。

循環(huán)隊(duì)列使用兩個(gè)變量--隊(duì)列頭和隊(duì)列尾記錄隊(duì)列的開(kāi)始和結(jié)束，其關(guān)鍵算法為隊(duì)列頭或尾的上移（標(biāo)志減一）和下移（標(biāo)志加一）。設(shè)pos為當(dāng)前位置，n_pos為移位后的位置，volume為循環(huán)隊(duì)列的容量，則上移（標(biāo)志減一）算法為：

n_pos=(volume+pos-1)%volume

下移（標(biāo)志加一）算法為：

n_pos=(pos+1)%volume

2.4 互斥鎖資源沖突的原子操作方法。所謂原子操作是指不會(huì)被線程調(diào)度機(jī)制打斷的操作，這種操作一旦開(kāi)始，就一直運(yùn)行到結(jié)束，中間不會(huì)被切換到另一個(gè)線程。

原子操作是不可分割[7]的，在執(zhí)行完畢不會(huì)被任何其它任務(wù)或事件中斷。在單處理器系統(tǒng)(UniProcessor)中，能夠在單條指令中完成的操作都可以認(rèn)為是“ 原子操作”，因?yàn)橹袛嘀荒馨l(fā)生于指令之間。這也是某些CPU指令系統(tǒng)中引入了test_and_set、test_and_clear等指令用于臨界資源互斥的原因。但是，在對(duì)稱多處理器（Symmetric Multi-Processor）結(jié)構(gòu)中就不同了，由于系統(tǒng)中有多個(gè)處理器在獨(dú)立地運(yùn)行，即使能在單條指令中完成的操作也有可能受到干擾。我們以decl（遞減指令）為例，這是一個(gè)典型的"讀－改－寫"過(guò)程，涉及兩次內(nèi)存訪問(wèn)。設(shè)想在不同CPU運(yùn)行的兩個(gè)進(jìn)程都在遞減某個(gè)計(jì)數(shù)值，可能發(fā)生的情況是：（1）CPU A（CPU A上所運(yùn)行的進(jìn)程，以下同）從內(nèi)存單元把當(dāng)前計(jì)數(shù)值1裝載進(jìn)它的寄存器中；（2）CPU B從內(nèi)存單元把當(dāng)前計(jì)數(shù)值2裝載進(jìn)它的寄存器中；（3）CPU A在它的寄存器中將計(jì)數(shù)值遞減為1；（4）CPU B在它的寄存器中將計(jì)數(shù)值遞減為1；（5）CPU A把修改后的計(jì)數(shù)值1寫回內(nèi)存單元；（6）CPU B把修改后的計(jì)數(shù)值1寫回內(nèi)存單元。我們看到，內(nèi)存里的計(jì)數(shù)值應(yīng)該是0，然而它卻是1。如果該計(jì)數(shù)值是一個(gè)共享資源的引用計(jì)數(shù)，每個(gè)進(jìn)程都在遞減后把該值與0進(jìn)行比較，從而確定是否需要釋放該共享資源。這時(shí)，兩個(gè)進(jìn)程都去掉了對(duì)該共享資源的引用，但沒(méi)有一個(gè)進(jìn)程能夠釋放它，所以兩個(gè)進(jìn)程都推斷出：計(jì)數(shù)值是1，共享資源仍然在被使用。

原子操作大部分使用匯編語(yǔ)言實(shí)現(xiàn)，因?yàn)镃語(yǔ)言并不能實(shí)現(xiàn)這樣的操作。以下是在x86體系下的一個(gè)原子加操作代碼：

3 互斥鎖統(tǒng)計(jì)算法的實(shí)現(xiàn)。首先，規(guī)避和解決在互斥鎖統(tǒng)計(jì)的限制因素：

1 )由于，本統(tǒng)計(jì)工具是用宏觀統(tǒng)計(jì)信息解決應(yīng)用程序的效率問(wèn)題，所以對(duì)互斥鎖的統(tǒng)計(jì)精度要求不高，在5%以內(nèi)的偏差是可以接受的。導(dǎo)致統(tǒng)計(jì)數(shù)據(jù)不準(zhǔn)確主要發(fā)生在多線程之間對(duì)互斥鎖競(jìng)爭(zhēng)操作的時(shí)候，這種極端環(huán)境對(duì)絕大多數(shù)應(yīng)用軟件不會(huì)在整個(gè)運(yùn)行周期普遍存在。所以采用修改C庫(kù)互斥鎖操作相關(guān)代碼，使用鉤子函數(shù)嵌入統(tǒng)計(jì)操作的方法可以滿足統(tǒng)計(jì)性能要求；

2 )為了不影響應(yīng)用軟件的效率，嵌入的統(tǒng)計(jì)操作應(yīng)該非?？焖佟?duì)于查找統(tǒng)計(jì)對(duì)象--互斥鎖，采用哈希算法，可以極大的減小查找開(kāi)銷；

3 )對(duì)于統(tǒng)計(jì)中不可避免的資源沖突，不能使用加互斥鎖或其它鎖的方式。本文采用原子操作解決該問(wèn)題；

4 )需要說(shuō)明：在記錄互斥鎖最近N次操作時(shí)，采用循環(huán)隊(duì)列技術(shù)，可以有效減小統(tǒng)計(jì)工具對(duì)內(nèi)存的需求，減小記錄結(jié)果插入隊(duì)列的時(shí)間開(kāi)銷。

應(yīng)用軟件運(yùn)行后，互斥鎖統(tǒng)計(jì)的步驟與操作的Glibc接口不同而稍有差異，但主要流程基本一致。下面以對(duì)pthread_mutex_lock接口操作為例，介紹工具運(yùn)行時(shí)的主要步驟：

setp1：應(yīng)用軟件運(yùn)行，統(tǒng)計(jì)工具構(gòu)造函數(shù)初始化作為統(tǒng)計(jì)結(jié)果儲(chǔ)存器的HASH表；

setp2：應(yīng)用軟件調(diào)用Glibc中的pthread_mutex_lock接口，獲取鎖被阻塞，觸發(fā)阻塞統(tǒng)計(jì)鉤子函數(shù)；

setp3：鉤子函數(shù)查詢HASH表找到相應(yīng)mutex統(tǒng)計(jì)對(duì)象，將其阻塞次數(shù)加一，記錄該次操作。如果HASH中不存在對(duì)應(yīng)mutex對(duì)象，則執(zhí)行setp4；

setp4：初始化一個(gè)新的mutex統(tǒng)計(jì)對(duì)象，并添加到HASH表中；

setp5：應(yīng)用軟件調(diào)用Glibc中的pthread_mutex_lock接口，試圖獲取鎖出現(xiàn)鎖狀態(tài)異常退出，觸發(fā)鎖狀態(tài)異常退出統(tǒng)計(jì)鉤子函數(shù)；

setp6：鉤子函數(shù)查詢HASH表找到相應(yīng)mutex統(tǒng)計(jì)對(duì)象，將其異常次數(shù)加一，記錄該次操作；如果HASH中不存在對(duì)應(yīng)mutex對(duì)象，則執(zhí)行setp4；

setp7：應(yīng)用軟件調(diào)用 Glibc中的pthread_mutex_lock接口，獲取鎖成功，觸發(fā)鎖成功統(tǒng)計(jì)鉤子函數(shù)；

setp8：鉤子函數(shù)查詢HASH表找到相應(yīng)mutex統(tǒng)計(jì)對(duì)象，將其成功鎖次數(shù)加一，記錄該次操作。如果HASH中不存在對(duì)應(yīng)mutex對(duì)象，則執(zhí)行setp4；

setp9：應(yīng)用程序退出，統(tǒng)計(jì)工具打印當(dāng)前互斥鎖的完整統(tǒng)計(jì)信息。

4 算法測(cè)試及性能分析

編寫測(cè)試程序，設(shè)置10個(gè)線程分別對(duì)20個(gè)互斥鎖進(jìn)行初始化、鎖和解鎖操作（其中每個(gè)線程對(duì)20個(gè)鎖依次申請(qǐng)，然后統(tǒng)一釋放，如此循環(huán)100次），得到的總體測(cè)試結(jié)果如表1所示。

表1 測(cè)試程序總體統(tǒng)計(jì)結(jié)果

為了分析加入互斥鎖統(tǒng)計(jì)后對(duì)軟件性能的影響，本文采用打點(diǎn)計(jì)數(shù)法。對(duì)于X86CPU體系的計(jì)算機(jī)，其CPU提供了一個(gè)64位高精度計(jì)時(shí)器，上電后清零，在每個(gè)CPU時(shí)鐘周期累加。計(jì)時(shí)器的值可以通過(guò)讀RDTSC寄存器獲得，由于使用X86指令實(shí)現(xiàn)打點(diǎn)計(jì)數(shù)只需要幾條匯編指令就可完成，用來(lái)分析統(tǒng)計(jì)的時(shí)間消耗影響較小。本文進(jìn)行了三次打點(diǎn)計(jì)數(shù)測(cè)試，測(cè)試結(jié)果如表2所示。

表2 加統(tǒng)計(jì)和不加統(tǒng)計(jì)的計(jì)時(shí)器對(duì)比

由于CPU的時(shí)鐘頻率為3.0GHz，統(tǒng)計(jì)執(zhí)行次數(shù)為48323，所以三次統(tǒng)計(jì)平均每次總消耗時(shí)間1.7977×10-4秒，平均每次統(tǒng)計(jì)耗時(shí)3.72×10-9秒。可以看出加入互斥鎖統(tǒng)計(jì)后對(duì)軟件的效率影響是比較小的，在大多數(shù)軟件的可接受范圍以內(nèi)。

結(jié)束語(yǔ)

本文提出一種針對(duì)Glibc互斥鎖的統(tǒng)計(jì)方法，給出了統(tǒng)計(jì)流程和算法的實(shí)現(xiàn)過(guò)程，分析了該統(tǒng)計(jì)方法對(duì)被統(tǒng)計(jì)應(yīng)用軟件效率的影響情況。本方法具有開(kāi)銷小和記錄互斥鎖近期操作的功能，特別是在應(yīng)用軟件項(xiàng)目的開(kāi)發(fā)測(cè)試階段使用，可以快速有效地定位死鎖流程，減小了無(wú)謂的互斥鎖阻塞，提高了應(yīng)用軟件的執(zhí)行效率。

[1]楊中良,蔣朝根.Linux內(nèi)核的可搶占性分析和研究 [J].成都信息工程學(xué)院學(xué)報(bào),2008 vol.23.5:505-507.

[2]Usui T,Behrends R,Evans J,Smaragdakis Y.AdaptiveLocks:Combining Transactionsand Locks for Efficient Concurrency[C]//International Conference on Parallel Architectures and Compilation Techniques.IEEE Computer Society,2010.Page(s):3-14

[3]Thomas H.Cormen,Charles E.Leiserso,Ronald L.Rivest著.潘金貴,顧鐵龍,李成法,譯.算法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2006,9.

[4William Stallings著. 陳向,群陳渝,譯.操作系統(tǒng):精髓與設(shè)計(jì)原理[M].北京:機(jī)械工業(yè)出版社,2010,9.

[5]Tsukamoto,Daisuke,Nakashima,Takuo.Implementation and Evaluation of Distributed Hash Table Using MPI[C]//International Conference on Broadband,Wireless Computing,Communication and Applications.IEEE Computer Society,2010.Page(s):684-688

[6]Mark Allen Weiss著.馮舜璽,譯.數(shù)據(jù)結(jié)構(gòu)與算法分析:C語(yǔ)言描述[M].北京:機(jī)械工業(yè)出版社,2004.1.

[7]William Stallings著.張昆藏,譯.計(jì)算機(jī)組織與體系結(jié)構(gòu):性能設(shè)計(jì)[M].北京:清華大學(xué)出版社,2006.3.