【摘要】：傳統(tǒng)實時系統(tǒng)性能分析以最差情況下執(zhí)行時間(worst-case execution time,WCET)作為主要輸入,導(dǎo)致分析過于保守.針對實時系統(tǒng)設(shè)計時預(yù)留冗余過大的問題,建立了以到達(dá)事件類型、數(shù)量和分布為決策變量,包括工作量曲線(workload curves)、逆工作量曲線(inverse workload curves)、工作量比率曲線(workload ratio curves)在內(nèi)的實時系統(tǒng)可變工作量模型,給出了相關(guān)計算方法.基于可變工作量模型分析了其在混合調(diào)度中的應(yīng)用,結(jié)果表明:采用可變工作量模型和算法可顯著減少任務(wù)所需的執(zhí)行工作量,降低了實時系統(tǒng)的資源需求.
【圖文】：

畝ㄒ逋評恚釓獐?γl－1(e)的定義，可得γl(k1)=γl(γl－1(e))=γl(mink1∈Z≥0{k1:γl(k1)≥e})≥e;根據(jù)γu－1(e)的定義，可得γu(k2)=γu(γu－1(e))=γl(maxk2∈Z≥0{k2:γu(k2)≤e})≤e;所以γl(k1)≥γu(k2)．至此可見由逆工作量曲線定義得出的結(jié)論與反證法最初假設(shè)推出的結(jié)論矛盾，因此性質(zhì)7得證．2工作量曲線與逆工作量曲線的算法2.1算法1———工作量曲線計算方法算法1的流程圖如圖1所示．圖1工作量曲線算法Fig.1Workloadcurvesalgorithm算法1基于定義1、定義3、定理1、定理2得出．算法1的時間復(fù)雜度為O(k×(n－k+1))，若k郙n，則算法時間復(fù)雜度退化成O(n)．2.2算法2———逆工作量曲線計算方法算法2的流程圖如圖2所示．圖2逆工作量曲線算法Fig.2Inverseworkloadcurvesalgorithm算法的時間復(fù)雜度為O(n×k×(n－k+1))，若k郙n，則退化成O(n2)．算法2是在算法1的基礎(chǔ)上基于定義5及其性質(zhì)得出．算法1和算法2中事件到達(dá)模型一般有兩種確定方法，一種是根據(jù)實際系統(tǒng)的經(jīng)驗數(shù)據(jù)，另一種是根據(jù)系統(tǒng)嚴(yán)格的形式化說明［7－8］．2.3仿真計算針對上述建模及計算方法，給出仿真計算示例．圖3給出一個長度為10的三種類型事件到達(dá)序列，以及各類型事件的WCET和BCET．圖3具有不同類型的事件序列Fig.3Eventsequencewithdifferenttypesofevents針對圖3所示的事件序列，采用算法1和算法2分別計算相應(yīng)的工作量曲線和逆工作量曲線，如圖4所示．可以看出:由于γl(10)=14，，所以當(dāng)工作量e≥15時，不存在最小工作量曲線的逆，算法返回值為－1;由于γu(10)=37，所以當(dāng)工作量e≥37時，?

l(maxk2∈Z≥0{k2:γu(k2)≤e})≤e;所以γl(k1)≥γu(k2)．至此可見由逆工作量曲線定義得出的結(jié)論與反證法最初假設(shè)推出的結(jié)論矛盾，因此性質(zhì)7得證．2工作量曲線與逆工作量曲線的算法2.1算法1———工作量曲線計算方法算法1的流程圖如圖1所示．圖1工作量曲線算法Fig.1Workloadcurvesalgorithm算法1基于定義1、定義3、定理1、定理2得出．算法1的時間復(fù)雜度為O(k×(n－k+1))，若k郙n，則算法時間復(fù)雜度退化成O(n)．2.2算法2———逆工作量曲線計算方法算法2的流程圖如圖2所示．圖2逆工作量曲線算法Fig.2Inverseworkloadcurvesalgorithm算法的時間復(fù)雜度為O(n×k×(n－k+1))，若k郙n，則退化成O(n2)．算法2是在算法1的基礎(chǔ)上基于定義5及其性質(zhì)得出．算法1和算法2中事件到達(dá)模型一般有兩種確定方法，一種是根據(jù)實際系統(tǒng)的經(jīng)驗數(shù)據(jù)，另一種是根據(jù)系統(tǒng)嚴(yán)格的形式化說明［7－8］．2.3仿真計算針對上述建模及計算方法，給出仿真計算示例．圖3給出一個長度為10的三種類型事件到達(dá)序列，以及各類型事件的WCET和BCET．圖3具有不同類型的事件序列Fig.3Eventsequencewithdifferenttypesofevents針對圖3所示的事件序列，采用算法1和算法2分別計算相應(yīng)的工作量曲線和逆工作量曲線，如圖4所示．可以看出:由于γl(10)=14，所以當(dāng)工作量e≥15時，不存在最小工作量曲線的逆，算法返回值為－1;由于γu(10)=37，所以當(dāng)工作量e≥37時，最大工作量曲線的逆等于10．192東北大學(xué)學(xué)報(自然科學(xué)版)第38卷
【作者單位】： 東北大學(xué)信息科學(xué)與工程學(xué)院;
【基金】：國家自然科學(xué)基金資助項目(61472072) 國家重點基礎(chǔ)研究發(fā)展計劃項目(2014CB360509)
【分類號】：TP301.6;TP332

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李勝利,秦嘯,韓宗芬,龐麗萍;分布式實時系統(tǒng)結(jié)構(gòu)的研究[J];計算機(jī)工程與科學(xué);2000年02期

2 于百煉;實時系統(tǒng)的技術(shù)要點(三)[J];電氣時代;2004年05期

3 胡成軍,王戟,陳火旺;實時系統(tǒng)的形式化驗證[J];計算機(jī)工程與科學(xué);2000年02期

4 楊英;可安裝在內(nèi)部的實時系統(tǒng)[J];管理科學(xué)文摘;1995年10期

5 屠梅紅,虞慧群;分布式實時系統(tǒng)設(shè)計的一種擴(kuò)展方法[J];華東理工大學(xué)學(xué)報;2002年03期

6 李勇,李宣東,鄭國梁;檢驗實時系統(tǒng)的有序時段性質(zhì)[J];南京大學(xué)學(xué)報(自然科學(xué)版);2003年05期

7 夏德深;鄭阿奇;;應(yīng)用高級BASIC陷阱技術(shù)開發(fā)實時系統(tǒng)[J];微型機(jī)與應(yīng)用;1992年12期

8 毛羽剛,張擁軍,金士堯;強(qiáng)實時系統(tǒng)的調(diào)度[J];計算機(jī)工程與科學(xué);2000年02期

9 郭江鴻;張敏;;一種基于整體優(yōu)先級空間的實時系統(tǒng)中斷管理模型[J];嘉應(yīng)學(xué)院學(xué)報;2007年06期

10 龐麗萍,張前鋒;分布式實時系統(tǒng)的組資格成員算法[J];華中理工大學(xué)學(xué)報;2000年01期

相關(guān)會議論文 前1條

1 楊仕平;熊光澤;桑楠;;基于雙超時檢測機(jī)制的三維容錯實時系統(tǒng)[A];第十屆全國容錯計算學(xué)術(shù)會議論文集[C];2003年

相關(guān)博士學(xué)位論文 前3條

1 鄒勇;開放式實時系統(tǒng)的調(diào)度方法研究[D];中國科學(xué)院研究生院（軟件研究所）;2003年

2 陳宇;高可靠容錯實時系統(tǒng)的支撐技術(shù)研究[D];電子科技大學(xué);2001年

3 周正勇;實時系統(tǒng)的容錯調(diào)度技術(shù)研究[D];華中科技大學(xué);2014年

相關(guān)碩士學(xué)位論文 前7條

1 武奎俊;多核實時系統(tǒng)資源預(yù)留映射與仿真研究[D];杭州電子科技大學(xué);2016年

2 周勁;基于消息的分布式實時系統(tǒng)的時間記賬機(jī)制[D];重慶大學(xué);2006年

3 邢靜宇;能量敏感實時系統(tǒng)中的能量管理研究與應(yīng)用[D];廣東工業(yè)大學(xué);2006年

4 王曉寅;基于實時系統(tǒng)的STM32網(wǎng)絡(luò)應(yīng)用[D];華東師范大學(xué);2011年

5 符利華;基于CPS的實時系統(tǒng)的面向方面的容錯調(diào)度模型[D];廣東工業(yè)大學(xué);2011年

6 劉軍萬;分布式實時系統(tǒng)中動態(tài)負(fù)載共享算法的研究[D];中南大學(xué);2002年

7 胡鵬;基于定點DSPs的實時系統(tǒng)設(shè)計與實現(xiàn)[D];武漢理工大學(xué);2003年

本文編號：2552313