一種基于EDF的運行時模型研究.pdf

1、實時動態(tài)調(diào)度是一個實用而有趣的課題。例如，在飛行控制系統(tǒng)中，測高任務(wù)的運行周期可以是動態(tài)的，飛行高度越低采樣率越高。類似地，在機器人目標(biāo)逼近測量場合，機器人越接近目標(biāo)，測量周期一般也應(yīng)該縮短。
　　 EDF(Earliest Deadline First)是實時系統(tǒng)中的一個經(jīng)典調(diào)度算法?；谠撍惴?，國際著名學(xué)者Buttazzo近年提出了一種彈性調(diào)度模型，以應(yīng)對上述實時動態(tài)調(diào)度場合。Qian改進了這種模型，特別是在計算模型中的一個

2、重要指標(biāo)“新任務(wù)插入時間”時，給出了一個更合理而快捷的公式。一般來說，這一時間越快越好。但是，關(guān)于最早插入時間的計算仍然是一個開問題。
　　 本文并非去探討最早插入時間的計算，而是研究在現(xiàn)有成果的基礎(chǔ)上，如何才能實現(xiàn)實時新任務(wù)運行時的盡早插入。為此，提出了選擇性壓縮思想，引入了剩余帶寬的概念，并將原有模型進行了適當(dāng)擴展，使之更接近于實際應(yīng)用場合。
　　 如果系統(tǒng)已是滿負荷運行，為了任務(wù)加速或插入新任務(wù)，必須對原有單個或多

3、個任務(wù)進行壓縮。選擇不同的受壓任務(wù)，往往具有不同的效果。我們提出：選擇讓新任務(wù)等待時間最短的現(xiàn)行任務(wù)進行壓縮。這是選擇性壓縮的基本思想。文中對此進行了深入研究和分析。
　　 對于受壓任務(wù)，其本作業(yè)周期的剩余執(zhí)行量是一個重要指標(biāo)。我們發(fā)現(xiàn)：真正重要的應(yīng)該是這一剩余執(zhí)行量與剩余時間之比。我們將這一比值定義為剩余帶寬，并將剩余帶寬與選擇性壓縮思想相結(jié)合，提出了基于剩余帶寬的選擇性壓縮算法，并給出和證明了相關(guān)定理。
　　 為了先

4、簡化問題的研究，Buttazzo和Qian的原有模型都作了一些假定。本文則適當(dāng)進行了模型擴展。考慮到并非所有場合都要求盡快插入和/或加速，有時只要在某一截止期之前完成就可以了。為此我們引入了任務(wù)插入截止期，與選擇性壓縮思想相結(jié)合后，新任務(wù)插入又有了新的內(nèi)涵。
　　 為了演示算法和思想的有效性，我們采用了一個交換網(wǎng)仿真工具Switchsim。文中詳細描述了算法在仿真工具中的實現(xiàn)。仿真結(jié)果表明：上述思想和算法能夠較好地完成新任務(wù)插入