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

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

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

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

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