本文關(guān)鍵詞： 多線程程序 特征研究 性能調(diào)試 數(shù)據(jù)競爭 不當(dāng)鎖同步　出處：《華中科技大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：隨著多核/眾核處理器的出現(xiàn),計(jì)算機(jī)的處理能力得到大幅增強(qiáng)。為了充分地發(fā)揮多核/眾核處理器強(qiáng)大的計(jì)算能力,多線程編程技術(shù)應(yīng)運(yùn)而生,但同時(shí)也引入了線程間通信問題,因此,設(shè)計(jì)出了鎖同步機(jī)制來協(xié)調(diào)線程間的通信。在多線程編程語言中,鎖同步機(jī)制的核心理念是保證不同線程對同一共享資源的沖突訪問以互斥的方式進(jìn)行。盡管鎖同步機(jī)制保證了線程間通信的正確性,但由于多線程程序運(yùn)行時(shí)調(diào)度的隨機(jī)性與復(fù)雜性,在程序動(dòng)態(tài)執(zhí)行的過程中,現(xiàn)有的鎖同步機(jī)制也同時(shí)帶來了大量的非沖突型互斥執(zhí)行,即不當(dāng)鎖同步。不當(dāng)鎖同步指由同一鎖保護(hù)的多個(gè)臨界區(qū)并未同時(shí)訪問同一共享資源。程序運(yùn)行時(shí)形成的不當(dāng)鎖同步帶來了諸多負(fù)面影響：1)在程序性能影響方面,由于不當(dāng)鎖同步保護(hù)的多個(gè)臨界區(qū)沒有對同一共享資源進(jìn)行沖突訪問,因此這些臨界區(qū)原本可并行執(zhí)行,然而鎖同步機(jī)制的互斥保護(hù)使得它們以串行的方式執(zhí)行,因此影響了多線程程序的性能。特別地,在鎖密集型的多線程程序中存在著大量的不當(dāng)鎖同步,這對多線程程序的性能造成了嚴(yán)重的影響。2)在數(shù)據(jù)競爭檢測方面,現(xiàn)階段主流的動(dòng)態(tài)數(shù)據(jù)競爭檢測方法大都基于Happens-Before (HB)關(guān)系實(shí)現(xiàn)。該檢測方法通常對不同線程間的解鎖和加鎖事件形成偏序時(shí)序關(guān)系,但凡兩個(gè)程序事件沒有偏序關(guān)系同時(shí)又沖突訪問了同一共享資源,那么它們便構(gòu)成一個(gè)數(shù)據(jù)競爭。然而,由于不當(dāng)鎖同步可并行化的特征,HB模型的強(qiáng)邊界時(shí)序關(guān)系通常會(huì)漏掉大量的數(shù)據(jù)競爭。此外,不當(dāng)鎖同步在程序動(dòng)態(tài)執(zhí)行過程中有指數(shù)量級(jí)變化的可能性,因此高效地識(shí)別不當(dāng)鎖同步并非一件易事。圍繞上述若干鎖同步相關(guān)問題,開展了“多線程鎖同步運(yùn)行時(shí)特征分析與調(diào)優(yōu)機(jī)制研究”的課題,主要包括以下三方面：在特征研究方面,首次對多線程鎖同步運(yùn)行時(shí)特征進(jìn)行了系統(tǒng)的分析,特別是不當(dāng)鎖同步運(yùn)行時(shí)的特征分析。具體來說,以若干真實(shí)的(real-world)多線程程序(例如OpenLDAP、mysq1、pbzip2、transmissionBT、handbrake)為基準(zhǔn)程序,對它們中的鎖同步進(jìn)行測試、跟蹤、收集,通過觀察進(jìn)一步對鎖同步運(yùn)行時(shí)特征進(jìn)行總結(jié),具體包括：鎖同步特征分類及其表現(xiàn)形式、產(chǎn)生原因、系統(tǒng)影響、防范策略和可能的修復(fù)措施等。特征研究同時(shí)揭示了11個(gè)鎖同步運(yùn)行時(shí)特征相關(guān)的新觀察,基于收集到的觀察結(jié)果探討了其所折射的研究蘊(yùn)意。通過對多線程鎖同步運(yùn)行時(shí)特征研究,加強(qiáng)了對不當(dāng)鎖同步的認(rèn)識(shí)與理解,對解決不當(dāng)鎖同步的程序影響有著重要的指導(dǎo)意義。在性能調(diào)試方面,針對不當(dāng)鎖同步所造成的性能影響問題,提出了基于記錄/重放技術(shù)的性能調(diào)試方法-PerfPlay。該方法的核心思想如下：首先,記錄下含有不當(dāng)鎖同步性能問題的原始程序執(zhí)行軌跡文件：其次,利用拓?fù)鋱D分析技術(shù)消除其中的不當(dāng)鎖同步執(zhí)行序列,使之變?yōu)椴缓胁划?dāng)鎖同步性能問題的程序執(zhí)行軌跡文件；接著,對原始和修改后的程序執(zhí)行軌跡文件重放；最后,對比分析兩次重放結(jié)果進(jìn)而定量分析出不當(dāng)鎖同步所造成的凈性能損耗。實(shí)驗(yàn)結(jié)果表明,PerfPlay方法：1)有著很高的性能穩(wěn)定性與性能精確性,進(jìn)而保證了重放分析的性能保真度；2)以低(4.3%)運(yùn)行時(shí)鎖集開銷,推薦的不當(dāng)鎖同步代碼段有很高的優(yōu)化價(jià)值；3)案例分析的結(jié)果也進(jìn)一步逆向證明了PerfPlay在發(fā)掘不當(dāng)鎖同步方面的有效性。在數(shù)據(jù)競爭檢測方面,提出了面向不當(dāng)鎖同步的弱時(shí)序邊界Happens-Before關(guān)系-ULCP-HB, ULCP-HB關(guān)系改善了傳統(tǒng)HB關(guān)系的強(qiáng)時(shí)序邊界特點(diǎn),其能穿透不當(dāng)鎖同步交錯(cuò)解鎖和加鎖事件之間形成的偏序關(guān)系并使之并行化。為了實(shí)現(xiàn)ULCP-HB關(guān)系,結(jié)合不當(dāng)鎖同步運(yùn)行時(shí)特征,進(jìn)一步提出了在線啟發(fā)式分析與離線重排序分析相結(jié)合的輕量級(jí)數(shù)據(jù)競爭檢測方法,該方法在幾乎不引入額外運(yùn)行時(shí)開銷的情況下能夠發(fā)掘出因不當(dāng)鎖同步而隱藏的數(shù)據(jù)競爭。實(shí)驗(yàn)表明,相比于HB檢測方法,ULCP-HB能發(fā)掘出額外19.8%的數(shù)據(jù)競爭；且在幾乎不引入(4.45%)運(yùn)行時(shí)分析開銷的情況下,能夠節(jié)約51.0%重排序開銷和52.3%執(zhí)行軌跡文件大小。綜上所述,圍繞多線程程序動(dòng)態(tài)運(yùn)行過程中產(chǎn)生的不當(dāng)鎖同步現(xiàn)象,從基礎(chǔ)研究(即多線程鎖同步運(yùn)行時(shí)特征研究)和擴(kuò)展研究(包括面向不當(dāng)鎖同步的性能調(diào)試技術(shù)和數(shù)據(jù)競爭檢測兩方面的研究)兩個(gè)方面對不當(dāng)鎖同步進(jìn)行了全面又深入的系統(tǒng)分析,這些研究加強(qiáng)了程序設(shè)計(jì)人員對不當(dāng)鎖同步的運(yùn)行時(shí)行為及程序影響的理解,進(jìn)而幫助程序設(shè)計(jì)人員有效地修復(fù)不當(dāng)鎖同步相關(guān)的程序影響。
[Abstract]:With the advent of multi-core / many core processor, computer processing power has been greatly enhanced. In order to make full use of multi-core / many core processor computing power came into being strong, multi thread programming technology, but also introduced the communication problem between threads, therefore, designed a lock synchronization mechanism to coordinate the communication between threads. In a multithreaded programming language, the core concept of lock synchronization mechanism is to ensure that different threads of the same access to shared resources conflict mutually exclusive. Although the lock synchronization mechanism to ensure the correctness of communication between threads, but due to the randomness of scheduling in multi thread programs and complexity in the process of dynamic program execution in the existing lock synchronization mechanism also brings lots of non conflict mutex implementation, namely the improper lock synchronization. Improper lock synchronization refers to the same lock protection a critical region did not visit at the same time The same shared resources. Improper lock is formed when running the synchronization has brought many negative effects: 1) in terms of program performance impact due to a number of critical region protection no improper lock synchronization conflicts access to the same shared resources, so these critical areas could be performed in parallel, but the mutex protection lock synchronization mechanism make them perform in serial mode, thus affecting the performance of multithreaded programs. In particular, in the lock intensive multi-threaded program in a large number of improper lock synchronization, the multi thread program performance caused by the influence of the severity of.2) in terms of data race detection, dynamic data race detection method at present. The mainstream is mostly based on the Happens-Before (HB). The relationship between detection methods are usually on different threads of unlocking and locking events in the formation of partial order relations, whenever two program events not ordered off The Department also visited the same conflict of shared resources, then they form a data race. However, due to improper lock synchronization can be parallel features, strong boundary timing HB model usually missed the competition a large amount of data. In addition, the improper lock possibility of the implementation of index magnitude change during the process in dynamic program simultaneously, so efficiently identify improper lock synchronization is not an easy task. On the above several lock synchronization related issues, carried out research on Characteristic Analysis and optimization mechanism of multi thread lock synchronization operation subject, mainly includes the following three aspects: the characteristics of research, for the first time on the multi thread lock synchronization operation characteristics of the system the analysis, especially the analysis of the characteristics of improper lock synchronization when running. Specifically, a number of real (real-world) multithreaded programs (such as OpenLDAP, mysq1, pbzip2, transmissionBT, handbrak E) as a benchmark program, for they lock synchronization testing, tracking, collection, through the observation of further lock synchronization operation characteristics were summarized, including: Lock synchronization feature classification and its manifestations, causes, impact, prevention strategies and possible repair measures. The study also revealed 11 features to observe the new lock synchronization runtime features related to the observation results, based on the collected on the meaning of refraction. By studying the characteristic of multi thread lock synchronization operation, strengthen the improper lock synchronization understanding and understanding, has important significance to solve the improper lock synchronization procedures. In the performance of debugging, to solve the problem of performance caused by improper lock synchronization, puts forward the core idea of -PerfPlay. performance debugging method the method of recording / playback technology based on record contains as follows: first of all, Improper lock synchronization performance problems of the original program execution trace file. Secondly, using topology analysis technology to eliminate the improper lock synchronization execution sequence, which was not with improper lock synchronization performance issues program execution path file; then, the original and modified program execution trace file playback; finally, the comparative analysis of the two the results of quantitative analysis and replay time net performance loss caused by improper lock synchronization. The experimental results show that the PerfPlay method: 1) with the stability and performance of high accuracy, and ensure the performance of fidelity replay analysis; 2) to low (4.3%) runtime overhead lock set, recommended the improper lock synchronization code optimization has very high value; 3) the case analysis results further proved that PerfPlay reverse in exploring the effectiveness of the improper lock synchronization. In the data race detection aspect, put forward The improper lock synchronization weak sequence boundary Happens-Before relations -ULCP-HB, ULCP-HB improved strong temporal boundary characteristics of traditional HB relation, partial order relation between the formation through improper locking and unlocking staggered lock synchronization events and make parallel. In order to realize the ULCP-HB relationship, combined with the improper lock synchronization operation characteristics, further put forward the online analysis and offline heuristic reordering lightweight data analysis combined with the competition detection method, we can discover hidden due to improper competition and the method of data synchronization overhead in almost no additional run-time conditions. Experimental results show that compared to the HB detection method, ULCP-HB can find out the competition 19.8% additional data; and in almost no introduction (4.45%) runtime analysis overhead, can save 51% reordering overhead and 52.3% track file execution. In summary, The improper lock synchronization phenomenon of dynamic multi thread program is running in the process, from basic research (i.e. the characteristics of multi thread lock synchronization operation) and extended research (including research on improper lock synchronization performance debugging technology and data race detection two) two aspects of improper lock synchronization to conduct a comprehensive and in-depth the research of system analysis, strengthen the effect of program design of program behavior and improper lock synchronization operation of the understanding, and help programmers effectively fix influence of improper lock synchronization related.

【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP332

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張利霞;多線程的實(shí)現(xiàn)方法[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年02期

2 趙海延;多線程及其實(shí)現(xiàn)方法[J];武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào);2002年03期

3 李學(xué)坤;數(shù)據(jù)采集處理系統(tǒng)中多線程的效率研究[J];工業(yè)控制計(jì)算機(jī);2003年04期

4 徐洪斌,蘇鐵熊,董小瑞;多線程技術(shù)及其實(shí)現(xiàn)[J];山西電子技術(shù);2003年03期

5 李文亮,閆宏印;多線程技術(shù)及其在多媒體CAI軟件中的應(yīng)用[J];太原理工大學(xué)學(xué)報(bào);2003年05期

6 周亦敏,張生;集散系統(tǒng)中基于多線程的多機(jī)串行通信實(shí)現(xiàn)[J];上海理工大學(xué)學(xué)報(bào);2003年04期

7 高正光,李啟炎;一種多線程并發(fā)環(huán)境下的對象緩存模型[J];計(jì)算機(jī)工程;2005年22期

8 王世強(qiáng);曹英;王宏;;基于多線程的肌電信號(hào)實(shí)時(shí)采集與分析系統(tǒng)[J];儀器儀表學(xué)報(bào);2006年S2期

9 李婷;虞鋼;;脈搏檢測分析系統(tǒng)中基于多線程的高速串口通信[J];計(jì)算機(jī)應(yīng)用與軟件;2007年03期

10 張躍平;;多線程設(shè)計(jì)中的克隆技術(shù)[J];信息技術(shù);2007年04期

相關(guān)會(huì)議論文 前10條

1 譚小彬;孔德光;奚宏生;;多線程程序時(shí)序的統(tǒng)計(jì)分析[A];第二十七屆中國控制會(huì)議論文集[C];2008年

2 賈韶旭;潘錦;;多線程技術(shù)在探地雷達(dá)中的應(yīng)用[A];2007年全國微波毫米波會(huì)議論文集（下冊）[C];2007年

3 胡杏;胡瑜;李曉維;;基于存儲(chǔ)級(jí)并行的同時(shí)多線程電壓緊急容錯(cuò)技術(shù)[A];第十四屆全國容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議(CFTC'2011)論文集[C];2011年

4 周大剛;龍昭華;;多線程在無線網(wǎng)絡(luò)處理中的應(yīng)用[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

5 李s，

本文編號(hào)：1452095