【正文】 操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運行；在第二對上下文切換時，將移出分派程序，而把新選進(jìn)程的 CPU現(xiàn)場信息裝入到處理機的各個相應(yīng)寄存器中。 ? 優(yōu)點：公平，能滿足對響應(yīng)時間有著較嚴(yán)格要求的實時任務(wù)的需求。類似地，也可把阻塞狀態(tài)進(jìn)一步分成 內(nèi)存阻塞 和 外存阻塞 兩種狀態(tài)。 常把響應(yīng)時間的長短用來評價 分時系統(tǒng) 的性能，這是選擇分時系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一。在要求較嚴(yán)格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時處理。 在大、中型系統(tǒng)中，不僅要使處理機的利用率高，而且還應(yīng)能有效地利用其它各類資源，如內(nèi)存、外存和 I/O設(shè)備等。在進(jìn)程調(diào)度中采用 FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進(jìn)入該隊列的進(jìn)程，為之分配處理機，使之投入運行。 第三章 處理機調(diào)度與死鎖 圖 34 FCFS和 SJF調(diào)度算法的性能 進(jìn)程名 A B C D E 平 均 到達(dá)時間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務(wù)時間 4 3 5 2 4 完成時間 4 7 12 14 18 周轉(zhuǎn)時間 4 6 10 11 14 9 FC FS (a ) 帶權(quán)周轉(zhuǎn)時間 1 2 2 5. 5 3. 5 2. 8 完成時間 4 9 18 6 13 周轉(zhuǎn)時間 4 8 16 3 9 8 SJF (b) 帶權(quán)周轉(zhuǎn)時間 1 2. 67 3. 1 1. 5 2. 25 2. 1 第三章 處理機調(diào)度與死鎖 2．短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 SJ(P)F（ Shortest job first ） ，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。 ? 用于進(jìn)程調(diào)度時，把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程。 靜態(tài)優(yōu)先權(quán) 特點 ：簡單易行，系統(tǒng)開銷??；不夠精確，可能出現(xiàn)優(yōu)先級低的作業(yè)或進(jìn)程，長期得不到調(diào)度。 (2) 當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。 圖 35示出了時間片分別為 q=1和 q=4時， A、 B、 C、 D、 E五個進(jìn)程的運行情況，而圖 36為 q=1和 q=4時各進(jìn)程的平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。隊列按 FCFS原則排列。 ?低優(yōu)先就緒隊 —— 一個進(jìn)程如果在運行中超過了它的時間量就進(jìn)入低優(yōu)先就緒隊列。 (4) 資源要求。系統(tǒng)首先調(diào)度任務(wù) 1執(zhí)行，在任務(wù) 1執(zhí)行期間，任務(wù) 3又先后到達(dá)。在 t = 0時， A1和 B1同時到達(dá)，由于 A1的截止時間比 B1早 ，故調(diào)度A1執(zhí)行；在 t = 10時， A1完成，又調(diào)度 B1執(zhí)行；在 t = 20時，A2到達(dá) ，由于 A2的截止時間比 B2早， B1被中斷而調(diào)度 A2執(zhí)行；在 t = 30時， A2完成，又重新調(diào)度 B1執(zhí)行；在 t = 40時，A3又到達(dá)，但 B1的截止時間要比 A3早，仍應(yīng)讓 B1繼續(xù)執(zhí)行直到完成 (t = 45)，然后再調(diào)度 A3執(zhí)行；在 t = 55時， A3完成，又調(diào)度 B2執(zhí)行。假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù) A和 B，任務(wù) A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次，執(zhí)行時間為 25 ms。 在 t6?=?55 ms時 ，任務(wù) A尚未進(jìn)入第 4周期 ， 而任務(wù) B已進(jìn)入第 2周期 ， 故再調(diào)度 B2執(zhí)行 。 第三章 處理機調(diào)度與死鎖 死鎖 ? 參與死鎖的進(jìn)程最少是兩個 ? 參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源 ? 參與死鎖的所有進(jìn)程都在等待資源 ? 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集 注 ： 死鎖的嚴(yán)重性： 如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，不僅涉及到死鎖的那些進(jìn)程無法執(zhí)行，而且還妨礙其他進(jìn)程的執(zhí)行，甚至導(dǎo)致系統(tǒng)崩潰。 Pr1： P進(jìn)程申請打印機 A Qr1： Q進(jìn)程申請磁帶機 B Pr2： P進(jìn)程申請磁帶機 B Qr2： Q進(jìn)程申請打印機 A Pr3： P進(jìn)程釋放打印機 A Qr3： Q進(jìn)程釋放磁帶機 B Pr4： P進(jìn)程釋放磁帶機 B Qr4： Q進(jìn)程釋放打印機 A 第三章 處理機調(diào)度與死鎖 圖 313 I/O設(shè)備共享時的死鎖情況 資源 —— 進(jìn)程有向圖 r1 r2 P1 P2 形成環(huán)路引起死鎖 分配 請求 第三章 處理機調(diào)度與死鎖 ?死鎖的起因 ?競爭臨時性資源 臨時性資源 ， 這是指由一個進(jìn)程產(chǎn)生 ， 被另一進(jìn)程使用一短暫時間后便無用的資源 ， 故也稱之為 消耗性資源 ， 它也可能引起死鎖 。 （ 資源獨占 ） (2) 請求和保持條件 ：指進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其它進(jìn)程占有，此時請求進(jìn)程阻塞，但又對自己已獲得的其它資源保持不放。該方法是通過設(shè)置某些 限制條件 ，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預(yù)防發(fā)生死鎖。這種方法并不須事先采取任何限制性措施，也不必檢查系統(tǒng)是否已經(jīng)進(jìn)入不安全區(qū)，而是允許系統(tǒng)在運行過程中發(fā)生死鎖。 2． 摒棄 “ 請求和保持 ” 條件 規(guī)定所有進(jìn)程在開始運行之前，都必須一次性地申請其在整個運行過程所需的全部資源。 第三章 處理機調(diào)度與死鎖 4． 摒棄 “ 環(huán)路等待 ” 條件 系統(tǒng)將所有資源按類型進(jìn)行線性排隊，并賦予不同的序號 。然而這種按規(guī)定次序申請的方法， 必然會限制用戶簡單、自主地編程。進(jìn)程 P1總共要求 10臺磁帶機， P2和 P3分別要求 4臺和 9臺。這樣申請者就可很快完成其計算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生。 這也是一個 n m的矩陣 ， 它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù) 。 第三章 處理機調(diào)度與死鎖 (3) 系統(tǒng) 試探著 把資源分配給進(jìn)程 P i， 并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available[j]:= Available[j]Request i[j] ； Allocation[i,j]:= Allocation[i,j]+Request i[j]； Need[i,j]:= Need[i,j]Request i[j]； (4) 系統(tǒng)執(zhí)行安全性算法 ，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。 第三章 處理機調(diào)度與死鎖 圖 316 T0時刻的資源分配表 Max A l l ocat i on N eed A vai l abl e 資源 情況 進(jìn) 程 A B C A B C A B C A B C P 0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P 1 3 2 2 2 0 0 1 2 2 ( 3 0 2 ) ( 0 2 0 ) P 2 9 0 2 3 0 2 6 0 0 P 3 2 2 2 2 1 1 0 1 1 P 4 4 3 3 0 0 2 4 3 1 第三章 處理機調(diào)度與死鎖 (1) T0時刻的安全性：利用安全性算法對 T0時刻的資源分配情況進(jìn)行分析 (見圖 317所示 )可知，在 T0時刻存在著一個安全序列 {P1， P3， P4， P2， P0}，故系統(tǒng)是安全的。 第三章 處理機調(diào)度與死鎖 圖 319 為 P0分配資源后的有關(guān)資源數(shù)據(jù) A l l ocat i on N eed A vai l abl e 資源 情況 進(jìn) 程 A B C A B C A B C P 0 0 3 0 7 3 2 2 1 0 P 1 3 0 2 0 2 0 P 2 3 0 2 6 0 0 P 3 2 1 1 0 1 1 P 4 0 0 2 4 3 1 第三章 處理機調(diào)度與死鎖 (5) 進(jìn)行安全性檢查：可用資源 Available(2， 1， 0)已不能滿足任何進(jìn)程的需要 ， 故系統(tǒng)進(jìn)入不安全狀態(tài) ， 此時系統(tǒng)不分配資源 。 (3) 當(dāng)進(jìn)程 Pi獲得資源后 ， 可順利執(zhí)行 ， 直至完成 ， 并釋放出分配給它的資源 ， 故應(yīng)執(zhí)行： Work[j]:= Work[j]+Allocation[i,j]； Finish[i]:=true； go to step 2； (4) 如果所有進(jìn)程的 Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。當(dāng) P i發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果 Request i[j]≤Need[i,j] ，便轉(zhuǎn)向步驟 (2)；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 如果Max[i,j]=K， 則表示進(jìn)程 i需要 Rj類資源的最大數(shù)目為 K。 第三章 處理機調(diào)度與死鎖 利用銀行家算法避免死鎖 ?銀行家算法： Dijkstra 于 1968年提出。 第三章 處理機調(diào)度與死鎖 2． 安全狀態(tài)之例 我們通過一個例子來說明安全性。 ?造成對資源的浪費 。這意味著某一進(jìn)程已經(jīng)占有的資源，在運行過程中會被暫時地釋放掉，也可認(rèn)為是被剝奪了，從而摒棄了 “ 不剝奪 ” 條件。死鎖的檢測和解除措施有可能使系統(tǒng)獲得較好的資源利用率和吞吐量，但在實現(xiàn)上難度也最大 。目前在較完善的系統(tǒng)中常用此方法來避免發(fā)生死鎖。 不讓死鎖發(fā)生： 為了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個必要條件之一 第三章 處理機調(diào)度與死鎖 處理死鎖的基本方法 (1) 預(yù)防死鎖 。 死鎖點 第三章 處理機調(diào)度與死鎖 產(chǎn)生死鎖的必要條件 (1) 互斥條件 ：指進(jìn)程對所分配到的資源進(jìn)行排它性使用 ，即在一段時間內(nèi)某資源只由一個進(jìn)程占用 。） 女朋友生氣了，心想：男朋友要是給我打了電話，我就給他回一個。 第三章 處理機調(diào)度與死鎖 Deadlock possible 產(chǎn)生死鎖的原因和必要條件 死鎖的概念 第三章 處理機調(diào)度與死鎖 Deadlock 第三章 處理機調(diào)度與死鎖 ?死鎖（ Deadlock）定義 指多個進(jìn)程因競爭共享資源而造成的一種僵局 ， 若無外力作用 ， 這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn) 。 在 t4?=?40 ms時 ， A3的松弛度為 10 ms(即 60??10??40)， 而 B1的松弛度僅為 5 ms(即 50??5??40)，故又應(yīng)重新調(diào)度 B1執(zhí)行 。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列最前面，調(diào)度程序總是選擇就緒隊列中的隊首任務(wù)執(zhí)行。其中任務(wù) A的到達(dá)時間為 0、 … ；任務(wù) A的最后期限為 60、 … ；任務(wù) B的到達(dá)時間為 0、 50、 100、 … ；任務(wù) B的最后期限為 50、 100、 150、 … (注：單位皆為 ms)。 1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 2) 立即搶占 (Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法 第三章 處理機調(diào)度與死鎖 圖 38 實時進(jìn)程調(diào)度 ( a ) 非搶占式輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程 實時進(jìn)程實時進(jìn)程請求調(diào)度實時進(jìn)程搶占當(dāng)前進(jìn)程并立即執(zhí)行( d ) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進(jìn)程 1 進(jìn)程 2實時進(jìn)程要求調(diào)度進(jìn)程 n 實時進(jìn)程調(diào)度實時進(jìn)程運行( b ) 非搶占式優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程 實時進(jìn)程實時進(jìn)程請求調(diào)度 當(dāng)前進(jìn)程運行完成調(diào)度時間當(dāng)前進(jìn)程實時進(jìn)程請求調(diào)度 時鐘中斷到來時調(diào)度時間( c ) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進(jìn)程?實時進(jìn)程加入隊尾等待下一個時間片 實時進(jìn)程加入隊首 阻塞 第三章 處理機調(diào)度與死鎖 常用的幾種實時調(diào)度算法 1． 最早截止時間優(yōu)先即 EDF(Earliest Deadline First)算法 1) 非搶占式調(diào)度方式用于非周期實時任務(wù) 圖 39示出了將該算法用于非搶占調(diào)度方式之例。 (2) 開始截止時間和完成截止時間。 ??? 長批處理作業(yè)用戶：依次在前 N1個隊列中執(zhí)行，在第 N個隊列中按輪轉(zhuǎn)方式運行。圖 37是多級反饋隊列算法的示意。 ?? 2）時間片的劃分 簡單循環(huán)