本文選題：并發(fā)缺陷 + 死鎖檢測與規(guī)避��； 參考：《哈爾濱工業(yè)大學》2017年博士論文

【摘要】：當前普遍流行的多核架構帶來無處不在的并行潛能。為從硬件的并行能力獲益,并發(fā)程序設計正成為主流程序開發(fā)模型。相對于順序程序,并發(fā)程序具有并發(fā)性和不確定性的特點。這導致并發(fā)程序易于遭遇并發(fā)缺陷且并發(fā)缺陷難以暴露、檢測、調試和修復。在傳統(tǒng)測試下,許多并發(fā)缺陷沒有被檢測出來而繼續(xù)潛伏在程序中,直至在生產性運行時被觸發(fā),造成重大事故或財產損失。為消除并發(fā)缺陷對程序正確性的威脅,可以采取2種措施:一種是設法盡快暴露和準確檢測并發(fā)缺陷,識別其構成要素以輔助調試和修復;另一種是容忍并發(fā)缺陷存在,有意識地控制執(zhí)行調度,避免并發(fā)缺陷發(fā)生。前者側重于缺陷檢測,后者側重于缺陷規(guī)避。因此,研究如何準確檢測和有效規(guī)避并發(fā)缺陷,對于提高并發(fā)程序質量和增強其運行可靠性,具有重要的科學理論意義和實際應用價值。本文首先將并發(fā)缺陷分為死鎖、數據競爭、原子性違背和順序違背4類,討論這4類并發(fā)缺陷的相互關系,接著就如何暴露、檢測和規(guī)避各類并發(fā)缺陷對已有研究做出分析、比較和歸納,提煉出4個尚待進一步研究的科學問題:如何增強死鎖檢測能力,如何降低數據競爭檢測誤報率和漏報率,如何增強死鎖規(guī)避能力并提高死鎖規(guī)避效率以及如何增強通用并發(fā)缺陷規(guī)避能力并降低其人工參與度,最后對這4個問題進行深入研究。針對現有死鎖檢測技術檢測能力弱,只能檢測互斥鎖死鎖的問題,研究并提出一種基于鎖分配圖的混合死鎖動態(tài)檢測方法,以檢測由互斥鎖和讀寫鎖造成的所有5類死鎖。首先提出混合死鎖的概念,給出混合鎖分配圖的定義和構建方法,然后通過劫持所有互斥鎖和讀寫鎖的加鎖解鎖操作,動態(tài)構建和實時更新一個反映目標程序同步狀態(tài)的混合鎖分配圖,最后通過在鎖分配圖上檢測環(huán)并判定該環(huán)是否為死鎖環(huán)來檢測死鎖,當檢測到死鎖時,輸出死鎖信息以輔助調試。實驗結果表明,該方法檢測能力強、對目標程序性能影響小且可擴展性好。針對現有靜態(tài)競爭檢測技術誤報率高和動態(tài)競爭檢測技術漏報率高的問題,研究并提出一種動靜結合的數據競爭檢測方法,以同時降低誤報率和漏報率。首先采用靜態(tài)分析找到所有可能的競爭訪問對,識別所有潛在自定義同步原語,然后采用動態(tài)分析監(jiān)視程序在競爭訪問點的行為,控制線程調度以盡量暴露數據競爭,并綜合使用鎖集算法和先發(fā)生于算法來檢測式地驗證被遮蔽的數據競爭,最后動態(tài)確認自定義同步原語,剔除虛假和良性數據競爭。實驗結果表明,該方法的檢測準確度高,誤檢率和漏檢率低,而性能影響和擴展性不差于已有方法。針對現有死鎖規(guī)避技術規(guī)避能力弱、被動盲目、開銷較大和影響程序正確性等問題,研究并提出一種基于未來鎖集的動靜結合死鎖規(guī)避方法�；舅枷胧�,對于一個加鎖操作,若其未來鎖集中的所有鎖都是空閑的,則執(zhí)行該加鎖操作不會導致死鎖。一個加鎖操作的未來鎖集包括當前要加鎖的鎖和從該加鎖操作到與之相對應的解鎖操作過程中遇到的所有加鎖操作所要加的鎖。通過靜態(tài)分析,計算鎖效應信息并插樁到相應的加鎖操作和函數調用操作前后。通過動態(tài)分析,劫持加鎖操作,根據其鎖效應信息為之計算未來鎖集,只有當未來鎖集中的所有鎖都未被鎖定才執(zhí)行該加鎖操作,否則等待。實驗結果表明該方法能智能主動地規(guī)避多種類型死鎖,對目標程序的性能影響較小,可擴展性好,不影響程序正確性。針對現有通用并發(fā)缺陷規(guī)避技術規(guī)避能力弱和人工參與度高的問題,研究并提出一種基于軟件事務內存的并發(fā)缺陷規(guī)避方法,能夠自動事務化目標程序,規(guī)避死鎖、數據競爭、原子性違背和順序違背等4類并發(fā)缺陷,支持事務I/O并合理處理條件變量。通過使用進程替代線程、利用進程間虛擬內存保護機制并定制內存分配回收邏輯,實現內存事務化。通過劫持每個線程的線程間操作并將它們之間的代碼劃分為事務,實現目標程序的自動事務化。通過在啟動/撤銷事務時保存/恢復當前線程的棧幀和CPU寄存器,實現執(zhí)行流可回滾化。通過建立和維護虛擬文件系統(tǒng),并將I/O操作重定向到它們上,實現I/O事務化。通過置空加鎖解鎖操作,定制條件變量操作和事務性地提交內存與I/O變更,實現對死鎖、數據競爭、原子性違背和順序違背的規(guī)避。實驗結果表明,該方法的規(guī)避能力強,無需人工參與,但對目標程序的性能影響較大。綜上所述,本文在如何增強死鎖檢測能力、降低數據競爭檢測誤報率和漏報率、增強死鎖規(guī)避能力與提高死鎖規(guī)避效率、增強通用并發(fā)缺陷規(guī)避能力并降低其人工參與度等科學問題上提供了新思路與新方法。
[Abstract]:Current popular multicore architectures bring ubiquitous parallel potential. In order to benefit from the parallel capabilities of hardware, concurrent programming is becoming the mainstream program development model. Relative to sequential programs, concurrent programs have the characteristics of concurrency and uncertainty. This leads to concurrent programs that are prone to concurrency defects and are difficult to expose concurrency defects. Detection, testing, debugging and repair. In traditional tests, many concurrency defects have not been detected and continue to lurk in the program until they are triggered in a productive operation, causing major accidents or property losses. In order to eliminate the threat of concurrent defects to the correctness of the program, 2 measures can be taken: one is to try to expose and detect accurately as soon as possible and Defects, identify its components to assist in debugging and repair; the other is tolerance of concurrency defects, conscious control of execution scheduling, and avoidance of concurrent defects. The former focuses on defect detection, and the latter focuses on defect avoidance. Therefore, it studies how to accurately detect and effectively circumvent concurrent defects and improve the quality of concurrent programs. In order to enhance its operational reliability, it has important scientific theoretical significance and practical application value. Firstly, this paper divides concurrency defects into 4 categories: deadlock, data competition, atomic violation and sequence violation, and discusses the relationship between the 4 kinds of concurrency defects. Then, the analysis of how to expose, detect and avoid various concurrency defects is analyzed and compared. And induction, 4 scientific problems to be further studied: how to enhance the ability of deadlock detection, how to reduce the false alarm rate and false alarm rate of data competition detection, how to enhance the ability of deadlock avoidance and to improve the efficiency of deadlock avoidance, how to enhance the ability to evade the common concurrency defects and reduce the manual participation, and finally to the 4 problems In order to detect the problem that the existing deadlock detection technology is weak and can only detect the deadlock of the mutex lock, a hybrid deadlock dynamic detection method based on the lock allocation graph is proposed to detect all 5 types of deadlocks caused by the mutex lock and the read write lock. First, the concept of mixed deadlock is proposed and the mixing lock allocation graph is given. Meaning and construction method, and then dynamically build and update a mixed lock map that reflects the synchronization state of the target program by hijacking all the mutex lock and read and write lock. Finally, the detection ring is detected on the lock allocation graph and whether the ring is dead lock, and the deadlock information is output when the deadlock is detected. The experimental results show that the method has the advantages of strong detection ability, small impact on the performance of target program and good scalability. In view of the problem of high false alarm rate and high leakage rate of dynamic competitive detection technology in the existing static competition detection technology, a method of dynamic and static combination of data competition detection is proposed in order to reduce the false alarm rate and leakage at the same time. Reporting rate. First, it uses static analysis to find all possible competitive access pairs, identify all potential custom synchronization primitives, then use dynamic analysis monitoring programs at competitive access points, control thread scheduling to expose data competition as far as possible, and use the lock set algorithm and algorithms to verify the occlusion. The experimental results show that the method has high detection accuracy, low error rate and low missed detection rate, and the performance impact and scalability are not bad for the existing methods. The basic idea is that for a lock operation, if all the locks in the future lock set are idle, the lock operation will not cause the deadlock. The future lock set of a lock operation includes the lock lock and the addition of the lock. Lock operation to all lock operations that are encountered during the unlocking operation corresponding to it. Through static analysis, the lock effect information is calculated and piled to the corresponding lock operation and function call operation. By dynamic analysis, the lock operation is hijacked, and the future lock set is calculated according to the information of its lock effect, only in the future. All locks in the lock are not locked until the lock operation is carried out, or otherwise, the experimental results show that the method can intelligently evade various types of deadlocks, have less impact on the performance of the target program, have good scalability, and do not affect the correctness of the program. High problem, research and propose a method of concurrency defect avoidance based on software transaction memory, which can automatically transactional target program, avoid 4 concurrency defects such as deadlock, data competition, atomic violation and sequential violation, support transaction I/O and handle conditional variables reasonably. Through using process instead of threads and using virtual memory between processes Protect the mechanism and customize the memory allocation recovery logic to realize memory transactional. By hijacking each thread's threads between threads and dividing the code between them into transactions, the target program is automatically transactional. The execution flow can be rolled back by saving / restoring the current thread's stack frame and CPU register when starting / revoking transactions. By setting up and maintaining the virtual file system and redirecting the I/O operations to them, I/O transactional. Through the empty and lock unlocking operation, the condition variable operation and the transactional submission of the memory and I/O changes to achieve the evasion of the deadlock, the data competition, the atomic violation and the CIS sequence violation. Experimental results show that the method is avoided. It has strong ability and no manual participation, but has great influence on the performance of the target program. In summary, this paper is how to enhance the deadlock detection ability, reduce the false alarm rate and false alarm rate of the data competition detection, enhance the deadlock avoidance ability and improve the efficiency of deadlock avoidance, enhance the general concurrency concurrence evasion ability and reduce the artificial participation degree. New ideas and new methods are provided.
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP311.1
，

本文編號：2100066