席衛(wèi)華

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

關(guān)鍵詞：嵌入式系統(tǒng)；LPM；Lamport clock；插樁；死鎖檢測(cè)

DOIDOI：10.11907/rjdk.172076

中圖分類(lèi)號(hào)：TP306

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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è)計(jì)在嵌入式系統(tǒng)中的應(yīng)用越來(lái)越廣泛。嵌入式系統(tǒng)特點(diǎn)是體積小、資源和計(jì)算能力有限、程序的執(zhí)行依賴(lài)外部輸入。因此，嵌入式軟件的并發(fā)缺陷比通常的計(jì)算機(jī)軟件更加棘手。死鎖是并發(fā)缺陷的典型問(wèn)題，有時(shí)會(huì)導(dǎo)致整個(gè)嵌入式系統(tǒng)陷入癱瘓，嚴(yán)重影響嵌入式系統(tǒng)的穩(wěn)定性、可靠性[1]。由于死鎖難以再現(xiàn)和修正，如何有效檢測(cè)死鎖成為嵌入式軟件領(lǐng)域的研究重點(diǎn)。

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

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

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

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

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

1 嵌入式死鎖檢測(cè)機(jī)制

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

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