基于抽象解釋的實(shí)時軟件WCET研究.pdf

1、實(shí)時系統(tǒng)與其它應(yīng)用系統(tǒng)不同之處在于其正確性不僅取決于輸出結(jié)果的正確性，同時也取決于其所產(chǎn)生輸出結(jié)果所耗費(fèi)的時間。實(shí)時系統(tǒng)的結(jié)果只有在規(guī)定的時間范圍內(nèi)完成才是有效的。因此，提前獲得系統(tǒng)中每個任務(wù)的最壞情況執(zhí)行時間(Worst Case Execution Time，WCET)對于實(shí)時系統(tǒng)的調(diào)度分析具有非常重要的意義。
　　 WCET分析要求安全和盡可能的精確。由于WCET動態(tài)測量分析方法不能保證WCET分析結(jié)果是安全的，因此靜態(tài)分

2、析成為WCET分析的常用方法。靜態(tài)分析方法是在分析程序流信息和處理器特性的基礎(chǔ)上，計(jì)算實(shí)時程序所占用的處理器時間上限值。本文提出了基于擴(kuò)展的抽象解釋理論的WCET分析方法。
　　 在程序流分析中，本文系統(tǒng)地提出了一個基于抽象執(zhí)行(Abstract Execution)和通用單調(diào)數(shù)據(jù)流框架來分析程序變量取值區(qū)間的方法。它能夠用于計(jì)算程序的循環(huán)迭代上限、標(biāo)識不可達(dá)路徑等程序流信息。基于抽象解釋理論是程序語義的近似表示，因此這種分析方

3、法能夠保證分析的正確性而且可以自動地計(jì)算WCET分析的程序流信息，而不需要使用任何輔助標(biāo)注。
　　 本文將處理器特性分析分為兩個部分：全局低層分析和局部低層分析。全局低層分析對處理器cache建立抽象模型，通過將cache與內(nèi)存映射的狀態(tài)進(jìn)行抽象，從而分析cache命中情況，在分析過程中，本文使用must analysis和may analysis分析方法在抽象域中進(jìn)行抽象執(zhí)行。局部低層分析利用全部低層分析結(jié)果在硬件模型上模擬執(zhí)