實時系統最壞執行時間分析及測試

殷鋒社，湯小明

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

0 引言

實時系統指能夠在指定時間內完成一定的計算和處理功能，并對外部事件作出響應的計算機系統。實時系統的正確性不僅取決于其輸出結果的正確性，還取決于產生輸出結果的時間的正確性。根據實時系統對時間性要求的不同，實時系統可分為軟實時系統和硬實時系統。在軟實時系統中，未在規定的時間內完成某項指定的功能或對外部事件作出響應，將會降低系統的性能，如視頻點播系統（VOD）等。而在硬實時系統中，不滿足系統的時間特性要求則可能引起重大的災難性后果，如飛行控制系統。控制律設計是飛行控制系統中非常重要的組成部分，在系統設計的最初，對控制算法設計的實時性進行分析及測試，是控制算法設計中非常重要的一個內容。

1 程序最壞執行時間

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

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

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

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

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

2 靜態WCET 分析

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

2.1 流分析

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

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

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

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

2.2 低層分析

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

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

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

2.3 靜態WCET 計算方法

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

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

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

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

3 靜態WCET 分析工具

靜態WCET 經過十多年的研究發展，不僅取得顯著的學術成果，而且也逐漸產生了一些好的WCET 分析工具，原型工具如SWEET,Heptane，商用工具如aiT 和BOUNT-T 開始在工程中取得應用。

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

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

4 WCET 分析評估

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

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

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

5 結論

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

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

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

[3]實時系統最壞執行時間分析，劉育芳,張立臣，計算機應用研究，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；