[發明專利]一種基于共享變量訪問頻度的采樣率決策方法與系統

無效

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

技術領域

本發明屬于多線程程序調試領域，更具體地，涉及一種基于共享變量訪問頻度的采樣率決策方法與系統，主要應用于多核/眾核處理器平臺下多線程程序的實時在線數據競爭檢測。

背景技術

隨著支持多線程技術的操作系統與多核處理器技術的普及，多線程編程成為了21世紀的熱點，并展現出廣闊的應用前景。越來越多的高并發量業務的商業應用都采用了多線程技術，然而多線程技術為人們帶來更高性能的同時也帶來很多問題。通常來說，相對于傳統的單線程編程，多線程編程是比較難以設計和實現的。程序員編程的過程中很容易由于疏忽等原因而引入同步性的錯誤，這類錯誤通常很隱蔽，在調試期間難于被發現和定位。在眾多錯誤類型中，數據競爭錯誤最為典型，它發生在兩個或多個線程同時訪問一個共享變量，而沒有為這個變量設置同步保護機制并且多個線程中至少有一個線程改變了共享變量狀態的時候。其中同步保護機制是針對程序中臨界資源而言的，因為多個線程能夠并發的訪問臨界資源而由于線程訪問順序的不確定性，所以會導致程序最終運行結果不確定。為了解決這種程序運行結果不確定性，操作系統或編程語言無一例外采用了同步保護機制(鎖機制)來對臨界資源加以排他性的鎖，通過加鎖后的臨界資源在任意時刻只能有一個線程中的同步方法訪問，但這種對臨界資源訪問的序列化將會嚴重的影響程序的性能。因此，如何提高多線程程序的質量，有效的檢測多線程程序中所存在的數據競爭錯誤是非常值得研究的問題。

現有的數據競爭檢測方法主要分為兩類，包括靜態分析方法和動態分析方法。靜態分析方法通過對待測程序的代碼或文檔進行靜態分析來尋找可能存在的問題，但由于數據競爭錯誤是一種運行時故障，靜態分析模擬程序的在線環境比較困難，隨著待測程序規模的增大可能會出現狀態空間的爆炸。和靜態分析方法相比，動態分析方法能夠在程序運行過程中動態地檢測數據競爭，更為準確，但是監測代碼基本都要花費原有程序開銷的3倍到30倍。此外，動態測試依賴于測試用例，由于線程調度的不確定性，導致一個數據競爭故障往往需要幾周或者數月才能被檢測出來。

有很多專家學者在數據競爭故障的動態檢測技術方面做出了不少工作，其中利用lockset算法和happen-before算法或兩者的結合來檢測數據競爭故障是該領域的主流做法?；谶@些算法的檢測都采用了動態分析的方法，即需要運行待測程序進行調測，通過維護鎖的使用策略或指令發生序關系來檢測數據競爭。這類方法有一個重要缺點，即針對程序的一種輸入對程序的一次執行進行檢測，不能檢測出所有的可行數據競爭。所以，為了充分發現實際存在的數據競爭，只有依靠反復執行待測程序來獲取覆蓋率。但是，單純重復插入檢測代碼檢測程序勢必帶來不能容忍的性能開銷。目前，一種較為先進的做法就是每次執行程序時采用一種有效的標準對部分代碼進行檢測，這種方法稱為采樣。采樣策略的好壞直接決定了采樣方法的效率（性能開銷和準確率）。

發明內容

本發明的目的是：克服數據競爭在線檢測性能開銷巨大的問題，提出一種可應用于低開銷的在線數據競爭實時分析檢測技術。

為實現上述目的，按照本發明的一個方面，提供了一種基于共享變量訪問頻度的采樣率決策方法，包括：

（1）基于共享變量訪問頻度的統計步驟，對共享變量的訪問進行監控，統計共享變量的訪問頻度；

（2）基于共享變量訪問頻度分布的變量分組步驟，根據共享變量訪問頻度的統計結果中，各共享變量訪問頻度的分布情況，對各共享變量進行分組；

（3）基于分組差異的自適應采樣率調整步驟，根據各共享變量的分組結果，計算各共享變量的采樣率。

優選地，所述步驟（1）中采用哈希表統計共享變量的訪問頻度，其中哈希表中的每個元素由共享變量的內存地址ID和訪問頻度n構成的鍵值對組成，訪問共享變量ID的時候，采用如下更新策略對哈希表進行更新：1）若共享變量ID已存在于哈希表中，則將對應的哈希表中的元素（ID,n）更改為（ID,n+1）；2）若共享變量ID不存在于哈希表中，則增添一個新的元素（ID,1）至哈希表中。

優選地，所述步驟（2）中采用絕對閾值和相對閾值結合的方式對各共享變量進行分組，在程序處于啟動過程中的時候，采用基于絕對閾值的方法進行分組，而在程序處于穩定運行的階段，采用基于相對閾值的方法進行分組，具體地：