【摘要】：以航空、汽車領(lǐng)域?yàn)榇淼默F(xiàn)代嵌入式實(shí)時(shí)系統(tǒng),高安全標(biāo)準(zhǔn)的軟件功能與其它非安全關(guān)鍵的軟件功能共享一個(gè)嵌入式平臺(tái),以解決軟件功能多樣化、復(fù)雜化的需求與硬件平臺(tái)受限SWa P(size weight and price)需求的沖突。此類系統(tǒng)的實(shí)時(shí)調(diào)度需同時(shí)滿足兩個(gè)目標(biāo):一是在相對(duì)保守的時(shí)間屬性設(shè)定下,滿足認(rèn)證標(biāo)準(zhǔn)對(duì)涉及安全關(guān)鍵功能的驗(yàn)證要求;同時(shí)在較樂觀的時(shí)間屬性設(shè)定下,滿足高效利用計(jì)算資源的設(shè)計(jì)要求。這類混合關(guān)鍵級(jí)系統(tǒng)的調(diào)度問題,無法使用傳統(tǒng)的實(shí)時(shí)調(diào)度算法解決。混合關(guān)鍵級(jí)調(diào)度問題已成為嵌入式領(lǐng)域極富挑戰(zhàn)的課題之一。本文基于混合關(guān)鍵級(jí)調(diào)度對(duì)安全關(guān)鍵與非安全關(guān)鍵任務(wù)的不同調(diào)度需求,以及高效利用資源的目標(biāo),分別研究了針對(duì)高、低關(guān)鍵級(jí)任務(wù)的不同調(diào)度策略。主要研究工作與成果如下:(1)基于事件觸發(fā)系統(tǒng)關(guān)鍵級(jí)提升的實(shí)際情況,分析了高關(guān)鍵級(jí)任務(wù)的可調(diào)度性,得到了關(guān)鍵級(jí)提升期,高關(guān)鍵級(jí)任務(wù)可調(diào)度的充分條件。指出系統(tǒng)關(guān)鍵級(jí)提升的觸發(fā)源于系統(tǒng)外部事件,基于響應(yīng)時(shí)間分析技術(shù),研究了關(guān)鍵級(jí)提升時(shí)刻對(duì)滿足高關(guān)鍵級(jí)任務(wù)截止時(shí)限的影響;并據(jù)此,在關(guān)鍵級(jí)提升期,提出了一個(gè)有條件的優(yōu)先級(jí)交換算法,可確保更多高關(guān)鍵級(jí)任務(wù)得到正確調(diào)度。仿真實(shí)驗(yàn)顯示了可調(diào)度條件以及優(yōu)先級(jí)交換算法的有效性。(2)提出了一種適合以截止時(shí)限為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)任務(wù)調(diào)度算法。定義了截止時(shí)限依賴于關(guān)鍵級(jí)的混合關(guān)鍵級(jí)任務(wù)模型,分析了關(guān)鍵級(jí)提升期低關(guān)鍵級(jí)任務(wù)對(duì)高關(guān)鍵級(jí)任務(wù)調(diào)度可能產(chǎn)生的干擾,以預(yù)先提升關(guān)鍵級(jí)的方式,犧牲有限的低關(guān)鍵任務(wù),可始終滿足高關(guān)鍵級(jí)任務(wù)隨系統(tǒng)關(guān)鍵級(jí)動(dòng)態(tài)變化的截止時(shí)限。仿真實(shí)驗(yàn)驗(yàn)證了預(yù)關(guān)鍵級(jí)提升算法適合以截止時(shí)限為關(guān)鍵參數(shù)的任務(wù)調(diào)度,且不受高關(guān)鍵級(jí)任務(wù)比率和截止時(shí)限變化程度的影響。(3)提出了一種適合同構(gòu)多處理器平臺(tái)上調(diào)度混合關(guān)鍵級(jí)任務(wù)的半局部調(diào)度算法。兼顧高關(guān)鍵任務(wù)利用率和低關(guān)鍵級(jí)任務(wù)可調(diào)度性,將全部高關(guān)鍵級(jí)任務(wù)和大部分低關(guān)鍵級(jí)任務(wù)固定在既定處理器上執(zhí)行,僅有數(shù)量不超過處理器數(shù)目的低關(guān)鍵級(jí)任務(wù)成為遷移任務(wù),能且僅能在相鄰的兩個(gè)處理器上發(fā)生遷移,并同步執(zhí)行。以有限的遷移換取對(duì)處理器資源的高效利用,并總能滿足高關(guān)鍵級(jí)任務(wù)的截止時(shí)限。仿真實(shí)驗(yàn)結(jié)果表明該半局部調(diào)度算法,相較于局部調(diào)度混合關(guān)鍵級(jí)任務(wù)的方法,將可調(diào)度任務(wù)比率提升了近10%。(4)提出了一種積極處理低關(guān)鍵任務(wù)的策略。對(duì)于符合標(biāo)準(zhǔn)認(rèn)證的混合關(guān)鍵級(jí)系統(tǒng),在關(guān)鍵級(jí)提升之后,回收多處理平臺(tái)上執(zhí)行中的空閑時(shí)段,以全局分配的方式匹配到被拋棄的低關(guān)鍵級(jí)任務(wù),既不干擾局部調(diào)度的高關(guān)鍵級(jí)任務(wù),又能讓盡可能多的任務(wù)獲得正確調(diào)度,以提升資源利用率。仿真實(shí)驗(yàn)與既有的TA、CD、CD-A算法比較,積極處理低關(guān)鍵級(jí)任務(wù)策略在系統(tǒng)可接受任務(wù)數(shù)目和拋棄任務(wù)比率上,均有明顯優(yōu)勢(shì)。(5)提出了一種自適應(yīng)回落系統(tǒng)關(guān)鍵級(jí)的閉環(huán)機(jī)制�；趯�(shí)時(shí)任務(wù)在不同執(zhí)行模式下實(shí)際執(zhí)行時(shí)間的分布特性,監(jiān)測(cè)高關(guān)鍵級(jí)任務(wù)的實(shí)際執(zhí)行時(shí)間,預(yù)測(cè)高關(guān)鍵級(jí)任務(wù)利用率變化趨勢(shì)與執(zhí)行模式,可及時(shí)恢復(fù)調(diào)度此前關(guān)鍵級(jí)提升時(shí)被拋棄的低關(guān)鍵任務(wù),且不影響高關(guān)鍵級(jí)任務(wù)的正確執(zhí)行,實(shí)現(xiàn)安全降低系統(tǒng)關(guān)鍵級(jí)。仿真實(shí)驗(yàn)結(jié)果顯示了自適應(yīng)關(guān)鍵級(jí)回落算法優(yōu)于至今被認(rèn)為最優(yōu)的BP方法。
[Abstract]:The modern embedded real-time system represented by the aviation and the automobile field, the software functions of the high security standard and other non-safety critical software functions share an embedded platform, so as to solve the problem that the software functions are diversified, Complicating demand conflicts with hardware platform limited SWa P (size and price) requirements. The real-time scheduling of such systems shall meet the two objectives at the same time: one is to meet the verification requirements for safety critical functions under the setting of relatively conservative time attribute; and at the same time, the design requirements of the high-efficiency utilization of the computing resources are met under the setting of a more optimistic time attribute. The scheduling problem of such hybrid key-level systems cannot be solved using the traditional real-time scheduling algorithm. The key-level scheduling problem has become one of the most challenging topics in the embedded field. In this paper, based on the different scheduling requirements of key-level scheduling for security and non-safety critical tasks, and the goal of efficient utilization of resources, different scheduling strategies for high and low key-level tasks are studied respectively. The main research work and results are as follows: (1) Based on the actual situation of the key-level improvement of the event-triggered system, the schedulability of the high-key task is analyzed, and the sufficient conditions for the scheduling of key-level and high-key tasks are obtained. It is pointed out that the trigger of the key-level improvement of the system is derived from the external event of the system. Based on the response time analysis technology, the influence of the key-level lifting time on the deadline for meeting the deadline of the high-critical-level tasks is studied. Based on this, a conditional priority switching algorithm is proposed in the key-level promotion period. Ensure that more critical-level tasks are properly scheduled. The simulation experiment shows the availability of the schedulable condition and the priority switching algorithm. (2) A hybrid key-level task scheduling algorithm, which is suitable for deadline-critical parameters, is proposed. The key-level task model of the critical-level task is defined, and the possible interference of the key-level task to the task scheduling of the high-critical stage is analyzed, so that the key-level task is improved in advance, and the limited low-key task is sacrificed. The deadline for critical-level tasks to dynamically change with system-critical levels can always be met. The simulation experiments prove that the pre-critical-level lifting algorithm is suitable for the task scheduling with the deadline as the key parameter, and is not affected by the high critical-level task ratio and the deadline change degree. (3) A semi-local scheduling algorithm is proposed for scheduling hybrid key-level tasks on a homogeneous multi-processor platform. in that invention, the high-key task utilization rate and the low-key-level task schedulability are taken into account, all high-critical tasks and most of the low-key-level tasks are fixed on a given processor, only a low-key-level task with a number of no more than the number of processors is the migration task, Can and can only be migrated on two adjacent processors, and can be synchronously executed. In exchange for efficient utilization of processor resources, the deadline for high-critical tasks can always be met. The simulation results show that the semi-local scheduling algorithm increases the schedulable task ratio by nearly 10% compared with the local scheduling hybrid key-level task. (4) A strategy to actively deal with the low-key task is put forward. for the hybrid key-level system with the standard authentication, after the critical level is improved, the idle time period in the execution in the multi-processing platform is recovered, the idle time period in the execution in the multi-processing platform is matched in a global allocation manner, the high-key task of the local scheduling is not interfered, It also allows as many tasks as possible to get the right schedule to improve resource utilization. The simulation experiment is compared with the existing TA, CD and CD-A algorithms, and the active processing of the low-key task strategy has a clear advantage in the number of acceptable tasks and the abandoned task ratio of the system. (5) A closed-loop mechanism for adaptive back-down system is proposed. based on the distribution characteristics of the actual execution time of the real-time task in different execution modes, the actual execution time of the high-key-level task is monitored, the trend and the execution mode of the high-key-level task utilization rate are predicted, and the low-key task which is abandoned when the key-level improvement in the scheduling is timely recovered, And the key level of the safety reduction system is realized. The simulation results show that the self-adaptive critical-level back-down algorithm is better than the BP method which is considered to be the best.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

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

1 劉文濤,張群,孫肅清;關(guān)于煉鋼廠重調(diào)度問題的研究[J];冶金自動(dòng)化;2004年06期

2 張居陽(yáng) ,禮欣 ,孫吉貴;基于約束的調(diào)度研究和實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2004年33期

3 劉琳;谷寒雨;席裕庚;;工件到達(dá)時(shí)間未知的動(dòng)態(tài)車間滾動(dòng)重調(diào)度[J];機(jī)械工程學(xué)報(bào);2008年05期

4 黃峰;丁亞武;;人機(jī)協(xié)同模式下的手工調(diào)度技術(shù)研究[J];黑龍江科技信息;2011年35期

5 郭艷東;黃敏;王慶;;鎖定初始調(diào)度的緊急工作單機(jī)重調(diào)度問題[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期

6 姜洋;孫偉;丁秋雷;張旭;;考慮行為主體的單機(jī)調(diào)度干擾管理模型[J];機(jī)械工程學(xué)報(bào);2013年14期

7 李向軍,王書振;網(wǎng)絡(luò)化集成制造模式下調(diào)度問題的混合遺傳算法[J];西安聯(lián)合大學(xué)學(xué)報(bào);2002年04期

8 王中杰,吳啟迪,有杰;基于多目標(biāo)的半導(dǎo)體生產(chǎn)線滿意調(diào)度[J];控制與決策;2002年06期

9 李云峰;凌曉冬;武小悅;;調(diào)度問題中的沖突研究[J];兵工自動(dòng)化;2007年06期

10 徐群嶺;;基于免疫優(yōu)化的公交駕駛員調(diào)度問題[J];計(jì)算機(jī)工程;2010年24期

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

1 李建更;涂?jī)錾?馬海濤;;單機(jī)拖后時(shí)間總和問題交付期擾動(dòng)時(shí)最優(yōu)調(diào)度不變范圍的一種求法[A];第十九屆中國(guó)控制會(huì)議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費(fèi)用最小的多機(jī)調(diào)度問題[A];1995中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調(diào)度的復(fù)雜性及解決方法[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調(diào)度[A];1996中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調(diào)度問題研究[A];2006年首屆ICT大會(huì)信息、知識(shí)、智能及其轉(zhuǎn)換理論第一次高峰論壇會(huì)議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時(shí)間的單機(jī)調(diào)度問題[A];1996中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調(diào)度問題[A];1997年中國(guó)控制會(huì)議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫(kù)調(diào)度問題研究[A];第25屆中國(guó)控制與決策會(huì)議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準(zhǔn)備時(shí)間和交付期的單機(jī)E／T調(diào)度問題研究[A];1998年中國(guó)控制會(huì)議論文集[C];1998年

相關(guān)重要報(bào)紙文章 前2條

1 本報(bào)記者 賈科華;火電機(jī)組叫苦調(diào)度不合理[N];中國(guó)能源報(bào);2012年

2 本報(bào)記者 高芳;牽住“牛鼻子” 巧解“推進(jìn)難”[N];湖南經(jīng)濟(jì)報(bào);2008年

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

1 郭鵬;具有分段惡化效應(yīng)生產(chǎn)過程的智能優(yōu)化調(diào)度研究[D];西南交通大學(xué);2014年

2 元野;基于圖著色模型的零擔(dān)物流調(diào)度優(yōu)化問題研究[D];哈爾濱工業(yè)大學(xué);2015年

3 李雪松;模糊環(huán)境下若干單機(jī)批加工調(diào)度問題的模型及其算法研究[D];哈爾濱工業(yè)大學(xué);2015年

4 湯雅連;關(guān)聯(lián)物流運(yùn)輸調(diào)度問題研究[D];廣東工業(yè)大學(xué);2015年

5 周理;高效可重構(gòu)陣列計(jì)算：體系結(jié)構(gòu)，設(shè)計(jì)方法與程序映射技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

6 馮大光;一類批處理機(jī)調(diào)度的理論和方法研究[D];東北大學(xué);2011年

7 孟盈;鋼鐵企業(yè)并行批生產(chǎn)決策與調(diào)度問題研究[D];東北大學(xué);2011年

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學(xué);2015年

9 李亞志;流水制造單元調(diào)度智能優(yōu)化方法[D];東南大學(xué);2015年

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學(xué);2016年

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

1 張亮;云計(jì)算環(huán)境下的資源調(diào)度技術(shù)的研究[D];江南大學(xué);2015年

2 馮卓鵬;重載運(yùn)輸卸車組織優(yōu)化研究[D];西南交通大學(xué);2015年

3 崔雪源;基于遺傳模擬退火算法的航班著陸調(diào)度問題[D];華中師范大學(xué);2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調(diào)度問題的研究[D];曲阜師范大學(xué);2015年

5 張勇;帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題[D];山東大學(xué);2015年

6 吳凡;基于粒子群優(yōu)化算法的風(fēng)電-火電機(jī)組組合調(diào)度研究[D];華北電力大學(xué);2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調(diào)度問題研究[D];重慶理工大學(xué);2015年

8 吉佳紅;基于細(xì)菌覓食算法的改進(jìn)及應(yīng)用研究[D];江蘇科技大學(xué);2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學(xué);2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調(diào)度研究[D];大連理工大學(xué);2015年

，

本文編號(hào)：2478995