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

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

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

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

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