第03章 處理機調(diào)度及死鎖

1、2022-5-7第三章 處理機調(diào)度與死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖第三章 處理機調(diào)度與死鎖3.1 處理機調(diào)度的層次3.2調(diào)度隊列模型和調(diào)度準則3.3調(diào)度算法3.4實時調(diào)度3.5 產(chǎn)生死鎖的原因和必要條件3.6 預(yù)防死鎖的方法3.7 死鎖的檢測和解除第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖在多道程環(huán)境下，進程數(shù)目往往多于處理機數(shù)目，致使它們爭用處理機。這就要求系統(tǒng)能按某種算法，動態(tài)地把處理機分配給就緒隊列中的一個進程，使之執(zhí)行。分配處理機的任務(wù)是由進程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計的中心問題之一。第三章 處理機調(diào)度與死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 進程調(diào)

2、度要解決的問題WHAT：按什么原則分配CPU 進程調(diào)度算法WHEN：何時分配CPU 進程調(diào)度的時機HOW： 如何分配CPU CPU調(diào)度過程（進程的上下文切換）第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1 處理機調(diào)度的層次處理機是計算機系統(tǒng)中的重要資源處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標有重要影響可把處理機調(diào)度分成三個層次： 高級調(diào)度 中級調(diào)度 低級調(diào)度第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖運行運行就緒就緒阻塞阻塞掛起阻塞掛起阻塞掛起就緒掛起就緒創(chuàng)建創(chuàng)建退出退出進程調(diào)度進程調(diào)度中級調(diào)度中級調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度調(diào)度的層次調(diào)度的層次第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.

3、1.1高級調(diào)度高級調(diào)度高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度） 決定哪些作業(yè)可參與競爭CPU和其他資源，它的調(diào)度對象是作業(yè); 將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCB等，插入就緒隊列; 一般用于批處理系統(tǒng)，分/實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1作業(yè)和作業(yè)步(1)作業(yè)(Job) 作業(yè)由一組統(tǒng)一管理和操作的進程集合構(gòu)成，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書。 作業(yè)可以是完成了編譯、鏈接之后的一個用戶程序，也可以是用各種命令構(gòu)成的一個腳本。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖(2) 作業(yè)步(Job Step)。在作業(yè)運行期間，經(jīng)過若干個

4、相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步。(3) 作業(yè)流。若干個作業(yè)進入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了處理作業(yè)流。1作業(yè)和作業(yè)步第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2作業(yè)控制塊JCB(Job Control Block)每個作業(yè)進入系統(tǒng)時由系統(tǒng)為其建立一個作業(yè)控制塊JCB（Job Control Block)，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息.第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3作業(yè)調(diào)度作業(yè)調(diào)度功能：1.記錄已進入系統(tǒng)的各作業(yè)的情況（JCB，

5、Job Control Block）；2.按一定的調(diào)度算法，從后備作業(yè)中選擇一個或幾個作業(yè)進入系統(tǒng)內(nèi)存；3.為被選中的作業(yè)創(chuàng)建進程，并且為其申請系統(tǒng)資源；4.作業(yè)結(jié)束后作善后處理工作。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3作業(yè)調(diào)度第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3作業(yè)調(diào)度每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定1) 決定接納多少個作業(yè) 作業(yè)調(diào)度每次要接納多少個作業(yè)進入內(nèi)存，取決于多道程序度(Degree of Multiprogramming)，2) 決定接納哪些作業(yè) 應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1

6、.2 低級調(diào)度通常也稱為進程調(diào)度、微觀調(diào)度或短程調(diào)度調(diào)度的對象是進程(或內(nèi)核級線程)。進程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1低級調(diào)度的功能低級調(diào)度的任務(wù)是控制協(xié)調(diào)進程對CPU的競爭。(1) 保存處理機的現(xiàn)場信息。(2) 按某種算法選取進程。(3) 把處理器分配給進程。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2進程調(diào)度中的三個基本機制為了實現(xiàn)進程調(diào)度，應(yīng)具有如下三個基本機制：(1) 排隊器。將系統(tǒng)中所有的就緒進程按照一定的方式排成一個或多個隊列。(2) 分派器。將處理機分配給從就緒隊列中選定的進程(3) 上下文切換機制。當(dāng)對處理機進行切換

7、時，會發(fā)生兩對上下文切換操作。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3進程調(diào)度方式進程調(diào)度可采用下述兩種調(diào)度方式。非搶占方式(Nonpreemptive Mode) 調(diào)度因素：v 正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；v 執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；1) 在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。優(yōu)點優(yōu)點：實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理：實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理OS缺點缺點：不適合不適合實時系統(tǒng)實時系統(tǒng)。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3進程調(diào)度方式2)

8、搶占方式(Preemptive Mode)搶占的原則有：v 優(yōu)先權(quán)原則：優(yōu)先權(quán)高的可以搶占優(yōu)先級低的進程的處理機。v 短作業(yè)（進程）優(yōu)先原則：短作業(yè)（進程）可以搶占長作業(yè)（進程）的處理機。1. 時間片原則：各進程按時間片運行，一個時間片用完時，停止該進程執(zhí)行重新進行調(diào)度。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1.3 中級調(diào)度 中級調(diào)度又稱為交換調(diào)度或中程調(diào)度（Medium-Term Scheduling）。 運行頻率：低中高。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1 高級、中級和低級調(diào)度第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.2 調(diào)度隊列模型和調(diào)度準則3.2.1調(diào)度

9、隊列模型1僅有進程調(diào)度的調(diào)度隊列模型就 緒 隊 列阻 塞 隊 列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1僅有進程調(diào)度的調(diào)度隊列模型每個進程在執(zhí)行時都可能出現(xiàn)以下三種情況：(1) 任務(wù)在給定的時間片內(nèi)已經(jīng)完成，該進程便在釋放處理機后進入完成狀態(tài)；(2) 任務(wù)在本次分得的時間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊列的末尾；(3) 在執(zhí)行期間，進程因為某事件而被阻塞后，被OS放入阻塞隊列。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2具有高級和低級調(diào)度的調(diào)度隊列模型CPU就就 緒緒 隊隊 列列時間片完時間片完進程調(diào)度進程調(diào)度等待事件等待事

10、件1進程完成進程完成后備隊列后備隊列等待事件等待事件2等待事件等待事件n事件事件1出現(xiàn)出現(xiàn)事件事件2出現(xiàn)出現(xiàn)事件事件n出現(xiàn)出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖CPU就就 緒緒 隊隊 列列時間片完時間片完進程調(diào)度進程調(diào)度進程完成進程完成后備隊列后備隊列作業(yè)調(diào)度作業(yè)調(diào)度中級調(diào)度中級調(diào)度就緒、掛起隊列就緒、掛起隊列阻阻 塞、掛塞、掛 起起 隊隊 列列掛起掛起事件出現(xiàn)事件出現(xiàn)等待事件等待事件掛起掛起阻阻 塞塞 隊隊 列列批量作業(yè)批量作業(yè)交互型作業(yè)交互型作業(yè)3同時具有三級調(diào)度的調(diào)度隊列模型事事件件出出現(xiàn)現(xiàn)第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖基本原則： 具有公平性 資源

11、利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時間(越短越好) 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量3.2.2選擇調(diào)度方式和調(diào)度算法的若干準則1面向用戶的準則2面向系統(tǒng)的準則第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1面向用戶的準則(1)周轉(zhuǎn)時間短 所謂周轉(zhuǎn)時間是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。包括：1、作業(yè)在外存后備隊列上等待調(diào)度的時間2、進程在就緒隊列上等待進程調(diào)度的時間3 、進程在CPU上執(zhí)行的時間4 、進程等待I/O操作完成的時間第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1面向用戶的準則作業(yè)的周轉(zhuǎn)時間：作業(yè)的周轉(zhuǎn)時間： ti i = tcici-

12、tsisi ti i:作業(yè)周轉(zhuǎn)時間作業(yè)周轉(zhuǎn)時間 tcici：作業(yè)完成時間：作業(yè)完成時間 tsisi: 作業(yè)提交時間作業(yè)提交時間 其中，其中，n為被測定作業(yè)流中的作業(yè)數(shù)為被測定作業(yè)流中的作業(yè)數(shù)第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1面向用戶的準則 T：衡量不同調(diào)度算法對同一個作業(yè)流的性能：衡量不同調(diào)度算法對同一個作業(yè)流的性能 W：同一調(diào)度算法對不同作業(yè)流的性能衡量：同一調(diào)度算法對不同作業(yè)流的性能衡量 第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1面向用戶的準則(2)響應(yīng)時間快 所謂響應(yīng)時間是指從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。包括：1、從鍵盤輸入的請求信息傳送

13、到處理機的時間2、處理機對請求信息進行處理的時間，3、以及將所形成的響應(yīng)信息送回到終端顯示器的時間。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1面向用戶的準則(3)截至?xí)r間的保證 所謂截止時間是指某任務(wù)必須開始執(zhí)行的最遲時間，或者必須完成的最遲時間。(4)優(yōu)先權(quán)準則 為了便于讓某些緊急的作業(yè)能得到及時的處理，在選擇調(diào)度算法時還應(yīng)該遵循優(yōu)先權(quán)準則。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2面向系統(tǒng)的準則(1)系統(tǒng)吞吐量高 所謂吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的工作量。 (2)處理機利用率好(3)各類資源的平衡使用第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.3調(diào) 度 算 法先進先出(FI

14、FO)算法短作業(yè)(進程)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 時間片輪轉(zhuǎn)法 多級反饋隊列第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.2.1先來先服務(wù)和短作業(yè)(進程)優(yōu)先調(diào)度算法1先來先服務(wù)調(diào)度算法將用戶作業(yè)和就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進行調(diào)度處理，是一種最普遍和最簡單的方法。它優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管要求運行時間的長短。DCBACPU完完成成第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1先來先服務(wù)調(diào)度算法下表列出了JOB1、JOB2、JOB3、JOB4四個作業(yè)分別到達系統(tǒng)的時間、要求服務(wù)的時間、開始執(zhí)行的時間及各自的完成時間，并計算

15、出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖作作業(yè)業(yè)進進入入時時間間估估計計運運行行時時間間（分分鐘鐘）開開始始時時間間結(jié)結(jié)束束時時間間周周轉(zhuǎn)轉(zhuǎn)時時間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T = 112.5作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 4.97545019.9第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖第第3章章

16、 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 A A B B C C D D E E ABCDE平均平均到達時間到達時間02468服務(wù)時間服務(wù)時間36452完成時間完成時間39131820周轉(zhuǎn)時間周轉(zhuǎn)時間37912128.6帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間11.17 2.252.462.5605101520FCFS第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1先來先服務(wù)調(diào)度算法該調(diào)度方式屬于非搶占方式FCFS算法比較有利于長作業(yè)(進程)，而不利于短作業(yè)(進程)。實現(xiàn)簡單，但效率較低。不能保證良好的響應(yīng)時間第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2短作業(yè)(進程)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法(SJF)是指對短

17、作業(yè)優(yōu)先調(diào)度，即從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存。 短進程優(yōu)先調(diào)度算法(SPF)，是指對短進程優(yōu)先調(diào)度，即從就緒隊列中選擇一個或若干個估計運行時間最短的進程，為它們分配處理機，使之投入運行。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2短作業(yè)(進程)優(yōu)先調(diào)度算法作作業(yè)業(yè)進進入入時時間間估估計計運運行行時時間間（分分鐘鐘）開開始始時時間間結(jié)結(jié)束束時時間間周周轉(zhuǎn)轉(zhuǎn)時時間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502

18、010：1010：30402作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T = 95作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 3.2538013第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖圖 FCFS和SJF調(diào)度算法的性能 FCFS和SJF的性能比較 進程名 JOB1 JOB3 JOB4 平 均 到達時間 8:00 8:50 9:00 9:50作業(yè) 情況 調(diào)度 算法 服務(wù)時間 12050 10 20 完成時間 10:00 10:50 11:00 11:20 周轉(zhuǎn)時間 120 120 12090 112.5 FCFS (a) 帶權(quán)周轉(zhuǎn)時間 1 2.4124.5 4.975完成時間 10:00 11

19、:20 10:10 10:30 周轉(zhuǎn)時間 120150 70 40 95 SJF (b) 帶權(quán)周轉(zhuǎn)時間 13723.25 JOB2第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2短作業(yè)(進程)優(yōu)先調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 A A B B E E C C D D ABCDE平均到達時間02468服務(wù)時間36452完成時間39152011周轉(zhuǎn)時間37111437.6帶權(quán)周轉(zhuǎn)時間11.17 2.752.81.51.8405101520 SPN第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2短作業(yè)(進程)優(yōu)先調(diào)度算法該算法對長作業(yè)不利。該算法完全未考慮作業(yè)的緊迫程度，因而不能保

20、證緊迫性作業(yè)(進程)會被及時處理。由于作業(yè)(進程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。有效降低作業(yè)的平均等待時間第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法為照顧緊迫性作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)為照顧緊迫性作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了先處理，引入了最高優(yōu)先權(quán)優(yōu)先（最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算調(diào)度算法。此算法常被用于法。此算法常被用于批處理系統(tǒng)批處理系統(tǒng)中，作為作業(yè)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的調(diào)度算法，也作為多種操作系統(tǒng)中的進程調(diào)度進程調(diào)度算法，還可用于算法，還可用于實時系統(tǒng)實時

21、系統(tǒng)中。它分為兩種：中。它分為兩種：非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2優(yōu)先權(quán)的類型對于高優(yōu)先權(quán)優(yōu)先調(diào)度算法，總是把處理機分配給就緒隊列中具有最高優(yōu)先權(quán)的進程。首先考慮的問題是如何確定進程的優(yōu)先數(shù)。動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)：在創(chuàng)建進程時所賦予的優(yōu)先權(quán)可以：在創(chuàng)建進程時所賦予的優(yōu)先權(quán)可以隨進程的推進或隨其等待時間的增加而改變。隨進程的推進或隨其等待時間的增加而改變。靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進程時確定的，在進程的：在創(chuàng)建進程時確定的，在進程的整個運行期間保持不變。一般利用某一范圍的整個運行期間保持不變。一般利用某

22、一范圍的一個整數(shù)來表示，又稱為優(yōu)先數(shù)。一個整數(shù)來表示，又稱為優(yōu)先數(shù)。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2優(yōu)先權(quán)的類型確定進程優(yōu)先權(quán)的依據(jù)有如下三個方面：(1) 進程類型。(2) 進程對資源的需求。(3) 用戶要求。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3高響應(yīng)比優(yōu)先調(diào)度算法響應(yīng)比： R=（W+T）/T = 1+W/TT：估計執(zhí)行時間W：等待時間W+T：響應(yīng)時間 高響應(yīng)比優(yōu)先是對高響應(yīng)比優(yōu)先是對FCFS和和SJF方式的一種綜合平衡方式的一種綜合平衡 每當(dāng)要進行調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3 高響應(yīng)比優(yōu)先調(diào)

23、度算法由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖算法特點(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。可升到很高，從而也可獲得處理機。 (1) 作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 服務(wù)的時間相同時，作

24、業(yè)的優(yōu)先權(quán)決定于其等服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。現(xiàn)的是先來先服務(wù)。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖作業(yè)作業(yè)進入時間進入時間估計運行估計運行時間時間（分鐘）（分鐘）開始時間開始時間結(jié)束時間結(jié)束時間周轉(zhuǎn)時間周轉(zhuǎn)時間（分鐘）（分鐘）帶權(quán)周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時間時間JOB18：001208：0010：001201JOB28：505010：1011：001302.6JOB39：001010：0010：10707JOB49：502011：0011：20904.5作業(yè)平均周轉(zhuǎn)時間作業(yè)平均

25、周轉(zhuǎn)時間 T = 102.5作業(yè)帶權(quán)平均周轉(zhuǎn)時間作業(yè)帶權(quán)平均周轉(zhuǎn)時間 W = 3.77541015.1第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 A A B B C C E E D D ABCDE平均到達時間02468服務(wù)時間36452完成時間39132015周轉(zhuǎn)時間3791478帶權(quán)周轉(zhuǎn)時間11.17 2.252.83.52.1405101520HRRN第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.3.3基于時間片的輪轉(zhuǎn)調(diào)度算法1時間片輪轉(zhuǎn)法1）基本原理將CPU 的處理時間分成固定大小的時間片，系統(tǒng)將所有就緒進程按先來先服務(wù)的原則排成隊列。每次

26、調(diào)度時，把CPU 分配給隊首進程，令其執(zhí)行一個時間片，時間片用完后，若進程未結(jié)束，則重新排入就緒隊列尾部。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖簡單輪轉(zhuǎn)法的調(diào)度模型第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1時間片輪轉(zhuǎn)法2) 時間片大小的確定時間片長度變化的影響過長退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。過短用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。對響應(yīng)時間的要求： T(響應(yīng)時間)=N(進程數(shù)目)*q(時間片)第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1時間片輪轉(zhuǎn)法下圖示出了時間片分別為q=1和q=4時，A、B、C、D、E五個進程的

27、運行情況。進程名進程名 A A B B C C D D E E 到達時間到達時間 0 0 1 1 2 2 3 3 4 4 作業(yè)情況作業(yè)情況 服務(wù)時間服務(wù)時間 4 4 3 3 4 4 2 2 4 4 第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖時間片時間片q q分別為分別為1 1和和4 4時，五個進程的運行情況時，五個進程的運行情況1時間片輪轉(zhuǎn)法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖進程名進程名 A A B B C C D D E E 平均平均 到達時間到達時間 0 0 1 1 2 2 3 3 4 4 作業(yè)情況作業(yè)情況 時間片時間片 服務(wù)時間服務(wù)時間 4 4 3 3 4 4 2 2 4 4

28、 完成時間完成時間 1515 1212 1616 9 9 1717 周轉(zhuǎn)時間周轉(zhuǎn)時間 1515 1111 1414 6 6 1313 11.811.8 RRRR q q=1=1 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 3.753.75 3.673.67 3.53.5 3 3 3.333.33 3.463.46 完成時間完成時間 4 4 7 7 1111 1313 1717 周轉(zhuǎn)時間周轉(zhuǎn)時間 4 4 6 6 9 9 1010 1313 8.48.4 RRRR q q=4=4 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 1 2 2 2.252.25 5 5 3.333.33 2.52.5 1時間片輪轉(zhuǎn)法第第3章章 處理機調(diào)度

29、與死鎖處理機調(diào)度與死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 A A B B C C D D E E ABCDE平均到達時間02468服務(wù)時間36452完成時間317112019周轉(zhuǎn)時間3157141110帶權(quán)周轉(zhuǎn)時間12.51.752.85.52.7105101520B B D D Round Robin第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2多級反饋隊列調(diào)度算法將就緒隊列分為N級，每個就緒隊列分配給不同的時間片，隊列級別越高，時間越長，級別越小，時間片越小，最后一級采用時間片輪轉(zhuǎn)，其他隊列采用先進先出；系統(tǒng)從第一級調(diào)度，當(dāng)?shù)谝患墳榭諘r，系統(tǒng)轉(zhuǎn)向第二個隊列，.當(dāng)運行進程用完一個時

30、間片，放棄CPU時，進入下一級隊列；等待進程被喚醒時，進入原來的就緒隊列；當(dāng)進程第一次就緒時，進入第一級隊列。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2多級反饋隊列調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖A A ABCDE平均到達時間02468服務(wù)時間36452完成時間417182014周轉(zhuǎn)時間4151414610.6帶權(quán)周轉(zhuǎn)時間 1.332.53.52.832.6305101520B B A A C C B B D D E E C C D D E E B B C C D D FeedBack第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死

31、鎖3多級反饋隊列調(diào)度算法的性能 多級反饋隊列調(diào)度算法具有較好的性能，能較好的滿足各種類型用戶的需要。終端型作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖Windows XP進程調(diào)度模型基于優(yōu)先權(quán)的、可搶占的多級反饋隊列算法調(diào)度線程（而不考慮被調(diào)度線程屬于哪個進程）線程優(yōu)先級：03116個實時優(yōu)先級隊列(1631)15個可變優(yōu)先級隊列(115)1個系統(tǒng)級隊列(0)：零頁線程高低等待線程被喚醒后，優(yōu)先級升高。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖Linux進程調(diào)度模型對于分時進程：分時輪轉(zhuǎn)，但時間片大小不固定。優(yōu)先選擇 進程剩余時間片最大的就緒進程。若所

32、有就緒進程的時間片都已用完(counter=0)，則根據(jù)進程優(yōu)先值priority，對所有進程(包括等待態(tài)進程)重新計算counter值,實在沒有就緒進程可運行，就選擇任務(wù)0。對于實時進程：選優(yōu)先級最高的進程先運行。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 進程調(diào)度的時機當(dāng)一個進程運行完畢，或由于某種錯誤而終止運當(dāng)一個進程運行完畢，或由于某種錯誤而終止運行。行。當(dāng)一個進程在運行中處于等待狀態(tài)當(dāng)一個進程在運行中處于等待狀態(tài)( (等待等待I/O)I/O)。分時系統(tǒng)中時間片到。分時系統(tǒng)中時間片到。當(dāng)有一個優(yōu)先級更高的進程就緒當(dāng)有一個優(yōu)先級更高的進程就緒( (可搶占式可搶占式) )。在進程通信中，

33、執(zhí)行中的進程執(zhí)行了某種原語操在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作作(P(P操作，阻塞原語，喚醒原語操作，阻塞原語，喚醒原語) )。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.4實 時 調(diào) 度3.4.1實現(xiàn)實時調(diào)度的基本條件1提供必要的信息2系統(tǒng)處理能力強3采用搶占式調(diào)度機制4具有快速切換機制第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1提供必要的信息就緒時間就緒時間：該任務(wù)成為就緒狀態(tài)的時間。：該任務(wù)成為就緒狀態(tài)的時間。開始截止時間和完成截止時間開始截止時間和完成截止時間：只需知道一個。：只需知道一個。處理時間處理時間：從開始執(zhí)行到完成所需時間。：從開始執(zhí)行到完成所需時間。資源要求

34、資源要求：任務(wù)執(zhí)行時所需的一組資源。：任務(wù)執(zhí)行時所需的一組資源。優(yōu)先級優(yōu)先級：根據(jù)任務(wù)性質(zhì)賦予不同優(yōu)先級。：根據(jù)任務(wù)性質(zhì)賦予不同優(yōu)先級。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2系統(tǒng)處理能力強假如系統(tǒng)中有M個周期性的硬實時任務(wù)，處理時間為Ci，周期時間表示為Pi 則單機系統(tǒng)中必須滿足條件 多處理機系統(tǒng)中必須滿足條件11miiiPCNPCmiii1第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3采用搶占式調(diào)度機制硬實時任務(wù)： 廣泛采用搶占機制。 小的實時系統(tǒng)： 可采用非搶占調(diào)度機制（簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷）。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖4具有快速切換機制為保

35、證要求較高的硬實時任務(wù)能及時運行，在實時系統(tǒng)中還應(yīng)具有快速切換機制。該機制應(yīng)具有如下兩方面的能力：(1) 對外部中斷的快速響應(yīng)能力。(2) 快速的任務(wù)分派能力。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.4.2實時調(diào)度算法的分類可以按照不同方式對實時調(diào)度算法加以分類：可以按照不同方式對實時調(diào)度算法加以分類：根據(jù)實時任務(wù)性質(zhì)的不同可分為根據(jù)實時任務(wù)性質(zhì)的不同可分為硬實時調(diào)硬實時調(diào)度算法度算法和和軟實時調(diào)度算法軟實時調(diào)度算法；按調(diào)度方式的不同可分為按調(diào)度方式的不同可分為非搶占調(diào)度算法非搶占調(diào)度算法和和搶占調(diào)度算法搶占調(diào)度算法；第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1) 非搶占式輪轉(zhuǎn)調(diào)度算

36、法1非搶占式調(diào)度算法如果在實時系統(tǒng)中存在著要求較為嚴格的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級。該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺計算機控制若干個相同的(或類似的)對象，為每一個被控對象建立一個實時任務(wù)。 2) 非搶占式優(yōu)先調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1非搶占式調(diào)度算法進程1進程2進程n實時進程調(diào)度時間調(diào)度時間實時進程要求調(diào)度實時進程要求調(diào)度調(diào)度實時進程運行調(diào)度實時進程運行a a 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度當(dāng)前進程運行完成當(dāng)前進程運行完成b b 非搶占優(yōu)先權(quán)調(diào)度非搶占優(yōu)先權(quán)調(diào)度調(diào)度時間調(diào)度時間

37、第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2搶占式調(diào)度算法更高優(yōu)先級的實時任務(wù)到達后，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機分配給請求中斷的緊迫任務(wù)。1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法更高優(yōu)先級的實時任務(wù)到達后，并不立即搶占當(dāng)前任務(wù)的處理機，而是等到時鐘中斷到來時。2) 立即搶占的優(yōu)先權(quán)調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖c c 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度實時進程搶占當(dāng)前實時進程搶占當(dāng)前進程，并立即執(zhí)行進程，并立即執(zhí)行b b 立即搶占優(yōu)先權(quán)調(diào)度立即搶占優(yōu)先權(quán)調(diào)度當(dāng)

38、前進程實時進程實時進程要求調(diào)度實時進程要求調(diào)度時鐘中斷到達時時鐘中斷到達時調(diào)度時間調(diào)度時間調(diào)度時間調(diào)度時間2搶占式調(diào)度算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.4.3常用的幾種實時調(diào)度算法最早截止時間優(yōu)先EDF（Earliest Deadline First）算法最低松弛度優(yōu)先LLF（Least Laxity First）算法第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1最早截止時間優(yōu)先即EDF算法 根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級 截止時間越早，優(yōu)先級越高 可以是搶占式或非搶占式第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1) 非搶占式調(diào)度方式用于非周期實時任務(wù) 四個非周期任務(wù)

39、，它們先后到達。四個非周期任務(wù)，它們先后到達。 系統(tǒng)先調(diào)度任務(wù)系統(tǒng)先調(diào)度任務(wù)1 1執(zhí)行，在其執(zhí)行期間，任務(wù)執(zhí)行，在其執(zhí)行期間，任務(wù)2 2、3 3又先后到達。又先后到達。 由于任務(wù)由于任務(wù)3 3的開始截止時間早于任務(wù)的開始截止時間早于任務(wù)2 2，故系統(tǒng)在任務(wù)，故系統(tǒng)在任務(wù)1 1后將調(diào)度任后將調(diào)度任務(wù)務(wù)3 3執(zhí)行。執(zhí)行。 在此期間又到達作業(yè)在此期間又到達作業(yè)4 4，其開始截止時間仍是早于任務(wù)，其開始截止時間仍是早于任務(wù)2 2的，故在的，故在任務(wù)任務(wù)3 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4 4執(zhí)行，最后才調(diào)度任務(wù)執(zhí)行，最后才調(diào)度任務(wù)2 2執(zhí)行。執(zhí)行。第第3章章 處理機調(diào)度與死鎖處理機

40、調(diào)度與死鎖2) 搶占式調(diào)度方式用于周期實時任務(wù) 有兩個周期性任務(wù)。有兩個周期性任務(wù)。 任務(wù)任務(wù)A A的周期時間為的周期時間為20 ms20 ms，每個周期的處理時間為，每個周期的處理時間為10 ms10 ms。 任務(wù)任務(wù)B B的周期時間為的周期時間為50 ms50 ms，每個周期的處理時間為，每個周期的處理時間為25 ms25 ms。圖中。圖中的第一行示出了兩個任務(wù)的到達時間、最后期限和執(zhí)行時間圖。的第一行示出了兩個任務(wù)的到達時間、最后期限和執(zhí)行時間圖。在在t = 0 t = 0 時，時， A1 A1和和B1B1同時到達，由于同時到達，由于A1A1的截止時間比的截止時間比B1B1早，故調(diào)度早，

41、故調(diào)度A1A1執(zhí)行；執(zhí)行；在在t = 10 t = 10 時，時， A1 A1完成，又調(diào)度完成，又調(diào)度B1B1執(zhí)行；執(zhí)行；在在t = 20 t = 20 時，時， A2 A2到達，由于到達，由于A2A2的截止時間比的截止時間比B2B2早，早，B1B1被中斷而調(diào)度被中斷而調(diào)度A2A2執(zhí)行；執(zhí)行；在在t = 30 t = 30 時，時， A2 A2完成，又重新調(diào)度完成，又重新調(diào)度B1B1執(zhí)行；執(zhí)行；在在t = 40 t = 40 時，時， A3 A3又到達，但又到達，但B1B1的截止時間要比的截止時間要比A A3 3早，仍應(yīng)讓早，仍應(yīng)讓B1B1繼續(xù)執(zhí)行直到完成繼續(xù)執(zhí)行直到完成(t = (t = 4

42、5)45)，然后再調(diào)度，然后再調(diào)度A3A3執(zhí)行；執(zhí)行；在在t = 55 t = 55 時，時， A3 A3完成，又調(diào)度完成，又調(diào)度B2B2執(zhí)行。執(zhí)行。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2最低松弛度優(yōu)先即LLF算法例如，一個任務(wù)在200 ms時必須完成，而它本身所需的運行時間就有100 ms，因此，調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100 ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列 。v松弛度：指任務(wù)緊急程度松弛度：指任務(wù)緊急程度第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2最低松弛度優(yōu)先即LLF算法在一個實時系統(tǒng)中，有兩個周

43、期性實時任務(wù)在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A A和和B B。任務(wù)。任務(wù)A A要要求每求每 20 ms20 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 10 ms10 ms；任務(wù)；任務(wù)B B只要求每只要求每5 50 ms0 ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為 25 ms25 ms。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖v 在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運行又需 10 ms，可算出A1的松弛度為10ms；vB1必須在50ms時完成， 而它本身運行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。v在t2=10 ms時，

44、A2的松弛度可按下式算出：vA2的松弛度=必須完成時間-其本身的運行時間-當(dāng)前時間 =40 ms-10 ms-10 ms=20 ms 2.最低松弛度優(yōu)先(LLF)算法 第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2.最低松弛度優(yōu)先(LLF)算法v類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B2運行。t3=30 ms時，A2的松弛度已減為0，B1的松弛度為15 ms，于是調(diào)度程序應(yīng)搶占B1的處理機而調(diào)度A2運行.第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.5產(chǎn)生死鎖的原因和必要條件死鎖問題在1965年由Dijkstra（迪科斯徹 ） 發(fā)現(xiàn)，并隨著計算機技術(shù)的發(fā)展，逐漸成為人們關(guān)心的問

45、題。什么是死鎖？死鎖是怎么產(chǎn)生的？用什么方法來解決死鎖？這些正是今天我們要討論的問題。 第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.5產(chǎn)生死鎖的原因和必要條件早期的操作系統(tǒng)對申請某種資源的進程，若該資源尚未分配時，立即將該資源分配給這個進程。后來發(fā)現(xiàn)，對資源不加限制地分配可能導(dǎo)致進程間由于競爭資源而相互制約以至于無法繼續(xù)運行的局面，人們把這種局面稱為死鎖 (deadlock)。死鎖：指多個進程因競爭共享資源而造成的一種死鎖：指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再僵局，若無外力作用，這些進程都將永遠不能再向前推進。向前推進。第第3章章 處理機調(diào)度與死鎖

46、處理機調(diào)度與死鎖可能會發(fā)生死鎖已經(jīng)發(fā)生死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖關(guān)于死鎖的一些結(jié)論參與死鎖的進程最少是兩個 參與死鎖的進程至少有兩個已經(jīng)占有資源參與死鎖的所有進程都在等待資源參與死鎖的進程是當(dāng)前系統(tǒng)中所有進程的子集如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.5.1 產(chǎn)生死鎖的原因1.競爭系統(tǒng)資源2.進程的推進順序不當(dāng) 可剝奪和非剝奪性資源可剝奪和非剝奪性資源永久性資源和臨時性資源永久性資源和臨時性資源第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1競爭資源引起進程死鎖1) 可剝奪和非剝奪性資源可把系統(tǒng)中的資源分成兩類一

47、類是可剝奪性資源，是指某進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)剝奪。另一類是不可剝奪性資源，當(dāng)系統(tǒng)把這類資源分配給某進程后，再不能強行收回。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1競爭資源引起進程死鎖2) 競爭非剝奪性資源系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足諸進程運行的需要，會使進程在運行過程中，因爭奪這些資源而陷入僵局。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1競爭資源引起進程死鎖 若系統(tǒng)中只有一臺打印機R1和一臺掃描儀R2，可供進程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖永久性資源和臨時性資源永久性資源：可

48、以被多個進程多次使用（可再用資源）可搶占資源不可搶占資源臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）“申請-分配-使用-釋放”模式第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3) 競爭臨時性資源S1、S2和S3是臨時性資源。進程P1產(chǎn)生消息S1，又要求從P3接收消息S3；進程P3產(chǎn)生消息S3，又要求從進程P2接收其所產(chǎn)生的消息S2；進程P2產(chǎn)生消息S2，又需要接收進程P1所產(chǎn)生的消息S1。1競爭資源引起進程死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 進程之間通信時的死鎖 S2P1S3P3S1P2第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1競爭資源引起進

49、程死鎖P1： Request(S3)； Release(S1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； P1： Release(S1)； Request(S3)； P2： Release(S2)； Request(S1)； P3： Release(S3)； Request(S2)； 如果消息通信按下述順序進行：則不可能發(fā)生死鎖，但若改成下述的運行順序：則可能發(fā)生死鎖。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖申請掃描儀申請打印機(阻塞)T1掃描儀打印機T2申請打印機申請掃描儀(阻塞)2進程推進順序不當(dāng)引起死鎖第

50、第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2進程推進順序不當(dāng)引起死鎖1) 進程推進順序合法在進程P1和P2并發(fā)執(zhí)行時，如果按下述順序推進：P1：Request(R1)；Request(R2)；P1：Release(R1)； Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)；No problem！第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2進程推進順序不當(dāng)引起死鎖213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R

51、2)4第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2進程推進順序不當(dāng)引起死鎖在進程P1和P2并發(fā)執(zhí)行時，按照上圖曲線所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。若按曲線的順序推進時，進入不安全區(qū) D內(nèi)，兩進程再推進會產(chǎn)生死鎖。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.5.2產(chǎn)生死鎖的必要條件雖然進程在運行過程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。死鎖的發(fā)生必須具備下列四個必要條件?；コ鈼l件（資源獨占）請求和保持條件（部分分配，占有申請）不剝奪條件（不可強占）環(huán)路等待條件。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.5.3處理死鎖的基本方法預(yù)防死鎖避免死鎖

52、檢測死鎖解除死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.6預(yù)防死鎖的方法在系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一。一、互斥條件是資源固有屬性，不能避免。一、互斥條件是資源固有屬性，不能避免。二、摒棄請求和保持條件二、摒棄請求和保持條件三、摒棄三、摒棄“不剝奪不剝奪”條件條件四、摒棄四、摒棄“環(huán)路環(huán)路”條件條件第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.6.1預(yù)防死鎖摒棄請求和保持條件 資源一次性分配-破壞請求和保持條件。摒棄“不剝奪”條件 可剝奪資源-即當(dāng)某進程新的資源未滿足時，釋放已占有的資源，破壞不可剝奪條件。摒棄“環(huán)路”條件 資

53、源有序分配法-系統(tǒng)給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反，破壞環(huán)路等待條件。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖在預(yù)防死鎖的幾種方法中，都施加了較強的限制條件；在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)啊，便可避免發(fā)生死鎖。3.6.2系統(tǒng)安全狀態(tài)第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖1安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進程順序來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。安全序列 一個進程序列P1，Pn是安全的，如果對于每一個

54、進程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進程Pj (j i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。 安全狀態(tài)一定是沒有死鎖發(fā)生的不安全狀態(tài)：若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2. 安全狀態(tài)之例進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223假定有三個進程假定有三個進程P1P1、 P2P2和和P3P3，共有，共有1212臺臺磁帶機。磁帶機。進程進程P1P1總共要求總共要求1010臺臺磁帶機，磁帶機，P2P2和和P3P3分別要求分別要求4 4臺臺和和9 9臺臺。假設(shè)在假設(shè)在T0T

55、0時刻，進程時刻，進程P1P1、P2P2和和P3P3已分別獲得已分別獲得5 5臺臺、2 2臺臺和和2 2臺臺磁帶機，尚有磁帶機，尚有3 3臺臺空閑未分配?？臻e未分配。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖2. 安全狀態(tài)之例經(jīng)分析發(fā)現(xiàn)，在T0時刻系統(tǒng)是安全的，因為此時存在一個安全序列，即只要系統(tǒng)按此進程序列分配資源，就能使每個進程都順利完成?？沈炞C。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖如果不按照安全序分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。 因為，此時無法再找到一個安

56、全序列。 3.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換進 程 最 大 需 求 已 分 配 可 用 P1P2P310495232第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)不一定導(dǎo)致死鎖第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.6.3利用銀行家算法避免死鎖由于在避免死鎖的策略中，允許進程動態(tài)地申請資源。因而，系統(tǒng)在進行資源分配之前預(yù)先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，進程等待。其中最具有代表性的避免死鎖算法是銀行家算法。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.6.3 利用銀行家算

57、法避免死鎖數(shù)據(jù)結(jié)構(gòu) Available：可利用資源向量 Max：最大需求矩陣 Allocation：分配矩陣 Need：需求矩陣銀行家算法安全性算法Available：含有m個元素的數(shù)組，每一個元素代表一類可利用的資源數(shù)目。其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。Max：nm的矩陣，定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數(shù)目為K。Allocation：nm的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果Allocationi,j=K，則表示進程i當(dāng)前已分得R

58、j類資源的數(shù)目為K。Need：nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Needi,j=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)；Request：nm的矩陣，用以表示每一個進程當(dāng)前提出的對某類資源的請求。Available：可利用資源向量Max：最大需求矩陣Allocation：分配矩陣Need：需求矩陣Request：請求矩陣Needi,j=Maxi,j-Allocationi,j第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.6.3 利用銀行家算法避免死鎖數(shù)據(jù)結(jié)構(gòu)銀行家算法 當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：安全性算法步驟一：如果Requestij Nee

59、di,j，便轉(zhuǎn)向步驟二；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。步驟二：如果Requestij Availablej，便轉(zhuǎn)向步驟三；否則，表示尚無足夠資源，Pi須等待。 步驟三：系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej := Availablej - Requestij Allocationi,j := Allocationi,j + RequestijNeedi,j := Needi,j - Requestij 步驟四：系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，完成本次分配；否則

60、將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。Requesti：是進程Pi的請求向量如果Requestij=K，表示進程i需要K個Rj類型的資源。第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖Pi請求資源請求資源Requestij Needj請求超量，錯返請求超量，錯返Requestij Available不滿足，等待不滿足，等待Available:=Available-RequestijAllocationj:=Allocationj+RequestijNeedj:=Needj-Requestj安全安全確認，確認，pi繼續(xù)繼續(xù)Available:=Available+Requestij