EDF算法中任務(wù)對帶寬轉(zhuǎn)讓問題的研究.pdf

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

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

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

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