【文章內(nèi)容簡介】 和調(diào)度效果如何？ 運行 低優(yōu)先就緒 高優(yōu)先就緒 等待 首先選擇100ms 其次選擇500ms 請求 I/O I/O完成 超時間片 第三章 處理機調(diào)度與死鎖 隊列結(jié)構(gòu) ? I/O等待隊列 —— 一個進程如果請求 I/O，則進入 I/O等待隊列。 ?低優(yōu)先就緒隊 —— 一個進程如果在運行中超過了它的時間量就進入低優(yōu)先就緒隊列。 ? 高優(yōu)先就緒隊列 —— 當進程從等待狀態(tài)變?yōu)榫途w狀態(tài)時則進入高優(yōu)先就緒隊列。 第三章 處理機調(diào)度與死鎖 進程調(diào)度算法 優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略： (1) 當 CPU空閑時，若高優(yōu)先就緒隊列非空，則從高優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為 100ms (2) 當 CPU空閑時，若高優(yōu)先就緒隊列為空，則從低優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為 500ms 調(diào)度效果 優(yōu)先照顧了 I∕O量大的進程； 適當照顧了計算量大的進程。 第三章 處理機調(diào)度與死鎖 運行 低優(yōu)先就緒 高優(yōu)先就緒 因盤或帶I/O而等待 進程調(diào)度500ms 請求盤或帶 I/O I/O完成 超時間片 中優(yōu)先就緒 因終端I/O而等待 因頁面I/O而等待 進程調(diào)度100ms 進程調(diào)度100ms I/O完成 I/O完成 請求終端 I/O 缺頁中斷 調(diào)度算法、效果？ 第三章 處理機調(diào)度與死鎖 思考 ?若在操作系統(tǒng)的就緒進程隊列中等待運行的共有三個進程 P P P3，已知它們各自的運行時間為 a、 b、 c，且滿足關(guān)系 a b c。請證明采用最短作業(yè)優(yōu)先調(diào)度算法能夠獲得最小平均周轉(zhuǎn)時間。 第三章 處理機調(diào)度與死鎖 實 時 調(diào) 度 實現(xiàn)實時調(diào)度的基本條件 1． 提供必要的信息 (1) 就緒時間 。 (2) 開始截止時間和完成截止時間。 (3) 處理時間。 (4) 資源要求。 (5) 優(yōu)先級。 2．系統(tǒng)處理能力強 3．采用搶占式調(diào)度機制 4．具有快速切換機制 第三章 處理機調(diào)度與死鎖 實時調(diào)度算法的分類 1． 非搶占式調(diào)度算法 1) 非搶占式輪轉(zhuǎn)調(diào)度算法 數(shù)秒至數(shù)十秒的響應(yīng)時間 ，可用于要求不太嚴格的實時控制系統(tǒng)中。 2) 非搶占式優(yōu)先調(diào)度算法 獲得僅 為數(shù)秒至數(shù)百毫秒級的響應(yīng)時間 ， 因而可用于有一定要求的實時控制系統(tǒng)中 。 第三章 處理機調(diào)度與死鎖 2． 搶占式調(diào)度算法 在要求較嚴格的 (響應(yīng)時間為數(shù) 十毫秒以下 )的實時系統(tǒng)中 ，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法 。 可根據(jù)搶占發(fā)生時間的不同而進一步分成以下兩種調(diào)度算法 。 1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 2) 立即搶占 (Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法 第三章 處理機調(diào)度與死鎖 圖 38 實時進程調(diào)度 ( a ) 非搶占式輪轉(zhuǎn)調(diào)度當前進程 實時進程實時進程請求調(diào)度實時進程搶占當前進程并立即執(zhí)行( d ) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進程 1 進程 2實時進程要求調(diào)度進程 n 實時進程調(diào)度實時進程運行( b ) 非搶占式優(yōu)先權(quán)調(diào)度當前進程 實時進程實時進程請求調(diào)度 當前進程運行完成調(diào)度時間當前進程實時進程請求調(diào)度 時鐘中斷到來時調(diào)度時間( c ) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進程?實時進程加入隊尾等待下一個時間片 實時進程加入隊首 阻塞 第三章 處理機調(diào)度與死鎖 常用的幾種實時調(diào)度算法 1． 最早截止時間優(yōu)先即 EDF(Earliest Deadline First)算法 1) 非搶占式調(diào)度方式用于非周期實時任務(wù) 圖 39示出了將該算法用于非搶占調(diào)度方式之例。該例中具有四個非周期任務(wù)，它們先后到達。系統(tǒng)首先調(diào)度任務(wù) 1執(zhí)行，在任務(wù) 1執(zhí)行期間，任務(wù) 3又先后到達。由于任務(wù) 3的開始截止時間早于任務(wù) 2，故系統(tǒng)在任務(wù) 1后將調(diào)度任務(wù) 3執(zhí)行。在此期間又到達作業(yè) 4，其開始截止時間仍是早于任務(wù) 2的，故在任務(wù) 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù) 4執(zhí)行，最后才調(diào)度任務(wù) 2執(zhí)行。 第三章 處理機調(diào)度與死鎖 圖 39 EDF算法用于非搶占調(diào)度的調(diào)度方式 1 3 4 2開始截止時間任務(wù)執(zhí)行任務(wù)到達1 2 3 41 3 4 2t到達 到達 到達 第三章 處理機調(diào)度與死鎖 2) 搶占式調(diào)度方式用于周期實時任務(wù) 圖 310示出了將最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例。在該例中有兩個周期性任務(wù)，任務(wù) A的周期時間為20 ms，每個周期的處理時間為 10 ms；任務(wù) B的周期時間為50 ms，每個周期的處理時間為 25 ms。圖中的第一行示出了兩個任務(wù)的到達時間、最后期限和執(zhí)行時間圖。其中任務(wù) A的到達時間為 0、 … ；任務(wù) A的最后期限為 60、 … ；任務(wù) B的到達時間為 0、 50、 100、 … ；任務(wù) B的最后期限為 50、 100、 150、 … (注：單位皆為 ms)。 第三章 處理機調(diào)度與死鎖 圖 310 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例 A1 B1 A2 B1 A3 B2 A4 B2 A5B1 A2 A3 B2 A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1 A2B2A3 A4 A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A2 B1 A3 A4 A5 ， B2A5 ， B2A4A1( 錯過 )A2 B1 A3( 錯過 )A1 A2 B1( 錯過 )A3 A4 A5 ， B20 10 20 30 40 50 60 70 80 90 100 時間 t /ms使用完成最后期限最早和最后期限調(diào)度(A 有較高優(yōu)先級 )(B 有較高優(yōu)先級 )最早截至?xí)r間優(yōu)先調(diào)度 最后期限 A到達就執(zhí)行 B到達就執(zhí)行 第三章 處理機調(diào)度與死鎖 第四行是采用最早截止時間優(yōu)先算法的時間圖。在 t = 0時， A1和 B1同時到達，由于 A1的截止時間比 B1早 ，故調(diào)度A1執(zhí)行；在 t = 10時， A1完成，又調(diào)度 B1執(zhí)行；在 t = 20時，A2到達 ，由于 A2的截止時間比 B2早， 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í)行。在該例中利用最早截止時間優(yōu)先算法可以 滿足系統(tǒng) 的要求。 第三章 處理機調(diào)度與死鎖 2． 最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 該算法是根據(jù)任務(wù)緊急 (或松弛 )的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在 200 ms時必須完成，而它本身所需的運行時間就有 100 ms，因此，調(diào)度程序必須在 100 ms之前調(diào)度執(zhí)行，該任務(wù)的 緊急程度 (松弛程度 )為100 ms。又如，另一任務(wù)在 400 ms時必須完成，它本身需要運行 150 ms，則其松弛程度為 250 ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列最前面，調(diào)度程序總是選擇就緒隊列中的隊首任務(wù)執(zhí)行。 第三章 處理機調(diào)度與死鎖 該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù) A和 B，任務(wù) A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次，執(zhí)行時間為 25 ms。由此可得知任務(wù) A和 B每次必須完成的時間分別為： A A A … 和 B B B … ，見圖 311。為保證不遺漏任何一次截止時間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。 第三章 處理機調(diào)度與死鎖 圖 311 A和 B任務(wù)每次必須完成的時間 A1A2A3A4A5A6A7A820 40 60 80 100 120 140 160B1B2B3t0第三章 處理機調(diào)度與死鎖 在剛開始時 (t1?=?0)， A1必須在 20 ms時完成，而它本身運行又需 10 ms，可算出 A1的松弛度為 10 ms； B1必須在 50 ms時完成，而它本身運行就需 25 ms，可算出 B1的松弛度為 25 ms，故調(diào)度程序應(yīng)先調(diào)度 A1執(zhí)行。在 t2?=?10 ms時， A2的松弛度可按下式算出： A2的松弛度 ?=?必須完成時間 ??其本身的運行時間 ??當前時間 ?? =?40 ms10 ms10 ms?=?20 ms 第三章 處理機調(diào)度與死鎖 類似地 ， 可算出 B1的松弛度為 15 ms， 故調(diào)度程序應(yīng)選擇B2運行 。 在 t3?=?30 ms時 ， A2的松弛度已減為 0(即 40??10??30)，而 B1的松弛度為 15 ms(即 50??5??30)， 于是調(diào)度程序應(yīng)搶占 B1的處理機而調(diào)度 A2運行 。 在 t4?=?40 ms時 ， A3的松弛度為 10 ms(即 60??10??40)， 而 B1的松弛度僅為 5 ms(即 50??5??40)，故又應(yīng)重新調(diào)度 B1執(zhí)行 。 在 t5?=?45 ms時 ， B1執(zhí)行完成 ， 而此時A3的松弛度已減為 5 ms(即 60??10??45)， 而 B2的松弛度為 30 ms(即 100??25??45)， 于是又應(yīng)調(diào)度 A3執(zhí)行 。 在 t6?=?55 ms時 ，任務(wù) A尚未進入第 4周期 ， 而任務(wù) B已進入第 2周期 ， 故再調(diào)度 B2執(zhí)行 。 在 t7?=?70 ms時 ， A4的松弛度已減至 0 ms(即 80??10??70)，而 B2的松弛度為 20 ms(即 100??10??70)， 故此時調(diào)度又應(yīng)搶占B2的處理機而調(diào)度 A4執(zhí)行 。 圖 312示出了具有兩個周期性實時任務(wù)的調(diào)度情況 。 第三章 處理機調(diào)度與死鎖 圖 312 利用 LLF算法進行調(diào)度的情況 t1A1( 10)10 20 30 40 50 60 80t0t1＝ 0B1( 20)t2t370A2( 10) A3( 10) A4( 10)t4t5t6t7t8B1( 5) B2( 15) B2( 10)第三章 處理機調(diào)度與死鎖 小結(jié) ?處理機調(diào)度的基本算法 ?先來先服務(wù) （ FCFS） ?短進程優(yōu)先 （ SPF） ?高優(yōu)先權(quán)調(diào)度 （ FPF ） ?時間片輪轉(zhuǎn)（ RR） ?多級反饋隊列調(diào)度 ?作業(yè)調(diào)度算法 ?先來先服務(wù) （ FCFS） ?短作業(yè)優(yōu)先 （ SJF） ?高優(yōu)先權(quán)調(diào)度（ FPF） ?高響應(yīng)比優(yōu)先（ HRN） 實時調(diào)度 ?最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 第三章 處理機調(diào)度與死鎖 綜合實驗 ?處理機調(diào)度模擬 (先來先服務(wù) （ FCFS）、 短進程優(yōu)先 （ SPF）、高優(yōu)先權(quán)調(diào)度 （ FPF ）、時間片輪轉(zhuǎn)（ RR） ?主存空間和磁盤空間的分配和回收 ?模擬文件系統(tǒng) ?模擬實現(xiàn)資源分配。同時要求編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并使用適當?shù)乃惴?，有效的防止和避免死鎖的發(fā)生。具體用銀行家算法實現(xiàn)資源分配。 第三章 處理機調(diào)度與死鎖 Deadlock possible 產(chǎn)生死鎖的原因和必要條件 死鎖的概念 第三章 處理機調(diào)度與死鎖 Deadlock 第三章 處理機調(diào)度與死鎖 ?死鎖（ Deadlock）定義