實(shí)時(shí)軟件最壞情況執(zhí)行時(shí)間估計(jì)研究.pdf

1、構(gòu)造一個(gè)實(shí)時(shí)系統(tǒng)的時(shí)候，安全性和程序最壞情況執(zhí)行時(shí)間(WCET)是必需的，為了給出WCET估計(jì)值，必須同時(shí)考慮到系統(tǒng)的軟件特性和硬件特性。傳統(tǒng)的方法是通過在目標(biāo)平臺(tái)上實(shí)際執(zhí)行程序來得到估計(jì)值的，但是這種方法既容易出錯(cuò)，也不能保證估計(jì)結(jié)果的正確性。另一種方法是靜態(tài)估計(jì)程序的WCET值，該方法必須考慮到所有可能的程序流和硬件特性的作用。在靜態(tài)估計(jì)方法中有三種常用WCET分析方法，它們分別是隱藏路徑列舉技術(shù)(IPET)、基于路徑(Path-b

2、ased)的計(jì)算方法和基于樹(Tree-based)的計(jì)算方法。 本文主要提出兩種基于路徑的計(jì)算實(shí)時(shí)程序最壞情況執(zhí)行時(shí)間的方法，這兩種方法首先檢測程序中存在的分支約束，然后將程序中存在的分支約束信息轉(zhuǎn)化為程序流程控制圖(CFG圖)中結(jié)點(diǎn)之間的語義沖突，并按照結(jié)點(diǎn)對(duì)的形式保存在相應(yīng)的沖突數(shù)組里，在接下來的WCET計(jì)算階段通過邊搜索程序執(zhí)行路徑邊檢測沖突數(shù)組里保存的已有的沖突關(guān)系以便在搜索路徑的同時(shí)排除非可行執(zhí)行路徑，提高搜索的效率

3、，最終在可行執(zhí)行路徑集中選擇具有最大執(zhí)行時(shí)間的執(zhí)行路徑。與以往的方法相比，本文的方法既避免了窮舉所有執(zhí)行路徑(其中包括可行執(zhí)行路徑和非可行執(zhí)行路徑)帶來的復(fù)雜度，也不需要在排除非可行執(zhí)行路徑之后重新回到流程控制圖(CFG圖)源結(jié)點(diǎn)重新搜索執(zhí)行路徑，而是在檢測沖突的同時(shí)適當(dāng)?shù)卣{(diào)整流程控制圖(CFG圖)并更新當(dāng)前路徑即可。 本文在給出這兩種方法詳細(xì)說明的同時(shí)也給出了它們對(duì)于標(biāo)準(zhǔn)實(shí)驗(yàn)程序的實(shí)驗(yàn)結(jié)果，并與其他方法做一個(gè)比較，實(shí)驗(yàn)證明對(duì)于