席衛(wèi)華

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

關(guān)鍵詞：嵌入式系統(tǒng)；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 引言

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

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

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

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

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

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

1 嵌入式死鎖檢測機制

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

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