[發明專利]一種基于同步關系的并行動態數據競爭檢測系統

無效

• 申請號: 201310716720.3
• 申請日: 2013-12-23
• 公開（公告）號: CN103729291A
• 公開（公告）日: 2014-04-16
• 發明（設計）人: 金海;邵志遠;彭建;黃能
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F9/44
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 朱仁玲

技術領域

本發明屬于計算機軟件測試與調試領域，更具體地，本發明描述一種基于同步關系的并行動態數據競爭檢測系統。

背景技術

隨著多核硬件的廣泛普及，多線程軟件也隨之滲入到計算領域的方方面面，多線程軟件能夠充分利用多核硬件資源，在同一時間執行多項任務，特別適用于需要快速響應用戶操作的任務，除此之外，多線程軟件還可以成倍的加速某些任務。然而多線程程序固有的不確定性帶來了數據競爭，死鎖以及違反原子性等運行時錯誤，其中數據競爭指的是當多個線程訪問同一個內存地址并且其中至少有一個為寫操作時的程序狀態，是多線程程序錯誤中最為普遍的一種錯誤。近幾十年來，數據競爭導致的軟件故障對社會造成了非常嚴重的損失和傷害，比如2003年美國東北部大范圍停電以及Therac-25重大醫療事故。不幸的是，這類錯誤與線程的調度順序密切相關，因而極其難以重現。近年來由于數據競爭造成的經濟損失甚至人身傷害迫使人們加大對數據競爭檢測方法的研究。

現有的數據競爭檢測方法一般可分為靜態和動態兩大類。靜態檢測方法在編譯時對程序源碼進行全局分析，其優勢在于可以覆蓋程序所有的執行路徑，從而檢測到潛在的數據競爭。靜態方法還可以加大檢測對象的粒度，比如以對象而不是機器字為基本檢測單位可以減小檢測開銷。然而，靜態方法由于缺少程序的運行時信息只能做很多保守的假設，導致檢測結果極其不準確，給用戶造成很多的困擾。反之，動態方法在程序運行時對其進行跟蹤檢測，因為可以利用程序的運行時信息，動態方法的檢測結果較為準確，甚至可以做到沒有誤報。動態方法的缺點在于檢測結果只限于程序具體的一次執行，因此沒有辦法檢測出潛在的競爭。另外，動態方法需要跟蹤程序的內存訪問記錄，而多線程程序的內存訪問數量往往極其龐大，所以動態方法的檢測開銷非常高。對于數據競爭這類極其難以推理和調試的錯誤，誤報產生的時間成本是難以容忍的，因此目前業界大都采用動態方法。由于數據競爭能夠造成難以估量的損失和傷害，工業界迫切需要一種準確并且低開銷的數據競爭檢測方法。

發明內容

針對現有動態數據競爭檢測方法開銷過高的缺點，本發明提出一種離線的并行數據競爭檢測系統，此方法充分利用待檢測程序的并行結構，使得訪存記錄量大幅減少，其檢測算法具有很高的并行性，因而可以充分利用現有的多核平臺來加快檢測速度。

本發明提供了一種基于同步關系的并行動態數據競爭檢測系統，包括過濾模塊、記錄模塊、向量時鐘計算模塊以及并行檢測模塊，其中：

所述過濾模塊用于監控線程的執行過程，截獲線程的內存訪問，過濾掉重復和不可能造成數據競爭的訪問，對訪問區間進行壓縮合并，最后將過濾后的訪存信息發送到所述記錄模塊；

所述記錄模塊用于建立待檢測程序的訪存記錄到外部記錄文件的映射關系，即將每個線程經過過濾的訪存信息寫入到與之對應的外部文件中，同時負責編碼和壓縮所記錄的信息；

所述向量時鐘計算模塊用于根據所述文件系統中記錄的信息計算各事件的向量時鐘，計算方法采用經典的向量時鐘算法，所述并行檢測模塊利用所述計算所得向量時鐘判斷兩個事件是否可能同時發生；

所述并行檢測模塊用于并行檢測并行程序執行過程中是否實際發生了數據競爭，并在檢測到數據競爭后將結果終結后報告給用戶。

優選地，所述過濾模塊基于下述過濾策略進行過濾：（1）所有發生在兩次同步操作之間的內存訪問，程序計算器、訪問地址、訪問寬度和訪問方式都相同的只被記錄一次；（2）對于每個線程，忽略其在當前活動記錄上的內存訪問。（3）將多個相互兼容的訪問區間合并成一個大的等價區間。

優選地，所述記錄模塊將每個線程過濾后的訪存信息寫入到與之對應的記錄文件，每個線程與記錄文件有一一對應的關系，給定一個線程可以直接獲取其對應的記錄文件，反之給定一個記錄文件可以直接獲取其對應的線程號。

進一步優選地，在所述記錄文件中，每個并行區對應一個目錄，目錄以“并行區號+創建并行區的線程號”命名，并行區內的每個線程對應這個目錄下的一個文件，文件直接以線程號命名。

優選地，所述向量時鐘計算模塊從所述記錄文件中讀入每個線程的訪存記錄，并將其分割成同步塊；所述向量時鐘計算模塊采用經典向量時鐘算法為每個同步塊計算向量時鐘值，同步塊中的所有內存訪問具有同一向量時鐘；通過比較兩個同步塊的時鐘向量可以得到兩個同步塊A，B的先后發生關系，所述關系包括A->B，B->A，A|B，其中->表示左邊先于右邊發生，|表示兩者同時發生，兩同步塊具有|關系時才可能發生數據競爭。