EDF算法中任務對帶寬轉讓問題的研究.pdf

1、隨著社會的發(fā)展和科技的進步，實時性應用不斷地涌現(xiàn)，對于實時系統(tǒng)的靈活性要求越來越高。實時調度算法作為保障實時系統(tǒng)性能的關鍵點，一直是實時系統(tǒng)研究領域中重要的課題之一。
　　EDF(Earliest Deadline First)是實時系統(tǒng)中一個經(jīng)典的動態(tài)調度算法，實時系統(tǒng)領域的著名學者Buttazzo于2002年在EDF基礎上提出了一種彈性調度模型，使得任務調度變得更加靈活，同時在該模型中新任務的最早可插入時間的問題進入了人們的視

2、野中。Buttazzo給出了這個問題的解決方案，一個計算最早可行時刻的公式（以下簡稱B定理），Qian在B定理基礎之上作出了改良，提出了一個更好的計算公式（以下簡稱Q定理）。但實際上使用Q定理求取的新任務最早可行時刻不是總是最早的，實際實驗中出現(xiàn)了比Q定理更好的插入時間，也就是說新任務插入的最早可行時間的計算仍然是一個開問題。
　　本文立足于以上研究背景，著眼于EDF動態(tài)調度模型中新任務插入或者現(xiàn)行任務加速引起的帶寬轉讓問題。本文

3、根據(jù)處理器需求準則，對新任務不同插入時刻的調度結果做了分析，提出了作業(yè)截止期準則，作業(yè)截止期準則給出了新任務插入時間是可行時刻的2個條件。從作業(yè)截止期準則得出了一個推論:在3個假定下得出的可行時刻就是最早可行時刻。這些假定對于其他任務的子集Γ則總是預留出最大的帶寬。但實際上考慮到Γ并不總是需要最大的帶寬，將Γ也納入研究的范圍，分析其和帶寬轉讓模型中任務對之間的搶占細節(jié)，是一個研究最早可行時刻的方向。本文中探討了幾種Γ也參與調度搶占的情形

4、，對這些情形下任務集的調度結果做了一些分析，在這種情形下能夠得到比B定理和Q定理更好的調度結果。
　　對于一個需要調度的任務集，其最早可行時刻可以通過計算機得到迭代方式計算而出，但這種方式消耗的時間較多，使得其在運行時的應用價值較低。本文針對一個任務對（一個受壓任務轉讓帶寬給另一個任務）的情形，滿足3個假定的前提下給出了一個計算新任務插入最早可行時刻的在線算法。通過大量的仿真實驗證明了這個在線算法求取的最早可行時刻比B定理和Q定理