一種Glibc互斥鎖的統計方法

王磊曹龍漢,2

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

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

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

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

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

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

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

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

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

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

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

2.2 互斥鎖統計對象的哈希表查找方法。本統計中的哈希表是根據哈希算法由C語言實現的，為了達到統計算法的要求，我們使用了以下幾個關鍵技術：

圖1 哈希表結構

1 )使用面向對象技術，針對每個哈希表對象封裝了一套自定義的哈希算法、哈希表遍歷操作；

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

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

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

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

n_pos=(volume+pos-1)%volume

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

n_pos=(pos+1)%volume

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

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

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

3 互斥鎖統計算法的實現。首先，規避和解決在互斥鎖統計的限制因素：

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

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

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

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

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

setp1：應用軟件運行，統計工具構造函數初始化作為統計結果儲存器的HASH表；

setp2：應用軟件調用Glibc中的pthread_mutex_lock接口，獲取鎖被阻塞，觸發阻塞統計鉤子函數；

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

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

setp5：應用軟件調用Glibc中的pthread_mutex_lock接口，試圖獲取鎖出現鎖狀態異常退出，觸發鎖狀態異常退出統計鉤子函數；

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

setp7：應用軟件調用 Glibc中的pthread_mutex_lock接口，獲取鎖成功，觸發鎖成功統計鉤子函數；

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

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

4 算法測試及性能分析

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

表1 測試程序總體統計結果

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

表2 加統計和不加統計的計時器對比

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

結束語

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

[1]楊中良,蔣朝根.Linux內核的可搶占性分析和研究 [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].北京:機械工業出版社,2006,9.

[4William Stallings著. 陳向,群陳渝,譯.操作系統:精髓與設計原理[M].北京:機械工業出版社,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著.馮舜璽,譯.數據結構與算法分析:C語言描述[M].北京:機械工業出版社,2004.1.

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