孟凡奇

摘 要：預(yù)測安全關(guān)鍵實(shí)時程序的執(zhí)行時間具有重要意義。本文簡要分析了程序執(zhí)行時間預(yù)測的研究現(xiàn)狀，對欲從事本方向研究的人員會有一定幫助。

關(guān)鍵詞：安全關(guān)鍵軟件；實(shí)時程序；執(zhí)行時間預(yù)測

安全關(guān)鍵系統(tǒng)（safety-critical system，CSC）[1]泛指具有潛在破壞力的一類系統(tǒng)。此類系統(tǒng)一旦失效（例如汽車的ABS失靈）就可能造成人員傷亡、財產(chǎn)損失或環(huán)境破壞等嚴(yán)重后果。

安全關(guān)鍵實(shí)時程序可理解為在安全關(guān)鍵系統(tǒng)中起重要控制作用的實(shí)時程序。需要指出的是，安全關(guān)鍵程序未必是實(shí)時程序，而實(shí)時程序也未必是安全關(guān)鍵程序。例如，遙控玩具飛機(jī)上的控制程序是實(shí)時程序，但不是安全關(guān)鍵程序。而醫(yī)療X射線機(jī)中的程序是安全關(guān)鍵程序，因?yàn)檩椛鋭┝靠刂频牟缓脮θ梭w造成傷害，但它不是實(shí)時程序。

本文余下首先對程序執(zhí)行時間預(yù)測進(jìn)行一個總覽，然后簡要分析安全關(guān)鍵實(shí)時程序執(zhí)行時間預(yù)測研究現(xiàn)狀及方向。

1 程序執(zhí)行時間預(yù)測研究現(xiàn)狀

程序執(zhí)行時間預(yù)測技術(shù)大體上可以分為3類：動態(tài)方法、靜態(tài)方法以及混合方法。

動態(tài)方法也稱為基于測量的方法，其基本原理是統(tǒng)計預(yù)測（Statistical Prediction），即：使用大量測試用例，多次運(yùn)行程序，獲取程序的執(zhí)行時間數(shù)據(jù)，加工后進(jìn)行預(yù)測。

靜態(tài)方法也稱基于分析的方法，其基本原理是圖論（graph theory），即：分析程序的控制流圖，搜尋特定輸入（具體值或者范圍）下，滿足目標(biāo)處理器特性約束的穿過程序的最長執(zhí)行路徑。

混合方法，顧名思義，要么先動態(tài)后靜態(tài)，要么先靜態(tài)后動態(tài)。

上述3種方法在預(yù)測程序執(zhí)行時間時各有利弊。動態(tài)方法的優(yōu)點(diǎn)是方法簡單，硬件適應(yīng)性強(qiáng)。缺點(diǎn)是多次測試，時間較長，且由于不能窮舉程序的所有執(zhí)行路徑以及硬件狀態(tài)，因此預(yù)測值比實(shí)際程序的執(zhí)行時間范圍要小，不能用于安全關(guān)鍵實(shí)時程序。靜態(tài)方法的優(yōu)點(diǎn)是有數(shù)學(xué)基礎(chǔ)，因此預(yù)測值比實(shí)際程序的執(zhí)行時間范圍要大，能用于安全關(guān)鍵實(shí)時程序。缺點(diǎn)是對硬件建模比較困難，尤其是對含有復(fù)雜架構(gòu)（比如多級Cache、流水線、分支預(yù)測等）的處理器建模?；旌戏椒▌t可以克服兩者的缺點(diǎn)，融合兩者的優(yōu)點(diǎn)。

2 程序執(zhí)行時間預(yù)測研究方向

從圖1中可以看出，近年來程序執(zhí)行時間預(yù)測所發(fā)SCI論文總體是呈上升趨勢的，說明這個研究方向是很有前景的。

安全關(guān)鍵實(shí)時程序執(zhí)行時間預(yù)測主要使用靜態(tài)方法。目前，在該領(lǐng)域有兩個較好的研究方向。一個面向編碼階段的交互式程序執(zhí)行時間預(yù)測。Harmon[2]等人采用基于語法樹的計算方法開發(fā)了volta ，該工具面向java程序和JOP處理器，能夠在編程過程中即時給出函數(shù)的WCET分析值。另一個是面向確認(rèn)階段的概率化程序執(zhí)行時間預(yù)測。Cazorla[3]設(shè)計了概率可分析的實(shí)時系統(tǒng)Proartis，能夠給出程序執(zhí)行時間的概率分布。確認(rèn)階段是由第三方對軟件進(jìn)行一致性驗(yàn)證的階段，安全關(guān)鍵軟件經(jīng)過安全性確認(rèn)后才可以交給用戶使用。

3 結(jié)束語

隨著信息物理系統(tǒng)的興起，安全關(guān)鍵實(shí)時程序必將應(yīng)用于更多的領(lǐng)域。為了確保系統(tǒng)安全，必須對程序執(zhí)行時間進(jìn)行預(yù)測，以保證程序能夠在安全的截至?xí)r間范圍內(nèi)運(yùn)行完成?；跍y量的方法由于獲得的執(zhí)行時間范圍比實(shí)際的小，因此不適用于安全關(guān)鍵實(shí)時程序。交互式以及概率化的程序執(zhí)行時間預(yù)測，作為靜態(tài)預(yù)測方法，具有很好的研究前景。

[參考文獻(xiàn)]

[1]魯志偉，馬文婧，宋文國，等.新立變電站接地系統(tǒng)安全性能研究[J]. 東北電力大學(xué)學(xué)報，2012，32（6）：28-32.

[2]Harmon T，Schoeberl M，Kirner R，et al.Fast，interactive worst-case execution time analysis with back-annotation[J]. Industrial Informatics，IEEE Transactions on，2012，8（2）：366-377.

[3]Cazorla F J，Quinones E，Vardanega T，et al.Proartis： Probabilistically analyzable real-time systems[J].ACM Transactions on Embedded Computing Systems （TECS），2013， 12（2s）：94.