多線程鎖同步運行時特征分析與調優(yōu)機制研究.pdf

1、隨著多核/眾核處理器的出現，計算機的處理能力得到大幅增強。為了充分地發(fā)揮多核/眾核處理器強大的計算能力，多線程編程技術應運而生，但同時也引入了線程間通信問題，因此，設計出了鎖同步機制來協調線程間的通信。在多線程編程語言中，鎖同步機制的核心理念是保證不同線程對同一共享資源的沖突訪問以互斥的方式進行。盡管鎖同步機制保證了線程間通信的正確性，但由于多線程程序運行時調度的隨機性與復雜性，在程序動態(tài)執(zhí)行的過程中，現有的鎖同步機制也同時帶來了大量的

2、非沖突型互斥執(zhí)行，即不當鎖同步。不當鎖同步指由同一鎖保護的多個臨界區(qū)并未同時訪問同一共享資源。程序運行時形成的不當鎖同步帶來了諸多負面影響：1）在程序性能影響方面，由于不當鎖同步保護的多個臨界區(qū)沒有對同一共享資源進行沖突訪問，因此這些臨界區(qū)原本可并行執(zhí)行，然而鎖同步機制的互斥保護使得它們以串行的方式執(zhí)行，因此影響了多線程程序的性能。特別地，在鎖密集型的多線程程序中存在著大量的不當鎖同步，這對多線程程序的性能造成了嚴重的影響。2）在數據競

3、爭檢測方面，現階段主流的動態(tài)數據競爭檢測方法大都基于Happens-Before（HB）關系實現。該檢測方法通常對不同線程間的解鎖和加鎖事件形成偏序時序關系，但凡兩個程序事件沒有偏序關系同時又沖突訪問了同一共享資源，那么它們便構成一個數據競爭。然而，由于不當鎖同步可并行化的特征，HB模型的強邊界時序關系通常會漏掉大量的數據競爭。此外，不當鎖同步在程序動態(tài)執(zhí)行過程中有指數量級變化的可能性，因此高效地識別不當鎖同步并非一件易事。圍繞上述若干

4、鎖同步相關問題，開展了“多線程鎖同步運行時特征分析與調優(yōu)機制研究”的課題，主要包括以下三方面：
　　在特征研究方面，首次對多線程鎖同步運行時特征進行了系統的分析，特別是不當鎖同步運行時的特征分析。具體來說，以若干真實的（real-world）多線程程序（例如 OpenLDAP、mysql、pbzip2、transmissionBT、handbrake）為基準程序，對它們中的鎖同步進行測試、跟蹤、收集，通過觀察進一步對鎖同步運行時特

5、征進行總結，具體包括：鎖同步特征分類及其表現形式、產生原因、系統影響、防范策略和可能的修復措施等。特征研究同時揭示了11個鎖同步運行時特征相關的新觀察，基于收集到的觀察結果探討了其所折射的研究蘊意。通過對多線程鎖同步運行時特征研究，加強了對不當鎖同步的認識與理解，對解決不當鎖同步的程序影響有著重要的指導意義。
　　在性能調試方面，針對不當鎖同步所造成的性能影響問題，提出了基于記錄/重放技術的性能調試方法—PerfPlay。該方法的

6、核心思想如下：首先，記錄下含有不當鎖同步性能問題的原始程序執(zhí)行軌跡文件；其次，利用拓撲圖分析技術消除其中的不當鎖同步執(zhí)行序列，使之變?yōu)椴缓胁划旀i同步性能問題的程序執(zhí)行軌跡文件；接著，對原始和修改后的程序執(zhí)行軌跡文件重放；最后，對比分析兩次重放結果進而定量分析出不當鎖同步所造成的凈性能損耗。實驗結果表明，PerfPlay方法：1）有著很高的性能穩(wěn)定性與性能精確性，進而保證了重放分析的性能保真度；2）以低（<4.3％）運行時鎖集開銷，推薦

7、的不當鎖同步代碼段有很高的優(yōu)化價值；3）案例分析的結果也進一步逆向證明了PerfPlay在發(fā)掘不當鎖同步方面的有效性。
　　在數據競爭檢測方面，提出了面向不當鎖同步的弱時序邊界Happens-Before關系—ULCP-HB，ULCP-HB關系改善了傳統HB關系的強時序邊界特點，其能穿透不當鎖同步交錯解鎖和加鎖事件之間形成的偏序關系并使之并行化。為了實現 ULCP-HB關系，結合不當鎖同步運行時特征，進一步提出了在線啟發(fā)式分析與離

8、線重排序分析相結合的輕量級數據競爭檢測方法，該方法在幾乎不引入額外運行時開銷的情況下能夠發(fā)掘出因不當鎖同步而隱藏的數據競爭。實驗表明，相比于HB檢測方法，ULCP-HB能發(fā)掘出額外19.8%的數據競爭；且在幾乎不引入（<4.45%）運行時分析開銷的情況下，能夠節(jié)約51.0%重排序開銷和52.3%執(zhí)行軌跡文件大小。
　　綜上所述，圍繞多線程程序動態(tài)運行過程中產生的不當鎖同步現象，從基礎研究（即多線程鎖同步運行時特征研究）和擴展研究（