王磊曹龍漢,2

（1.重慶郵電大學通信工程學院，重慶 400065 2.重慶通信學院控制工程重點實驗室，重慶 400035）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n_pos=(volume+pos-1)%volume

下移（標志加一）算法為：

n_pos=(pos+1)%volume

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

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

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

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

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

2 )為了不影響應用軟件的效率，嵌入的統(tǒng)計操作應該非常快速。對于查找統(tǒng)計對象--互斥鎖，采用哈希算法，可以極大的減小查找開銷；

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

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

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

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

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

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

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

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

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

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

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

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

4 算法測試及性能分析

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

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

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

表2 加統(tǒng)計和不加統(tǒng)計的計時器對比

由于CPU的時鐘頻率為3.0GHz，統(tǒng)計執(zhí)行次數(shù)為48323，所以三次統(tǒng)計平均每次總消耗時間1.7977×10-4秒，平均每次統(tǒng)計耗時3.72×10-9秒?？梢钥闯黾尤牖コ怄i統(tǒng)計后對軟件的效率影響是比較小的，在大多數(shù)軟件的可接受范圍以內(nèi)。

結(jié)束語

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

[1]楊中良,蔣朝根.Linux內(nèi)核的可搶占性分析和研究 [J].成都信息工程學院學報,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著.潘金貴,顧鐵龍,李成法,譯.算法導論[M].北京:機械工業(yè)出版社,2006,9.

[4William Stallings著. 陳向,群陳渝,譯.操作系統(tǒng):精髓與設(shè)計原理[M].北京:機械工業(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語言描述[M].北京:機械工業(yè)出版社,2004.1.

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