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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2552313