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

【摘要】：當(dāng)前普遍流行的多核架構(gòu)帶來無(wú)處不在的并行潛能。為從硬件的并行能力獲益,并發(fā)程序設(shè)計(jì)正成為主流程序開發(fā)模型。相對(duì)于順序程序,并發(fā)程序具有并發(fā)性和不確定性的特點(diǎn)。這導(dǎo)致并發(fā)程序易于遭遇并發(fā)缺陷且并發(fā)缺陷難以暴露、檢測(cè)、調(diào)試和修復(fù)。在傳統(tǒng)測(cè)試下,許多并發(fā)缺陷沒有被檢測(cè)出來而繼續(xù)潛伏在程序中,直至在生產(chǎn)性運(yùn)行時(shí)被觸發(fā),造成重大事故或財(cái)產(chǎn)損失。為消除并發(fā)缺陷對(duì)程序正確性的威脅,可以采取2種措施:一種是設(shè)法盡快暴露和準(zhǔn)確檢測(cè)并發(fā)缺陷,識(shí)別其構(gòu)成要素以輔助調(diào)試和修復(fù);另一種是容忍并發(fā)缺陷存在,有意識(shí)地控制執(zhí)行調(diào)度,避免并發(fā)缺陷發(fā)生。前者側(cè)重于缺陷檢測(cè),后者側(cè)重于缺陷規(guī)避。因此,研究如何準(zhǔn)確檢測(cè)和有效規(guī)避并發(fā)缺陷,對(duì)于提高并發(fā)程序質(zhì)量和增強(qiáng)其運(yùn)行可靠性,具有重要的科學(xué)理論意義和實(shí)際應(yīng)用價(jià)值。本文首先將并發(fā)缺陷分為死鎖、數(shù)據(jù)競(jìng)爭(zhēng)、原子性違背和順序違背4類,討論這4類并發(fā)缺陷的相互關(guān)系,接著就如何暴露、檢測(cè)和規(guī)避各類并發(fā)缺陷對(duì)已有研究做出分析、比較和歸納,提煉出4個(gè)尚待進(jìn)一步研究的科學(xué)問題:如何增強(qiáng)死鎖檢測(cè)能力,如何降低數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)誤報(bào)率和漏報(bào)率,如何增強(qiáng)死鎖規(guī)避能力并提高死鎖規(guī)避效率以及如何增強(qiáng)通用并發(fā)缺陷規(guī)避能力并降低其人工參與度,最后對(duì)這4個(gè)問題進(jìn)行深入研究。針對(duì)現(xiàn)有死鎖檢測(cè)技術(shù)檢測(cè)能力弱,只能檢測(cè)互斥鎖死鎖的問題,研究并提出一種基于鎖分配圖的混合死鎖動(dòng)態(tài)檢測(cè)方法,以檢測(cè)由互斥鎖和讀寫鎖造成的所有5類死鎖。首先提出混合死鎖的概念,給出混合鎖分配圖的定義和構(gòu)建方法,然后通過劫持所有互斥鎖和讀寫鎖的加鎖解鎖操作,動(dòng)態(tài)構(gòu)建和實(shí)時(shí)更新一個(gè)反映目標(biāo)程序同步狀態(tài)的混合鎖分配圖,最后通過在鎖分配圖上檢測(cè)環(huán)并判定該環(huán)是否為死鎖環(huán)來檢測(cè)死鎖,當(dāng)檢測(cè)到死鎖時(shí),輸出死鎖信息以輔助調(diào)試。實(shí)驗(yàn)結(jié)果表明,該方法檢測(cè)能力強(qiáng)、對(duì)目標(biāo)程序性能影響小且可擴(kuò)展性好。針對(duì)現(xiàn)有靜態(tài)競(jìng)爭(zhēng)檢測(cè)技術(shù)誤報(bào)率高和動(dòng)態(tài)競(jìng)爭(zhēng)檢測(cè)技術(shù)漏報(bào)率高的問題,研究并提出一種動(dòng)靜結(jié)合的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法,以同時(shí)降低誤報(bào)率和漏報(bào)率。首先采用靜態(tài)分析找到所有可能的競(jìng)爭(zhēng)訪問對(duì),識(shí)別所有潛在自定義同步原語(yǔ),然后采用動(dòng)態(tài)分析監(jiān)視程序在競(jìng)爭(zhēng)訪問點(diǎn)的行為,控制線程調(diào)度以盡量暴露數(shù)據(jù)競(jìng)爭(zhēng),并綜合使用鎖集算法和先發(fā)生于算法來檢測(cè)式地驗(yàn)證被遮蔽的數(shù)據(jù)競(jìng)爭(zhēng),最后動(dòng)態(tài)確認(rèn)自定義同步原語(yǔ),剔除虛假和良性數(shù)據(jù)競(jìng)爭(zhēng)。實(shí)驗(yàn)結(jié)果表明,該方法的檢測(cè)準(zhǔn)確度高,誤檢率和漏檢率低,而性能影響和擴(kuò)展性不差于已有方法。針對(duì)現(xiàn)有死鎖規(guī)避技術(shù)規(guī)避能力弱、被動(dòng)盲目、開銷較大和影響程序正確性等問題,研究并提出一種基于未來鎖集的動(dòng)靜結(jié)合死鎖規(guī)避方法�；舅枷胧�,對(duì)于一個(gè)加鎖操作,若其未來鎖集中的所有鎖都是空閑的,則執(zhí)行該加鎖操作不會(huì)導(dǎo)致死鎖。一個(gè)加鎖操作的未來鎖集包括當(dāng)前要加鎖的鎖和從該加鎖操作到與之相對(duì)應(yīng)的解鎖操作過程中遇到的所有加鎖操作所要加的鎖。通過靜態(tài)分析,計(jì)算鎖效應(yīng)信息并插樁到相應(yīng)的加鎖操作和函數(shù)調(diào)用操作前后。通過動(dòng)態(tài)分析,劫持加鎖操作,根據(jù)其鎖效應(yīng)信息為之計(jì)算未來鎖集,只有當(dāng)未來鎖集中的所有鎖都未被鎖定才執(zhí)行該加鎖操作,否則等待。實(shí)驗(yàn)結(jié)果表明該方法能智能主動(dòng)地規(guī)避多種類型死鎖,對(duì)目標(biāo)程序的性能影響較小,可擴(kuò)展性好,不影響程序正確性。針對(duì)現(xiàn)有通用并發(fā)缺陷規(guī)避技術(shù)規(guī)避能力弱和人工參與度高的問題,研究并提出一種基于軟件事務(wù)內(nèi)存的并發(fā)缺陷規(guī)避方法,能夠自動(dòng)事務(wù)化目標(biāo)程序,規(guī)避死鎖、數(shù)據(jù)競(jìng)爭(zhēng)、原子性違背和順序違背等4類并發(fā)缺陷,支持事務(wù)I/O并合理處理?xiàng)l件變量。通過使用進(jìn)程替代線程、利用進(jìn)程間虛擬內(nèi)存保護(hù)機(jī)制并定制內(nèi)存分配回收邏輯,實(shí)現(xiàn)內(nèi)存事務(wù)化。通過劫持每個(gè)線程的線程間操作并將它們之間的代碼劃分為事務(wù),實(shí)現(xiàn)目標(biāo)程序的自動(dòng)事務(wù)化。通過在啟動(dòng)/撤銷事務(wù)時(shí)保存/恢復(fù)當(dāng)前線程的棧幀和CPU寄存器,實(shí)現(xiàn)執(zhí)行流可回滾化。通過建立和維護(hù)虛擬文件系統(tǒng),并將I/O操作重定向到它們上,實(shí)現(xiàn)I/O事務(wù)化。通過置空加鎖解鎖操作,定制條件變量操作和事務(wù)性地提交內(nèi)存與I/O變更,實(shí)現(xiàn)對(duì)死鎖、數(shù)據(jù)競(jìng)爭(zhēng)、原子性違背和順序違背的規(guī)避。實(shí)驗(yàn)結(jié)果表明,該方法的規(guī)避能力強(qiáng),無(wú)需人工參與,但對(duì)目標(biāo)程序的性能影響較大。綜上所述,本文在如何增強(qiáng)死鎖檢測(cè)能力、降低數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)誤報(bào)率和漏報(bào)率、增強(qiáng)死鎖規(guī)避能力與提高死鎖規(guī)避效率、增強(qiáng)通用并發(fā)缺陷規(guī)避能力并降低其人工參與度等科學(xué)問題上提供了新思路與新方法。
[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.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.1
，

本文編號(hào)：2100066