【文章內(nèi)容簡介】 即使進程未執(zhí)行 完畢，系統(tǒng)也剝奪該進程的 CPU， 將該進 程排在就緒隊列末尾。同時系統(tǒng)選擇另一 個進程運行 分時系統(tǒng)中常用時間片輪轉(zhuǎn)法 1）基本原理 2021/11/12 46 時間片選擇問題： 固定時間片 可變時間片 與時間片大小有關(guān)的因素： 系統(tǒng)響應(yīng)時間 就緒進程個數(shù) CPU能力 2）時間片大小的確定 2021/11/12 47 時間片輪轉(zhuǎn)調(diào)度過程演示： q=4 初始調(diào)度隊列： P0(0,4) P1(1,3) P2(2,5) P3(3,2) P4(4,4) 第一輪調(diào)度后： P1(1,3) P2(2,5) P3(3,2) P4(4,4) P0正好完成，退出 第二輪調(diào)度后： P2(2,5) P3(3,2) P4(4,4) P1在 3ms內(nèi)完成，退出 2021/11/12 48 第三輪調(diào)度后： P3(3,2) P4(4,4) P2(2,1) P2未完成，讓出處理機，到就緒隊列 隊尾等待 2021/11/12 49 第四，僅當?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列 中的進程運行。 過程：首先設(shè)置多個就緒隊列，并為各個隊列賦予不同的 優(yōu)先權(quán)。 其次，賦予各個隊列中進程執(zhí)行時間片的大小也各不相同 第三，當一個新進程進入內(nèi)存后，首先將它放入第一隊 列的末尾，按 FCFS原則排隊等待調(diào)度。 第五，在第 n隊列中按時間片輪轉(zhuǎn)的方式運行 2021/11/12 50 多級反饋隊列調(diào)度過程演 示：優(yōu)先級由高到低 P0(4) P1(3) P2(5) P3(2) 就緒隊列 1 q=1 P0(3) P1(2) P2(4) P3(1) 就緒隊列 2 q=2 至 CPU 就緒隊列 3 q=4 P0(1) P2(2) 至 CPU 就緒隊列 n q=2n 2021/11/12 51 (1)終端型作業(yè)用戶 (2)短批處理作業(yè)用戶 (3)長批處理作業(yè) 返回 2021/11/12 52 進程調(diào)度的時機（補充） ? 當一個進程運行完畢，或由于某種錯誤而終止運行 ? 當一個進程在運行中處于等待狀態(tài) (等待 I/O) ? 分時系統(tǒng)中時間片到 ? 當有一個優(yōu)先級更高的進程就緒（可搶占式） ? 在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作（ P操作，阻塞原語，喚醒原語） 2021/11/12 53 進程切換（補充） ? 進程切換 定義：一個進程讓出處理器，由另一個進程占用處理器的過程 ? 進程的切換使系統(tǒng)中的各進程均有機會占用CPU ? 進程的切換是由進程狀態(tài)的變化引起的，而進程狀態(tài)的變化又與出現(xiàn)中斷事件有關(guān) 2021/11/12 54 實時調(diào)度 P97（未修改） 實時任務(wù)的分類： 1 按任務(wù)執(zhí)行時是否呈現(xiàn)周期性來劃分 （ 1）周期性實時任務(wù) （ 2）非周期性實時任務(wù) ?開始截止時間 ?完成截止時間 2 根據(jù)對截止時間的要求來劃分 （ 1）硬實時任務(wù) （ 2）軟實時任務(wù) 2021/11/12 55 實現(xiàn)實時調(diào)度的基本條件 包括： 就緒時間、 開始截止時間和完成截止時間、 處理時間、 資源要求、 優(yōu)先級 2021/11/12 56 2. 系統(tǒng)處理能力強 假定系統(tǒng)中有 m個周期性的硬實時任務(wù)，它們的處理 時間可表示為 Ci， 周期時間表示為 Pi， 則： ??miPiCi1≤ 1 系統(tǒng)才是可調(diào)度的。 2021/11/12 57 解決方法： 第一、 仍采用單處理機系統(tǒng)，但需增強其處理能力， 以顯著地減少對每一個任務(wù)的處理時間； 第二、 采用多處理機系統(tǒng)。 2021/11/12 58 3 . 采用搶占式調(diào)度機制 4 .具有快速切換機制 （ 1）對外部中斷的快速響應(yīng)能力； （ 2）快速的任務(wù)分派能力。 2021/11/12 59 實時調(diào)度算法的分類 P99 按 調(diào)度方式 的不同： 1 . 非搶占式調(diào)度算法 （ 1）非搶占式輪轉(zhuǎn)調(diào)度算法。 多個控制對象相同或相近；每個控制對象建立 一個實時任務(wù)，并排成輪轉(zhuǎn)隊列；每次選擇隊 列首部的任務(wù)投入運行，任務(wù)完成后加入隊尾； 響應(yīng)時間幾秒或幾十秒，實時要求不太嚴格； 該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中。 2021/11/12 60 （ 2）非搶占式優(yōu)先調(diào)度算法。 可用于有一定要求的實時控制系統(tǒng)中。 對實時要求嚴格的任務(wù)賦予較高的優(yōu)先級；當高 優(yōu)先級任務(wù)到達時安排在就緒隊列的隊首，等待 當前任務(wù)完成或自我終止時可被等待執(zhí)行；響應(yīng) 時間幾秒或幾百微秒 2021/11/12 61 2 . 搶占式調(diào)度算法 （ 1）基于時鐘中斷的搶占式優(yōu)先調(diào)度算法。 此算法可用于大多數(shù)的實時系統(tǒng)中。 （ 2）立即搶占的優(yōu)先權(quán)調(diào)度算法 高優(yōu)先級的實時任務(wù)到來時并不立即搶占當前 任務(wù)的處理機，要等到時鐘中斷到來時；等到 延遲幾十毫秒或幾毫秒 一旦出現(xiàn)外部中斷，只要當前任務(wù)未處于臨界區(qū)， 便能立即剝奪當前任務(wù)的執(zhí)行 2021/11/12 62 常用的幾種實時調(diào)度算法 基于優(yōu)先權(quán)的幾種調(diào)度算法。 EDF（ Earliest Deadline First)算法 該算法既可用于搶占式調(diào)度，也可用于非搶占式 調(diào)度。 例子： 2021/11/12 63 開始截止時間： 1 3 4 2 任務(wù)執(zhí)行： 1 3 4 2 任務(wù)到達： 1 2 3 4 例 1 非搶占調(diào)度用于非周期性實時任務(wù) 2021/11/12 64 例 2 搶占式調(diào)度方式用于周期實時任務(wù) ? 描述：有兩個周期性任務(wù)， A的周期時間為20ms，每個周期的處理時間為 10ms； B的周期時間為 50ms，每個周期的處理時間為25ms。 2021/11/12 65 2 .最低松弛度優(yōu)先即 LLF(Least Laxity First) 算法 該算法根據(jù)任務(wù)緊急（或松弛）的程度，來確定任務(wù) 的優(yōu)先級。 例子：一個任務(wù)在 200ms時必須完成，本身 運行時間有 100ms， 因此，必須在 100ms之 前調(diào)度執(zhí)行； 該任務(wù)的緊急程度（松弛程度）為 100ms。 2021/11/12 66 該算法主要用于可搶占調(diào)度中。 松弛度＝必須完成時間－本身運行時間－ 當前時間 實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的 實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列 最前面，調(diào)度程序總是選擇就緒隊列中的隊首任 務(wù)執(zhí)行。 2021/11/12 67 例子： 兩個周期性的實時任務(wù) A和 B， 任務(wù) A要求每 20ms執(zhí)行一次，執(zhí)行時間為 10ms； 任務(wù) B 要求每 50ms執(zhí)行一次，執(zhí)行時間為 25ms。 返回首頁 2021/11/12 68 產(chǎn)生死鎖的原因和必要條件 P103 定義：所謂死鎖（ Deadlock)， 是指多個進程在 運行過程中因爭奪資源而造成的一種僵局，當 進程處于這種僵持狀態(tài)時，若無外力作用，它 們都將無法再向前推進。 2021/11/12 69 本節(jié)主要 內(nèi)容 ： 產(chǎn)生死鎖的原因 產(chǎn)生死鎖的必要條件 處理死鎖的基本方法 本節(jié)學習目標： 熟練掌握 死鎖的定義； 熟練掌握 產(chǎn)生 死鎖的原因和必要條件； 掌握 處理死鎖的基本方法 返回 2021/11/12 70 死鎖的現(xiàn)象 概 述 2021/11/12 71 注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(tǒng)崩潰。 關(guān)于死鎖的一些結(jié)論： 1)參與死鎖的進程最少是兩個 （兩個以上進