基于DNA-GA的最早截止期限優(yōu)先調度算法優(yōu)化.pdf

1、實時調度算法是嵌入式實時系統(tǒng)設計和實現(xiàn)的關鍵問題之一，也是保障實時系統(tǒng)兩個必備特性(時限性和可靠性)的重要方法，是實時系統(tǒng)中重要而活躍的研究領域。 在眾多的實時調度算法中，速率單調(Rate Monotonic，RM)和最早截止期限優(yōu)先(Earliest Deadline First，EDF)分別是靜態(tài)調度和動態(tài)調度領域中經典的調度算法。RM算法屬于靜態(tài)調度算法，在系統(tǒng)運行前決定任務的調度，實現(xiàn)簡單，在滿足前提條件的情況下可以保

2、證實時任務集的成功調度。EDF算法屬于動態(tài)調度算法，在系統(tǒng)運行時決定任務的調度，CPU利用率可以達到100％(理想情況下)。雖然RM和EDF算法以其各自所具備的優(yōu)良性能在嵌入式實時系統(tǒng)中得到了廣泛應用，但是我們也不能忽視它們本身存在的實時性問題。 本文是在考慮“任務調度開銷時間”的情況下，通過優(yōu)化EDF調度算法中各個任務的啟動時間來提高EDF調度算法的實時性能的。 首先介紹實時調度算法的應用背景：實時系統(tǒng)、嵌入式系統(tǒng)、

3、實時操作系統(tǒng)和嵌入式實時操作系統(tǒng)。 接著對現(xiàn)有的實時調度模型、實時調度基本理論、調度策略和實時調度算法進行了分析和研究。對RM和EDF實時調度算法進行了詳細分析，并舉例說明了它們的調度過程。 然后介紹了本文用到的優(yōu)化算法—DNA遺傳算法(Deoxyribonucleic acid Genetic Algorithm，DNA-GA)，及其基本理論和操作方法，并說明了DNA(Deoxyribonucleic acid)算法的

4、生物學基礎和遺傳算法的基本理論。 最后，通過使用DNA-GA對EDF調度算法中各個任務的啟動時間進行離線優(yōu)化，離線計算各實時任務的啟動時間，運用這些優(yōu)化的啟動時間作為在線實時系統(tǒng)使用EDF調度算法的參數(shù)進行實時任務調度，以此來提高實時系統(tǒng)的實時性能。本文模擬了基于DNA-GA的最早截止期限優(yōu)先調度算法的優(yōu)化調度，并比較了優(yōu)化前后因搶占引起的調度開銷。實驗結果表明：使用DNA遺傳算法可以對實時任務的啟動時間進行優(yōu)化，可以減少實時