基于記錄重播的嵌入式系統死鎖檢測方法

席衛華

摘要：針對嵌入式系統死鎖缺陷問題，提出了一種基于Lamport clock插樁記錄的嵌入式系統死鎖檢測方法——LPM（Lamport clock Pile Record Deadlock Detection Method）。首先利用Lamport clock對嵌入式程序線程關系、資源依賴關系進行記錄，然后離線提取日志記錄信息，獲取資源圖并進行死鎖檢測。仿真實驗表明，與經典的插樁機制相比，該方法可有效降低插樁開銷并能準確檢測出死鎖。

關鍵詞：嵌入式系統；LPM；Lamport clock；插樁；死鎖檢測

DOIDOI：10.11907/rjdk.172076

中圖分類號：TP306

文獻標識碼：A 文章編號：1672-7800（2017）012-0022-04

Abstract：Aiming at the problem that the deadlock of the embedded system is more difficult than the usual computer software， a deadlock detection method based on Clock Lamport interpolation is presented in this paper—LPM（Lamport clock Pile Record Deadlock Detection Method）. In this method， the Lamport clock is used to record the relationship between the thread and the resource dependence. Then the log information is extracted， the resource map is obtained and the deadlock detection is carried out. Experimental simulation results have shown that this method can effectively reduce the overhead of the pile， and can detect the deadlock accurately.

Key Words：embedded system； LPM； lamport clock； pile record； deadlock detection

0 引言

隨著嵌入式系統性能要求的提高，并發多線程程序設計在嵌入式系統中的應用越來越廣泛。嵌入式系統特點是體積小、資源和計算能力有限、程序的執行依賴外部輸入。因此，嵌入式軟件的并發缺陷比通常的計算機軟件更加棘手。死鎖是并發缺陷的典型問題，有時會導致整個嵌入式系統陷入癱瘓，嚴重影響嵌入式系統的穩定性、可靠性[1]。由于死鎖難以再現和修正，如何有效檢測死鎖成為嵌入式軟件領域的研究重點。

目前死鎖的檢測方法主要有靜態檢測和動態檢測。靜態檢測原理是通過分析源代碼進行抽象，構建出狀態模型，進而發現潛在的死鎖。文獻[2，3]設計了基于數據流分析源代碼的框架，該框架根據函數、指針等參數構建資源圖，并利用環檢測等算法檢測出死鎖。文獻[4]通過對程序的預處理獲取中間代碼、函數依賴關系和控制流圖等，進而得到線程之間的函數調用圖，并利用Petri[5]網模型進行死鎖檢測。動態檢測原理是通過對運行時的程序插入探針代碼，從而獲得程序的運行狀態和數據信息實現死鎖檢測，它避免了抽象模型和可執行程序之間不一致問題[6]。動態檢測典型工具有Intel Pin[7]和FastTrack[8]。Pin是Intel公司推出的一款動態二進制分析框架，利用Pin提供的API，在可執行二進制代碼中插入探測函數從而獲取程序運行時的數據和狀態變量等。FastTrack基于文獻[9，10]提出的DJIT+探測機制進行改進，用輕量級的自適應VCs[11]（Vector Clocks）代替原本繁重的VCs，使其在確保探測精度的情況下減少探針開銷。

雖然上述方法在一定程度上實現了死鎖檢測，但還存在不足：

（1）嵌入式軟件的靜態死鎖檢測一般采用保守方法進行變量值估計，需要在電腦端對源碼進行分析，而嵌入式軟件依賴外部輸入，具有突發性和實時性，因此檢測結果誤報率較高，且缺乏精確的運行信息。

（2）較大的性能開銷是所有動態死鎖檢測工具共同面臨的問題，特別是對于嵌入式系統而言，其程序的執行、線程的開創等都依賴于外部輸入，而外部輸入又是實時突發的，所以嵌入式軟件對探針效應[12]的敏感度要遠高于桌面軟件。

本文提出一種基于插樁記錄的嵌入式系統死鎖檢測方法。該方法分為兩個階段：①對嵌入式程序線程關系、資源依賴關系的記錄階段；②對記錄日志信息提取，獲取資源圖并進行檢測的死鎖檢測階段。相比于靜態檢測方法，基于插樁記錄的嵌入式系統死鎖檢測機制能提供更準確的運行信息，對潛在的死鎖進行更準確的檢測。相對于傳統的動態檢測機制，該方法能有效減小插樁開銷。

1 嵌入式死鎖檢測機制

基于插樁的程序都是在插樁引擎上加入自定義的程序分析工具，這類工具往往會對被測程序產生影響。由于這類工具結構原理大同小異，因此，下面以典型的Intel Pin插樁工具（以下簡稱Pin）為例進行分析。

在利用Pin插樁工具進行程序分析時，被測程序和分析程序是交叉運行的，當程序運行到插樁點時，程序會產生中斷，保存現場，然后根據采集到的數據執行分析程序。執行完分析程序后，恢復現場并繼續執行被測程序。如圖1所示，可以很明顯地看出，Pin工具的性能開銷很大一部分來源于被測程序到分析程序之間的切換和分析程序的執行。