操作系統(tǒng)之資源分配與死鎖

1、第三章第三章 資源分配與死鎖資源分配與死鎖 目錄目錄1.資源管理概述資源管理概述 2.資源管理的機(jī)制和策略資源管理的機(jī)制和策略3.死鎖的基本概念死鎖的基本概念4.處理死鎖的基本方法處理死鎖的基本方法2 包含資源的物理名、邏輯名、類型、地址、分配狀態(tài)等包含資源的物理名、邏輯名、類型、地址、分配狀態(tài)等 信息。信息。 決定資源應(yīng)分給誰，何時(shí)分配，分配多少等問題。決定資源應(yīng)分給誰，何時(shí)分配，分配多少等問題。 執(zhí)行資源分配；資源收回工作。執(zhí)行資源分配；資源收回工作。4、 對(duì)資源的存取進(jìn)行控制并對(duì)資源實(shí)施安全保護(hù)措施。對(duì)資源的存取進(jìn)行控制并對(duì)資源實(shí)施安全保護(hù)措施。3.1 資源管理概述資源管理概述一一. .

2、資源管理功能資源管理功能3 系統(tǒng)對(duì)作業(yè)一級(jí)采用資源靜態(tài)分配方法。系統(tǒng)對(duì)作業(yè)一級(jí)采用資源靜態(tài)分配方法。 系統(tǒng)在調(diào)度作業(yè)時(shí)，根據(jù)作業(yè)所需資源進(jìn)行分配；并在系統(tǒng)在調(diào)度作業(yè)時(shí)，根據(jù)作業(yè)所需資源進(jìn)行分配；并在作業(yè)運(yùn)行完畢作業(yè)運(yùn)行完畢 時(shí)，收回所分配的全部資源。這種分配通常稱為時(shí)，收回所分配的全部資源。這種分配通常稱為資源的靜態(tài)分配。資源的靜態(tài)分配。 系統(tǒng)對(duì)進(jìn)程一級(jí)采用資源動(dòng)態(tài)分配方法。系統(tǒng)對(duì)進(jìn)程一級(jí)采用資源動(dòng)態(tài)分配方法。 系統(tǒng)在進(jìn)程運(yùn)行中，根據(jù)進(jìn)程提出的資源需求，進(jìn)行資源系統(tǒng)在進(jìn)程運(yùn)行中，根據(jù)進(jìn)程提出的資源需求，進(jìn)行資源 的動(dòng)態(tài)分配和回收。這種分配通常稱為資源的動(dòng)態(tài)分配。的動(dòng)態(tài)分配和回收。這種分配通常稱

3、為資源的動(dòng)態(tài)分配。3.1 資源管理概述資源管理概述二二. .4 物理資源物理資源 (實(shí)資源實(shí)資源) 虛擬資源虛擬資源 (邏輯資源邏輯資源) 方便用戶使用方便用戶使用資源可動(dòng)態(tài)分配，提高資源利用率資源可動(dòng)態(tài)分配，提高資源利用率 3.1 資源管理概述資源管理概述三三. .虛擬資源虛擬資源5進(jìn)程調(diào)度進(jìn)程調(diào)度地址映射地址映射邏輯設(shè)備邏輯設(shè)備虛擬設(shè)備虛擬設(shè)備 文件邏輯結(jié)構(gòu)文件邏輯結(jié)構(gòu)進(jìn)程進(jìn)程設(shè)備分配設(shè)備分配動(dòng)態(tài)映射動(dòng)態(tài)映射 虛存虛存(程序地址空間程序地址空間)磁盤空間分配磁盤空間分配文件目錄查找文件目錄查找 資源類別資源類別 物理資源物理資源 虛擬虛擬(邏輯邏輯) 映射映射 處理機(jī)處理機(jī) CPU 存儲(chǔ)器

4、存儲(chǔ)器 主存主存 設(shè)備設(shè)備 外部設(shè)備外部設(shè)備 信息信息 文件物理結(jié)構(gòu)文件物理結(jié)構(gòu)3.1 資源管理概述資源管理概述三三. .虛擬資源虛擬資源6資源描述器定義資源描述器定義 描述描述各類資源的最小分配單位的數(shù)描述描述各類資源的最小分配單位的數(shù) 據(jù)結(jié)構(gòu)稱為資源描述器據(jù)結(jié)構(gòu)稱為資源描述器 rd。 如：主存分區(qū)分配方法中，最小分配單如：主存分區(qū)分配方法中，最小分配單 位為主存分區(qū)。位為主存分區(qū)。 資源描述器內(nèi)容資源描述器內(nèi)容 資源名、資源類型、最小分配單位的大資源名、資源類型、最小分配單位的大 小、地址、分配標(biāo)志、描述器鏈接信息、小、地址、分配標(biāo)志、描述器鏈接信息、 存取權(quán)限、密級(jí)、存取時(shí)間存取權(quán)限、密

5、級(jí)、存取時(shí)間 20KB 0 52KB66KB130KB230KB256KB 1主存主存程序程序4程序程序1程序程序3OS內(nèi)存分布狀況圖內(nèi)存分布狀況圖3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略72、 資源信息塊定義資源信息塊定義 描述某類資源的請(qǐng)求者、可用資源和該類資源分配程序等描述某類資源的請(qǐng)求者、可用資源和該類資源分配程序等 必要信息的數(shù)據(jù)結(jié)構(gòu)。必要信息的數(shù)據(jù)結(jié)構(gòu)。 資源信息塊內(nèi)容資源信息塊內(nèi)容 請(qǐng)求者隊(duì)列請(qǐng)求者隊(duì)列可利用資源隊(duì)列可利用資源隊(duì)列資源分配程序資源分配程序等待隊(duì)列頭指針等待隊(duì)列頭指針可利用資源隊(duì)列頭指針可利用資源隊(duì)列頭指針資源分配程序入口地址資源分配程序入口地址3.2 資源

6、管理的機(jī)制和策略資源管理的機(jī)制和策略8 中央處理機(jī)資源信息塊內(nèi)容中央處理機(jī)資源信息塊內(nèi)容 PCB1PCB2PCBk進(jìn)程調(diào)度程序進(jìn)程調(diào)度程序ready_q_start可用處理機(jī)信息可用處理機(jī)信息scheduler_addrCPU3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略9先請(qǐng)求先服務(wù)先請(qǐng)求先服務(wù)每一個(gè)新產(chǎn)生的請(qǐng)求均排在隊(duì)尾；每一個(gè)新產(chǎn)生的請(qǐng)求均排在隊(duì)尾；當(dāng)資源可用時(shí)，取隊(duì)首元素，并滿足其需要。當(dāng)資源可用時(shí)，取隊(duì)首元素，并滿足其需要。 排序原則排序原則：按請(qǐng)求的先后次序排序。：按請(qǐng)求的先后次序排序。 表頭表頭按請(qǐng)求的先后次序分配資源按請(qǐng)求的先后次序分配資源先先后后3.2 3.2 資源

7、管理的機(jī)制和策略資源管理的機(jī)制和策略10對(duì)每一個(gè)進(jìn)程指定一個(gè)優(yōu)先級(jí)；對(duì)每一個(gè)進(jìn)程指定一個(gè)優(yōu)先級(jí)； 每一個(gè)新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插到相應(yīng)的每一個(gè)新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插到相應(yīng)的 位置；位置；當(dāng)資源可用時(shí)，取隊(duì)首元素，并滿足其需要。當(dāng)資源可用時(shí)，取隊(duì)首元素，并滿足其需要。 排序原則排序原則：按優(yōu)先級(jí)的高低排序。：按優(yōu)先級(jí)的高低排序。 表頭表頭按按優(yōu)先級(jí)的高低排序按按優(yōu)先級(jí)的高低排序高高低低3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略優(yōu)先調(diào)度策略優(yōu)先調(diào)度策略三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理 數(shù)據(jù)的組織和格式：數(shù)據(jù)的組織和格式：（1 1）基本概念：）基本概念： 盤面號(hào)

8、（磁頭號(hào)）：盤面號(hào)（磁頭號(hào)）： 0 0 M-1M-1； 柱面號(hào)（磁道號(hào)）：柱面號(hào)（磁道號(hào)）： 0 0 L-1L-1； 扇區(qū)號(hào)：扇區(qū)號(hào)： 1 1 N N； 扇扇區(qū)區(qū)標(biāo)識(shí)符字段標(biāo)識(shí)符字段數(shù)據(jù)字段數(shù)據(jù)字段校驗(yàn)字段校驗(yàn)字段3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略 數(shù)據(jù)的組織和格式：數(shù)據(jù)的組織和格式：（2 2）存儲(chǔ)容量：）存儲(chǔ)容量：（3 3）扇區(qū)編址方式）扇區(qū)編址方式u CHSCHS（柱面（柱面/ /磁頭磁頭/ /扇區(qū)）方式：扇區(qū)）方式： 磁道（柱面），磁道（柱面），磁頭，磁頭，扇區(qū)扇區(qū) DOSDOS中稱為中稱為“絕對(duì)扇區(qū)絕對(duì)扇區(qū)”表示法。表示法。u LBALBA（相對(duì)扇區(qū)號(hào)）方式：（相

9、對(duì)扇區(qū)號(hào)）方式： 以磁盤第一個(gè)扇區(qū)（以磁盤第一個(gè)扇區(qū)（0 0柱面、柱面、0 0磁頭、磁頭、1 1扇區(qū)）作為扇區(qū)）作為L(zhǎng)BALBA的的 0 0扇區(qū)扇區(qū) = =磁頭數(shù)磁頭數(shù)磁道（柱面）數(shù)磁道（柱面）數(shù)每道扇區(qū)數(shù)每道扇區(qū)數(shù) 每扇區(qū)字節(jié)數(shù)每扇區(qū)字節(jié)數(shù) 三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略 數(shù)據(jù)的組織和格式：數(shù)據(jù)的組織和格式：(4)LBA(4)LBA扇區(qū)號(hào)與（柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)）間的轉(zhuǎn)換：扇區(qū)號(hào)與（柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)）間的轉(zhuǎn)換： 若若L L、M M、N N分別表示一個(gè)磁盤的柱面數(shù)（磁道數(shù)）、盤面數(shù)分別表示一個(gè)磁盤的柱面數(shù)（磁道數(shù)）、盤面數(shù)

10、（磁頭數(shù)）、扇區(qū)數(shù)，則第（磁頭數(shù)）、扇區(qū)數(shù)，則第i i柱面、柱面、j j磁頭、磁頭、k k扇區(qū)所對(duì)應(yīng)的扇區(qū)所對(duì)應(yīng)的LBALBA扇扇區(qū)號(hào)為：區(qū)號(hào)為： 若知道若知道LBALBA扇區(qū)號(hào)，則對(duì)應(yīng)的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)分別扇區(qū)號(hào)，則對(duì)應(yīng)的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)分別是：是： LBA= (iLBA= (i* *M M* *N) + (jN) + (j* *N) + k-1N) + k-1 柱面號(hào)：柱面號(hào)：i=int(i=int(LBALBA /(M/(M* *N)N) 磁頭號(hào)：磁頭號(hào)：j=j=LBALBA mod(M mod(M* *N)/NN)/N 扇區(qū)號(hào)：扇區(qū)號(hào)：k =k =LBALBA mod(M

11、mod(M* *N) mod N+1N) mod N+1三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略2. 2. 磁盤的類型磁盤的類型 1) 1) 固定頭磁盤固定頭磁盤; ; 2) 2) 移動(dòng)頭磁盤移動(dòng)頭磁盤 ：串行讀寫：串行讀寫 3. 3. 磁盤訪問時(shí)間磁盤訪問時(shí)間 1) 1) 尋道時(shí)間尋道時(shí)間T Ts s ：把磁頭移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間把磁頭移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。 T Ts s= =m mn n+ +s s m m：一般磁盤：一般磁盤：0.20.20.30.3； 高速磁盤：高速磁盤：m0.1m0.1 S S：磁臂啟動(dòng)時(shí)間，約為：

12、磁臂啟動(dòng)時(shí)間，約為2ms2ms 3ms3ms三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略 3) 傳輸時(shí)間傳輸時(shí)間Tt 把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間。把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間。因此，因此， 可將磁盤訪問時(shí)間可將磁盤訪問時(shí)間Ta表示為：表示為： 3. 3. 磁盤訪問時(shí)間磁盤訪問時(shí)間 rNbTt= =rNbrTTsa+ + += =212) 2) 旋轉(zhuǎn)延遲時(shí)間旋轉(zhuǎn)延遲時(shí)間TrTr 這是指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。這是指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。 TrTr = 1/2r= 1/2r三三. .磁盤存儲(chǔ)器

13、管理磁盤存儲(chǔ)器管理3.2 3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略4.4.磁盤調(diào)度磁盤調(diào)度 當(dāng)有大量磁盤當(dāng)有大量磁盤I/O請(qǐng)求時(shí)，恰當(dāng)選擇調(diào)度順序，以降低完成請(qǐng)求時(shí)，恰當(dāng)選擇調(diào)度順序，以降低完成這些這些I/O服務(wù)的總時(shí)間。服務(wù)的總時(shí)間。 移臂調(diào)度移臂調(diào)度：當(dāng)同時(shí)有多條磁道訪問請(qǐng)求時(shí)，確定磁道訪問：當(dāng)同時(shí)有多條磁道訪問請(qǐng)求時(shí)，確定磁道訪問順序，以減少平均尋道時(shí)間順序，以減少平均尋道時(shí)間旋轉(zhuǎn)調(diào)度旋轉(zhuǎn)調(diào)度：當(dāng)一條磁道上有多個(gè)扇區(qū)訪問請(qǐng)求時(shí)，確定扇：當(dāng)一條磁道上有多個(gè)扇區(qū)訪問請(qǐng)求時(shí)，確定扇區(qū)訪問順序，以減少旋轉(zhuǎn)延遲時(shí)間區(qū)訪問順序，以減少旋轉(zhuǎn)延遲時(shí)間三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理3.2

14、3.2 資源管理的機(jī)制和策略資源管理的機(jī)制和策略（1 1）先來先服務(wù)）先來先服務(wù)FCFS(First-Come, First Served)FCFS(First-Come, First Served) 假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號(hào)磁道，磁頭正向磁道號(hào)增加的方向號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：2323， 376376，205205，132132，6161， 190190， 2929，4 4， 4040則磁盤調(diào)度順序和尋道距離為：則磁盤調(diào)度順序和尋道距離為：2323， 376376，205205，

15、132132，6161， 190190， 2929，4 4， 4040T Ts s = = (100-23)(100-23) +(376-23)+(376-23)+(376-205)+(376-205)+(205-132)+(205-132)+(132-61)+(132-61)+(190-61)+(190-61)+(190-29)+(190-29)+(29-4)+(29-4) +(40-4)+(40-4)平均尋道距離平均尋道距離=T=Ts s/9/9三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號(hào)磁道，磁頭號(hào)磁道，磁頭正向磁道

16、號(hào)增加正向磁道號(hào)增加的方向的方向（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：2323，376376，205205，132132，6161，190190，2929，4 4，40,40,則磁盤調(diào)度順序和尋道距離為：則磁盤調(diào)度順序和尋道距離為：2323， 376376，205205，132132，6161， 190190， 2929，4 4， 4040T Ts s = = (132-100)(132-100) +(190-132)+(190-132)+(205-190)+(205-190)+(205-61)+(205-61)+(61-40)+(61-40)

17、+(40-29)+(40-29) +(29-23)+(29-23) +(23-4)+(23-4) +(376-4)+(376-4)問題問題： （1 1）不能保證平均尋道距離最短；）不能保證平均尋道距離最短； （2 2）會(huì)產(chǎn)生饑餓現(xiàn)象；）會(huì)產(chǎn)生饑餓現(xiàn)象； （3 3）影響磁盤的機(jī)械壽命。）影響磁盤的機(jī)械壽命。（2 2）最短尋道時(shí)間優(yōu)先算法）最短尋道時(shí)間優(yōu)先算法SSTFSSTF三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：（3 3）掃描）掃描(SCAN)(SCAN)算法算法 ：（又稱為電梯算法）（又稱為電梯算法） （1）欲訪問磁道與當(dāng)前磁道的距離；）欲訪問磁道與當(dāng)前磁道的

18、距離； （2）磁頭當(dāng)前的移動(dòng)方向。）磁頭當(dāng)前的移動(dòng)方向。假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號(hào)磁道，磁頭正向磁道號(hào)增加的方向號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：2323，376376，205205，132132，6161，190190，2929，4 4，40,40,則磁盤調(diào)度順序和尋道距離為：則磁盤調(diào)度順序和尋道距離為：2323， 376376，205205，132132，6161， 190190， 2929，4 4， 4040T Ts s = = (132-100)(132-100) +(190-132)

19、+(190-132)+(205-190)+(205-190)+(376-205)+(376-205)+(376-61)+(376-61)+(61-40)+(61-40) +(40-29)+(40-29) +(29-23)+(29-23) +(23-4)+(23-4)三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：（4 4） N-Step-SCAN N-Step-SCAN算法算法 “磁臂粘著磁臂粘著”現(xiàn)象現(xiàn)象算法思想：將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為算法思想：將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列，磁的子隊(duì)列，磁盤調(diào)度將按盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列；算法依

20、次處理這些子隊(duì)列； 而每處理一個(gè)子而每處理一個(gè)子隊(duì)列時(shí)又采用隊(duì)列時(shí)又采用SCAN算法。算法。例如：例如：2323， 376376，205205，132132，6161， 190190， 2929，4 4， 4040若子隊(duì)列長(zhǎng)度若子隊(duì)列長(zhǎng)度N=4N=4，則分成，則分成3 3個(gè)隊(duì)列：個(gè)隊(duì)列： 23, 376, 205, 23, 376, 205, 132132 61, 190, 29, 61, 190, 29, 4040 4 4FCFSFCFSSCANSCAN三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.磁盤調(diào)度算法：磁盤調(diào)度算法：（5 5）FSCANFSCAN算法算法 該算法實(shí)質(zhì)上是該算法實(shí)質(zhì)上

21、是N步步SCAN算法的簡(jiǎn)化，算法的簡(jiǎn)化， 它只將磁盤它只將磁盤請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列：請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列： 由當(dāng)前所有請(qǐng)求磁盤形成的隊(duì)列，由磁盤調(diào)度按由當(dāng)前所有請(qǐng)求磁盤形成的隊(duì)列，由磁盤調(diào)度按SCAN算法進(jìn)行處理。算法進(jìn)行處理。 在掃描期間，將新出現(xiàn)的所有磁盤在掃描期間，將新出現(xiàn)的所有磁盤I/O請(qǐng)求，請(qǐng)求， 放入另放入另一個(gè)等待處理的請(qǐng)求隊(duì)列。一個(gè)等待處理的請(qǐng)求隊(duì)列。 23, 376, 205, 13223, 376, 205, 132，61, 190, 2961, 190, 29，40, 440, 4 三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：13當(dāng)同一磁

22、道（柱面）上有多個(gè)扇區(qū)請(qǐng)求時(shí)，總是選取與當(dāng)前讀當(dāng)同一磁道（柱面）上有多個(gè)扇區(qū)請(qǐng)求時(shí)，總是選取與當(dāng)前讀寫頭最近的那個(gè)寫頭最近的那個(gè)I/O請(qǐng)求，使旋轉(zhuǎn)圈數(shù)最少。請(qǐng)求，使旋轉(zhuǎn)圈數(shù)最少。例：對(duì)磁盤訪問的例：對(duì)磁盤訪問的5個(gè)請(qǐng)求，若磁頭在個(gè)請(qǐng)求，若磁頭在1號(hào)柱面，先按號(hào)柱面，先按SCAN算算法做移臂調(diào)度，再進(jìn)行旋轉(zhuǎn)調(diào)度，則調(diào)度順序如下：法做移臂調(diào)度，再進(jìn)行旋轉(zhuǎn)調(diào)度，則調(diào)度順序如下：柱面號(hào)柱面號(hào) 盤面號(hào)盤面號(hào) 塊號(hào)塊號(hào) 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3 三三. .磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理5.5.旋轉(zhuǎn)調(diào)度算法：旋轉(zhuǎn)調(diào)度算法：柱面號(hào)柱面號(hào) 盤面號(hào)盤面號(hào) 塊號(hào)塊號(hào) 5 2 1 5

23、 3 8 5 3 5 40 6 3 2 7 7柱面號(hào)柱面號(hào) 盤面號(hào)盤面號(hào) 塊號(hào)塊號(hào) 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3 一一. .死鎖的定義死鎖的定義例例1：兩輛車過單車道橋的僵局：兩輛車過單車道橋的僵局：3.3 死鎖的基本概念死鎖的基本概念例例2. 競(jìng)爭(zhēng)外部設(shè)備。設(shè)系統(tǒng)中有打印機(jī)、掃描儀競(jìng)爭(zhēng)外部設(shè)備。設(shè)系統(tǒng)中有打印機(jī)、掃描儀各一臺(tái)，進(jìn)程各一臺(tái)，進(jìn)程A、B的申請(qǐng)如下的申請(qǐng)如下：掃描儀掃描儀進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B占用占用請(qǐng)求請(qǐng)求阻塞阻塞死鎖打印機(jī)打印機(jī)一一. .死鎖的定義死鎖的定義3.3 死鎖死鎖3.3 死鎖的基本概念死鎖的基本概念 一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)

24、程中另一進(jìn)程一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的且永遠(yuǎn)無法釋放的資源，這種現(xiàn)象稱為進(jìn)程所占有的且永遠(yuǎn)無法釋放的資源，這種現(xiàn)象稱為進(jìn)程死鎖死鎖，這一組進(jìn)程就稱為這一組進(jìn)程就稱為死鎖進(jìn)程死鎖進(jìn)程。關(guān)于死鎖的一些結(jié)論：關(guān)于死鎖的一些結(jié)論： 參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程最少是兩個(gè) 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩如果死鎖發(fā)生，會(huì)浪費(fèi)大

25、量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。潰。一一. .死鎖的定義死鎖的定義3.3 死鎖死鎖3.3 死鎖的基本概念死鎖的基本概念產(chǎn)生死鎖的原因有兩點(diǎn)：產(chǎn)生死鎖的原因有兩點(diǎn)： (1)(1)競(jìng)爭(zhēng)資源：競(jìng)爭(zhēng)資源：為多個(gè)進(jìn)程所共享的資源不夠，引起為多個(gè)進(jìn)程所共享的資源不夠，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖；它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖； (2)(2)進(jìn)程推進(jìn)順序不當(dāng)：進(jìn)程推進(jìn)順序不當(dāng)：在進(jìn)程運(yùn)行過程中，請(qǐng)求資在進(jìn)程運(yùn)行過程中，請(qǐng)求資源和釋放資源的順序不當(dāng)，也會(huì)產(chǎn)生死鎖。源和釋放資源的順序不當(dāng)，也會(huì)產(chǎn)生死鎖。二二. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因3.3 死鎖死鎖3.3 死鎖的基本概念死鎖的基本概念1 1、競(jìng)爭(zhēng)資源引起的

26、死鎖、競(jìng)爭(zhēng)資源引起的死鎖可剝奪性資源：可剝奪性資源：是指系統(tǒng)中那些已被進(jìn)程占用但又可被其它是指系統(tǒng)中那些已被進(jìn)程占用但又可被其它進(jìn)程所搶占的系統(tǒng)資源。進(jìn)程所搶占的系統(tǒng)資源。 如處理機(jī)、內(nèi)存區(qū)等。如處理機(jī)、內(nèi)存區(qū)等。非剝奪性資源：非剝奪性資源：是指系統(tǒng)中那些已被進(jìn)程占用后便不能被其是指系統(tǒng)中那些已被進(jìn)程占用后便不能被其它進(jìn)程所搶占的系統(tǒng)資源。它進(jìn)程所搶占的系統(tǒng)資源。 如：打印機(jī)、掃描儀等。如：打印機(jī)、掃描儀等。一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因3.3 死鎖死鎖3.3 死鎖的基本概念死鎖的基本概念例例. 競(jìng)爭(zhēng)外部設(shè)備。設(shè)系統(tǒng)中有打印機(jī)、掃描儀各一臺(tái)，競(jìng)爭(zhēng)外部設(shè)備。設(shè)系統(tǒng)中有打印機(jī)、掃描儀各一臺(tái)

27、，進(jìn)程進(jìn)程A、B的申請(qǐng)如下的申請(qǐng)如下：掃描儀掃描儀進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B占用占用請(qǐng)求請(qǐng)求阻塞阻塞死鎖打印機(jī)打印機(jī)(1)競(jìng)爭(zhēng)非剝奪性資源的例子競(jìng)爭(zhēng)非剝奪性資源的例子 一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因1 1、競(jìng)爭(zhēng)資源引起的死鎖、競(jìng)爭(zhēng)資源引起的死鎖執(zhí)行順序執(zhí)行順序1：P1: Release(S1);Request(S3);P2: Release(S2);Request(S1); P3: Release(S3);Request(S2); 執(zhí)行順序執(zhí)行順序2：P1: Request(S3); Release(S1); P2: Request(S1); Release(S2); P3: Request

28、(S2); Release(S3); 進(jìn)程進(jìn)程P2進(jìn)程進(jìn)程P3進(jìn)程進(jìn)程P1臨時(shí)性資源S3臨時(shí)性資源S1臨時(shí)性資源S2請(qǐng)求產(chǎn)生產(chǎn)生請(qǐng)求產(chǎn)生請(qǐng)求(2)競(jìng)爭(zhēng)臨時(shí)性資源：競(jìng)爭(zhēng)臨時(shí)性資源： 臨時(shí)性資源臨時(shí)性資源是指由一個(gè)進(jìn)程產(chǎn)生的被另一進(jìn)程使用一短暫是指由一個(gè)進(jìn)程產(chǎn)生的被另一進(jìn)程使用一短暫時(shí)間后便無用的資源。也稱時(shí)間后便無用的資源。也稱消耗性資源消耗性資源。如消息如消息, ,中斷信號(hào)，同中斷信號(hào)，同步信號(hào)等步信號(hào)等不會(huì)不會(huì) “死鎖死鎖”“死鎖死鎖”（1）進(jìn)程推進(jìn)順序合法：）進(jìn)程推進(jìn)順序合法：如如按曲線按曲線 、和不會(huì)產(chǎn)生和不會(huì)產(chǎn)生“死鎖死鎖” 2. 進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖D

29、P2Req(S1)P2Req(S2)P1Req(S2)P1Req(S1)P1Rel(S2)P1Rel(S1)P2Rel(S2)P2Rel(S1)DP2P1一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因DP2Req(S1)P2Req(S2)P1Req(S2)P1Req(S1)P1Rel(S2)P1Rel(S1)P2Rel(S2)P2Rel(S1)D（2）進(jìn)程推進(jìn)順序非法：）進(jìn)程推進(jìn)順序非法：如如曲線，產(chǎn)生曲線，產(chǎn)生“死鎖死鎖”。 死鎖點(diǎn)死鎖點(diǎn)區(qū)域區(qū)域D D稱為稱為“死鎖區(qū)死鎖區(qū)”P2P12. 進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因二二. 產(chǎn)生死鎖的必要

30、條件產(chǎn)生死鎖的必要條件 1.互斥條件：互斥條件： 2.請(qǐng)求和保持請(qǐng)求和保持條件條件： 3.不剝奪不剝奪條件條件： 4.環(huán)路等待環(huán)路等待條件條件：資源分配圖資源分配圖 這四個(gè)必要條件中只要有一個(gè)條這四個(gè)必要條件中只要有一個(gè)條 件不滿足，都不會(huì)形成件不滿足，都不會(huì)形成“死鎖死鎖”P1P2R1R2資源請(qǐng)求邊資源請(qǐng)求邊資源分配邊資源分配邊3.3 死鎖的基本概念死鎖的基本概念l 預(yù)防與避免死鎖預(yù)防與避免死鎖l 檢測(cè)與解除死鎖檢測(cè)與解除死鎖3.4 處理死鎖的基本方法處理死鎖的基本方法一一. .預(yù)防死鎖：預(yù)防死鎖： 靜態(tài)分配資源：靜態(tài)分配資源：在作業(yè)調(diào)度時(shí)為選中的作業(yè)分配它所需要的在作業(yè)調(diào)度時(shí)為選中的作業(yè)分

31、配它所需要的所有資源，當(dāng)所有資源，當(dāng) 資源一旦分配給該作業(yè)后，在其整個(gè)運(yùn)行期資源一旦分配給該作業(yè)后，在其整個(gè)運(yùn)行期間這些資源為它獨(dú)占。間這些資源為它獨(dú)占。 缺點(diǎn)缺點(diǎn)：1）資源利用率低；）資源利用率低； 2）進(jìn)程的運(yùn)行可能被推遲；）進(jìn)程的運(yùn)行可能被推遲；一一.預(yù)防死鎖預(yù)防死鎖2、動(dòng)態(tài)預(yù)防死鎖的方法：、動(dòng)態(tài)預(yù)防死鎖的方法： 采用有序資源分配策略采用有序資源分配策略：將所有的系統(tǒng)資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)；將所有的系統(tǒng)資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)；所有進(jìn)程對(duì)資源的請(qǐng)求應(yīng)嚴(yán)格按資源序號(hào)遞增順序提出。所有進(jìn)程對(duì)資源的請(qǐng)求應(yīng)嚴(yán)格按資源序號(hào)遞增順序提出。例如：例如：1 1磁帶機(jī)，磁

32、帶機(jī)，2 2掃描儀，掃描儀，3 3打印機(jī)，打印機(jī)，4 4繪圖儀，繪圖儀，P1：申請(qǐng)申請(qǐng)2申請(qǐng)申請(qǐng)4P2：申請(qǐng)申請(qǐng)2申請(qǐng)申請(qǐng)4P3 P10優(yōu)點(diǎn)：優(yōu)點(diǎn)：較之前面兩種方法資源利用率高，系統(tǒng)吞吐量大。較之前面兩種方法資源利用率高，系統(tǒng)吞吐量大。缺點(diǎn)：缺點(diǎn)：(1)為系統(tǒng)中各種資源類型分配序號(hào)時(shí)，必須相對(duì)穩(wěn)定，為系統(tǒng)中各種資源類型分配序號(hào)時(shí)，必須相對(duì)穩(wěn)定， 從而限制了從而限制了 新設(shè)備的增加；新設(shè)備的增加； (2)會(huì)出現(xiàn)作業(yè)使用的資源順序與系統(tǒng)規(guī)定的順序不同的情況，造成資會(huì)出現(xiàn)作業(yè)使用的資源順序與系統(tǒng)規(guī)定的順序不同的情況，造成資 源的浪費(fèi)源的浪費(fèi)二二. 避免死鎖避免死鎖1、系統(tǒng)安全狀態(tài)、系統(tǒng)安全狀態(tài) （1

33、）安全狀態(tài)定義）安全狀態(tài)定義 所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)(稱稱P1, P2, , Pn序列為安全序列序列為安全序列)，來為每個(gè)進(jìn)程，來為每個(gè)進(jìn)程Pi分分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。則稱系統(tǒng)處于不安全狀態(tài)。 3.4 處理死鎖的基本方法處理死鎖的基本方法1、系統(tǒng)安全狀態(tài)、系統(tǒng)安全狀態(tài) （2）安全狀態(tài)之例）安全狀態(tài)之

34、例 我們通過一個(gè)例子來說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)我們通過一個(gè)例子來說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程程P1、 P2和和P3，共有，共有12臺(tái)磁帶機(jī)臺(tái)磁帶機(jī)。進(jìn)程。進(jìn)程P1總共要求總共要求10臺(tái)磁帶臺(tái)磁帶機(jī)，機(jī)，P2和和P3分別要求分別要求4臺(tái)和臺(tái)和9臺(tái)。假設(shè)在臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P1、P2和和P3已分別獲得已分別獲得5臺(tái)、臺(tái)、2臺(tái)和臺(tái)和2臺(tái)磁帶機(jī)，尚有臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如臺(tái)空閑未分配，如下表所示：下表所示： 進(jìn)進(jìn) 程程 最最 大大 需需 求求 T0時(shí)已時(shí)已 分分 配配還需要還需要可可 用用 P1P2P310495225273二二. 避免死鎖避免死鎖3.4 處理死鎖的

35、基本方法處理死鎖的基本方法1、系統(tǒng)安全狀態(tài)、系統(tǒng)安全狀態(tài) （3） 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全順序分配資源，則系統(tǒng)可能由安全狀態(tài)進(jìn)如果不按照安全順序分配資源，則系統(tǒng)可能由安全狀態(tài)進(jìn)入不安全狀態(tài)。入不安全狀態(tài)。例：例：假定系統(tǒng)有三個(gè)進(jìn)程假定系統(tǒng)有三個(gè)進(jìn)程P1、P2和和P3，有，有12臺(tái)磁帶機(jī)。臺(tái)磁帶機(jī)。進(jìn)程進(jìn)程 最大需求量最大需求量 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P3 9 2 在在T0時(shí)刻時(shí)刻P3又申請(qǐng)了一臺(tái)磁帶機(jī)，若將剩余又申請(qǐng)了一臺(tái)磁帶機(jī)，若將剩余3臺(tái)中的一臺(tái)分臺(tái)中的一臺(tái)分配給配給P3 則系統(tǒng)會(huì)進(jìn)入不安全狀態(tài)。則系統(tǒng)會(huì)進(jìn)

36、入不安全狀態(tài)。為什么？為什么？已分配已分配 還需要還需要 可用可用 5 5 2 2 2 3 6 二二. 避免死鎖避免死鎖3.4 處理死鎖的基本方法處理死鎖的基本方法2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 避免死鎖算法中最有代表性的算法是避免死鎖算法中最有代表性的算法是Dijkstra E.W 于于1968年提出的銀行家算法：年提出的銀行家算法：它的模型基于一個(gè)小城鎮(zhèn)的銀行它的模型基于一個(gè)小城鎮(zhèn)的銀行家，該算法可描述如下：假定一個(gè)銀行家擁有資金，數(shù)量為家，該算法可描述如下：假定一個(gè)銀行家擁有資金，數(shù)量為，被，被N個(gè)客戶共享。銀行家對(duì)客戶提出下列約束條件：個(gè)客戶共享。銀行家對(duì)客戶提出下

37、列約束條件：每個(gè)客戶必須預(yù)先說明自己所要求的最大資金量；每個(gè)客戶必須預(yù)先說明自己所要求的最大資金量；每個(gè)客戶每次提出部分資金量申請(qǐng)和獲得分配；每個(gè)客戶每次提出部分資金量申請(qǐng)和獲得分配；如果銀行滿足了某客戶對(duì)資金的最大需求量，那么，客戶如果銀行滿足了某客戶對(duì)資金的最大需求量，那么，客戶在資金運(yùn)作后，應(yīng)在有限時(shí)間內(nèi)全部歸還銀行。在資金運(yùn)作后，應(yīng)在有限時(shí)間內(nèi)全部歸還銀行。二二. 避免死鎖避免死鎖3.4 處理死鎖的基本方法處理死鎖的基本方法（1） 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 可利用資源向量可利用資源向量Availablem。 其中的每一個(gè)元素代表一類可利用的資源數(shù)目 Availabl

38、ej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 最大需求矩陣最大需求矩陣Max1.n,1.m 該矩陣定義了系統(tǒng)中n個(gè)進(jìn)程對(duì)m類資源的最大需求。 Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 二二. 避免死鎖避免死鎖3.4 處理死鎖的基本方法處理死鎖的基本方法 分配矩陣分配矩陣Allocation1.n,1.m 該矩陣表示系統(tǒng)中每個(gè)進(jìn)程當(dāng)前已分配到的每類資源數(shù)量。 Allocationi,j=K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。 需求矩陣需求矩陣Need1.n,1.m 該矩陣表示每個(gè)進(jìn)程尚需的各類資源數(shù)。Needi,j=K，

39、則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。 Needi,j=Maxi,j-Allocationi,j 請(qǐng)求向量請(qǐng)求向量Requesti of integer; 某進(jìn)程申請(qǐng)需要某類資源的資源數(shù)（1） 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 二二. 避免死鎖避免死鎖當(dāng)進(jìn)程當(dāng)進(jìn)程Pi提出資源申請(qǐng)?zhí)岢鲑Y源申請(qǐng)Requesti時(shí)，系統(tǒng)執(zhí)行下列步驟：時(shí)，系統(tǒng)執(zhí)行下列步驟： 若若RequestiNeedi,轉(zhuǎn)；轉(zhuǎn)；否則錯(cuò)誤返回； 若若RequestiAvailable，轉(zhuǎn)；否則，表示尚無足夠資，轉(zhuǎn)；否則，表示尚無足夠資源，源，Pi須等待；須等

40、待； 系統(tǒng)嘗試把資源分配給進(jìn)程系統(tǒng)嘗試把資源分配給進(jìn)程Pi，并修改以下數(shù)據(jù)結(jié)構(gòu)，并修改以下數(shù)據(jù)結(jié)構(gòu)： Available:= Allocationi:= Needi:= 執(zhí)行安全性算法：執(zhí)行安全性算法： 檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，則將資源分配給進(jìn)程則將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。等待。Available-Requesti;Allocationi+Requesti;Need

41、i-Requesti;（2） 銀行家算法描述銀行家算法描述2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 二二. 避免死鎖避免死鎖 設(shè)置兩個(gè)臨時(shí)向量：設(shè)置兩個(gè)臨時(shí)向量： 1）工作向量）工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available; 2） Finishn: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。 （3） 安全性算法描述安全性算法描述2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 二二.

42、避免死鎖避免死鎖從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： 1） Finishi=false; 2）Needi,jWorkj； 若找到，若找到， 執(zhí)行步驟執(zhí)行步驟 ， 否則，執(zhí)行步驟否則，執(zhí)行步驟 ； 當(dāng)進(jìn)程當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放獲得資源后，可順利執(zhí)行，直至完成，并釋放 出分配給它的資源，故應(yīng)執(zhí)行：出分配給它的資源，故應(yīng)執(zhí)行： Workj = Finishi = go to step ; 如果所有進(jìn)程的如果所有進(jìn)程的Finishi=true都滿足，都滿足， 則表示系統(tǒng)則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)處于安全狀

43、態(tài)；否則，系統(tǒng)處于不安全狀態(tài)Workj+Allocationi,j;true;（3） 安全性算法描述安全性算法描述2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 二二. 避免死鎖避免死鎖例例1： 假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源和三類資源A, B, C，各種資源的數(shù)量分別為，各種資源的數(shù)量分別為10、5、7，在，在T0時(shí)刻的資時(shí)刻的資源分配情況如圖所示。源分配情況如圖所示。 （1 1）T T0 0時(shí)刻的安全性；時(shí)刻的安全性；（2 2）P1P1請(qǐng)求資源：請(qǐng)求資源：Request1Request1（1 1，0 0，2 2）；）；A B CA

44、 B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源情況情況0 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 31 2 26 0 00 1 14 3 1 3 3 2P0P1P2P3P4（4） 銀行家算法舉例銀行家算法舉例2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖 WorkNeedAllocationWork+AllocationA B CA B CA B CA B C進(jìn)程進(jìn)程資源資源情況情況1 2 20 1 14 3 16 0 07 4 33 3 25 3 27 4 37 4 510

45、 4 72 0 02 1 10 0 23 0 20 1 0 5 3 27 4 37 4 510 4 710 5 7P1P3P4P2P0 truetruetruetruetrueFinishA B CA B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源情況情況0 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 31 2 26 0 00 1 14 3 1 3 3 2P0P1P2P3P4由于由于T0時(shí)刻存在安全序列時(shí)刻存在安全序列P1, P3, P4, P2, P0,故此時(shí)系統(tǒng)是安全的。故此時(shí)系統(tǒng)

46、是安全的。A B CA B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源情況情況0 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 31 2 26 0 00 1 14 3 1 3 3 2P0P1P2P3P4（2）當(dāng)）當(dāng)P1請(qǐng)求資源：請(qǐng)求資源：Request1（1，0，2）時(shí)：）時(shí)： Request1（1，0，2） Need1 （1，2，2） Request1（1，0，2） Available（3，3，2） 試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。 對(duì)試分配后狀態(tài)進(jìn)行安全性檢查

47、：對(duì)試分配后狀態(tài)進(jìn)行安全性檢查： 3, 0, 20, 2, 02, 3, 0 WorkNeedAllocationWork+AllocationA B CA B CA B CA B C進(jìn)程進(jìn)程資源資源情況情況0 2 00 1 14 3 16 0 07 4 32 3 05 3 27 4 37 4 510 4 73 0 22 1 10 0 23 0 20 1 0 5 3 27 4 37 4 510 4 710 5 7P1P3P4P2P0 truetruetruetruetrueFinishA B CA B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源

48、情況情況0 1 03 0 23 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 30 2 06 0 00 1 14 3 1 2 3 0P0P1P2P3P4由于此時(shí)存在安全序列由于此時(shí)存在安全序列P1, P3, P4, P2, P0,故系統(tǒng)是安全的，可為故系統(tǒng)是安全的，可為P1分配上述資源。分配上述資源。A B CA B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源情況情況0 1 03 0 23 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 30 2 06 0 00 1 14

49、 3 1 2 3 0P0P1P2P3P4（3）當(dāng)）當(dāng)P4請(qǐng)求資源：請(qǐng)求資源：Request4（3，3，0）時(shí)：）時(shí)： Request4（3，3，0） Need4 （4，3，1）成立；）成立； Request4（3，3，0） Available（2，3，0）不成立，）不成立，故讓故讓P4等待。等待。 A B CA B CA B CA B CAvailableNeedAllocationMax 進(jìn)程進(jìn)程資源資源情況情況0 1 03 0 23 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 37 4 30 2 06 0 00 1 14 3 1 2 3 0P0P1P2P3P4

50、（4）當(dāng)）當(dāng)P0請(qǐng)求資源：請(qǐng)求資源：Request0（0，2，0）時(shí)：）時(shí)： Request0（0，2，0） Need0 （7，4，3）成立；）成立； Request0（0，2，0） Available（2，3，0）成立；）成立； 試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。 對(duì)試分配后的狀態(tài)進(jìn)行安全性檢查：由于對(duì)試分配后的狀態(tài)進(jìn)行安全性檢查：由于Available（2,1,0）已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，所以不能為已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，所以不能為P0分配資源，而應(yīng)恢復(fù)原來的狀態(tài)，讓分配資源，而應(yīng)恢復(fù)原來的狀態(tài)，讓P0等待。等待。 0,

51、 3, 07, 2, 32, 1, 0課堂討論課堂討論：假設(shè)有兩類資源假設(shè)有兩類資源A和和B，A類資源類資源10個(gè)，個(gè)，B類資源類資源14個(gè)，當(dāng)前個(gè)，當(dāng)前系統(tǒng)的資源分配情況如下表所示。根據(jù)分配表，回答下面系統(tǒng)的資源分配情況如下表所示。根據(jù)分配表，回答下面兩個(gè)問題：兩個(gè)問題： 請(qǐng)?zhí)顚懴到y(tǒng)的需求矩陣。請(qǐng)?zhí)顚懴到y(tǒng)的需求矩陣。 使用銀行家的算法，確定系統(tǒng)是否死鎖狀態(tài)？如果不使用銀行家的算法，確定系統(tǒng)是否死鎖狀態(tài)？如果不死鎖給出安全序列，如果死鎖給出死鎖的四個(gè)條件。死鎖給出安全序列，如果死鎖給出死鎖的四個(gè)條件。進(jìn)程進(jìn)程AllocationA BMaxA BNeedA BAvailableA BP02 02 42 7P13 210 2P21 45 4P32 13 1P40 04 20 47 04 01 04 2需求矩陣如下：需求矩陣如下： 進(jìn)程進(jìn)程 Need A B P0 0 4 P1 7 0 P2 4 0 P3 1 0 P4 4 2答：系統(tǒng)處于安全狀態(tài)。答：系統(tǒng)處于安全狀態(tài)。安全序列為：安全序列為