實時系統(tǒng)最壞執(zhí)行時間分析及測試

殷鋒社，湯小明

（陜西工業(yè)職業(yè)技術(shù)學院，陜西咸陽，712000中航工業(yè)西安飛行自動控制研究所，陜西西安，710075）

0 引言

實時系統(tǒng)指能夠在指定時間內(nèi)完成一定的計算和處理功能，并對外部事件作出響應(yīng)的計算機系統(tǒng)。實時系統(tǒng)的正確性不僅取決于其輸出結(jié)果的正確性，還取決于產(chǎn)生輸出結(jié)果的時間的正確性。根據(jù)實時系統(tǒng)對時間性要求的不同，實時系統(tǒng)可分為軟實時系統(tǒng)和硬實時系統(tǒng)。在軟實時系統(tǒng)中，未在規(guī)定的時間內(nèi)完成某項指定的功能或?qū)ν獠渴录鞒鲰憫?yīng)，將會降低系統(tǒng)的性能，如視頻點播系統(tǒng)（VOD）等。而在硬實時系統(tǒng)中，不滿足系統(tǒng)的時間特性要求則可能引起重大的災(zāi)難性后果，如飛行控制系統(tǒng)?？刂坡稍O(shè)計是飛行控制系統(tǒng)中非常重要的組成部分，在系統(tǒng)設(shè)計的最初，對控制算法設(shè)計的實時性進行分析及測試，是控制算法設(shè)計中非常重要的一個內(nèi)容。

1 程序最壞執(zhí)行時間

靜態(tài)最壞時間分析在考慮程序所有可能的輸入，系統(tǒng)狀態(tài)和軟硬件間交互的前提下，對軟件和硬件進行數(shù)學建模來分析確定程序的最壞執(zhí)行時間，而不用真實地運行程序。靜態(tài)程序最壞執(zhí)行時間分析開始于上世紀八十年代，歷經(jīng)二十多年的發(fā)展，取得了顯著的成果，已經(jīng)成為實時系統(tǒng)的一個重要研究領(lǐng)域。

WCET 分析包括動態(tài)度量、靜態(tài)分析和混合方法共3 種方法。

動態(tài)度量方法就是直接運行程序以測量程序的執(zhí)行時間，而由于通過驗證所有的輸入條件來測量最壞執(zhí)行時間通常難以實現(xiàn)，動態(tài)度量方法很難保證所得到結(jié)果是安全的，極可能會低估系統(tǒng)的最壞執(zhí)行時間。

混合方法是既包括靜態(tài)分析也包括動態(tài)度量的方法。該方法首先對程序進行分析，根據(jù)分析結(jié)果進行測試，或者先度量，然后在度量的基礎(chǔ)上靜態(tài)計算程序的WCET 值。

靜態(tài)分析方法根據(jù)程序的流信息，針對運行程序的處理器特性估算出程序的最壞執(zhí)行時間。而由于程序流信息分析的復(fù)雜性，特別是現(xiàn)代處理器體系架構(gòu)大都采用Cache 和流水線，超標量等技術(shù)，其建模非常復(fù)雜，靜態(tài)分析和計算也非常復(fù)雜。但靜態(tài)分析方法能夠保證得到的結(jié)果是安全的，而且能夠不運行程序就獲得結(jié)果，從而成為程序最壞執(zhí)行時間WCET 分析研究的主流。

2 靜態(tài)WCET 分析

靜態(tài)WCET 分析依賴于程序的模型和時間行為特性。靜態(tài)WCET分析必須是準確而且安全的。對程序WCET 的低估可能導(dǎo)致程序在規(guī)定時間內(nèi)不能完成所分配的工作，造成不可預(yù)知的后果。而過高的WCET 分析則喪失其作用并造成硬件資源的浪費。為了實現(xiàn)以上目的，靜態(tài)WCET 分析主要分為了三個階段：流分析，低層分析和WCET 計算。

2.1 流分析

流分析用于分析程序中可能及不可能的程序流信息。比如說，哪些函數(shù)可能會被調(diào)用，循環(huán)的迭代次數(shù)，條件判斷語句之間的相關(guān)性等。分析可以基于源代碼，也可以基于目標代碼或中間代碼。流分析又可以大致分為以下三個階段：

a)程序信息提取。程序流信息的提取階段主要是對程序的分析，抽象提取法是本階段使用的典型方法之一。抽象提取法是在不執(zhí)行程序的前提下，利用程序所有可能的輸入分析程序的行為特性。

b)程序結(jié)構(gòu)信息表示。提取所得的程序流信息可以用圖、語法樹或程序代碼的形式表示，表示的方式應(yīng)考慮到不僅便于閱讀，而且便于工具自動處理。

c)信息計算的轉(zhuǎn)化。在完成信息的表示后，需要將表示形式轉(zhuǎn)化為一種計算方式。在轉(zhuǎn)化過程中，可能需要將一些不會影響分析安全性的因素撇棄。

2.2 低層分析

由于控制算法的最終實現(xiàn)與底層硬件也是密切相關(guān)，因此需要針對目標代碼根據(jù)目標硬件獲取算法程序的實際行為特性，稱為低層分析。相對而言，以上所講的流分析也稱為高層分析。低層分析又可以分為全局低層分析和局部低層分析。

a)全局低層分析。全局低層分析主要包括高速緩存（Cache），流水線（pipeline）及動態(tài)分支預(yù)取等的分析。對高速緩存，需要針對緩存的類型是數(shù)據(jù)緩存還是指令緩存，分析緩存的替換（調(diào)度）策略，每一行的大小，訪問某一行時的加載延遲等。對動態(tài)預(yù)取指令的分析包括預(yù)取緩沖區(qū)的大小，替換策略以及動態(tài)預(yù)取失敗后的延遲等。

b)局部低層分析。局部低層分析一條單獨的指令及其臨近指令執(zhí)行時間的硬件特性，如管道重疊，存儲器的存取速度，指令或數(shù)據(jù)的可緩存性(Cacheability)等。

2.3 靜態(tài)WCET 計算方法

在完成程序的流分析和低層分析后，就可以開始計算程序的最差執(zhí)行時間。在計算方法上，主要分為三種：

a)基于路徑的計算方法：計算路徑的執(zhí)行時間，然后找出最長路徑的執(zhí)行時間即為程序最差執(zhí)行時間。

b)基于隱藏路徑列舉（IPET Implicit Path Enumeration Techniques）的計算方法：將程序分解為兩個約束集，一個表示程序的結(jié)構(gòu)信息，另一個表示程序執(zhí)行時最大循環(huán)迭代次數(shù)，在這兩個約束集上尋求最大化目標函數(shù)獲取程序最差執(zhí)行時間。

c)基于語法樹的計算方法：根據(jù)編譯后的匯編代碼，提取程序的控制流圖，根據(jù)不同語法結(jié)構(gòu)的不同規(guī)則，采用自底向上的語法樹回溯算法，計算程序最差執(zhí)行時間。

3 靜態(tài)WCET 分析工具

靜態(tài)WCET 經(jīng)過十多年的研究發(fā)展，不僅取得顯著的學術(shù)成果，而且也逐漸產(chǎn)生了一些好的WCET 分析工具，原型工具如SWEET,Heptane，商用工具如aiT 和BOUNT-T 開始在工程中取得應(yīng)用。

BOUND_T 是由芬蘭航天中心為歐洲航天協(xié)會開發(fā)的WCET 分析工具，基于可執(zhí)行代碼進行靜態(tài)WCET 分析，分析過程獨立于程序的源代碼，可以對多種不同語言開發(fā)的程序進行WCET 分析。

aiT 是由德國AbsInt 公司開發(fā)為嵌入式系統(tǒng)開發(fā)的WCET 分析工具，基于程序的可執(zhí)行代碼建立后續(xù)分析所需的流信息，在高速緩存和流水線分析中采用了抽象解釋的方法。

4 WCET 分析評估

為了檢測aiT 及BOUND_T 的適用性，AbsInt 公司和芬蘭航天中心都對自己的軟件工具進行了工程試用。AbsInt 公司利用aiT對實時操作系統(tǒng)OSE 中的系統(tǒng)調(diào)用和關(guān)中斷代碼段基于ARM7 硬件平臺進行了WCET 分析。結(jié)果顯示，關(guān)中斷代碼段非常適合WCET分析，因為這部分代碼通常比較簡短而且沒有太多循環(huán)，對這部分代碼的WCET 可以完全自動地完成。但由于系統(tǒng)調(diào)用中包括例外處理和循環(huán)，其WCET 分析不能自動完成。BOUND_T 對歐洲航天協(xié)會CryoSat 衛(wèi)星的控制和數(shù)據(jù)管理系統(tǒng)（CDMU Control and Data Management Unit）進行了WCET 分析，結(jié)果表明，BOUND_T 可以用于對CDMU 進行WCET 估計，但是，目前尚不足以自動完成整個分析過程。

AbsInt 公司同時還嘗試將aiT 與CCS 開發(fā)工具的開發(fā)流程進行整合，在此過程中，他們將使用aiT 所得到的WCET 分析結(jié)果與動態(tài)測試的結(jié)果進行了對比，見下表1。其中動態(tài)測試結(jié)果是通過使用邏輯分析儀獲取的。

通過上表我們可以發(fā)現(xiàn)，與仿真所估計的時間的比較，aiT 分析所得的WCET 較長，說明靜態(tài)WCET 具有良好的安全性。但是，我們也可以看出，靜態(tài)WCET 分析很可能過高地估計程序的最壞執(zhí)行時間，即其精確性仍有待進一步的改進。

5 結(jié)論

如果在系統(tǒng)設(shè)計的最初，使用靜態(tài)WCET 分析獲取程序的最差執(zhí)行時間，而在程序下載到目標機中后，使用邏輯分析儀對所獲取的最差執(zhí)行時間進行進一步的精確，可能是一個比較理想的應(yīng)用方式。我們相信，隨著靜態(tài)WCET 分析技術(shù)的發(fā)展以及WCET 工具的不斷完善，靜態(tài)WCET 分析在控制算法設(shè)計中，將會獲得系統(tǒng)設(shè)計師們更多的關(guān)注，并取得更廣泛地應(yīng)用。

[1]實時系統(tǒng)程序最差情況執(zhí)行時間(WCET) 的分析,姬孟洛,齊治昌,計算機科學,2006，第10 期；

[2]一種基于抽象解釋的WCET 自動分析工具，姬孟洛,李軍，計算機工程，2006，第14 期；

[3]實時系統(tǒng)最壞執(zhí)行時間分析，劉育芳,張立臣，計算機應(yīng)用研究，2005年，第11 期；

[4]Evaluating Static Worst-Case Execution-Time Analysis for a Commercial Real-Time Operating System，Daniel Sandell，2004 ；

[5]Evaluation of Static Time Analysis for CC Systems，Ola Eriksson，2005；

[6]Experience from industrial WCET Analysis Case Studies,Andreas Ermedahl,Jan Gustafsson,Bj’’orn Lisper,2005；