【摘要】：改善單調(diào)速率(rate monotonic,簡(jiǎn)稱RM)可調(diào)度性判定算法的效率,是過(guò)去40年計(jì)算機(jī)實(shí)時(shí)系統(tǒng)設(shè)計(jì)的重要問(wèn)題.最近,研究人員把可調(diào)度性判定問(wèn)題擴(kuò)展到了更一般的優(yōu)化設(shè)計(jì)問(wèn)題,即,如何調(diào)節(jié)在區(qū)間可選擇情況下的任務(wù)運(yùn)行時(shí)間,使得:(1)系統(tǒng)RM可調(diào)度;(2)系統(tǒng)的某個(gè)性能(如CPU利用率)達(dá)到最優(yōu).在已有的求解實(shí)時(shí)系統(tǒng)RM優(yōu)化設(shè)計(jì)問(wèn)題的方法中,都是先把原問(wèn)題建模成廣義約束優(yōu)化問(wèn)題,然后再對(duì)廣義約束優(yōu)化問(wèn)題進(jìn)行求解.但現(xiàn)有方法的求解速度較慢,任務(wù)數(shù)較多時(shí)不再適用.提出一種求解優(yōu)化問(wèn)題的方法——基于樹(shù)狀的線性規(guī)劃搜索(linear programming search,簡(jiǎn)稱LPS)方法.該方法先將實(shí)時(shí)系統(tǒng)RM優(yōu)化設(shè)計(jì)問(wèn)題建模成廣義約束優(yōu)化問(wèn)題,再將其分拆成若干線性規(guī)劃子問(wèn)題,然后構(gòu)造線性規(guī)劃搜索樹(shù),利用剪枝搜索算法求解部分線性規(guī)劃子問(wèn)題,最后得到優(yōu)化解.實(shí)驗(yàn)結(jié)果表明:LPS方法相比于已有的方法能夠節(jié)省20%~70%的求解時(shí)間,任務(wù)數(shù)越多,節(jié)省時(shí)間越多.該研究成果可以與計(jì)算機(jī)可滿足性模定理(satisfiability modulo theories,簡(jiǎn)稱SMT)領(lǐng)域的多個(gè)研究熱點(diǎn)問(wèn)題聯(lián)系起來(lái),并可望改善SMT問(wèn)題的求解效率.
[Abstract]:Improving the efficiency of monotone rate (rate monotonic, (RM) schedulability decision algorithm is an important problem in the design of computer real-time system in the past 40 years. Recently, researchers extended the schedulability decision problem to the more general optimization design problem, that is, how to adjust the task running time under the condition of interval selection, which makes: (1) system RM schedulable; (2) the performance of the system (such as CPU utilization) is optimized. In the existing methods for solving the RM optimization design problem of real-time systems, the original problem is modeled as a generalized constrained optimization problem, and then the generalized constrained optimization problem is solved. However, the existing methods are slow to solve the problem and are no longer applicable when the number of tasks is more. In this paper, a method for solving optimization problems is presented, which is based on a tree-like linear programming search method called (linear programming search, (LPS). In this method, the RM optimization design problem of real-time system is modeled as a generalized constrained optimization problem, then it is divided into several linear programming subproblems, and then the linear programming search tree is constructed, and the pruning search algorithm is used to solve the partial linear programming subproblem. Finally, the optimal solution is obtained. The experimental results show that the LPS method can save 20% 70% of the solving time compared with the existing methods, the more tasks, the more time is saved. The research results can be related to many hot problems in the field of computer satisfiability modulus theorem (satisfiability modulo theories, (SMT), and it is expected to improve the efficiency of solving SMT problem.
【作者單位】： 中國(guó)科學(xué)院軟件研究所基礎(chǔ)軟件國(guó)家工程研究中心;中國(guó)科學(xué)院大學(xué);計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院軟件研究所);中國(guó)科學(xué)院軟件研究所互聯(lián)網(wǎng)軟件技術(shù)實(shí)驗(yàn)室;
【基金】：國(guó)家自然科學(xué)基金(61170072) 國(guó)家青年科學(xué)基金(61303057) 中國(guó)科學(xué)院、國(guó)家外國(guó)專家局創(chuàng)新團(tuán)隊(duì)國(guó)際合作伙伴計(jì)劃~~
【分類號(hào)】：TP301.6;TP302

【參考文獻(xiàn)】

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

1 王永吉,陳秋萍;單調(diào)速率及其擴(kuò)展算法的可調(diào)度性判定[J];軟件學(xué)報(bào);2004年06期

【共引文獻(xiàn)】

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

1 王娟;吳秀文;張鐘澍;;實(shí)時(shí)操作系統(tǒng)集成調(diào)度的兩級(jí)方案設(shè)計(jì)[J];成都信息工程學(xué)院學(xué)報(bào);2007年01期

2 謝永悠;楊斌;劉海青;;基于面向?qū)ο蟮那度胧皆O(shè)備檢測(cè)方法的設(shè)計(jì)與實(shí)現(xiàn)[J];成都信息工程學(xué)院學(xué)報(bào);2010年04期

3 徐德;;嵌入式Linux操作系統(tǒng)調(diào)度算法改進(jìn)[J];電腦知識(shí)與技術(shù);2011年07期

4 王濤;劉大昕;;基于頂點(diǎn)覆蓋問(wèn)題解的與/或優(yōu)先約束任務(wù)調(diào)度算法[J];哈爾濱工程大學(xué)學(xué)報(bào);2007年05期

5 洪雪玉;張凌;袁華;;Linux下的實(shí)時(shí)調(diào)度算法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

6 邢建生;劉軍祥;王永吉;;RM及其擴(kuò)展可調(diào)度性判定算法性能分析[J];計(jì)算機(jī)研究與發(fā)展;2005年11期

7 陳尹立;彭詩(shī)力;廖春藍(lán);;基于阻塞調(diào)度的優(yōu)先級(jí)反轉(zhuǎn)解決策略[J];計(jì)算機(jī)工程與應(yīng)用;2007年22期

8 楊麟祥;岳繼光;張曉云;;POSIX零星事件調(diào)度策略的研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2009年11期

9 趙維Oz;李迪;萬(wàn)加富;黃培燦;;網(wǎng)絡(luò)化運(yùn)動(dòng)控制系統(tǒng)的經(jīng)典調(diào)度算法應(yīng)用研究[J];計(jì)算機(jī)工程與應(yīng)用;2010年29期

10 肖和龍;唐文勝;;基于RTAI改進(jìn)的Linux實(shí)時(shí)調(diào)度算法[J];計(jì)算機(jī)工程與應(yīng)用;2012年01期

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

1 葉永凱;董威;舒紹嫻;徐小平;;freeRTOS內(nèi)核的RM調(diào)度器的設(shè)計(jì)與實(shí)現(xiàn)[A];第十六屆計(jì)算機(jī)工程與工藝年會(huì)暨第二屆微處理器技術(shù)論壇論文集[C];2012年

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

1 殷進(jìn)勇;可重構(gòu)系統(tǒng)中實(shí)時(shí)任務(wù)調(diào)度算法研究[D];哈爾濱工程大學(xué);2010年

2 朱萍;硬實(shí)時(shí)容錯(cuò)調(diào)度算法研究[D];華中科技大學(xué);2011年

3 祝義;嵌入式軟件需求規(guī)約到軟件體系結(jié)構(gòu)模型的轉(zhuǎn)換研究[D];南京航空航天大學(xué);2011年

4 趙明;具備約束的實(shí)時(shí)調(diào)度關(guān)鍵問(wèn)題的研究[D];東北大學(xué);2010年

5 陳積明;弱硬實(shí)時(shí)系統(tǒng)及其調(diào)度算法[D];浙江大學(xué);2005年

6 高軍禮;基于模型驅(qū)動(dòng)開(kāi)發(fā)方法的開(kāi)放式結(jié)構(gòu)計(jì)算機(jī)數(shù)控系統(tǒng)的研究[D];華南理工大學(xué);2005年

7 王濤;實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度若干關(guān)鍵技術(shù)的研究[D];哈爾濱工程大學(xué);2006年

8 姚鑫驊;數(shù)控實(shí)時(shí)系統(tǒng)調(diào)度理論及應(yīng)用研究[D];浙江大學(xué);2006年

9 李建國(guó);實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度模型與算法研究[D];中南大學(xué);2006年

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

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

1 趙萍;模型驅(qū)動(dòng)系統(tǒng)中模型轉(zhuǎn)換技術(shù)的研究[D];哈爾濱工程大學(xué);2010年

2 石林勇;多處理器全局FP調(diào)度算法的研究[D];江蘇大學(xué);2010年

3 王巖;基于ARM的動(dòng)態(tài)壓力記錄分析儀的研究與開(kāi)發(fā)[D];長(zhǎng)春工業(yè)大學(xué);2010年

4 李婷;實(shí)時(shí)系統(tǒng)中混合調(diào)度策略的研究[D];昆明理工大學(xué);2008年

5 李玉奇;基于Linux的實(shí)時(shí)嵌入式操作系統(tǒng)內(nèi)核的改進(jìn)研究[D];沈陽(yáng)理工大學(xué);2011年

6 徐建華;基于AADL的ARINC653配置工具的研究與實(shí)現(xiàn)[D];西南交通大學(xué);2011年

7 翟玉健;支持IPv4/IPv6混合網(wǎng)絡(luò)的傳輸軟件研究和實(shí)現(xiàn)[D];南京航空航天大學(xué);2010年

8 趙明陽(yáng);基于嵌入式實(shí)時(shí)操作系統(tǒng)的軟總線技術(shù)研究[D];南京航空航天大學(xué);2011年

9 王凱;基于多核的嵌入式操作系統(tǒng)的研究和設(shè)計(jì)[D];南京航空航天大學(xué);2010年

10 陳磊;嵌入式實(shí)時(shí)操作系統(tǒng)ARTs-OS的EDF調(diào)度算法改進(jìn)[D];華中科技大學(xué);2011年

【二級(jí)參考文獻(xiàn)】

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

1 鄒勇,李明樹(shù),王青;開(kāi)放式實(shí)時(shí)系統(tǒng)的調(diào)度理論與方法分析[J];軟件學(xué)報(bào);2003年01期

2 金宏,王宏安,王強(qiáng),戴國(guó)忠;一種任務(wù)優(yōu)先級(jí)的綜合設(shè)計(jì)方法[J];軟件學(xué)報(bào);2003年03期

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

8 屠梅紅,虞慧群;分布式實(shí)時(shí)系統(tǒng)的一種轉(zhuǎn)化設(shè)計(jì)方法[J];華東理工大學(xué)學(xué)報(bào);2001年05期

9 胡華平,金士堯,王維;分布式實(shí)時(shí)系統(tǒng)的高可靠性研究與實(shí)現(xiàn)[J];計(jì)算機(jī)研究與發(fā)展;1998年09期

10 李天鐸;實(shí)時(shí)方式標(biāo)準(zhǔn)化[J];管理科學(xué)文摘;1998年03期

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

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

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

1 鄒勇;開(kāi)放式實(shí)時(shí)系統(tǒng)的調(diào)度方法研究[D];中國(guó)科學(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é)位論文 前6條

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

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

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

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

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

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

，

本文編號(hào)：2390427