【摘要】：隨著嵌入式技術(shù)的迅猛發(fā)展以及嵌入式應(yīng)用復(fù)雜性的不斷攀升,當(dāng)今嵌入式系統(tǒng)的應(yīng)用環(huán)境通常包含多種類型的應(yīng)用需求,而對于系統(tǒng)進行滿足實時約束的服務(wù)不再是實時調(diào)度的唯一目標。為了能夠正確的執(zhí)行系統(tǒng)功能,在系統(tǒng)調(diào)度的過程中,還需要考慮任務(wù)間的偏序約束、任務(wù)間的資源共享約束以及為任務(wù)提供滿足QoS要求的服務(wù)等問題。 雖然傳統(tǒng)的實時調(diào)度理論及其相關(guān)模型仍是目前實時系統(tǒng)中實時調(diào)度的理論基礎(chǔ),但僅僅使用任務(wù)的基本時間特征來作出系統(tǒng)的調(diào)度決策并不能充分滿足多種類型的應(yīng)用需求,而且單一的調(diào)度目標往往不能夠滿足具備其他約束的實時系統(tǒng)需要。因此在確保滿足實時任務(wù)可調(diào)度性這一根本需求的前提下,如何根據(jù)具體應(yīng)用的實際約束需求進行正確有效的調(diào)度,是目前實時調(diào)度研究領(lǐng)域需要解決的關(guān)鍵問題。本文主要對具備約束的實時調(diào)度問題進行研究,主要包括具備偏序約束的實時調(diào)度問題和具備QoS約束的實時調(diào)度問題。 具備偏序約束的實時調(diào)度問題源于實際應(yīng)用中特定功能的設(shè)計要求,這樣的實時應(yīng)用通常被設(shè)計為在計算資源上調(diào)度運行的交互任務(wù),由于這些并行任務(wù)要實現(xiàn)整體計算,因此任務(wù)間需要滿足執(zhí)行的優(yōu)先順序關(guān)系來確保整體功能的正確性。為了解決在線調(diào)度算法無法處理釋放時間任意的任務(wù)集的問題,本文以并行拓撲排序原理為基礎(chǔ),通過任務(wù)間的并行性和串行性分析來在線確定不可搶占調(diào)度序列,可證明該方法在任務(wù)按偏序約束層次釋放時最優(yōu)。離線調(diào)度是解決具備偏序約束調(diào)度問題的另一個手段,本文通過對具備偏序約束的實時任務(wù)集的不可搶占調(diào)度的分析,將調(diào)度約束總結(jié)為任務(wù)的實時約束、任務(wù)間的偏序約束以及調(diào)度序列中不可搶占的序列約束,將這三種約束轉(zhuǎn)換為線性規(guī)劃求解問題的標準約束形式,采用分支檢測策略,不斷修正調(diào)度序列約束來進行規(guī)劃,以求解滿足偏序和實時約束的可行調(diào)度序列。 具備QoS約束的實時調(diào)度問題來自嵌入式實時系統(tǒng)在控制系統(tǒng)、網(wǎng)絡(luò)通信系統(tǒng)、工業(yè)網(wǎng)絡(luò)系統(tǒng)等領(lǐng)域中的應(yīng)用,在這類應(yīng)用中,在有限時間區(qū)間內(nèi)部分任務(wù)截止期的錯過不會影響整個應(yīng)用的性能,但這種截止期不滿足的情況需要在QOS約束允許的范圍內(nèi)。本文提出滿足QoS約束的在線調(diào)度算法,基于任務(wù)周期和實時QoS約束采用RM調(diào)度策略進行任務(wù)固定優(yōu)先級設(shè)置,根據(jù)當(dāng)前實時約束參數(shù)滿足情況的統(tǒng)計將任務(wù)在搶占和可選間進行調(diào)整,以時刻反映任務(wù)當(dāng)前的QoS服務(wù)等級需求,同時為了滿足系統(tǒng)對高負載的適應(yīng)性,該算法可以結(jié)合QoS適度退化機制,在保證為緊要任務(wù)提供滿足最低QoS的服務(wù)的前提下,最大限度的為所有任務(wù)提供有效的服務(wù)。該算法即具備了靜態(tài)調(diào)度算法可以進行可調(diào)度判定的優(yōu)點,又能夠像動態(tài)調(diào)度算法那樣根據(jù)系統(tǒng)負載動態(tài)設(shè)定任務(wù)的執(zhí)行模式。本文還針對具備QoS約束的實時系統(tǒng)在能耗約束系統(tǒng)中的應(yīng)用,基于遺傳算法提出最小化能耗的任務(wù)執(zhí)行模式的離線優(yōu)化方案,并針對于采用標準遺產(chǎn)算法求解任務(wù)的最佳執(zhí)行模式出現(xiàn)“早熟”等問題,將模擬退火算法引入到遺傳算法變異過程形成混合遺傳算法,提高最優(yōu)解的搜索性能。 在對兩個約束調(diào)度目標、四種調(diào)度策略的論述過程中,本文分別使用算例分析、仿真實驗等手段驗證了所提出調(diào)度算法的正確性和有效性。
【圖文】：

則可由RM調(diào)度。以L(N)表示N個任務(wù)的CPU利用率的最小上界。L(N)與君無關(guān)，，以N)隨著N單調(diào)遞減，當(dāng)N崢co，定的物理意義如圖2.1所示。L(N)=0.693。利用CPU利用率作為可調(diào)度判 u................麟黔撇黝 0Boundl圖2.1利用CPU利用率最小上界進行可調(diào)度判定的物理意義 Fig.2.1PhysiealmeaningofsehedulablitytestwithCPUutilizationleastuPbounds圖2.1中三種情況所代表的物理意義如下:(l)整個CPu利用率小于L(N)，任務(wù)集是RM可調(diào)度的;(2)整個CPU利用率大于1，任務(wù)集是RM不可調(diào)度的;(3)整個CPu利用率介于L(N)和1之間，無法判定�？梢�，對于圖中處于灰色區(qū)域內(nèi)的任務(wù)集，有可能可調(diào)度，但利用CPU利用率最小上界來判定卻無能為力。可見，定理2.1是RM調(diào)度的充分條件。實際上，不滿足上述定理的實時任務(wù)集也可能由RM調(diào)度。RM算法是一種靜態(tài)優(yōu)先級調(diào)度算法。它在運行前確定任務(wù)的執(zhí)行順序，運行調(diào)度開銷小

圖5.1示例1的R五1一RTO調(diào)度序列 Fig.5.1SchedulingsequeneebyRM一RTOofExamPlel從圖5.1可以看出，采用RM一Rl，O的固定優(yōu)先級設(shè)置方法，在一個超周期內(nèi)，所有周期任務(wù)的強制任務(wù)都能夠滿足截至期的要求，從而達到了實時Qos約束參數(shù)的要求。若采用本調(diào)度算法對該任務(wù)集進行調(diào)度，由于尸，欠介z<pZ廠k2<P3欠兒，因此分別設(shè)置:，，:2和:。搶占任務(wù)的優(yōu)先級為1
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2010
【分類號】：TP368.1

【參考文獻】

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

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

2 林劍檸,吳慧中;基于遺傳算法的網(wǎng)格資源調(diào)度算法[J];計算機研究與發(fā)展;2004年12期

3 黎群;流水車間作業(yè)排序中的改進NEH算法[J];系統(tǒng)工程理論方法應(yīng)用;1999年04期

本文編號：2650886