面向多級中斷系統(tǒng)的任務(wù)最差響應(yīng)時(shí)間分析

于廣良,楊孟飛,徐建,姜宏

1.北京控制工程研究所,北京100190 2.中國空間技術(shù)研究院,北京100094

面向多級中斷系統(tǒng)的任務(wù)最差響應(yīng)時(shí)間分析

于廣良1,*,楊孟飛2,徐建1,姜宏1

1.北京控制工程研究所,北京100190 2.中國空間技術(shù)研究院,北京100094

針對航天嵌入式系統(tǒng)中存在多級中斷情況下的時(shí)間分析問題,提出了中斷與任務(wù)混合的響應(yīng)時(shí)間計(jì)算模型。該模型中斷與任務(wù)使用統(tǒng)一的優(yōu)先級定義,將多級中斷嵌套的響應(yīng)時(shí)間分析與任務(wù)嵌套的響應(yīng)時(shí)間分析相結(jié)合,推導(dǎo)出了混合模型下響應(yīng)時(shí)間計(jì)算公式。并進(jìn)一步比較了中斷與任務(wù)的異同,闡述了公式中關(guān)鍵參數(shù)的含義與計(jì)算方法。最后利用開源的LEON3平臺和Modelsim軟件對所述方法進(jìn)行了仿真驗(yàn)證,結(jié)果表明,任務(wù)最差響應(yīng)時(shí)間過估小于5%,可以得到準(zhǔn)確的分析結(jié)果,有較高的工程應(yīng)用價(jià)值。

實(shí)時(shí)系統(tǒng);嵌入式軟件;多級中斷;固定優(yōu)先級調(diào)度;可調(diào)度性分析;最差響應(yīng)時(shí)間;航天器

對于航天嵌入式系統(tǒng)而言,其上運(yùn)行的軟件通常有著明確的時(shí)間約束,保證其正確性的一個(gè)關(guān)鍵問題是保證各個(gè)任務(wù)在其截止時(shí)間之前完成。由于此類系統(tǒng)通常使用中斷方式接收和處理來自外部設(shè)備的各種隨機(jī)或周期信號,隨時(shí)隨處都會發(fā)生的中斷成為影響實(shí)時(shí)性的一個(gè)重要因素,當(dāng)系統(tǒng)中有多級中斷時(shí)更是如此[1]。

中斷會打斷任務(wù)程序的執(zhí)行,引入額外的時(shí)間開銷,這對于驗(yàn)證任務(wù)是否滿足其截止時(shí)間提出了挑戰(zhàn)。最差響應(yīng)時(shí)間(Worst Case Response Time,WCRT)[2]是指任務(wù)從釋放到執(zhí)行完成的最大可能時(shí)間間隔,通常的分析是針對任務(wù)間的搶占情況,通過計(jì)算各任務(wù)被其他任務(wù)搶占時(shí)的最差響應(yīng)時(shí)間,將其與該任務(wù)的截止時(shí)間比較,以求得出任務(wù)集的可調(diào)度性,目前這方面研究已有進(jìn)展[3-4]。但是對于中斷影響下的任務(wù)時(shí)間特性的分析研究還比較少。

文獻(xiàn)[5]考慮了中斷驅(qū)動程序截止時(shí)間分析問題,即檢查每個(gè)中斷是否都能在截止時(shí)間前處理完成。文獻(xiàn)[6]利用了上下文切換次數(shù)限制和采用基本路徑來限制需搜索的路徑空間,將中斷驅(qū)動程序轉(zhuǎn)化為順序程序進(jìn)行分析,以得出主程序在多個(gè)中斷服務(wù)程序(Interrupt Service Routine,ISR)影響下的最差執(zhí)行時(shí)間。文獻(xiàn)[7]分析了衛(wèi)星控制系統(tǒng)時(shí)序問題,建立了包含中斷在內(nèi)的時(shí)序模型。文獻(xiàn)[8]考慮了中斷處理開銷對動態(tài)優(yōu)先級系統(tǒng)可調(diào)度性的影響,文獻(xiàn)[9]則考慮了多處理器系統(tǒng)的中斷開銷計(jì)算。

但是上述研究都將中斷單獨(dú)考慮,沒有與任務(wù)的時(shí)間分析方法融合。本文將中斷集與任務(wù)集結(jié)合起來,定義統(tǒng)一的參數(shù)并在一個(gè)統(tǒng)一的優(yōu)先級空間里進(jìn)行分析。利用任務(wù)響應(yīng)時(shí)間分析方法來分析多級中斷下的任務(wù)最差響應(yīng)時(shí)間,仿真結(jié)果表明本文所述方法可以很好地推廣到包含多級中斷系統(tǒng)的時(shí)間和時(shí)序分析中。

1 系統(tǒng)描述及模型定義

1.1 系統(tǒng)描述

本文研究的航天嵌入式系統(tǒng)軟件模型由任務(wù)程序和中斷服務(wù)程序組成,如圖1所示。系統(tǒng)在上電復(fù)位之后首先進(jìn)行硬件的初始化,在最開始部分是初始化中斷向量表,為每個(gè)中斷的服務(wù)程序定義一個(gè)入口地址;完成硬件初始化后跳轉(zhuǎn)到系統(tǒng)主函數(shù),完成系統(tǒng)的配置及操作系統(tǒng)內(nèi)核初始化等;最后使能中斷,內(nèi)核啟動空閑任務(wù),等待各個(gè)滿足條件的任務(wù)進(jìn)行調(diào)度(如圖1中任務(wù)1到任務(wù)N所示)。在任務(wù)運(yùn)行期間,如果有中斷請求信號產(chǎn)生,則處理器會響應(yīng)相應(yīng)的中斷請求,運(yùn)行圖1中中斷1到中斷M代表的中斷服務(wù)程序。

一般來說,處理器的異常包含了中斷、陷阱、故障和終止。陷阱、故障和終止通常是同步發(fā)生的,是執(zhí)行當(dāng)前指令的結(jié)果,中斷是異步發(fā)生的,是來自處理器外部的I/O設(shè)備的信號的結(jié)果[10]。本文只考慮異步中斷,不考慮其他異常控制流。

中斷對低優(yōu)先級任務(wù)的搶占除了引入其最差執(zhí)行時(shí)間之外,其中一項(xiàng)非常重要的代價(jià)是由于高速緩存(cache)塊的驅(qū)逐引起的。中斷可能會將對低優(yōu)先級任務(wù)有用高速緩存塊驅(qū)逐出高速緩存,導(dǎo)致重新運(yùn)行低優(yōu)先級任務(wù)時(shí)這些高速緩存塊需要從內(nèi)存中重新加載,這段搶占代價(jià)稱為高速緩存相關(guān)的搶占延遲(Cache Related Preemption Delay,CRPD),其大小限界為g×tbr,其中g(shù)為由于搶占導(dǎo)致的重新加載的高速緩存塊數(shù)目的上限,tbr為從內(nèi)存中加載塊到高速緩存內(nèi)需要的時(shí)間上限[11]。本文研究的是航天嵌入式系統(tǒng),通常為了保證時(shí)間確定性,較少使用高速緩存,本文為了簡化分析,暫不考 慮cache的影響,對其分析將作為以后的工作。

圖1 航天嵌入式系統(tǒng)軟件模型Fig.1 Software model of aerospace embedded system

1.2 模型定義

本文考慮的系統(tǒng)采用固定優(yōu)先級搶占式調(diào)度,允許多級中斷嵌套。系統(tǒng)的中斷服務(wù)程序集定義為IM=(ξ1,ξ2,…,ξm),任務(wù)集定義為TN=(τ1,τ2,…,τn),對中斷和任務(wù)而言,下標(biāo)順序代表了其優(yōu)先級順序,下標(biāo)越小,則優(yōu)先級越高,任務(wù)和中斷都具有惟一獨(dú)有的優(yōu)先級。為了方便起見,本文使用相同的符號表示任務(wù)和中斷,將中斷與任務(wù)的混合集定義為(τ1,τ2,…,τm,τm+1,…,τm+n),按照優(yōu)先級從大到小排列,下標(biāo)從1到m代表中斷,從m+1到n代表任務(wù)。在需要區(qū)分時(shí),用下標(biāo)τ和ξ來分別代表任務(wù)和中斷的性質(zhì)。所用到的符號及其描述(i=1,2,…,m+n):τi為任務(wù)集中優(yōu)先級為i的任務(wù);ξi為中斷集中優(yōu)先級為i的中斷;ri為任務(wù)的釋放時(shí)間或者中斷的觸發(fā)時(shí)間;ai為任務(wù)的到達(dá)時(shí)間或中斷信號的產(chǎn)生時(shí)間;si為任務(wù)或者中斷的開始執(zhí)行時(shí)間;fi為任務(wù)或者中斷的執(zhí)行完成時(shí)間;Ci為任務(wù)或者中斷的最差執(zhí)行時(shí)間;Di為任務(wù)或者中斷的相對時(shí)間限(相對于任務(wù)到達(dá)時(shí)間或者中斷產(chǎn)生時(shí)間);Ti為任務(wù)或者中斷的周期,對于非周期任務(wù)和中斷為其最小間隔時(shí)間;Bi為任務(wù)的阻塞時(shí)間,或者中斷禁止導(dǎo)致的中斷延遲時(shí)間;Ji為任務(wù)或者中斷的釋放抖動時(shí)間,即為任務(wù)從到達(dá)到釋放或者中斷從信號產(chǎn)生到觸發(fā)的時(shí)間;Ri為任務(wù)或者中斷的響應(yīng)時(shí)間,有Ri= fi-ri。

定義hp(i)和lp(i)代表優(yōu)先級高于和低于τi或ξi任務(wù)和中斷,用hep(i)和lep(i)代表優(yōu)先級大于等于或者小于等于τi或ξi的任務(wù)和中斷。這里認(rèn)為任務(wù)和中斷的截止時(shí)間是受限的,即Di≤Ti。并且任務(wù)和中斷一旦開始執(zhí)行,不會停頓一直到執(zhí)行完畢,除非被搶占或阻塞。任務(wù)的最差響應(yīng)時(shí)間為其釋放到其運(yùn)行結(jié)束的最長時(shí)間,中斷的最差響應(yīng)時(shí)間為其被處理器識別到其運(yùn)行完畢的最長時(shí)間。任務(wù)和中斷的最差響應(yīng)時(shí)間應(yīng)該滿足小于或等于截止時(shí)間減去其抖動時(shí)間Ri≤Di-Ji。

圖2給出了上述模型的一個(gè)例子,整個(gè)系統(tǒng)由兩個(gè)中斷和兩個(gè)任務(wù)組成,分別屬于中斷集和任務(wù)集,依照其優(yōu)先級從高到低,統(tǒng)一進(jìn)行編號,不過相同的參數(shù)對于中斷與任務(wù)來說,含義可能不同。在任務(wù)2執(zhí)行過程中任務(wù)1到達(dá),然后被操作系統(tǒng)釋放到就緒隊(duì)列,調(diào)度器檢測到高優(yōu)先級任務(wù)1就緒則發(fā)起上下文切換,任務(wù)1搶占任務(wù)2得到優(yōu)先運(yùn)行,期間中斷2被觸發(fā),系統(tǒng)響應(yīng)中斷后執(zhí)行中斷服務(wù)程序,中斷2的中斷服務(wù)程序運(yùn)行期間中斷1產(chǎn)生,發(fā)生中斷嵌套,各自運(yùn)行完成后依次返回,最后返回到任務(wù)2繼續(xù)執(zhí)行。

圖2 任務(wù)與中斷混合模型示例Fig.2 Example of task and ISR integrated model

2 響應(yīng)時(shí)間分析

由圖1和圖2的系統(tǒng)模型和示例可以看出,系統(tǒng)中可能包含有任務(wù)嵌套、中斷嵌套以及中斷對任務(wù)的搶占。假設(shè)系統(tǒng)中沒有或禁止中斷,則某任務(wù)的響應(yīng)時(shí)間主要受到高優(yōu)先級任務(wù)搶占的影響,這是目前大部分響應(yīng)時(shí)間分析所研究的問題。如果系統(tǒng)中存在中斷,由于所有中斷的優(yōu)先級均高于任務(wù)的優(yōu)先級,故某中斷的響應(yīng)時(shí)間主要受到高優(yōu)先級中斷搶占的影響,本節(jié)將詳細(xì)闡述如何利用任務(wù)搶占下的任務(wù)響應(yīng)時(shí)間分析方法來分析中斷搶占下的中斷響應(yīng)時(shí)間。有了中斷的響應(yīng)時(shí)間分析,則容易分析系統(tǒng)中只有一個(gè)主函數(shù),其他功能都是通過中斷來實(shí)現(xiàn)的中斷驅(qū)動程序的響應(yīng)時(shí)間,此類系統(tǒng)的時(shí)間開銷主要來自于中斷的搶占。如果系統(tǒng)中同時(shí)存在任務(wù)嵌套與中斷嵌套,這時(shí)候某任務(wù)的響應(yīng)時(shí)間將分別受到高優(yōu)先級任務(wù)搶占與中斷搶占所帶來的影響,利用前面所得到的分析結(jié)果也容易擴(kuò)展到這種情況。

本節(jié)首先回顧固定優(yōu)先級搶占式調(diào)度下任務(wù)的響應(yīng)時(shí)間計(jì)算公式,接著說明如何利用其計(jì)算中斷響應(yīng)時(shí)間,進(jìn)而得出中斷驅(qū)動程序的響應(yīng)時(shí)間計(jì)算,最后導(dǎo)出在多任務(wù)和多級中斷情況下的任務(wù)的最差響應(yīng)時(shí)間計(jì)算公式。

2.1 任務(wù)嵌套下的任務(wù)響應(yīng)時(shí)間

對固定優(yōu)先級搶占式調(diào)度的響應(yīng)時(shí)間分析[]:

式中 ?·?為向上取整運(yùn)算,代表任務(wù)τi的響應(yīng)期間被任務(wù)τj搶占的最大次數(shù);Ci為任務(wù)τi的最差執(zhí)行時(shí)間;Bi為其最大阻塞時(shí)間;Jj為高優(yōu)先級任務(wù)τj的釋放抖動;Cj為其最差執(zhí)行時(shí)間,Tj為其周期。

2.2 中斷嵌套下的中斷響應(yīng)時(shí)間

利用式(1)計(jì)算中斷嵌套下的中斷響應(yīng)時(shí)間,不改變公式的形式,式(1)中的參數(shù)含義采用第2.2節(jié)模型中的中斷參數(shù)的定義,記為

對于式(2)的求解應(yīng)從高優(yōu)先級到低優(yōu)先級依次進(jìn)行,首先從最高優(yōu)先級中斷ξ1開始,由于其為最高優(yōu)先級,所以hp(1)=?,根據(jù)式(2),其最差響應(yīng)時(shí)間應(yīng)為R1=C1+B1,其中C1為其最差執(zhí)行時(shí)間,其值包含了從處理器跳轉(zhuǎn)到返回之間的所有執(zhí)行時(shí)間的最大值;B1為優(yōu)先級小于1的中斷程序和任務(wù)程序中的最長關(guān)中斷的時(shí)間。

接著依次求解ξ2一直到ξm,對于ξm,其可能被ξm-1到ξ1搶占,所以hp(m)={ξm-1,ξm-2,…,ξ1},求解過程是一個(gè)迭代的過程。首先計(jì)算其不被中斷情況下的最差響應(yīng)時(shí)間為R0m= Cm+Bm,其中Cm為其最差執(zhí)行時(shí)間,Bm為任務(wù)程序中最長關(guān)中斷時(shí)間。考慮被搶占的情況,則有:

式(3)中上標(biāo)n代表迭代次數(shù),對于存在搶占情況下ξm響應(yīng)時(shí)間的求取是一個(gè)迭代過程,迭代從R0m開始,直到Rnm=Rn-1m或者Rnm＞Dm-Jm為止,前者表明已經(jīng)求得最差響應(yīng)時(shí)間為Rnm,而后者代表最差響應(yīng)時(shí)間已經(jīng)超過了ξm的截止時(shí)間限。需要說明的是,式(3)的迭代在優(yōu)先級高于m的所有中斷的總CPU利用率小于1時(shí)總會收斂,即總會有時(shí)間留給中斷m執(zhí)行,則最終會執(zhí)行完畢。

下面做進(jìn)一步說明,式(3)中?·?為ξm可能被高優(yōu)先級中斷搶占的最大次數(shù),向上取整;包含了阻塞時(shí)間Bm,這是因?yàn)榧僭O(shè)當(dāng)系統(tǒng)關(guān)中斷時(shí)產(chǎn)生中斷,在系統(tǒng)開中斷后將依次響應(yīng)相應(yīng)的中斷請求,而不會丟失中斷;使用Cj而不是Rj,是因?yàn)閷τ谧枞麜r(shí)間來說,如果中斷j＜m被阻塞,則可能存在兩種情況:①中斷m正在執(zhí)行關(guān)中斷區(qū)域,這段時(shí)間包含在了Cm中;②中斷m也被阻塞,這段時(shí)間包含在了Bm中。對于中斷j再被更高優(yōu)先級的中斷搶占的情況來說(中斷m被更高優(yōu)先級的中斷間接搶占),也已經(jīng)包含在搶占次數(shù)的計(jì)算里了。

對于中斷而言,一般情況下,截止時(shí)間應(yīng)小于其周期,這樣便不會發(fā)生中斷丟失。實(shí)際上,若在某中斷響應(yīng)期間,同一中斷信號再次到來,只要這時(shí)已經(jīng)清除了CPU的中斷請求位,中斷也不會丟失。但是這樣的設(shè)計(jì)余量非常小,本文并不考慮這種極端情況,而認(rèn)為中斷的截止時(shí)間小于等于其周期,即Di≤Ti, 1≤i≤m。

2.3 中斷嵌套下的任務(wù)響應(yīng)時(shí)間

對于任務(wù)之間不存在嵌套,但是中斷之間存在嵌套的中斷驅(qū)動軟件而言,某任務(wù)τi的響應(yīng)時(shí)間為

式中Ci為任務(wù)τi的最差執(zhí)行時(shí)間,由于任務(wù)間無嵌套,故不會被阻塞,因此沒有包含阻塞時(shí)間。式(4)等式右端第2部分為所有中斷對其可能的搶占所占用的時(shí)間。

2.4 中斷與任務(wù)嵌套下的任務(wù)響應(yīng)時(shí)間

由本節(jié)前面的分析可得,在圖1和圖2所示的集成模型里,某任務(wù)τi的響應(yīng)時(shí)間為

其中,等式右邊第3部分為優(yōu)先級大于i的任務(wù)對其的搶占所占用的時(shí)間,第4部分為所有中斷對其搶占所占用的時(shí)間。式(5)求解迭代到其響應(yīng)時(shí)間不再變化或者超過截止時(shí)間為止,得到在中斷與任務(wù)嵌套下的某任務(wù)的最差響應(yīng)時(shí)間。

3 參數(shù)含義與計(jì)算方法

3.1 最差執(zhí)行時(shí)間

程序的最差執(zhí)行時(shí)間(Worst Case Execution Time,WCET)[12]是指在所有可能的情況中,程序在對應(yīng)的硬件平臺上執(zhí)行時(shí)花費(fèi)的最長時(shí)間。WCET給出了某段程序執(zhí)行的時(shí)間上限,評判其分析方法或者工具好壞的兩個(gè)準(zhǔn)則是安全性和精確性:如果分析得到的時(shí)間大于程序的實(shí)際WCET值,稱這種分析結(jié)果是“安全(Safe)”的;分析結(jié)果越接近實(shí)際的WCET值,稱其越“精確(Precision)”。

WCET是任務(wù)自身(例如獨(dú)享處理器)的最差行為,而WCRT是任務(wù)在任務(wù)集(例如共享同一處理器)中的最差行為,WCET分析是WCRT分析的基礎(chǔ)。在一個(gè)實(shí)時(shí)系統(tǒng)中,當(dāng)沒有搶占時(shí),可以用WCET來檢查任務(wù)是否滿足截止時(shí)間;當(dāng)有多個(gè)任務(wù)允許搶占時(shí),需要使用WCRT來驗(yàn)證是否滿足時(shí)間約束。

尋找程序的WCET有靜態(tài)分析和基于測量的方法共兩種主流方法,代表性的商業(yè)工具有aiT和RapiTime等,在這里并不展開闡述,對于任務(wù)的最差執(zhí)行時(shí)間可以通過上面任意一種方法或工具獲得。但是對于中斷的最差執(zhí)行時(shí)間的獲取卻并不那么直接,因?yàn)槠渲邪酥袛嗟那袚Q時(shí)間。一個(gè)典型的中斷處理流程如圖3所示。

任務(wù)程序在t0時(shí)刻開始執(zhí)行,t1時(shí)刻中斷信號產(chǎn)生,t2時(shí)刻處理器開始響應(yīng)中斷,此時(shí)處理器將繼續(xù)完成正在執(zhí)行的指令(有些處理器可能允許中斷長指令),完成斷點(diǎn)保存并跳轉(zhuǎn)到中斷向量表處,以上部分由處理器自動完成。從t3時(shí)刻起執(zhí)行中斷向量表中指令并分支到相應(yīng)的中斷服務(wù)程序,開始任務(wù)上下文的保存等,從t4時(shí)刻到t5時(shí)刻為用戶編寫的中斷服務(wù)程序的執(zhí)行時(shí)間,到t6時(shí)刻恢復(fù)了被中斷任務(wù)的上下文,中斷服務(wù)程序處理完成,任務(wù)程序繼續(xù)執(zhí)行到t7時(shí)刻結(jié)束。

圖3 中斷服務(wù)時(shí)間流程Fig.3 Timeline of ISR

前述公式中中斷的Cj(1≤j≤m)指的是t2～t6時(shí)間段,其中t2～t3時(shí)間段為CPU相關(guān),設(shè)其最大時(shí)間為tξp;t3～t4時(shí)間段和t5～t6時(shí)間段為操作系統(tǒng)相關(guān),分別設(shè)為tξo1和tξo2,總的為tξo;t4～t5時(shí)間段為用戶相關(guān),最大時(shí)間設(shè)為tξu。在分析的時(shí)候,應(yīng)根據(jù)相應(yīng)CPU手冊和操作系統(tǒng)的說明并進(jìn)行測試得到tξp和tξo,這兩個(gè)時(shí)間是相對固定的。但對tξu而言,與應(yīng)用相關(guān),差別較大,這里對不同中斷使用其優(yōu)先級來區(qū)分,表示為tu,j,可得Cj= tξp+tξo+tu,j(1≤j≤m),與中斷相比,任務(wù)搶占導(dǎo)致的上下文切換完全是由操作系統(tǒng)來完成的,故沒有處理器跳轉(zhuǎn)的時(shí)間,一般來說其切換效率要比中斷低,花費(fèi)的時(shí)間也比中斷長。

3.2 最大阻塞時(shí)間

對任務(wù)而言,當(dāng)其訪問一些共享變量時(shí),通常要確保獨(dú)占性訪問,此任務(wù)操作共享變量的指令構(gòu)成了一個(gè)臨界區(qū),為了保證正確性,不同的任務(wù)執(zhí)行臨界區(qū)指令時(shí),必須實(shí)現(xiàn)互斥的訪問。一個(gè)低優(yōu)先級任務(wù)通過鎖定臨界區(qū)來確保獨(dú)占性訪問時(shí)可以阻塞高優(yōu)先級的任務(wù),這樣可能導(dǎo)致優(yōu)先級反轉(zhuǎn)的產(chǎn)生,采用優(yōu)先級繼承協(xié)議能夠避免優(yōu)先級反轉(zhuǎn)問題,但是難以避免死鎖的發(fā)生,采用優(yōu)先級上限協(xié)議可以避免優(yōu)先級反轉(zhuǎn)和死鎖[13]。

但是對于中斷而言,為了保證快速響應(yīng),一般不能被阻塞,所以中斷服務(wù)程序與任務(wù)間共享數(shù)據(jù)只能通過開關(guān)中斷進(jìn)行保護(hù);同時(shí)任務(wù)程序中和中斷服務(wù)程序中某些需要連續(xù)執(zhí)行的部分也會采用關(guān)中斷的方式進(jìn)行保護(hù)。定義βi為任務(wù)程序和優(yōu)先級小于ξi的中斷服務(wù)程序中所有關(guān)中斷區(qū)域的集合,設(shè)bmaxi為集合βi中關(guān)中斷區(qū)域最差執(zhí)行時(shí)間的最大值,則有Bi=bmaxi。

3.3 最小到達(dá)時(shí)間

對于周期性中斷而言,其最小到達(dá)時(shí)間就是其周期。但對于隨機(jī)中斷,可能會隨時(shí)到達(dá),但通常會有一個(gè)最小的時(shí)間間隔。以總線的接收中斷為例,其最小時(shí)間間隔為發(fā)送的數(shù)據(jù)包在線上的傳輸時(shí)間加上數(shù)據(jù)包發(fā)送之間的時(shí)間間隔[7]。

假設(shè)單次中斷所需要的數(shù)據(jù)總傳輸位數(shù)為d,數(shù)據(jù)傳輸?shù)乃俾蕿閒,則可知其線上傳輸時(shí)間為設(shè)定兩次數(shù)據(jù)之間的最小發(fā)送時(shí)間間隔為tδ,則可估算中斷的最小觸發(fā)周期為Tj= tδ,j+tl,j。

3.4 釋放抖動

任務(wù)到達(dá)后不一定會被立刻被放到就緒隊(duì)列里,這樣從任務(wù)到達(dá)到其釋放(放到就緒隊(duì)列)之間的時(shí)間稱為釋放抖動。對中斷而言,從中斷信號產(chǎn)生到被識別(例如高電平觸發(fā),電平變高需維持一段時(shí)間被識別)的時(shí)間定義為中斷的釋放抖動,這段時(shí)間一般非常短暫。事實(shí)上,釋放抖動使得中斷連續(xù)兩次觸發(fā)的時(shí)間間隔并不嚴(yán)格等同于其周期,對于中斷的多次釋放,抖動對被搶占的任務(wù)或中斷響應(yīng)時(shí)間影響僅存在第一個(gè)和最后一個(gè),設(shè)釋放抖動的最大時(shí)間為tmaxJ,最小時(shí)間為tminJ,容易得到Jj=tmaxJ-tminJ。

4 仿真分析

以一個(gè)航天嵌入式控制軟件為例分析,控制系統(tǒng)的任務(wù)通常是同步的、周期性的、由時(shí)間觸發(fā)的。本文設(shè)定在一個(gè)任務(wù)周期內(nèi)任務(wù)在各自分配的時(shí)間片內(nèi)運(yùn)行,沒有相互間的嵌套和跨時(shí)間片任務(wù),時(shí)間片的結(jié)束時(shí)刻是其截止時(shí)間。在不同的任務(wù)周期間,任務(wù)重復(fù)的運(yùn)行。中斷是異步發(fā)生的,它們可以搶占任務(wù)得到優(yōu)先運(yùn)行,造成任務(wù)執(zhí)行時(shí)間的延遲,當(dāng)系統(tǒng)中有多個(gè)中斷時(shí),中斷之間還可能產(chǎn)生嵌套,這樣不但要分析中斷下任務(wù)的最差響應(yīng)時(shí)間,同時(shí)需要分析中斷嵌套下中斷的最差響應(yīng)時(shí)間。

4.1 環(huán)境配置

利用開源的處理器LEON3和自主開發(fā)的SpaceOS操作系統(tǒng)在Modelsim軟件中仿真驗(yàn)證多級中斷對任務(wù)響應(yīng)時(shí)間的影響。LEON3是歐洲航天局下的Gaisler研究所開發(fā)的一個(gè)使用SPARC V8指令集的32位RISC處理器,它的源代碼由可綜合的VHDL代碼構(gòu)成。基于GPL許可證協(xié)議,LEON3非容錯版本軟核IP提供VHDL源代碼。空間嵌入式操作系統(tǒng)SpaceOS是由北京控制工程研究所研制的星載計(jì)算機(jī)嵌入式操作系統(tǒng),已經(jīng)在多個(gè)航天型號任務(wù)上得到了應(yīng)用[14]。

硬件環(huán)境配置是時(shí)鐘頻率為100 MHz,處理器核心數(shù)為1,寄存器窗口數(shù)目設(shè)置為8個(gè),為保證時(shí)間確定性,不使用浮點(diǎn)數(shù)單元,整數(shù)單元不使用分支預(yù)測,不使用指令與數(shù)據(jù)cache,不開啟存儲器管理單元(MMU)。片外連接8 M×32bit的SRAM存儲器,帶有5個(gè)片內(nèi)定時(shí)器和兩個(gè)通用串口等。軟件環(huán)境配置為使用分時(shí)調(diào)度,任務(wù)周期中斷由外部中斷0產(chǎn)生,時(shí)間片中斷由定時(shí)器1產(chǎn)生,任務(wù)的讀寫等待周期全部設(shè)置為1。系統(tǒng)另外設(shè)計(jì)為包含4個(gè)任務(wù)和4個(gè)中斷,相應(yīng)參數(shù)如表1和表2所示,表1中TIMR1括號內(nèi)的值是帶有任務(wù)釋放時(shí)的最差執(zhí)行時(shí)間。

表1 系統(tǒng)的中斷組成Table 1 Interrupts of the system

表2 系統(tǒng)的任務(wù)組成Table 2 Tasks of the system

表1和表2中WCET的值是通過測試的方法,采用大量仿真選取的最大值,由于系統(tǒng)的軟硬件設(shè)計(jì)比較確定,所以時(shí)間波動很小,時(shí)間抖動則是采用第3.4節(jié)所述方法求得。對于最大阻塞時(shí)間Bi的計(jì)算,由于任務(wù)在不同的時(shí)間釋放并在不同的時(shí)間區(qū)間內(nèi)運(yùn)行,所以任務(wù)間無阻塞發(fā)生。對中斷而言,阻塞主要由關(guān)中斷引起的,通過大量仿真得到,任務(wù)程序最長關(guān)中斷時(shí)間為bmax=47.9μs,中斷程序的最長關(guān)中斷時(shí)間bmax=5.5μs,故Bi可以通過4.2節(jié)所述方法求得。

4.2 仿真結(jié)果分析

綜上所述,計(jì)算得到的任務(wù)和中斷最差響應(yīng)時(shí)間與仿真得到的最差響應(yīng)時(shí)間對比見表3。對于中斷只給出了具有代表性的EXINT 0和 UART1的值,由于TIMER1和EXINT0不會同時(shí)發(fā)生,故表中UART(1)指的是在EXINT0搶占下的最差響應(yīng)時(shí)間,UART(2)則是在TIMER1搶占下的最差響應(yīng)時(shí)間。可以看出,所有任務(wù)的最差響應(yīng)時(shí)間的分析值均大于仿真值,說明分析結(jié)果是安全的;同時(shí)最差響應(yīng)時(shí)間的最大過估比率僅為3.74%,說明本文所述的多級中斷下任務(wù)最差響應(yīng)時(shí)間的計(jì)算方法是精確的。中斷的最差響應(yīng)時(shí)間最大過估比率達(dá)到31.09%,這是由于中斷發(fā)生的隨機(jī)性,很難使用測試的方法得到最差情況。當(dāng)然一般情況下,中斷并不會如此頻繁發(fā)生,所以在實(shí)際的工程應(yīng)用中對于中斷的時(shí)間分析還需要設(shè)定一些約束條件,以便得到更加實(shí)用的結(jié)果,這將留作以后的工作。

表3 多級中斷下任務(wù)和中斷最差響應(yīng)時(shí)間結(jié)果Table 3 Results of WCRT of tasks and interrupts under multilevel interrupts

5 結(jié)束語

本文針對包含多級中斷的航天嵌入式系統(tǒng),通過定義中斷與任務(wù)的混合時(shí)間分析模型,將任務(wù)間搶占的響應(yīng)時(shí)間分析方法推廣到了中斷與任務(wù)混合搶占的時(shí)間分析中,更加符合航天嵌入式系統(tǒng)的應(yīng)用環(huán)境。文中給出的仿真實(shí)例說明了該方法的有效性,但是在最差響應(yīng)時(shí)間計(jì)算時(shí),考慮的是最差情況而忽略了一些實(shí)際工程的約束條件,根據(jù)真實(shí)工程應(yīng)用的約束進(jìn)一步提高分析的精度將作為后續(xù)工作。

References)

[1] 楊孟飛,顧斌,郭向英,等.航天嵌入式軟件可信保障

技術(shù)及應(yīng)用研究[J].中國科學(xué):技術(shù)科學(xué),2015,45(2):198-203. YANG M F,GU B,GUO X Y,et al.Aerospace embedded software dependability guarantee technology and application[J].Scientia Scinica Technologica,2015,45(2): 198-203(in Chinese).

[2] JOSEPH M,PANDYA P.Finding response times in a real-time systems[J].The Computer Journal,1986,29 (5):390-395.

[3] DAVIS R I,BURNS A.Response time upper bounds for fixed priority real-time systems[C].Real-Time Systems Symposium,Barcelona,Spain,November 30-December 3,2008.

[4] M?KI-TURJA J,NOLIN M.Efficient implementation of tight response-times for tasks with offsets[J]. Real-time System,2008,40:77-116.

[5] BRYLOW D,PALSBERG J.Deadline analysis of interrupt-driven software[J].IEEE Transactions on Soft-ware Engineering,2004,30(10):634-655.

[6] JONATHAN K,DORSA S,SANJIT A S.Timing analysis of interrupt-driven programs under context bounds[C].Formal Methods in Computer-Aided Design, Austin,Texas,USA,October 30-November 2,2011.

[7] 王磊,袁利,戴居峰.衛(wèi)星控制系統(tǒng)時(shí)序建模分析方法研究[J].空間控制技術(shù)與應(yīng)用,2014,40(3):31-35. WANG L,YUAN L,DAI J F.Timing modeling and analysis method for satellite control system[J]. Aerospace Control and Application,2014,40(3):31-35(in Chinese).

[8] JEFFAY K,STONE D L.Accounting for interrupt handling costs in dynamic priority task systems[C]. Real-Time Symposium,NC,USA,December,1993.

[9] BRANDENBURG B B,LEONTYEV H,ANDERSON J M.An overview of interrupt accounting techniques for multiprocessor real-time systems[J].Journal of Systems Architecture,2011,57:638-654.

[10] RANDAL E BRYANT,DAVID R O′HALLARON. Computer systems:a programmer′s perspective[M].2nd ed.New Jersey:Pearson Prentice Hall,2011.

[11] SEBASTIAN A,ROBERT I D,CLAIRE M. Improved cache related preemption delay aware response time analysis for fixed priority preemptive systems[J].Real-time System,2012,48: 499-526.

[12] WILHELM R,ENGBLOM J,ERMEDAHL A,et al.The worst-case execution-time problem-overview of methods and survey of tools[J].ACM Transactions on Embedded Computing Systems,2008,7(3):1-53.

[13] SHA L,RAJKUMAR R,LEHOCZHY JP.Priority inheritance protocols:an approach to real-time synchronization[J].IEEE Transactions on Computers, 1990,39(9):1175-1185.

[14] 譚彥亮,楊樺,喬磊.基于Event-B的Space OS2操

作系統(tǒng)任務(wù)管理需求形式化建模與驗(yàn)證[J].空間控制技術(shù)與應(yīng)用,2014,40(4):57-62. TAN Y L,YANG H,QIAO L.Formal modeling and verification of task-management requirement for Space OS2 based on Event-B[J].Aerospace Control and Application,2014,40(4):57-62(in Chinese).

(編輯:車曉玲)

Worst case response time analysis of multi-level interrupt systems

YU Guangliang1,*,YANG Mengfei2,XU Jian1,JIANG Hong1
1.BeijingInstituteofControlEngineering,Beijing100190,China2.ChinaAcademyofSpaceTechnology,Beijing100094,China

A computation model integrated with interrupts and tasks was presented for the analysis of worst case response time(WCRT)for an aerospace embedded system with multilevel interrupts.Both interrupts and tasks was used for a unified priority definition in this model,so the timing analysis of nested interrupts can be combined with task response time analysis techniques.The WCRT of both interrupts and tasks was derived in the integrated model.Furthermore,detailed descriptions of key parameters were proposed and the differences between interrupts and tasks were also discussed.The open source LEON3processor platform and Modelsim software were introduced to simulate and verify the method.The results show that the overestimate of task WCRT is less than 5%which demonstrates the effectiveness of the method and the value for engineering applications.

real time system;embedded software;multi-level interrupt;fixed priority scheduling;schedulability analysis;worst case response time;spacecraft

A

10.16708/j.cnki.1000-758X.2016.0003

2015-05-08;

:2015-07-27;錄用日期:2015-09-28;< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間:2016-04-19 14:46:13

http:∥www.cnki.net/kcms/detail/11.1859.V.20160419.1446.002.html

*

:于廣良(1986-),男,博士研究生,yal_222@126.com,主要研究方向?yàn)楹教烨度胧较到y(tǒng)可信軟件

于廣良,楊孟飛,徐建,等.面向多級中斷系統(tǒng)的任務(wù)最差響應(yīng)時(shí)間分析[J].中國空間科學(xué)技術(shù),2016,36(2): 28-36.YUGL,YANGMF,XUJ,etal.Worstcaseresponsetimeanalysisofmulti-levelinterruptsystems[J].Chinese SpaceScienceandTechnology,2016,36(2):28-36(inChinese).

:V411.8

http:∥zgkj.cast.cn