課件操作系統(tǒng)處理機調度ppt課件(參考版)
2025-05-06 18:16本頁面
【正文】 第三章 處理機調度與死鎖 圖 39 利用 ELLF算法進行調度的情況 t1A1( 1 0 )10 20 30 40 50 60 80t0t1＝ 0B1( 2 0 )t2t370A2( 1 0 ) A3( 1 0 ) A4( 1 0 )t4t5t6t7t8B1( 5 ) B2( 1 5 ) B2( 1 0 )。 第三章 處理機調度與死鎖 t6=55ms， 任務 A尚未進入第 4周期 ， 而任務 B已進入第 2周期 ， 故再調度 B2執(zhí)行 。 t4=40 ms時 ， A3的松弛度為 10 ms(即 601040)， 而 B1的松弛度僅為 5 ms(即 50540)， 故又應重新調度 B1執(zhí)行 。 在t2=10 ms時 ， A2的松弛度可按下式算出： A2的松弛度 =必須完成時間 其本身的運行時間 當前時間 =40 ms10 ms10 ms=20 ms 第三章 處理機調度與死鎖 B1的松弛度為 15ms， 故調度程序應選擇 B1運行 。 第三章 處理機調度與死鎖 圖 38 A和 B任務每次必須完成的時間 A1A2A3A4A5A6A7A820 40 60 80 1 0 0 1 2 0 1 4 0 1 6 0B1B2B3t0依照此圖中進程 AB必須完成的時間點，向前推算什么時候隊各進程進行調度。 第三章 處理機調度與死鎖 例子： 在一個實時系統(tǒng)中，有兩個周期性的進程 A和 B，任務 A要求每 20毫秒執(zhí)行一次，執(zhí)行時間為 10毫秒；任務 B只要求每 50毫秒執(zhí)行一次，執(zhí)行時間為 25毫秒。 理解：在保證進程被調度執(zhí)行的情況下 ， 最晚應該在什么時間得到調度 ， 才能夠保證順利完成任務 。 任務的緊急程度愈高 ， 為該任務所賦予的優(yōu)先級就愈高 ， 以使之優(yōu)先執(zhí)行 。 在該例中利用最早截止時間優(yōu)先算法可以滿足系統(tǒng)的要求。 第三章 處理機調度與死鎖 第四行是采用最早截止時間優(yōu)先算法的時間圖。 第二行中假定任務 A具有較高的優(yōu)先級 ， 所以在 t=0 ms時 ， 先調度 A1執(zhí)行 ， 在 A1完成后 (t = 10 ms)才調度 B1執(zhí)行；在 t = 20 ms時 ， 調度 A2執(zhí)行；在 t = 30 ms時 ， A2完成 ， 又調度 B1執(zhí)行；在 t = 40 ms時 ， 調度 A3執(zhí)行；在 t = 50 ms時 ， 雖然 A3已完成 ， 但 B1已錯過了它的最后期限 ， 這說明了利用通常的優(yōu)先級調度已經(jīng)失敗 。其中任務 A的到達時間為 0、 … ；任務A的最后期限為 60、 … ；任務 B的到達時間為 0、 50、100、 … ；任務 B的最后期限為 50、 100、 150、 … (注：單位皆為 ms)。 任務 A的周期時間為 20 ms，每個周期的處理時間為 10 ms；任務 B的周期時間為 50 ms，每個周期的處理時間為 25 ms。在此期間又到達作業(yè) 4，其開始截止時間仍是早于任務 2的，故在任務 3執(zhí)行完后，系統(tǒng)又調度任務 4執(zhí)行，最后才調度任務 2執(zhí)行。 系統(tǒng)首先調度任務 1執(zhí)行，在任務 1執(zhí)行期間，任務 3又先后到達。 該調度算法首先運行隊首進程，即截止時間最近的那個進程。 ( a ) 非搶占 輪轉調度當前進 程 實時進 程實時進 程請求調度實時進 程槍占當前進程，并立即 執(zhí)行( d ) 立即搶 占的優(yōu)先權調度調度時 間進程 1 進程 2實時進 程要求調度進程 n 實時進 程調度實 時進程運行( b ) 非搶占 優(yōu)先權調度當前進 程 實時進 程實時進 程請求調度 當前進 程運行完成調度時 間當前進 程實時進 程請求調度 時鐘中 斷到來時調度時 間( c ) 基于時 鐘中斷搶占的優(yōu)先權搶占調度調度時 間實時進 程圖 36 實時進程調度比較 第三章 處理機調度與死鎖 常用的幾種實時調度算法 1. 最早截止時間優(yōu)先即 EDF(Earliest Deadline First)算法 算法思想是： 當一個事件發(fā)生時，對應的進程就被加入就緒進程隊列。為要求響應的任務設置較高的優(yōu)先級 ，并將其掛在隊首，等待當前任務執(zhí)行完畢后進入執(zhí)行。 主要用于實時要求不高的系統(tǒng)中。 第三章 處理機調度與死鎖 實時調度算法的分類 1. 非搶占式調度算法 (1) 非搶占式輪轉調度算法。 在完成任務調度后 ， 便應進行任務切換 。 為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應 ， 要求系統(tǒng)具有快速硬件中斷機構 ， 還應使禁止中斷的時間間隔盡量短 ， 以免耽誤時機 (其它緊迫任務 )。 這種機制采用比較廣泛 ， 因為很難對任務的開始和截止進行預先的估計 ， 所以非搶占式調度機制一般很少采用 。 第三章 處理機調度與死鎖 3. 采用搶占式調度機制 當一個優(yōu)先權更高的任務到達時 ， 允許將當前任務暫時掛起 ， 而令高優(yōu)先權任務立即投入運行 ， 這樣便可滿足該硬實時任務對截止時間的要求 。 解決的方法是提高系統(tǒng)的處理能力 ， 其途徑有二：其一仍是采用單處理機系統(tǒng) ， 但須增強其處理能力 ， 以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統(tǒng) 。 處理機要保證在特定的時間內使作業(yè)得到調度 。 (5) 優(yōu)先級。 (3) 處理時間。 第三章 處理機調度與死鎖 實 時 調 度 實現(xiàn)實時調度的基本條件 1. 提供必要的信息
教學課件相關推薦
鄂ICP備17016276號-1