搶占式調(diào)度方式用于周期實時任務(wù)

搶占式調(diào)度方式用于周期實時任務(wù) 主講人：韓成喜 教案制作：李春強課件制作：陳存衡劉永華最早截止時間優(yōu)先即EDF（EarliestDeadlineFirst）算法： 根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實時任務(wù)就緒隊列，該隊列按各任務(wù)截止時間的早晚排序。調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊列中的第一個任務(wù)，為之分配處理機，使之投入運行。 該算法既可以用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。包括開始截止時間和完成截止時間問題描述 有兩個周期性任務(wù)，任務(wù)A的周期時間為20ms，每個周期處理時間為10ms；任務(wù)B的周期時間為50ms，每個周期處理時間為25ms。兩個任務(wù)的到達時間，最后期限和執(zhí)行時間如下圖：B2最后期限A1A3A5A4A2B1B2A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限0102030405060708090100 時間t/msA1A2A3A4A5B1B1B2B2B2B2最后期限A1A3A5A4A2B1B20102030405060708090100 時間t/msA1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限固定優(yōu)先級調(diào)度（A有較高優(yōu)先級）A1A2B1(錯過)A4A5，B2A3這說明利用通常的固定優(yōu)先級調(diào)度已經(jīng)失敗。t=0ms時，先調(diào)度A1執(zhí)行，在A1完成后才調(diào)度B1執(zhí)行t=20ms時，調(diào)度A2執(zhí)行在t=30ms時，A2完成，又調(diào)度B1執(zhí)行在t=40ms時，調(diào)度A3執(zhí)行在t=50ms時，雖然A3完成，但B1已錯過了它的最后期限在t=60ms時，A4到達調(diào)度A4執(zhí)行在t=70ms時，A4完成，又調(diào)度B2執(zhí)行執(zhí)行在t=80ms時，A5到達，調(diào)度A5執(zhí)行在t=900ms時，A5完成，又調(diào)度B2執(zhí)行B2最后期限A1A3A5A4A2B1B20102030405060708090100 時間t/msA1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限B1A2A3B2A5

固定優(yōu)先級調(diào)度（B有較高的優(yōu)先級）A1（錯過）A2B1A3A4（錯過）A5,B2A1A3A5A4A2B1B2A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限A2B1A5A1B1A30102030405060708090100 時間t/msA4B2B2使用完成最后期限最早和最后期限調(diào)度A1A2B1A3A4A5,B2在該例中利用最早截止時間優(yōu)先算法可以滿足系統(tǒng)要求。在t=0時，A1和B1同時到達，由于A1的截止時間比B1早，故調(diào)度A1執(zhí)行t=10ms時，A1完成，調(diào)度B1執(zhí)行在t=20ms時，A2到達，由于A2的截止時間比B2早，B1被中斷而調(diào)度A2執(zhí)行在t=30ms時，A2完成，又重新調(diào)度B1執(zhí)行在t=40ms時，A3又到達，但B1的截止時間比A3早，仍讓B1繼續(xù)執(zhí)行直到完成（t=45ms時），然后調(diào)度A3執(zhí)行t=55ms時，A3完成，又調(diào)度B2執(zhí)行t=60ms時，A4到達，由于A4的截止時間比B2早，B2被中斷而調(diào)度A4執(zhí)行t=70ms時，A4完成，又重新調(diào)度B2執(zhí)行t=80ms時，A5到達，由于A5和B2的截止時間相同，繼續(xù)執(zhí)行B2t=90ms時，B2完成，調(diào)度A5執(zhí)行B2最后期限

總結(jié):固定優(yōu)先級調(diào)度（A有較高優(yōu)先級）時