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

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

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

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

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