【摘要】：實時系統(tǒng)時間驗證主要包括可調(diào)度性分析和最壞情況執(zhí)行時間(WCET)分析。其中WCET分析的目的是計算實時任務(wù)在最壞情況下的執(zhí)行時間,其結(jié)果是可調(diào)度性分析的重要輸入。在硬實時系統(tǒng)中,為保證分析結(jié)果的安全性,通常采用靜態(tài)方法分析程序的WCET。靜態(tài)分析主要包括處理器行為分析、程序流分析和WCET計算三個子任務(wù)。目前在WCET計算技術(shù)方面,隱式路徑枚舉技術(shù)是主導(dǎo)技術(shù),但是該技術(shù)的主要問題是描述復(fù)雜程序控制流程信息的能力很有限,進而也限制了處理器行為分析所能采用的技術(shù)。在處理器行為分析方面,Cache分析一直是一個難度較大的任務(wù)。目前基于抽象解釋技術(shù)的分析方法在分析LRU替換策略中占有主導(dǎo)地位,但是對于基于FIFO等其他替換策略的Cache行為的分析尚不成熟。隨著處理器體系結(jié)構(gòu)向多核發(fā)展,共享Cache成為了主要的設(shè)計趨勢之一。不同核心上的程序在共享Cache中相互干涉,給Cache分析帶來了極大的挑戰(zhàn)。此外,隨著WCET分析技術(shù)的不斷發(fā)展,相關(guān)技術(shù)在實際系統(tǒng)中的可用性問題也逐漸受到越來越多的關(guān)注。 基于上述研究現(xiàn)狀,本文針對WCET靜態(tài)分析中的WCET計算、單核與多核Cache行為分析、實時操作系統(tǒng)WCET分析等課題進行了深入研究。主要工作包括如下幾點： (1)提出了一種全新的基于模型檢測技術(shù)的WCET計算方法,設(shè)計了從程序到對應(yīng)自動機模型的轉(zhuǎn)換語義。該方法作為靜態(tài)WCET分析的基礎(chǔ)性框架,充分利用了模型檢測技術(shù)搜索最優(yōu)解的能力,使得分析結(jié)果具有更高的精度。探索了采用不同工作原理的模型檢測器用于WCET計算的時間可伸縮性和空間可伸縮性,給出了基于模型檢測技術(shù)的WCET計算方法的適用范圍。 (2)提出了一種基于剪枝思想的單核系統(tǒng)Cache分析方法。在基于模型檢測技術(shù)的WCET計算框架的基礎(chǔ)上,研究了利用這一技術(shù)對單核系統(tǒng)中采用FIFO替換策略的Cache進行分析的方法。針對模型檢測技術(shù)在WCET分析中可能出現(xiàn)的狀態(tài)空間爆炸問題,提出了基于剪枝思想的分析方法。該方法通過削減程序模型中符合特定條件的程序分支,能夠在不損失分析精度的前提下,有效提高分析的性能以及可伸縮性。 (3)提出了一種面向多核共享Cache的處理器行為分析方法。分析多核系統(tǒng)的共享Cache,關(guān)鍵在于對程序間的干涉情況進行精確的分析�，F(xiàn)有的方法在分析這一問題的過程中只考慮了不同核心上的程序在地址上的沖突情況,導(dǎo)致分析結(jié)果的過度估計過高。本文采用模型檢測技術(shù)對多核共享Cache的行為進行建模,模型能夠在更細(xì)的粒度上挖掘沖突發(fā)生的時間關(guān)系,從而大大提高了分析的精確性。 (4)對工業(yè)界廣泛使用的μC/OS-Ⅱ?qū)崟r操作系統(tǒng)進行了WCET分析。實時操作系統(tǒng)以控制密集型代碼為主,其代碼結(jié)構(gòu)和時間行為特性與普通應(yīng)用程序有很大區(qū)別。本文對μC/OS-Ⅱ?qū)崟r操作系統(tǒng)的系統(tǒng)調(diào)用和禁止中斷區(qū)間進行了靜態(tài)WCET分析,詳細(xì)分析了傳統(tǒng)技術(shù)在分析實時操作系統(tǒng)代碼時的精度以及尚存在的主要問題。同時,實驗結(jié)果本身就是對μC/OS-Ⅱ?qū)崟r操作系統(tǒng)實時特性的一個完整的量化描述,它對于使用者了解該系統(tǒng)的時間特性,以及對于系統(tǒng)開發(fā)者改善系統(tǒng)的實時性能都具有重要的應(yīng)用價值。 (5)本文在新加坡國立大學(xué)開發(fā)的Chronos工具的基礎(chǔ)上,設(shè)計并實現(xiàn)了一個支持多核體系結(jié)構(gòu)的靜態(tài)WCET分析工具,實現(xiàn)了本文所提出的基于模型檢測技術(shù)的WCET計算方法、基于FIFO替換算法的單核Cache行為分析、面向多核共享Cache的處理器行為分析、實時操作系統(tǒng)WCET分析等具體技術(shù)和方法,并驗證了這些方法的正確性和有效性。 總之,本文研究了采用模型檢測技術(shù)進行靜態(tài)WCET分析的問題,實驗表明采用這種技術(shù)能夠有效的提高靜態(tài)分析的精確性。同時還探討了采用靜態(tài)WCET分析方法分析實時操作系統(tǒng)的可行性及主要問題。本文的研究對于靜態(tài)WCET分析以及WCET分析可用性等領(lǐng)域的研究具有一定的參考價值。
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2010
【分類號】：TP368.1
【圖文】：

態(tài)WCET分析可以用數(shù)學(xué)手段證明其正確性，因此可以保證分析得到的執(zhí)行時間一定不會小于程序的實際WCET值。執(zhí)行時間觀測值、執(zhí)行時間估計值、及程序的實際WCET值的關(guān)系見圖1.1。分布執(zhí)行時間圖1.1程序執(zhí)行時間的基本概念[5]Fig.l一 Basieeoneeptsofexeeutiontimesofpro紅ams[5]如果分析得到的執(zhí)行時間大于程序的實際WCET值，我們稱這種分析結(jié)果是“安全(Safe)”的。分析結(jié)果越接近實際的WCET值，我們稱其越“精確(Aceurate)”。硬實時系統(tǒng)的WCET分析要求分析結(jié)果必須是安全的，因此通常采用靜態(tài)分析的方法。在實際系統(tǒng)中，程序的最壞情況執(zhí)行時間是很多因素綜合作用的結(jié)果，影響程序WCET的主要因素有三類:第一類是程序的流程，包括分支、循環(huán)、函數(shù)調(diào)用等;第二類是處

不同的指令集會影響程序的執(zhí)行時間。例如，某些簡單處理器其指令集中的所有指令都具有固定長度的執(zhí)行時間(通常以處理器周期為單位);而復(fù)雜處理器的指令集中常包含一些諸如乘法運算等的指令，這些指令的執(zhí)行時間往往依賴操作數(shù)的數(shù)值。為提高處理器的指令吞吐率，目前幾乎所有的桌面處理器和嵌入式處理器都采用了流水線的設(shè)計。同時為了更高效的利用處理器內(nèi)部的計算資源，流水線通常設(shè)計為亂序執(zhí)行的，也就是將可執(zhí)行代碼中的機器指令順序打亂執(zhí)行(但保證邏輯結(jié)果的正確性)。流水線的存在導(dǎo)致程序執(zhí)行時間的波動和不可預(yù)測。例如程序中的循環(huán)結(jié)構(gòu)，每次執(zhí)行到循環(huán)體的第一條指令的時候，流水線中的內(nèi)容通常是不固定的，這樣就導(dǎo)致循環(huán)的每次執(zhí)行時間都可能不相同。為得到較為精確的分析結(jié)果，就必須對流水線的工作過程進行詳細(xì)分析，這將導(dǎo)致分析難度的加大。另一方面，為了解決處理器運算速度和主存訪問速度之間的差異，目前幾乎所有的處理器都引入了Cache來解決上述問題。無論是指令還是數(shù)據(jù)，在Cache中命中與否都將直接影響程序的執(zhí)行時間。由于Cache的組織形式各異，替換策略也不盡相同，這就導(dǎo)致分析程序在最壞情況下的Cache命中情況變得非常困難。DE指令到達C|，|BI

本文編號：2735635