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

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

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

【參考文獻】

相關期刊論文 前3條

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

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

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

本文編號：2650886