軟件最壞場(chǎng)景運(yùn)行時(shí)間快速計(jì)算方法

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了軟件最壞場(chǎng)景運(yùn)行時(shí)間快速計(jì)算方法范文，希望能給你帶來靈感和參考，敬請(qǐng)閱讀。

【摘要】在安全關(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í)間（WorstCaseExecutionTime,WCET）。論文在傳統(tǒng)靜態(tài)WCET分析方法的基礎(chǔ)上，提出了將拓?fù)渑判蛩惴☉?yīng)用到WCET的計(jì)算中，較大地提升了WCET的計(jì)算效率。

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

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í)行的最長可能時(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í)行路徑信息，以便找出最長路徑。底層分析主要考慮處理器體系架構(gòu)對(duì)軟件運(yùn)行時(shí)間的影響，如何對(duì)緩存、流水線、亂序執(zhí)行、分支預(yù)測(cè)等特性進(jìn)行建模來提高WCET估計(jì)的精度。WCET計(jì)算主要研究如何在控制流分析、底層分析的基礎(chǔ)上找出WCET的算法。

2WCET分析技術(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)上比較成熟的工具有德國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í)行流），以找出最長路徑。控制流分析不考慮軟件運(yùn)行環(huán)境的硬件信息，分析研究主要集中在控制流的提取、邏輯結(jié)構(gòu)的表示、控制流的表示與轉(zhuǎn)換（如確定循環(huán)結(jié)構(gòu)）、循環(huán)上界及不可達(dá)路徑的確定等。控制流的提取主要依據(jù)源代碼（或目標(biāo)碼）的各種語法結(jié)構(gòu)如：構(gòu)等（或目標(biāo)碼中的跳轉(zhuǎn)、條件跳轉(zhuǎn)等），而確定循環(huán)最大次數(shù)，不可達(dá)路徑，需要更多的語義分析，必要時(shí)需要通過注解的方式來獲取。控制流的描述法主要有：語法樹、域樹、時(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è)分析等。

5WCET計(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（IntegerLinearProgramming）。本文采用基于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ò)（activityonvertexnetwork）有向圖。我們要對(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ù)渑判虻乃惴ㄈ缦拢孩僭诳刂屏鲌D中選取一個(gè)函數(shù)入口基本塊（沒有前趨）。②在控制流圖中刪除該基本塊及其所發(fā)出的所有邊。③重復(fù)執(zhí)行①、②，直至輸出全部沒有前趨的基本塊。當(dāng)過程結(jié)束時(shí)，如果有向圖中的所有基本塊均已輸出，則說明有向圖中不存在回路，否則說明有向圖存在回路。使用拓?fù)渑判蚩梢源_定有向圖中是否有回路，而在控制流圖中，只有循環(huán)存在時(shí)，才會(huì)存在回路。因此，使用拓?fù)渑判颍粌H可以排列出程序基本塊執(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ù)渑判蛩惴ǎ瑯O大地簡(jiǎn)化了WCET的計(jì)算，WCET計(jì)算的時(shí)間復(fù)雜度為O(n)，其中n表示函數(shù)基本塊的數(shù)目。經(jīng)過實(shí)際測(cè)試的驗(yàn)證，該方法的運(yùn)算速度快于ILP。

作者：陳勇 單位：中國航發(fā)控制系統(tǒng)研究所