第3章處理機調(diào)度和死鎖

1、2022-4-22阜陽師范學院計算機與信息學院1第3章 處理機調(diào)度與死鎖o 3.1 處理機調(diào)度的基本概念o 3.2 調(diào)度算法o 3.3 實時調(diào)度o 3.4 產(chǎn)生死鎖的原因和必要條件o 3.5 預防死鎖的方法o 3.6 死鎖的檢測與解除 2022-4-22阜陽師范學院計算機與信息學院23.1 處理機調(diào)度的基本概念o 3.1.1 高級調(diào)度、中級調(diào)度、低級調(diào)度o 3.1.2 調(diào)度隊列模型o 3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準則2022-4-22阜陽師范學院計算機與信息學院32022-4-22阜陽師范學院計算機與信息學院43.1.1 高級、中級和低級調(diào)度經(jīng)歷下述三級調(diào)度:n高級調(diào)度（High

2、Scheduling）n中級調(diào)度（Intermediate-Level Scheduling）n低級調(diào)度（Low Level Scheduling）2022-4-22阜陽師范學院計算機與信息學院51. 高級調(diào)度 又稱為作業(yè)調(diào)度、宏觀調(diào)度或長程調(diào)度。用于決定把后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，為他們分配必要的資源，并創(chuàng)建進程。 批處理系統(tǒng) ：分時系統(tǒng) ：實時系統(tǒng) ：需要作業(yè)調(diào)度不需作業(yè)調(diào)度不需作業(yè)調(diào)度2022-4-22阜陽師范學院計算機與信息學院61. 高級調(diào)度執(zhí)行作業(yè)調(diào)度時，必須作出兩個決定：o 接納多少作業(yè)每次接納多少作業(yè)進入內(nèi)存，取決于多道程序度，即允許多少個作業(yè)同時在內(nèi)存中運行。o 接納哪些

3、作業(yè)應接納哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。2022-4-22阜陽師范學院計算機與信息學院72. 低級調(diào)度 通常也稱為進程調(diào)度、微觀調(diào)度或短程調(diào)度。進程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。用于決定就緒隊列中哪個進程應先獲得處理機，并將處理機分配給選中的進程。為實現(xiàn)進程調(diào)度，應具有如下三個基本機制： 排隊器 分派器 上下文切換2022-4-22阜陽師范學院計算機與信息學院82. 低級調(diào)度進程調(diào)度可采用下述兩種調(diào)度方式：o 非搶占方式o 搶占方式搶占的原則有：（1）優(yōu)先權(quán)原則（2）短作業(yè)（進程）優(yōu)先原則（3）時間片原則2022-4-22阜陽師范學院計算機與信息學院93. 中級調(diào)

4、度 中級調(diào)度又稱為交換調(diào)度、中程調(diào)度或內(nèi)存調(diào)度。 它按一定的算法將外存中已具備運行條件的進程換入內(nèi)存，而將內(nèi)存中處于阻塞狀態(tài)的某些進程換出至外存。運行就緒阻塞掛起阻塞掛起就緒創(chuàng)建退出進程調(diào)度中級調(diào)度作業(yè)調(diào)度調(diào)度的層次2022-4-22阜陽師范學院計算機與信息學院113.1.2 調(diào)度隊列模型o 僅有進程調(diào)度的調(diào)度隊列模型o 具有高級和低級調(diào)度的調(diào)度隊列模型o 同時具有三級調(diào)度的調(diào)度隊列模型2022-4-22阜陽師范學院計算機與信息學院121. 僅有進程調(diào)度的調(diào)度隊列模型 在分時系統(tǒng)中就緒進程組織成FIFO隊列形式，按時間片輪轉(zhuǎn)方式運行。CPU就 緒 隊 列阻 塞 隊 列時間片完進程調(diào)度等待事件進

5、程完成交互用戶事件出現(xiàn)2022-4-22阜陽師范學院計算機與信息學院132. 具有高級和低級調(diào)度的調(diào)度隊列模型CPU就 緒 隊 列時間片完進程調(diào)度等待事件1進程完成后備隊列等待事件2等待事件n事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)作業(yè)調(diào)度2022-4-22阜陽師范學院計算機與信息學院143. 同時具有三級調(diào)度的調(diào)度隊列模型CPU就 緒 隊 列時間片完進程調(diào)度進程完成后備隊列等待事件事件出現(xiàn)作業(yè)調(diào)度批量作業(yè)交互型作業(yè)中級調(diào)度就緒、掛起隊列事件出現(xiàn)阻 塞、掛 起 隊 列掛起阻 塞 隊 列掛起中級調(diào)度2022-4-22阜陽師范學院計算機與信息學院153.1.3 選擇調(diào)度方式和調(diào)度算法的若干準則o 面向用戶的

6、準則周轉(zhuǎn)時間短n平均周轉(zhuǎn)時間Tn平均帶權(quán)周轉(zhuǎn)時間（W= T(周轉(zhuǎn))/Ts(CPU執(zhí)行)響應時間快截止時間的保證優(yōu)先權(quán)準則o 面向系統(tǒng)的準則 系統(tǒng)吞吐量高 處理機利用率好 各類資源的平衡利用練習1o 設有4個作業(yè)同時到達，每個作業(yè)執(zhí)行時間均為2h，它們在一臺處理器上按單道方式運行，則平均周轉(zhuǎn)時間為（ ） A. 1h B. 5h C. 2.5h D.8hB2022-4-22阜陽師范學院計算機與信息學院173.2 調(diào)度算法o 3.2.1 FCFS與SJF/SPF調(diào)度算法o 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法o 3.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法2022-4-22阜陽師范學院計算機與信息學院183.2

7、.1 FCFS與SJF/SPF調(diào)度算法1. 先來先服務調(diào)度算法(FCFS) 按進程申請CPU（就緒）的次序processRun timeP127P23P35P1P2P3 0 27 30 352022-4-22阜陽師范學院計算機與信息學院19 FCFS實例 下表列出了A、B、C、D四個作業(yè)分別到達系統(tǒng)的時間、要求服務的時間、開始執(zhí)行的時間及各自的完成時間，計算出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。FCFS（First Come First Serve)2022-4-22阜陽師范學院計算機與信息學院20作業(yè)名 到達時間服務時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A01B1100C21D3100FCF

8、S（First Come First Serve)0111110110011011021001001022021991.992022-4-22阜陽師范學院計算機與信息學院21FCFS的特點: o FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進程）o 比較有利于長作業(yè)，而不利于短作業(yè)FCFS（First Come First Serve)2022-4-22阜陽師范學院計算機與信息學院222. 短作業(yè)（進程）優(yōu)先調(diào)度算法帶權(quán)周轉(zhuǎn)時間周轉(zhuǎn)時間完成時間 SJF帶權(quán)周轉(zhuǎn)時間周轉(zhuǎn)時間完成時間 FCFS42534服務時間43210到達時間平均EDCBA作業(yè)名 作業(yè)情 況調(diào)度算法44

9、17621210214115.518143.592.8441982.6718163.2631.51392.2582.12022-4-22阜陽師范學院計算機與信息學院232 . 短作業(yè)（進程）優(yōu)先調(diào)度算法SJF調(diào)度算法的優(yōu)缺點：優(yōu)點：有效降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量缺點：(1) 對長作業(yè)不利(2) 不能保證緊迫性作業(yè)（進程）的及時處理(3) 不一定能真正做到短作業(yè)優(yōu)先2022-4-22阜陽師范學院計算機與信息學院243.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法1. 優(yōu)先權(quán)調(diào)度算法的類型 為照顧緊迫性作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先（HPF）調(diào)度算法。它分為兩種：o 非搶占

10、式優(yōu)先權(quán)算法o 搶占式優(yōu)先權(quán)調(diào)度算法2022-4-22阜陽師范學院計算機與信息學院253.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法2. 優(yōu)先權(quán)的類型o 靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進程時確定的，在進程的整個運行期間保持不變,又稱優(yōu)先數(shù)。1) 動態(tài)優(yōu)先權(quán)：在創(chuàng)建進程時所賦予的優(yōu)先權(quán)可以隨進程的推進或隨其等待時間的增加而改變。2022-4-22阜陽師范學院計算機與信息學院263. 高響應比優(yōu)先調(diào)度算法(HRRN) 為每個作業(yè)引入動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高，則可解決問題。見下式： 優(yōu)先權(quán)=(等待時間+要求服務時間)/要求服務時間 響應時間/要求服務時間 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法練

11、習2o 一個作業(yè)8：00到達系統(tǒng)，估計運行時間為1h。若10:00開始執(zhí)行該作業(yè)，其響應比是（ ） A. 2 B.1 C.3 D.0.5C例題1o 設有4個作業(yè)J1、J2、J3、J4，它們的到達時間和計算時間如表所示。若這4個作業(yè)在一臺處理器上按單道方式運行，采用高響應比優(yōu)先調(diào)度算法，試寫出各作業(yè)的執(zhí)行順序、各作業(yè)的周轉(zhuǎn)時間及平均周轉(zhuǎn)時間作業(yè)到達時間 計算時間J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：優(yōu)先權(quán)（響應比）=(等待時間+要求服務時間)/要求 服務時間響應時間/要求服務時間作業(yè)提交時間開始時間執(zhí)行時間結(jié)束時間周轉(zhuǎn)時間J18：008：

12、00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例題2o 在一個批處理系統(tǒng)中，有兩個作業(yè)進程。有一個作業(yè)序列，其到達時間及估計運行時間如表所示。系統(tǒng)作業(yè)采用最高響應比優(yōu)先調(diào)度算法，進程的調(diào)度采用短進程優(yōu)先的搶占式調(diào)度算法作業(yè)到達時間 估計運行時間J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例題2o （1）列出各作業(yè)的執(zhí)行時間（即列出每個作業(yè)運行的時間片段，如作業(yè)i的運行時

13、間序列為10：00-10：40）o （2）計算這批作業(yè)的平均周轉(zhuǎn)時間。2022-4-22阜陽師范學院計算機與信息工程學院32J110:00J4:20m10:10J2到達到達J210:35J1完成完成J4進內(nèi)存進內(nèi)存分析：分析：J3J4J510:55J4完成完成J3進內(nèi)存進內(nèi)存J1:10mJ1:25m11:25J2完成完成J5進內(nèi)存進內(nèi)存J2:30mJ5:30m11:55J5完成完成12:40J3完成完成J3:45m例題3o 有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式優(yōu)先級調(diào)度算法，作業(yè)的運行情況如表所示，其中作業(yè)的優(yōu)先數(shù)即為進程的優(yōu)先數(shù)，優(yōu)先數(shù)越小，優(yōu)先

14、級越高。2022-4-22阜陽師范學院計算機與信息學院33作業(yè)到達時間運行時間優(yōu)先數(shù)J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作業(yè)進入內(nèi)存的時間及結(jié)束的時間（2）計算平均周轉(zhuǎn)時間2022-4-22阜陽師范學院計算機與信息工程學院34J18:00J1:20m8:20J2到達到達J28:30分析：分析：J3J48:50J2完成完成J4進入進入J1:20mJ2:10m9:10J1完成完成J3進內(nèi)存進內(nèi)存J3:50mJ4:20m10:00J3完成完成10:20J4完成完成J2:20m2022-4-22阜陽師范學院計算機與信息學院353

15、.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法(RR) 在分時系統(tǒng)中，為保證能及時響應用戶的請求，必須采用基于時間片的輪轉(zhuǎn)式進程調(diào)度算法。在早期，分時系統(tǒng)中采用的是簡單的時間片輪轉(zhuǎn)法，進入90年代后，廣泛采用多級反饋隊列調(diào)度算法。2022-4-22阜陽師范學院計算機與信息學院36u將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列。u每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片。u在一個時間片結(jié)束時，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程。一、時間片輪轉(zhuǎn)算法1. 基本原理2022-4-22阜陽師范學院計算機與信息學院372. 時間片長度的確定v時間片長度變化的影響過長退化為F

16、CFS算法。過短用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加。對響應時間的要求：T(響應時間)=N(進程數(shù)目)*q(時間片)一、時間片輪轉(zhuǎn)算法2022-4-22阜陽師范學院計算機與信息學院382022-4-22阜陽師范學院計算機與信息學院39二、多級反饋隊列調(diào)度算法 實施過程如下：（1） 應設置多個隊列并為各個隊列賦予不同的優(yōu)先級。第一個最高，依次降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也不相同，優(yōu)先權(quán)越高，時間片越短。1. 調(diào)度算法2022-4-22阜陽師范學院計算機與信息學院40多級反饋隊列調(diào)度算法 就緒隊列1就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至

17、CPU至CPU(時間片：S1 S2 S3)2022-4-22阜陽師范學院計算機與信息學院41二、多級反饋隊列調(diào)度算法(2) 當一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。如它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾。(3）僅當?shù)?（i-1）隊列空閑時，才會調(diào)度第i隊列中的進程運行。2022-4-22阜陽師范學院計算機與信息學院422. 多級反饋隊列調(diào)度算法的性能p 終端型作業(yè)用戶p 短作業(yè)優(yōu)先o 短批處理作業(yè)用戶n 周轉(zhuǎn)時間較短o 長批處理作業(yè)用戶二、多級反饋隊列調(diào)度算法2022-4-22阜陽師范學院計算機與信息學院43補充作業(yè)o 假如

18、有四道作業(yè)，它們的進入時間和運行時間由下表給出，在單道程序環(huán)境下，分別填寫先來先服務、短作業(yè)優(yōu)先和RR（3）算法的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。2022-4-22阜陽師范學院計算機與信息學院44作業(yè)號進入時間運行時間FCFSSJFRR（3）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1042110326432平均2022-4-22阜陽師范學院計算機與信息學院45第3章 處理機調(diào)度與死鎖o 3.3 實時調(diào)度o 3.4 產(chǎn)生死鎖的原因和必要條件o 3.5 預防死鎖的方法o 3.6 死鎖的檢測與解除 2022-4-22阜陽師

19、范學院計算機與信息學院463.3 實時調(diào)度o 實時調(diào)度：n 合理安排就緒實時任務的執(zhí)行次序，滿足每個實時任務時間約束條件的調(diào)度o 實時任務：n 具有明確時間約束的計算任務2022-4-22阜陽師范學院計算機與信息學院473.3 實時調(diào)度o 3.3.1 實現(xiàn)實時調(diào)度的基本條件o 3.3.2 實時調(diào)度算法的分類o 3.3.3 常用的幾種實時調(diào)度算法2022-4-22阜陽師范學院計算機與信息學院483.3.1 實現(xiàn)實時調(diào)度的基本條件o 提供必要的信息o 系統(tǒng)處理能力強o 采用搶占式調(diào)度機制o 具有快速切換機制2022-4-22阜陽師范學院計算機與信息學院491. 提供必要的信息o 就緒時間o 開始截

20、止時間和完成截止時間o 處理時間o 資源要求o 優(yōu)先級2022-4-22阜陽師范學院計算機與信息學院502. 系統(tǒng)處理能力強 假如系統(tǒng)中有M個周期性的硬實時任務，處理時間為Ci，周期時間表示為Pi 則單機系統(tǒng)中必須滿足條件 （ Ci / Pi ）1 多處理機系統(tǒng) （ Ci / Pi ）N2022-4-22阜陽師范學院計算機與信息學院513. 采用搶占式調(diào)度機制o 硬實時任務： 廣泛采用搶占機制 o 小的實時系統(tǒng)： 可采用非搶占調(diào)度機制（簡化調(diào)度程序和對任務調(diào)度時所花費的系統(tǒng)開銷）3. 采用搶占式調(diào)度機制2022-4-22阜陽師范學院計算機與信息學院52(a) 非搶占式輪轉(zhuǎn)調(diào)度當前進程實時進程實

21、時進程請求調(diào)度實時進程搶占當前進程并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進程 1進程 2實時進程要求調(diào)度進程 n實時進程調(diào)度實時進程運行(b) 非搶占式優(yōu)先權(quán)調(diào)度當前進程實時進程實時進程請求調(diào)度 當前進程運行完成調(diào)度時間當前進程實時進程請求調(diào)度 時鐘中斷到來時調(diào)度時間(c) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進程2022-4-22阜陽師范學院計算機與信息學院534. 具有快速切換機制 (1) 對外部中斷的快速響應能力(2) 快速的任務分派能力2022-4-22阜陽師范學院計算機與信息學院543.3.2 實時調(diào)度算法的分類可以按照不同方式對實時調(diào)度算法加以分類：o 根據(jù)實時任務

22、性質(zhì)的不同可分為硬實時調(diào)度算法和軟實時調(diào)度算法；o 按調(diào)度方式的不同可分為非搶占調(diào)度算法和搶占調(diào)度算法；2022-4-22阜陽師范學院計算機與信息學院553.3.3 常用的幾種實時調(diào)度算法 o 最早截止時間優(yōu)先EDF（Earliest Deadline First）算法o 最低松弛度優(yōu)先LLF（Least Laxity First）算法2022-4-22阜陽師范學院計算機與信息學院56EDF算法用于非搶占調(diào)度圖示 1 3 4 2t按開始截止時間早晚的排序任務執(zhí)行任務到達 1 3 4 2 1 2 3 4 1. 最早截止時間優(yōu)先EDF算法 截止時間越早，其優(yōu)先級越高2022-4-22阜陽師范學院計

23、算機與信息學院572. 最低松弛度優(yōu)先LLF算法o 松弛度=完成截止時間運行時間當前時間o 任務的緊急程度愈高，松弛度愈低，優(yōu)先級愈高。o 要求系統(tǒng)有一個按松弛度排序的實時任務就緒隊列o 該算法主要用于可搶占調(diào)度方式中2022-4-22阜陽師范學院計算機與信息學院58LLF算法例tA1 A2 A3 A4 A5 A6B1 B2 0 20 40 60 80 100 120 假如在一個實時系統(tǒng)中，有兩個周期型實時任務A、B，任務A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms；由此可得知AB任務每次必須完成的時間分別為A1、A2、A3和B1、B2、B3如

24、下圖：2022-4-22阜陽師范學院計算機與信息學院59LLF算法例圖示tt1 t2 t3 t4 t5 t6 t7 t8 0 10 20 30 40 50 60 70 80A1(10) A2(10) A3(10) A4 (10) B1(20) B1 (5) B2(15) B2(10) 2022-4-22阜陽師范學院計算機與信息學院603.5 產(chǎn)生死鎖的原因和必要條件o3.5.1 產(chǎn)生死鎖的原因o3.5.2 產(chǎn)生死鎖的必要條件o3.5.3 處理死鎖的基本方法2022-4-22阜陽師范學院計算機與信息學院61關(guān)于死鎖 死鎖是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種狀態(tài)時，若

25、無外力作用，它們都將無法再向前推進。2022-4-22阜陽師范學院計算機與信息學院623.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點：o 競爭資源1. 進程間推進順序非法n 可搶占和非搶占性資源n 可重用性（永久性）資源和可消耗性（臨時性）資源2022-4-22阜陽師范學院計算機與信息學院63P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D進程推進順序不當引起死鎖2022-4-22阜陽師范學院計算機與信息學院643.5.2 產(chǎn)生死鎖的必要條件 雖然進程在運行過程中可能發(fā)生死鎖，但死鎖的

26、發(fā)生也必須具備一定的條件?？梢钥闯觯仨毦邆湟韵滤膫€條件:1. 互斥條件：進程所競爭的資源必須被互斥使用。2. 請求和保持條件：指進程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放。2022-4-22阜陽師范學院計算機與信息學院653.5.2 產(chǎn)生死鎖的必要條件 3. 不剝奪條件：指進程已獲得的資源，只能在使用完時由自己釋放。 4. 環(huán)路等待條件：指在發(fā)生死鎖時，必然存在一個“進程資源”的環(huán)形鏈，環(huán)路中的每一條邊是進程在請求另一進程已經(jīng)占有的資源。2022-4-22阜陽師范學院計算機與信息學院663.5.3 處理死

27、鎖的基本方法一、預防死鎖消除產(chǎn)生死鎖的必要條件二、避免死鎖分配資源時防止進入不安全狀態(tài)三、檢測死鎖不預防死鎖，出現(xiàn)死鎖就解除四、解除死鎖與檢測死鎖配合使用2022-4-22阜陽師范學院計算機與信息學院673.6 預防與避免死鎖的方法o3.6.1 預防死鎖o3.6.2 系統(tǒng)安全狀態(tài)o3.6.3 利用銀行家算法避免死鎖2022-4-22阜陽師范學院計算機與信息學院683.6.1 預防死鎖1. 摒棄“請求和保持”條件靜態(tài)資源分配法 一次性地申請其在整個過程運行過程中所需要的全部資源o優(yōu)點：算法簡單、易于實現(xiàn)且很安全o缺點：資源浪費嚴重，進程延遲運行2022-4-22阜陽師范學院計算機與信息學院692

28、. 摒棄“不剝奪”條件o 資源暫時釋放策略:申請新的資源得不到滿足則暫時釋放已有的所有資源。從而摒棄了“不剝奪”條件。o 該方法實現(xiàn)起來比較復雜且付出很大代價?？赡軙斐汕肮ΡM棄，反復申請和釋放情況。3.6.1 預防死鎖2022-4-22阜陽師范學院計算機與信息學院703. 摒棄“環(huán)路等待”條件o 有序資源分配法：o 與前兩種策略比較，資源利用率和系統(tǒng)吞吐量都有較明顯的改善。o 但也存在嚴重問題：為資源編號限制新設備的增加；進程使用設備順序與申請順序相反；限制用戶編程自由。r1r2rk.申請次序rm2022-4-22阜陽師范學院計算機與信息學院71檢測可滿足請求 分配 不分配安全不安全系統(tǒng)處于

29、安全狀態(tài)：存在安全進程序列;安全不安全死鎖1. 安全狀態(tài)3.6.2 系統(tǒng)安全狀態(tài)o 避免死鎖的實質(zhì)就是系統(tǒng)在進行資源分配時，如何使系統(tǒng)不進入不安全狀態(tài)。2022-4-22阜陽師范學院計算機與信息學院722. 安全狀態(tài)之例 假定系統(tǒng)中有三個進程A、B和C，共有12臺磁帶機。進程A總共要求10臺，B和C分別要求4臺和9臺。假設在T0時刻,進程A、B和C已分別獲得5臺、2臺和2臺，尚有3臺未分配，如下表所示：進程最大需求已分配還需可用ABC10495225273進程最大需求已分配還需可用B 4 2 235A 10 5 510C 9 2 712 經(jīng)分析發(fā)現(xiàn)，在T0時刻系統(tǒng)是安全的，因為此時存在一個安全

30、序列，即只要系統(tǒng)按此進程序列分配資源，就能使每個進程都順利完成。2022-4-22阜陽師范學院計算機與信息學院733. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換o 如果在T0時刻后，C又請求到一臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給C，則系統(tǒng)便進入不安全狀態(tài)。因為，此時再也無法找到一個安全序列，結(jié)果導致死鎖。進程最大需求已分配還需可用A10553B422C927o 所以，引入安全狀態(tài)的目的在于進行資源分配時，要使系統(tǒng)不發(fā)生死鎖，只要保證當前的系統(tǒng)狀態(tài)是安全的，即每次資源分配之后系統(tǒng)都處于安全狀態(tài)。 2C 9 3 6練習1o 某計算機系統(tǒng)中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。

31、該系統(tǒng)可能會發(fā)生死鎖的K的最小值是（ ），不會發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5解析：p R類資源共m個， n個進程互斥使用，每個進程對R類資源最大需求量為wp 設：M=n*（w-1）+1p 則m=M絕對不會死鎖 練習1o 某計算機系統(tǒng)中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的K的最小值是（ ），不會發(fā)生死鎖的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5CB2022-4-22阜陽師范學院計算機與信息學院773.6.3 利用銀行家算法避免死鎖o最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由

32、于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名的。1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其動態(tài)初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配與回收而動態(tài)的改變。如果Availablej=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個。（2）最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K,則表示進程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統(tǒng)中每一類資源當前已

33、分配給每一進程的資源數(shù)。如果Allocationi,j=K,則表示進程i當前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Needi,j=K,則表示進程i還需要Rj類資源K個，方能完成其任務。上述三個矩陣間存在的關(guān)系：Needi,j=Maxi,j-Allocationi,j2022-4-22阜陽師范學院計算機與信息學院783.6.3 利用銀行家算法避免死鎖o 安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（1）設置兩個向量： 工作向量work：表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時

34、，work:=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配進程，使之運行完成。開始時先做Finishi:=false;當有足夠資源分配給進程時，再令Finishi:=true。2022-4-22阜陽師范學院計算機與信息學院79安全性檢測算法FWork:=Available;Finish:=false; 有滿足條件的有滿足條件的j:Finishi=falseNeedj WorkFinishi=true;Work:=Work+AllocationjT i ,Finishi=trueTF安全安全不安全不安全賦初值賦初值進程是否完成進程是否完成資源是否夠用資源是否夠用進程獲得資

35、源后，順進程獲得資源后，順利完成并釋放資源利完成并釋放資源進程是否進程是否都完成都完成2022-4-22阜陽師范學院計算機與信息學院80（2）從進程集合中找到一個能滿足下述條件的進程： Finishi=false;Needi,j=workj;若找到，執(zhí)行步驟3，否則執(zhí)行步驟4。 （3）當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： workj:= worki+ Allocationi,j ; Finishi:=true; goto step 2;（4）如果所有進程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。安全性算法202

36、2-4-22阜陽師范學院計算機與信息學院814. 銀行家算法之例 假定系統(tǒng)中有五個進程P0,P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖所示。4 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P21 2 22 0 03 2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C 資源情況資源情況進程進程2022-4-22阜陽師范學院計算機與信息學院824. 銀行家算法之例 T0時刻的安全性：利用安全

37、性算法對T0時刻的資源分配情況進行分析可知，在T0時刻存在著一個安全序列P1,P3,P4,P2,P0，故系統(tǒng)是安全的。FalseFalseFalseFalseFalseTrue10 5 70 1 07 4 310 4 7P0True10 4 73 0 26 0 07 4 5P2True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 22 0 01 2 23 3 2P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 資源情況資源情況進程進程2022-4-22阜

38、陽師范學院計算機與信息學院833.6.3 利用銀行家算法避免死鎖o 銀行家算法 設Requesti是進程Pi的請求向量，如果Requesti j=K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：2022-4-22阜陽師范學院計算機與信息學院84Pi請求資源請求資源Requestij Needj請求超量，錯返請求超量，錯返Requestij Availablej不滿足，等待不滿足，等待Availablej:=Availablej-RequestijAllocationi,j:=Allocationi,j+RequestijNeedi,j:=Needi,j-R

39、equestij安全安全確認，確認，pi繼續(xù)繼續(xù)Availablej:=Availablej+RequestijAllocationi,j:=Allocationi,j-RequestijNeedi,j:=Needi,j+Requestijpi等待等待FTFTTF請求的資源是否超請求的資源是否超出實際需求出實際需求是否有足夠的是否有足夠的資源資源暫時分配資源暫時分配資源恢復原來的資源恢復原來的資源分配狀態(tài)分配狀態(tài)2022-4-22阜陽師范學院計算機與信息學院85（1）如果Requestij= Needi,j,便轉(zhuǎn)向步驟2；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。（2）如果Re

40、questij= Availablej,便轉(zhuǎn)向步驟3；否則，表示尚無足夠資源，Pi需等待。 （3）系統(tǒng)試探著把資源分配給進程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)以決定是否完成本次分配。銀行家算法2022-4-22阜陽師范學院計算機與信息學院864. 銀行家算法之例o P1請求資源：P1發(fā)出請求向量Request1(1， 0，

41、2),系統(tǒng)按銀行家算法進行檢查：（1）Request1(1，0，2)=Need1(1，2，2)（2）Request1(1，0，2)=Available1(3，3，2)（3）系統(tǒng)先假定可為P1分配資源，并修改Available、Allocation1和Need1向量。 （4）再利用安全性算法檢查此時系統(tǒng)是否安全。如下表：2022-4-22阜陽師范學院計算機與信息學院87FalseFalseFalseFalseFalse4. 銀行家算法之例 由所進行的安全性檢查得知，可以找到一個安全序列P1,P3,P4,P0,P2,因此，系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。True10 5 73 0

42、 26 0 07 5 5P2True7 5 50 1 07 4 37 4 5P0True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 23 0 20 2 02 3 0P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 資源情況資源情況進程進程2022-4-22阜陽師范學院計算機與信息學院884. 銀行家算法之例o P4請求資源：P4發(fā)出請求向量Request4(3，3，0),系統(tǒng)按銀行家算法進行檢查：（1）Request4(3，3，0)=Need4(4，3

43、，1);（2）Request4(3，3，0)=Available(2，3，0),讓P4等待。o P0請求資源：P0發(fā)出請求向量Request0(0，2，0),系統(tǒng)按銀行家算法進行檢查：（1）Request0(0，2，0)=Need0(7，4，3); （2）Request0(0，2，0)=Available(2，3，0)；（3）系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如下表所示：2022-4-22阜陽師范學院計算機與信息學院894. 銀行家算法之例o 進行安全性檢查：可用資源Available(2,1,0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。o 如果在銀行家算法中，把P0發(fā)出的請求向量改為Request0(0,1,0),系統(tǒng)是否能將資源分配給它。4 3 10 0 2P40 1 12 1 1P36 0