操作系統(tǒng)第3章

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

2、什么原則分配CPU 進(jìn)程調(diào)度算法WHEN：何時分配CPU 進(jìn)程調(diào)度的時機(jī)HOW： 如何分配CPU CPU調(diào)度過程（進(jìn)程的上下文切換）第三章處理機(jī)調(diào)度與死鎖 1. 高級、中級和低級調(diào)度l處理機(jī)是計算機(jī)系統(tǒng)中的重要資源l處理機(jī)調(diào)度算法對整個計算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響l可把處理機(jī)調(diào)度分成三個層次： 高級調(diào)度高級調(diào)度 中級調(diào)度中級調(diào)度 低級調(diào)度低級調(diào)度第三章處理機(jī)調(diào)度與死鎖 高級調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度 高級調(diào)度的時間尺度通常是分鐘、小時或天 中級調(diào)度涉及進(jìn)程在內(nèi)外存間的交換，從存儲器資源管理的角度來看，把進(jìn)程的部分或全部換出到外存上，可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進(jìn)程所需

3、部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問 低級調(diào)度也稱微觀調(diào)度，從處理機(jī)資源分配的角度來看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài)，低級調(diào)度的時間尺度通常是毫秒級的。由于低級調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時做到高效第三章處理機(jī)調(diào)度與死鎖 2.進(jìn)程調(diào)度的任務(wù) 進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對CPU的競爭,即按一定的調(diào)度算法從就緒隊(duì)列中選中一個進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程第三章處理機(jī)調(diào)度與死鎖 3.確定算法的原則 具有公平性 資源利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量第三章處理機(jī)調(diào)度與死鎖 4

4、.進(jìn)程調(diào)度方式 非剝奪方式：分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時，才把處理機(jī)分配給另一個進(jìn)程。 剝奪方式：當(dāng)一個進(jìn)程正在運(yùn)行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。剝奪原則有：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時間片原則。第三章處理機(jī)調(diào)度與死鎖 5.進(jìn)程調(diào)度性能衡量的指標(biāo) 周轉(zhuǎn)時間 響應(yīng)時間 CPU-I/O執(zhí)行期第三章處理機(jī)調(diào)度與死鎖 6.進(jìn)程調(diào)度模型 1) 1)只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型第三章處理機(jī)調(diào)度與死鎖 2)具有高低級調(diào)度的調(diào)度隊(duì)列模型圖 3-

5、2 具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型第三章處理機(jī)調(diào)度與死鎖 3)具有三級調(diào)度的調(diào)度隊(duì)列模型圖 3-3 具有三級調(diào)度時的調(diào)度隊(duì)列模型第三章處理機(jī)調(diào)度與死鎖 7.選擇進(jìn)程調(diào)度方式的準(zhǔn)則 面向用戶的準(zhǔn)則：周轉(zhuǎn)時間短；響應(yīng)時間快；截止時間的保證；優(yōu)先權(quán)準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡利用第三章處理機(jī)調(diào)度與死鎖 3.2 3.2 進(jìn)程調(diào)度算法 先進(jìn)先出(FIFO)算法 最短CPU運(yùn)行期優(yōu)先調(diào)度算法 最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 輪轉(zhuǎn)法 多級反饋隊(duì)列 第三章處理機(jī)調(diào)度與死鎖 1.先進(jìn)先出(FIFO)算法 該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個進(jìn)程一旦分得處理機(jī)，便執(zhí)

6、行下去，直到該進(jìn)程完成或阻塞時，才釋放處理機(jī)。 優(yōu)點(diǎn):實(shí)現(xiàn)簡單. 缺點(diǎn):沒考慮進(jìn)程的優(yōu)先級第三章處理機(jī)調(diào)度與死鎖 2.最短CPU運(yùn)行期優(yōu)先調(diào)度算法 該算法從就緒隊(duì)列中選出“下一個CPU執(zhí)行期”最短的進(jìn)程，為之分配處理機(jī)。 該算法雖可獲得較好的調(diào)度性能，但難以準(zhǔn)確地知道下一個CPU執(zhí)行期，而只能根據(jù)每一個進(jìn)行的執(zhí)行歷史來預(yù)測。第三章處理機(jī)調(diào)度與死鎖 圖 3-4 FCFS和SJF調(diào)度算法的性能 3. FCFS和SJF的性能比較第三章處理機(jī)調(diào)度與死鎖 4.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 該算法總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。常用以下兩種方法來確定進(jìn)程的優(yōu)先權(quán)(優(yōu)先級根據(jù)優(yōu)先數(shù)來決定) 靜態(tài)

7、優(yōu)先數(shù)法：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，在整個運(yùn)行期間不再改變。依據(jù)有：進(jìn)程類型、進(jìn)程對資源的要求、用戶要求的優(yōu)先權(quán)。 動態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時創(chuàng)立一個優(yōu)先數(shù)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動態(tài)變化。如等待時間長優(yōu)先數(shù)可改變第三章處理機(jī)調(diào)度與死鎖 5.高響應(yīng)比優(yōu)先調(diào)度算法 優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 第三章處理機(jī)調(diào)度與死鎖 6. 輪轉(zhuǎn)法 把CPU劃分成若干時間片,并且按順序賦給就緒隊(duì)列中的每一個進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時間片用完時，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程

8、排在就緒隊(duì)列末尾。同時系統(tǒng)選擇另一個進(jìn)程運(yùn)行 簡單輪轉(zhuǎn)法：系統(tǒng)將所有就緒進(jìn)程按FIFO規(guī)則排隊(duì)，按一定的時間間隔把處理機(jī)分配給隊(duì)列中的進(jìn)程。這樣，就緒隊(duì)列中所有進(jìn)程均可獲得一個時間片的處理機(jī)而運(yùn)行。 多級隊(duì)列方法：將系統(tǒng)中所有進(jìn)程分成若干類，每類為一級。 第三章處理機(jī)調(diào)度與死鎖 7.分時系統(tǒng)中常用時間片輪轉(zhuǎn)法時間片選擇問題時間片選擇問題： 固定時間片 可變時間片與時間片大小有關(guān)的因素：與時間片大小有關(guān)的因素： 系統(tǒng)響應(yīng)時間 就緒進(jìn)程個數(shù) CPU能力 第三章處理機(jī)調(diào)度與死鎖 1)簡單輪轉(zhuǎn)法的調(diào)度模型第三章處理機(jī)調(diào)度與死鎖 2)多隊(duì)列反饋調(diào)度算法 將就緒隊(duì)列分為N級，每個就緒隊(duì)列分配給不同的時間片

9、，隊(duì)列級別越高，時間越長，級別越小，時間片越小，最后一級采用時間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出； 系統(tǒng)從第一級調(diào)度，當(dāng)?shù)谝患墳榭諘r，系統(tǒng)轉(zhuǎn)向第二個隊(duì)列，.當(dāng)運(yùn)行進(jìn)程用完一個時間片，放棄CPU時，進(jìn)入下一級隊(duì)列；等待進(jìn)程被喚醒時，進(jìn)入原來的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時，進(jìn)入第一級隊(duì)列 第三章處理機(jī)調(diào)度與死鎖 * 首先系統(tǒng)中設(shè)置多個就緒隊(duì)列* 每個就緒隊(duì)列分配給不同時間片，優(yōu)先級高的為第一級隊(duì)列，時間片最小，隨著隊(duì)列級別的降低，時間片加大* 各個隊(duì)列按照先進(jìn)先出調(diào)度算法* 一個新進(jìn)程就緒后進(jìn)入第一級隊(duì)列* 進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列* 當(dāng)有一個

10、優(yōu)先級更高的進(jìn)程就緒時，可以搶占CPU，被搶占進(jìn)程回到原來一級就緒隊(duì)列末尾* 當(dāng)?shù)谝患夑?duì)列空時，就去調(diào)度第二級隊(duì)列，如此類推* 當(dāng)時間片到后，進(jìn)程放棄CPU，回到下一級隊(duì)列第三章處理機(jī)調(diào)度與死鎖 3)多隊(duì)列反饋調(diào)度算法第三章處理機(jī)調(diào)度與死鎖 8.進(jìn)程調(diào)度的時機(jī)當(dāng)一個進(jìn)程運(yùn)行完畢，或由于某種錯誤而終止運(yùn)行當(dāng)一個進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）分時系統(tǒng)中時間片到當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒（可搶占式） 例如：新創(chuàng)建一個進(jìn)程，一個等待進(jìn)程變成就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作（P操作，阻塞原語，喚醒原語）第三章處理機(jī)調(diào)度與死鎖 何時切換進(jìn)程 只要OS取得對CPU的控制，進(jìn)程切換就

11、可能發(fā)生，如:超級用戶調(diào)用 來自程序的顯式請求來自程序的顯式請求 ( (如：打開文件如：打開文件) )，該，該進(jìn)程通常會被阻塞進(jìn)程通常會被阻塞陷阱 最末一條指令導(dǎo)致出錯，會引起進(jìn)程移至退最末一條指令導(dǎo)致出錯，會引起進(jìn)程移至退出狀態(tài)出狀態(tài)中斷 外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至至IHIH（中斷處理程序）（中斷處理程序）第三章處理機(jī)調(diào)度與死鎖 9.引起進(jìn)程調(diào)度的原因 正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行； 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作如P操作、阻塞、掛起原語等； 在可剝奪式調(diào)度中，有比

12、當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列； 在時間片輪轉(zhuǎn)法中，時間片完。 通常系統(tǒng)是按先來先服務(wù)或優(yōu)先權(quán)形式來組織調(diào)度隊(duì)列。 第三章處理機(jī)調(diào)度與死鎖 10.進(jìn)程調(diào)度算法 其中，RQ為就緒隊(duì)列指針，EP為運(yùn)行隊(duì)列指針。第三章處理機(jī)調(diào)度與死鎖 3.3 3.3 實(shí)實(shí) 時時 調(diào)調(diào) 度度 1.實(shí)現(xiàn)實(shí)時調(diào)度的基本條件實(shí)現(xiàn)實(shí)時調(diào)度的基本條件 提供必要的信息(就緒時間、截止時間、處理時間、資源優(yōu)先級) 系統(tǒng)處理能力強(qiáng) 采用搶占式調(diào)度機(jī)制 具有快速切換機(jī)制第三章處理機(jī)調(diào)度與死鎖 2.實(shí)時調(diào)度算法的分類 1)非搶占式調(diào)度算法非搶占式調(diào)度算法 : 非搶占式輪轉(zhuǎn)調(diào)度算法 非搶占式優(yōu)先調(diào)度算法2)2)搶占式調(diào)度算法搶占式調(diào)

13、度算法: : 基于時鐘中斷的搶占優(yōu)先調(diào)度算法 立即搶占優(yōu)先權(quán)調(diào)度算法。 第三章處理機(jī)調(diào)度與死鎖 圖 3-5 實(shí)時進(jìn)程調(diào)度 第三章處理機(jī)調(diào)度與死鎖 3.常用的幾種實(shí)時調(diào)度算法 1）最早截止時間優(yōu)先即）最早截止時間優(yōu)先即EDF(Earliest Deadline First)算法算法 圖 3-6 EDF算法用于非搶占調(diào)度方式 第三章處理機(jī)調(diào)度與死鎖 2）最低松弛度優(yōu)先(LLF)算法 該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。該算法主要用于可搶占調(diào)度方式中。 假如在一個實(shí)時系統(tǒng)中，有兩個周期性實(shí)時任務(wù)A和B，任務(wù)A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務(wù)B只要求每50

14、 ms執(zhí)行一次，執(zhí)行時間為 25 ms。 圖 3-7 A和B任務(wù)每次必須完成的時間第三章處理機(jī)調(diào)度與死鎖 在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運(yùn)行又需 10 ms，可算出A1的松弛度為10ms；B1必須在50ms時完成， 而它本身運(yùn)行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10 ms時，A2的松弛度可按下式算出： A2的松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間 =40 ms-10 ms-10 ms=20 ms 類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B2運(yùn)行。t3=30 ms時，A2的松弛度已減為0，B1的松

15、弛度為15 ms，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行.圖 3-8 利用ELLF算法進(jìn)行調(diào)度的情況第三章處理機(jī)調(diào)度與死鎖 3.4 多處理機(jī)系統(tǒng)中的調(diào)度 1.1.多處理器系統(tǒng)的類型多處理器系統(tǒng)的類型 (1) 緊密耦合(Tightly Coupted)MPS。 (2) 松散耦合(Loosely Coupled)MPS。2.2.對稱對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)3.進(jìn)程分配方式 (1)對稱多處理器系統(tǒng)中的進(jìn)程分配方式 靜態(tài)分配(Static Assigenment)方式 動態(tài)分配(Dynamic Assgement)方式 (2)非對稱MPS中的進(jìn)程分配方式4. 進(jìn)程(線程)調(diào)度方式 (

16、1）自調(diào)度(Self-Scheduling)方式 （2）成組調(diào)度(Gang Scheduling)方式第三章處理機(jī)調(diào)度與死鎖 第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件第三章處理機(jī)調(diào)度與死鎖 3.5.1 死鎖的概念死鎖的概念1.1.死鎖例子死鎖例子: : 一個由于一個由于申請不同類型資源申請不同類型資源而產(chǎn)生死鎖而產(chǎn)生死鎖的例子的例子 設(shè)系統(tǒng)有一臺打印機(jī)設(shè)系統(tǒng)有一臺打印機(jī)(R1)(R1)一臺掃描儀一臺掃描儀(R2)(R2)，兩進(jìn)程共享這兩臺設(shè)備。，兩進(jìn)程共享這兩臺設(shè)備。 用信號量用信號量S1S1表示表示R1R1是否可用，用信號量是否

17、可用，用信號量S2S2表示表示R2R2是否可用，是否可用， S1S1、 S2S2初值為初值為1 1。 第三章處理機(jī)調(diào)度與死鎖 死鎖例子死鎖例子 這兩個進(jìn)程在并發(fā)執(zhí)行過程中，可這兩個進(jìn)程在并發(fā)執(zhí)行過程中，可能會發(fā)生死鎖。大家可以思考一下，如能會發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會發(fā)生死鎖。何修改，進(jìn)程才不會發(fā)生死鎖。第三章處理機(jī)調(diào)度與死鎖 2.死鎖概念 指多個進(jìn)程因競爭共享資源而造成的指多個進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。都將永遠(yuǎn)不能再向前推進(jìn)。 即：一組進(jìn)程中，每個進(jìn)程都無限等即：一組進(jìn)程中，每個進(jìn)程

18、都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。為死鎖進(jìn)程。第三章處理機(jī)調(diào)度與死鎖 3.關(guān)于死鎖的一些結(jié)論關(guān)于死鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是兩個 參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。第三章處理機(jī)調(diào)度與死鎖 4.永久性資源和臨時性資源永久性資源：可以被多個進(jìn)程多次永久性資源：可以被多個進(jìn)程多次使用（可

19、再用資源）使用（可再用資源） 可搶占資源可搶占資源 不可搶占資源不可搶占資源臨時性資源：只可使用一次的資源；臨時性資源：只可使用一次的資源；如信號量如信號量, ,中斷信號，同步信號中斷信號，同步信號等（可消耗性資源）等（可消耗性資源）“申請申請-分配分配-使用使用-釋放釋放”模式模式第三章處理機(jī)調(diào)度與死鎖 3.5.2 產(chǎn)生死鎖的原因1.1.競爭系統(tǒng)資源競爭系統(tǒng)資源2.2.進(jìn)程的推進(jìn)順序不當(dāng)進(jìn)程的推進(jìn)順序不當(dāng) 第三章處理機(jī)調(diào)度與死鎖 1. 1. 競爭系統(tǒng)資源 若系統(tǒng)中只有一臺打印機(jī)若系統(tǒng)中只有一臺打印機(jī)R1R1和一臺和一臺讀卡機(jī)讀卡機(jī)R2R2，可供進(jìn)程，可供進(jìn)程P1P1和和P2P2共享。若共享。

20、若形形成環(huán)路成環(huán)路，這樣會產(chǎn)生死鎖，這樣會產(chǎn)生死鎖。第三章處理機(jī)調(diào)度與死鎖 2.2.進(jìn)程的推進(jìn)順序不當(dāng) 在進(jìn)程在進(jìn)程P1P1和和P2P2并發(fā)執(zhí)行時，按照左圖曲并發(fā)執(zhí)行時，按照左圖曲線線所示順序推進(jìn)時，兩進(jìn)程會順?biāo)卷樞蛲七M(jìn)時，兩進(jìn)程會順利完成，我們稱這種推進(jìn)順序是合法的。利完成，我們稱這種推進(jìn)順序是合法的。若按曲線若按曲線的順序推進(jìn)時，進(jìn)入不安全的順序推進(jìn)時，進(jìn)入不安全區(qū)區(qū)D D內(nèi)，兩進(jìn)程再推進(jìn)會產(chǎn)生死鎖。內(nèi)，兩進(jìn)程再推進(jìn)會產(chǎn)生死鎖。第三章處理機(jī)調(diào)度與死鎖 3.5.3 產(chǎn)生死鎖的必要條件 互斥條件互斥條件（資源獨(dú)占）（資源獨(dú)占） 請求和保持條件請求和保持條件（部分分配，（部分分配，占有申請）占

21、有申請） 不剝奪條件（不剝奪條件（不可強(qiáng)占）不可強(qiáng)占） 環(huán)路等待條件。環(huán)路等待條件。第三章處理機(jī)調(diào)度與死鎖 解決死鎖的基本辦法 預(yù)防死鎖預(yù)防死鎖 避免死鎖避免死鎖 檢測死鎖檢測死鎖 解除死鎖解除死鎖第三章處理機(jī)調(diào)度與死鎖 3.6 預(yù)防死鎖的方法和避免死鎖 1.預(yù)防死鎖的方法 在系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一。 1)1)資源一次性分配；資源一次性分配；(破壞請求和保持條件) 2)2)可剝奪資源；可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時，釋放已占有的資源(破壞不可剝奪條件) 3)3)資源有序分配法資源有序分配法；做法：系統(tǒng)給每類資源賦予一個編號

22、，每一個進(jìn)程按編號遞增的順序請求資源，釋放則相反(破壞環(huán)路等待條件)第三章處理機(jī)調(diào)度與死鎖 2. 死鎖避免 死鎖避免定義死鎖避免定義:在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進(jìn)行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。 預(yù)防死鎖的幾種策略，會嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來避免死鎖。 由于在避免死鎖的策略中，允許進(jìn)程動態(tài)地申請資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算

23、法是銀行家算法。第三章處理機(jī)調(diào)度與死鎖 3. 安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)指系統(tǒng)能按某種進(jìn)程安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來為每個進(jìn)程分配其所需資順序來為每個進(jìn)程分配其所需資源，直至最大需求，使每個進(jìn)程源，直至最大需求，使每個進(jìn)程都可順序完成。若系統(tǒng)不存在這都可順序完成。若系統(tǒng)不存在這樣一個序列，則稱系統(tǒng)處于不安樣一個序列，則稱系統(tǒng)處于不安全狀態(tài)。全狀態(tài)。 第三章處理機(jī)調(diào)度與死鎖 1)安全序列 一個進(jìn)程序列一個進(jìn)程序列PP1 1，P Pn n 是安是安全的，如果對于每一個進(jìn)程全的，如果對于每一個進(jìn)程P Pi i(1(1i in n），它以后尚需要的資源），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩

24、余資源量與所有量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程進(jìn)程P Pj j (j i ) (j i )當(dāng)前占有資源量之和，當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。系統(tǒng)處于安全狀態(tài)。 ( (安全狀態(tài)一定是沒有死鎖發(fā)生的安全狀態(tài)一定是沒有死鎖發(fā)生的) )第三章處理機(jī)調(diào)度與死鎖 2) 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程P1、 P2和P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示： 進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2

25、P310495223第三章處理機(jī)調(diào)度與死鎖 3) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機(jī)，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，此時也無法再找到一個安全序列， 例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 第三章處理機(jī)調(diào)度與死鎖 安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài):不存在一個安全序列

26、，不安全狀態(tài)一定導(dǎo)致死鎖第三章處理機(jī)調(diào)度與死鎖 4.利用銀行家算法避免死鎖 1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。 第三章處理機(jī)調(diào)度與死鎖 (2) 最大需求矩陣Max。這是一個nm的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 (3) 分配

27、矩陣Allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 (4) 需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。 Needi,j=Maxi,j-Allocationi,j 第三章處理機(jī)調(diào)度與死鎖 2)銀行家算法銀行家算法 設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requestij=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查

28、： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 第三章處理機(jī)調(diào)度與死鎖 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)

29、。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 第三章處理機(jī)調(diào)度與死鎖 3)安全性算法安全性算法 (1) 設(shè)置兩個向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work =Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時， 再令Finishi =true。 第三章處理機(jī)調(diào)度與死鎖 (2) 從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程： Finis

30、hi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 第三章處理機(jī)調(diào)度與死鎖 4) 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資

31、源分配情況如圖 3-15 所示。 圖 3-8 T0時刻的資源分配表 第三章處理機(jī)調(diào)度與死鎖 (1) T0時刻的安全性： 圖 3-9 T0時刻的安全序列 第三章處理機(jī)調(diào)度與死鎖 (2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號所示。 再利用安全性算法檢查此時系統(tǒng)是否安全

32、。 第三章處理機(jī)調(diào)度與死鎖 圖 3-10 P1申請資源時的安全性檢查 第三章處理機(jī)調(diào)度與死鎖 (3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓P4等待。 (4) P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系統(tǒng)暫時先假定可為

33、P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 3-18 所示。 第三章處理機(jī)調(diào)度與死鎖 圖 3-11 為P0分配資源后的有關(guān)資源數(shù)據(jù) 第三章處理機(jī)調(diào)度與死鎖 允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生 一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價恢復(fù)操作系統(tǒng)運(yùn)行3.7 死鎖的檢測和解除第三章處理機(jī)調(diào)度與死鎖 1.檢測時機(jī) 當(dāng)進(jìn)程等待時檢測死鎖 （其缺點(diǎn)是系統(tǒng)的開銷大） 定時檢測 系統(tǒng)資源利用率下降時檢測死鎖第三章處理機(jī)調(diào)度與死鎖 2.死鎖檢測算法 每個進(jìn)程和資源指定唯一編號 設(shè)置一張資源分配表 記錄各進(jìn)程與其占用資源之間的關(guān)系 設(shè)置一張進(jìn)程等待表 記錄各進(jìn)程與要申請資源之間的關(guān)系第三章處理機(jī)調(diào)度與死鎖 1) 資源分配表和進(jìn)程等待表資源分配表 進(jìn)程等待表r1 p2