陳勇

【摘? 要】在安全關(guān)鍵實(shí)時(shí)系統(tǒng)設(shè)計(jì)中，為了保證系統(tǒng)的安全運(yùn)行，實(shí)時(shí)任務(wù)必須在截止期之前完成，否則將產(chǎn)生嚴(yán)重的后果。衡量系統(tǒng)實(shí)時(shí)性的重要指標(biāo)是任務(wù)的最壞場(chǎng)景運(yùn)行時(shí)間（Worst Case Execution Time， WCET）。論文在傳統(tǒng)靜態(tài)WCET分析方法的基礎(chǔ)上，提出了將拓?fù)渑判蛩惴☉?yīng)用到WCET的計(jì)算中，較大地提升了WCET的計(jì)算效率。

【Abstract】In the design of safety-critical real-time system， in order to ensure the safe operation of the system， the real-time task must be completed before the deadline， otherwise serious consequences may happen. Worst Case Execution Time （WCET） of a task is an important indicator of system real-time performance. Based on the traditional static WCET analysis method， this paper puts forward the application of topological sorting algorithm to the calculation of WCET， which greatly improves the calculation efficiency of WCET.

【關(guān)鍵詞】安全關(guān)鍵;實(shí)時(shí)系統(tǒng);WCET

【Keywords】safety-critical; real-time system; WCET

【中圖分類號(hào)】TP301.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號(hào)】1673-1069（2021）04-0158-02

1 引言

實(shí)時(shí)系統(tǒng)中對(duì)軟件運(yùn)行時(shí)間，相對(duì)于非實(shí)時(shí)系統(tǒng)來說有著嚴(yán)格的時(shí)限要求，非實(shí)時(shí)系統(tǒng)有較高的運(yùn)行時(shí)限容忍度，軟件偶然的運(yùn)行超時(shí)并不會(huì)造成嚴(yán)重后果，僅僅是降低了系統(tǒng)的吞吐量。而實(shí)時(shí)系統(tǒng)有剛性的、嚴(yán)格的時(shí)間限制，軟件運(yùn)行超出時(shí)限后，會(huì)導(dǎo)致系統(tǒng)不能實(shí)現(xiàn)它的預(yù)期目標(biāo)，或者帶來損害甚至導(dǎo)致系統(tǒng)失效，對(duì)于安全關(guān)鍵實(shí)時(shí)系統(tǒng)，系統(tǒng)失效帶來的后果可能是災(zāi)難性的，故它不允許任何超出時(shí)限的錯(cuò)誤。實(shí)時(shí)系統(tǒng)的時(shí)間性要求更關(guān)注的WCET是在目標(biāo)環(huán)境中的一個(gè)給定處理器上，完成一組任務(wù)執(zhí)行的最長(zhǎng)可能時(shí)間，要求在邏輯結(jié)果正確的前提下，WCET在分配的時(shí)間范圍之內(nèi)。

實(shí)時(shí)任務(wù)的WCET與軟件的輸入、采用的算法以及軟件運(yùn)行的目標(biāo)環(huán)境相關(guān)。基于程序的源代碼或目標(biāo)代碼，通過分析程序中的基本塊，對(duì)每個(gè)函數(shù)的控制流進(jìn)行分析，并獲取程序可能的執(zhí)行路徑信息，以便找出最長(zhǎng)路徑。底層分析主要考慮處理器體系架構(gòu)對(duì)軟件運(yùn)行時(shí)間的影響，如何對(duì)緩存、流水線、亂序執(zhí)行、分支預(yù)測(cè)等特性進(jìn)行建模來提高WCET估計(jì)的精度。WCET計(jì)算主要研究如何在控制流分析、底層分析的基礎(chǔ)上找出WCET的算法。

2 WCET分析技術(shù)

WCET分析方法分為三種：動(dòng)態(tài)測(cè)量方法、靜態(tài)分析方法和混合方法。

動(dòng)態(tài)測(cè)量是在目標(biāo)硬件環(huán)境下，基于需求，通過給定不同的輸入對(duì)程序進(jìn)行測(cè)試。通過收集程序每次的運(yùn)行時(shí)間可以獲得程序的最大運(yùn)行時(shí)間。然后對(duì)結(jié)果增加一定的時(shí)間余度以防止測(cè)量值低于實(shí)際的最壞場(chǎng)景下的運(yùn)行時(shí)間，由于測(cè)試不能窮舉，所以不能保證結(jié)果是安全的。

靜態(tài)分析方法是在分析處理器性能特性的基礎(chǔ)上，分析程序源代碼（或目標(biāo)碼）以獲取程序運(yùn)行時(shí)特征（如訪問的內(nèi)存地址、循環(huán)邊界等），最后計(jì)算程序所占用的處理器時(shí)間。主要過程包括：控制流分析、底層分析、WCET計(jì)算。典型WCET靜態(tài)分析過程如圖1所示。目前市場(chǎng)上比較成熟的工具有德國(guó)Absint公司的aiT[1]。

混合方法是綜合運(yùn)用靜態(tài)分析方法和動(dòng)態(tài)測(cè)量方法，但這里動(dòng)態(tài)測(cè)量與上述動(dòng)態(tài)測(cè)量方法的內(nèi)容是不相同的。在對(duì)程序中的小程序單位（如基本塊）進(jìn)行動(dòng)態(tài)測(cè)量（即替換了圖1中的底層分析過程）后，再進(jìn)行靜態(tài)分析得到WCET。

本文描述的是WCET靜態(tài)分析方法。

3 控制流分析

控制流分析基于程序的源代碼或目標(biāo)代碼，通過分析程序中的基本塊，對(duì)每個(gè)函數(shù)的控制流進(jìn)行分析，并獲取程序可能的執(zhí)行路徑信息（執(zhí)行流），以找出最長(zhǎng)路徑?？刂屏鞣治霾豢紤]軟件運(yùn)行環(huán)境的硬件信息，分析研究主要集中在控制流的提取、邏輯結(jié)構(gòu)的表示、控制流的表示與轉(zhuǎn)換（如確定循環(huán)結(jié)構(gòu)）、循環(huán)上界及不可達(dá)路徑的確定等?？刂屏鞯奶崛≈饕罁?jù)源代碼（或目標(biāo)碼）的各種語法結(jié)構(gòu)，如if-else、switch-case結(jié)構(gòu)等（或目標(biāo)碼中的跳轉(zhuǎn)、條件跳轉(zhuǎn)等），而確定循環(huán)最大次數(shù)，不可達(dá)路徑，需要更多的語義分析，必要時(shí)需要通過注解的方式來獲取?？刂屏鞯拿枋龇ㄖ饕校赫Z法樹、域樹、時(shí)間樹、控制流圖等[2]。本文基于目標(biāo)碼來生成函數(shù)的控制流圖，如圖2所示。

4 底層分析

如果指令是順序執(zhí)行的，則對(duì)順序執(zhí)行的程序指令，簡(jiǎn)單相加指令周期就可以得到程序運(yùn)行時(shí)間的一個(gè)估計(jì)。而具有CACHE、流水線、亂序執(zhí)行、分支預(yù)測(cè)等硬件特性的目標(biāo)處理器上，這種指令周期相加的計(jì)算方法只能得出相當(dāng)不準(zhǔn)確的WCET估計(jì)。因此，必須結(jié)合處理器各種加速特性對(duì)目標(biāo)碼進(jìn)行底層分析，才能獲取更為精確的WCET估計(jì)。底層分析一般包括：變量值分析、CACHE分析、流水線分析、分支預(yù)測(cè)分析等。

5 WCET計(jì)算

WCET的計(jì)算是通過結(jié)合控制流分析和底層分析的結(jié)果來計(jì)算程序的WCET估計(jì)值，當(dāng)前主要有三種計(jì)算方法：基于隱藏路徑枚舉的計(jì)算方法（IPET）、基于樹的計(jì)算方法及基于路徑的方法。

基于IPET的計(jì)算方法通過建立程序流程和基本塊的迭代模型及用數(shù)學(xué)約束，建立目標(biāo)函數(shù)，對(duì)WCET的計(jì)算就是進(jìn)行最大化求解，一般使用的約束包括：結(jié)構(gòu)約束和功能約束。結(jié)構(gòu)約束與程序的控制流有關(guān)，功能約束則與循環(huán)邊界、路徑信息和函數(shù)調(diào)用有關(guān)。最大化求解的主要的方法是整數(shù)線性規(guī)劃ILP（Integer Linear Programming）。本文采用基于IPET的計(jì)算方法，但在最后計(jì)算階段未使用ILP，而是引入了一種全新的計(jì)算方法，基于拓?fù)渑判虻挠?jì)算方法。

5.1 拓?fù)渑判蚝?jiǎn)介

拓?fù)渑判颍╰opological-sort）是指由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。拓?fù)渑判虺Ｓ脕泶_定一個(gè)包含依賴關(guān)系集合中，事物發(fā)生的先后順序。拓?fù)渑判蚴菍?duì)有向無環(huán)圖中的頂點(diǎn)的一種排序，排序的規(guī)則是：如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序中，A排在B的前面。

拓?fù)渑判虻牡湫蛻?yīng)用是根據(jù)作業(yè)或任務(wù)的相關(guān)性來安排它們的順序。例如，洗衣服時(shí)，洗衣機(jī)必須先洗出衣服，然后我們才能將衣服放入烘干機(jī)。這個(gè)特性可以應(yīng)用到工程上的施工流程。用頂點(diǎn)表示子工程（活動(dòng)），用有向邊表示活動(dòng)間的先后關(guān)系，這就形成了一個(gè)AOV網(wǎng)絡(luò)（activity on vertex network）有向圖。我們要對(duì)某個(gè)工程的施工流程是否可行進(jìn)行論證，就是必須檢測(cè)相應(yīng)的AOV網(wǎng)絡(luò)是否存在回路，一個(gè)AOV網(wǎng)絡(luò)中如果存在回路，這就意味著某個(gè)子工程的開工要以自身的完工為前提條件，這顯然是不可能的。確定AOV網(wǎng)絡(luò)是否存在回路則通過拓?fù)渑判騺硗瓿?。因此，研究拓?fù)渑判蛩惴ㄊ呛苡袑?shí)際意義的。

5.2 拓?fù)渑判蛩惴ㄔ赪CET中的應(yīng)用

從圖2可以看出，函數(shù)的控制流圖就是一個(gè)典型的有向圖。頂點(diǎn)表示程序基本塊，有向邊表示基本塊執(zhí)行的先后順序，如果從基本塊A到基本塊B之間存在一條路徑，則稱基本塊A是基本塊B的前趨，或稱基本塊B是基本塊A的后繼。如果[A， B]是控制流圖中的一條邊，則稱A是B的直接前趨，或稱B是A的直接后繼。拓?fù)渑判虻乃惴ㄈ缦拢?/p>

①在控制流圖中選取一個(gè)函數(shù)入口基本塊（沒有前趨）。

②在控制流圖中刪除該基本塊及其所發(fā)出的所有邊。

③重復(fù)執(zhí)行①、②，直至輸出全部沒有前趨的基本塊。

當(dāng)過程結(jié)束時(shí)，如果有向圖中的所有基本塊均已輸出，則說明有向圖中不存在回路，否則說明有向圖存在回路。

使用拓?fù)渑判蚩梢源_定有向圖中是否有回路，而在控制流圖中，只有循環(huán)存在時(shí)，才會(huì)存在回路。因此，使用拓?fù)渑判?，不僅可以排列出程序基本塊執(zhí)行的先后順序，還可以準(zhǔn)確地確定函數(shù)中的循環(huán)起點(diǎn)基本塊和循環(huán)終點(diǎn)基本塊，通過循環(huán)變化后，可以將函數(shù)控制流圖變成完整的拓?fù)浣Y(jié)構(gòu)圖。這樣，計(jì)算函數(shù)WCET的時(shí)間，就轉(zhuǎn)化成了對(duì)拓?fù)浣Y(jié)構(gòu)中每一個(gè)頂點(diǎn)完成時(shí)間的計(jì)算。函數(shù)的WCET實(shí)際上就是最后一個(gè)頂點(diǎn)完成的時(shí)間。

6 結(jié)語

本文對(duì)目前WCET分析技術(shù)進(jìn)行了詳細(xì)的研究討論，并給出了一個(gè)基于目標(biāo)碼分析的WCET分析過程。采用拓?fù)渑判蛩惴?，極大地簡(jiǎn)化了WCET的計(jì)算，WCET計(jì)算的時(shí)間復(fù)雜度為O（n），其中n表示函數(shù)基本塊的數(shù)目。經(jīng)過實(shí)際測(cè)試的驗(yàn)證，該方法的運(yùn)算速度快于ILP。

【參考文獻(xiàn)】

【1】AbsInt.The industry standard for static timing analysis[EB/OL].https：//www.absint.com/ait.

【2】Kirner R， Puschner P. Classification of WCET analysis techniques[C]// Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing （ISORC'05）. IEEE， 2005.