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