本文關(guān)鍵詞：帶時間約束實(shí)時任務(wù)圖模型上可調(diào)度性分析算法研究

  更多相關(guān)文章： 時間約束 實(shí)時任務(wù)圖 可調(diào)度性分析 需求上界函數(shù) 動態(tài)規(guī)劃

【摘要】：帶時間約束的實(shí)時任務(wù)圖(TCDRT)模型具有接近于時間自動機(jī)的豐富表達(dá)性,但是其關(guān)聯(lián)的可調(diào)度性分析(SA)問題卻是強(qiáng)NP困難的.目前的研究僅關(guān)注一類約束個數(shù)為常數(shù)K的易解模型:K-TCDRT,且局限于SA問題的圖轉(zhuǎn)換求解方法.這種間接求法使得問題的計算復(fù)雜度隨約束寬度呈指數(shù)倍增長.該文研究TCDRT模型上可調(diào)度性分析問題的直接求解方法,為兩個核心子問題給出新的理論結(jié)果:第一,針對需求上界函數(shù)(DBF)的計算問題,提出了考慮時間約束的路徑需求結(jié)構(gòu),并據(jù)此設(shè)計了新的動態(tài)規(guī)劃算法,其時間復(fù)雜度與約束寬度無關(guān);第二,對于可調(diào)度分析上界T的限定問題,從理論上證明了該問題是偽多項式時間可解的,且計算復(fù)雜度不再與K指數(shù)相關(guān),這使得文中算法性能較已有結(jié)果有指數(shù)級提升.更進(jìn)一步地,該文方法還蘊(yùn)含著一類新的TCDRT易解模型.該類模型突破了約束個數(shù)必須為常數(shù)的局限,其分析難度也較K-TCDRT有指數(shù)倍地下降.
【作者單位】： 東北大學(xué)信息科學(xué)與工程學(xué)院;
【關(guān)鍵詞】： 時間約束 實(shí)時任務(wù)圖 可調(diào)度性分析 需求上界函數(shù) 動態(tài)規(guī)劃
【基金】：國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項目預(yù)研項目(2014CB360509) 國家自然科學(xué)基金(61300022,61300194,61472072) 中央高�；究蒲袠I(yè)務(wù)費(fèi)(N130423007,N130504008) 河北省自然科學(xué)基金(F2013501048)資助~~
【分類號】：TP301.6
【正文快照】： 然科學(xué)基金(61300022,61300194,61472072)、中央高�；究蒲袠I(yè)務(wù)費(fèi)(N130423007,N130504008)、河北省自然科學(xué)基金(F2013501048)1引言在實(shí)時系統(tǒng)驗(yàn)證領(lǐng)域,形式化模型更關(guān)注系統(tǒng)的時間行為和不確定性等非功能特征,是系統(tǒng)可調(diào)度性分析的理論基礎(chǔ).為便于理論分析,形式化模型通常

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 徐建華;李允;;基于單調(diào)速率的可調(diào)度性判定改進(jìn)算法[J];計算機(jī)工程;2011年22期

2 牛云;戴冠中;梁亞琳;;基于時間需求迭代和排隊模型的開放式實(shí)時系統(tǒng)可調(diào)度性分析算法研究[J];計算機(jī)科學(xué);2009年01期

3 于曉;王家禮;;偏序的周期任務(wù)間可調(diào)度性判定算法[J];電子測量與儀器學(xué)報;2009年04期

4 張永悅;孫瑜;李允;徐建華;;復(fù)雜實(shí)時系統(tǒng)可調(diào)度性判定工具的研究與實(shí)現(xiàn)[J];計算機(jī)工程;2013年01期

5 郭銳鋒;劉嫻;丁萬夫;李杰;王鴻亮;;回卷恢復(fù)模型下容錯實(shí)時系統(tǒng)的可調(diào)度性分析[J];小型微型計算機(jī)系統(tǒng);2013年06期

6 毛羽剛,張擁軍,金士堯,胡華平;一種改進(jìn)的分布強(qiáng)實(shí)時系統(tǒng)可調(diào)度性分析算法[J];軟件學(xué)報;2001年02期

7 王高才;李偉;;基于隨機(jī)模型的軟實(shí)實(shí)時時系統(tǒng)的任務(wù)期望可調(diào)調(diào)度度性[J];控制理論與應(yīng)用;2012年01期

8 謝拴勤;潘姿君;;實(shí)時多任務(wù)系統(tǒng)可調(diào)度性工程評估方法研究[J];計算機(jī)測量與控制;2007年12期

9 李俊,陽富民,盧炎生;一種可行的容錯實(shí)時系統(tǒng)可調(diào)度性分析[J];軟件學(xué)報;2005年08期

10 陳勁林,楊士元,胡東成;基于確定周期性任務(wù)的進(jìn)程管理及可調(diào)度性分析[J];計算機(jī)研究與發(fā)展;2000年03期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 周美嬌;應(yīng)啟戛;張鳳登;蕭偉;馮治寶;;帶有空閑幀的FIP總線可調(diào)度性分析[A];第六屆全國信息獲取與處理學(xué)術(shù)會議論文集（3）[C];2008年

2 王宇;侯朝楨;;數(shù)字化操控系統(tǒng)中CAN總線的信息可調(diào)度性分析[A];《制造業(yè)自動化與網(wǎng)絡(luò)化制造》學(xué)術(shù)交流會論文集[C];2004年

3 王宇;侯朝楨;;數(shù)字化操控系統(tǒng)中CAN總線的信息可調(diào)度性分析[A];先進(jìn)制造技術(shù)論壇暨第三屆制造業(yè)自動化與信息化技術(shù)交流會論文集[C];2004年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前6條

1 王磊;容錯實(shí)時系統(tǒng)可調(diào)度性分析研究[D];浙江大學(xué);2005年

2 李俊;容錯硬實(shí)時系統(tǒng)的可調(diào)度性分析[D];華中科技大學(xué);2007年

3 竇強(qiáng);分布式強(qiáng)實(shí)時系統(tǒng)中可調(diào)度性分析算法的研究[D];國防科學(xué)技術(shù)大學(xué);2001年

4 姚興華;資源供需進(jìn)程演算的證明系統(tǒng)研究[D];華東師范大學(xué);2014年

5 于曉;基于嵌入式Linux的儀器操作系統(tǒng)的研究[D];西安電子科技大學(xué);2009年

6 錢之琳;基于服務(wù)的信息物理融合系統(tǒng)可信建模與分析[D];華東理工大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前3條

1 王好;基于eM-Plant原油處理過程的可調(diào)度性分析[D];廣東工業(yè)大學(xué);2013年

2 余飛;基于Uppaal的多處理器實(shí)時系統(tǒng)的可調(diào)度性分析[D];上海交通大學(xué);2011年

3 張永悅;基于仿真的實(shí)時系統(tǒng)可調(diào)度性分析工具的研究與實(shí)現(xiàn)[D];云南師范大學(xué);2014年

，

本文編號：668030