[計算機軟件及應(yīng)用]os第三章-資料下載頁
2025-01-19 17:27本頁面
【正文】 60 70 80 90 100 B1 A1 A2 A3 A4 A5 B2 A2 最后期限 A1 最后期限 A3 最后期限 A4 最后期限 A5 最后期限 B1 最后期限 到達時間、執(zhí)行時間和最后期限 搶占式 EDF 0 10 40 20 30 50 60 70 80 90 100 時間 t/ms A1 B1 A2 B1 A3 A4 B2 A5 B2 A1,B1到達 在 t=0時， A1和 B1同時到達，由于 A1的截止時間比 B1早，故調(diào)度 A1執(zhí)行； 在 t=10時， A1完成，又調(diào)度 B1執(zhí)行； 在 t=20時， A2到達，由于 A2的截止時間比 B1早， B1被中斷而調(diào)度 A2執(zhí)行； 在 t=30時， A2完成，又重新調(diào)度 B1執(zhí)行； 在 t=40時， A3又到達，但 B1的截止時間要比 A3早，仍應(yīng)該讓 B1繼續(xù)執(zhí)行直到完成（ t=45），然后再調(diào)度 A3執(zhí)行； 在 t=55時， A3完成，又調(diào)度 B2執(zhí)行。 A1最后期限 A2最后期限 B1最后期限 A3最后期限 A4最后期限 A2到達 A3到達 A4到達 A5到達 B2到達 LLF算法 基本思想：根據(jù)任務(wù)緊急（或松弛）程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度越高，為該任務(wù)賦予的優(yōu)先級越高，以使之優(yōu)先執(zhí)行。 例如：一個任務(wù)在 200ms時必須完成，而它本身所需的運行時間就有 100ms，因此，調(diào)度程序必須在 100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度（松弛程度）為 100ms。又如，另一任務(wù)400ms時必須完成，它本身運行需要 150ms，則其松弛程度為250ms。 實現(xiàn)該算法時，要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)隊列，松弛度最低的任務(wù)排在隊列最前面，調(diào)度程序總是選擇隊列中的隊首任務(wù)執(zhí)行。 松弛度 =必須完成時間 其本身的運行時間 當(dāng)前時間 LLF算法舉例 在實時系統(tǒng)中，有兩個周期性實時任務(wù) A和 B，任務(wù) A要求每20ms執(zhí)行一次，執(zhí)行時間為 10ms；任務(wù) B則要求每 50ms執(zhí)行一次，執(zhí)行時間為 25ms。任務(wù) A和 B每次必須完成的時間A1,A2,A3… 和 B1,B2,B3… 如下圖所示。 t A1 A2 A3 A4 A5 A6 A7 A8 0 20 40 60 80 100 120 140 160 B1 B2 B3 松弛度 =必須完成時間 其本身的運行時間 當(dāng)前時間 A1(10) 0 10 20 30 40 50 60 70 80 t1 B1(20) A2(10) t2 t3 t4 B1(5) A3(10) B2(15) t5 t6 t7 t8 A4(10) B2(10) t=0ms時， A1的松弛度是 10ms， B1的松弛度是 25ms，調(diào)度 A1執(zhí)行； t=10ms時， A2尚未到達，調(diào)度 B1執(zhí)行； t=30ms時， A2的松弛度是 0ms， B1的松弛度是 15（ 50530） ms，調(diào)度 A2執(zhí)行； t=40ms時， A3的松弛度是 10ms， B1的松弛度是 5（ 50540） ms，重新調(diào)度 B1執(zhí)行； t=45ms時， B1執(zhí)行完成， A3的松弛度是 5（ 601045） ms，調(diào)度 A3執(zhí)行； t=55ms時， A尚未進入第 4周期， B已進入第二周期，故再調(diào)度 B2執(zhí)行； t=70ms時， A4松弛度已減至 0ms，而 B2的松弛度為 20（ 1007010） ms，故此時又應(yīng)該搶占 B2的處理機而調(diào)度 A4執(zhí)行。 書上的解釋 松弛度 =必須完成時間 其本身的運行時間 當(dāng)前時間 A1(10) 0 10 20 30 40 50 60 70 80 t1 B1(20) A2(10) t2 t3 t4 B1(5) A3(10) B2(15) t5 t6 t7 t8 A4(10) B2(10) t=0ms時， A1的松弛度是 10ms， B1的松弛度是 25ms，調(diào)度 A1執(zhí)行； t=10ms時， A2尚未到達，調(diào)度 B1執(zhí)行； t=20ms時，由于 A1已完成， A2剛到達，故而沒有比較 A2和 B1的松弛度，而是 B1接著執(zhí)行。并且還要時刻監(jiān)控著 A2的松弛度，等到松弛度為 0，也就是 30ms時，搶占 B1的 CPU。 這種方法的效率并不高，原因在于 A2剛到達時，沒有和 B1的松弛度比較，而是等 A2到達后，不斷監(jiān)控 A2的緊迫程度，等緊迫度升到最高，也就是松弛度最低時，才又搶占 CPU。 松弛度 =必須完成時間 其本身的運行時間 當(dāng)前時間 t=0ms時， A1的松弛度是 10ms， B1的松弛度是 25ms，調(diào)度 A1執(zhí)行； t=10ms時， A2尚未到達，調(diào)度 B1執(zhí)行； t=20ms時， A2到達， A2的松弛度是 10（ 401020） ms， B1的松弛度是（ 501520=15） ms，調(diào)度 A2執(zhí)行； t=30ms時， A3尚未到達，調(diào)度 B1執(zhí)行； t=40ms時， A3的松弛度是 10（ 604010） ms， B1的松弛度是 5（ 50540） ms， B1繼續(xù)執(zhí)行； t=45ms時， B1執(zhí)行完成，調(diào)度 A3執(zhí)行； T=50ms時， B2到達， A3松弛度是（ 60550=5）， B2松弛度是 25（ 1002550）， A3繼續(xù)執(zhí)行； t=55ms時， A尚未進入第 4周期， B已進入第二周期，故再調(diào)度 B2執(zhí)行； t=60ms時， A4到達， A4松弛度為 10ms（ 801060）， B2松弛度是 20（ 1002060）， A4執(zhí)行； A1(10) 0 10 20 30 40 50 60 70 80 t1 B1(10) A2(10) t2 t3 t4 A3(10) B2 t5 t6 t7 t8 A4(10) B1(15) B2(5) 另一情況 調(diào)度發(fā)生在兩種場合：①有新進程到達時，計算松弛度決定是否搶占； ②有進程釋放 CPU（ CPU空閑時）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1