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

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

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

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

4、存儲器 主存主存 設(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)容 資源名、資源類型、最小分配單位的大資源名、資源類型、最小分配單位的大 小、地址、分配標志、描述器鏈接信息、小、地址、分配標志、描述器鏈接信息、 存取權(quán)限、密級、存取時間存取權(quán)限、密

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

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

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

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

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

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

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

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

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

14、3.2 資源管理的機制和策略資源管理的機制和策略（1 1）先來先服務(wù)）先來先服務(wù)FCFS(First-Come, First Served)FCFS(First-Come, First Served) 假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號磁道，磁頭正向磁道號增加的方向號磁道，磁頭正向磁道號增加的方向（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：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三三. .磁盤存儲器管理磁盤存儲器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號磁道，磁頭號磁道，磁頭正向磁道

16、號增加正向磁道號增加的方向的方向（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：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）會產(chǎn)生饑餓現(xiàn)象；）會產(chǎn)生饑餓現(xiàn)象； （3 3）影響磁盤的機械壽命。）影響磁盤的機械壽命。（2 2）最短尋道時間優(yōu)先算法）最短尋道時間優(yōu)先算法SSTFSSTF三三. .磁盤存儲器管理磁盤存儲器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：（3 3）掃描）掃描(SCAN)(SCAN)算法算法 ：（又稱為電梯算法）（又稱為電梯算法） （1）欲訪問磁道與當(dāng)前磁道的距離；）欲訪問磁道與當(dāng)前磁道的

18、距離； （2）磁頭當(dāng)前的移動方向。）磁頭當(dāng)前的移動方向。假設(shè)當(dāng)前磁道在假設(shè)當(dāng)前磁道在100100號磁道，磁頭正向磁道號增加的方向號磁道，磁頭正向磁道號增加的方向（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：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)三三. .磁盤存儲器管理磁盤存儲器管理5.5.移臂調(diào)度算法：移臂調(diào)度算法：（4 4） N-Step-SCAN N-Step-SCAN算法算法 “磁臂粘著磁臂粘著”現(xiàn)象現(xiàn)象算法思想：將磁盤請求隊列分成若干個長度為算法思想：將磁盤請求隊列分成若干個長度為N的子隊列，磁的子隊列，磁盤調(diào)度將按盤調(diào)度將按FCFS算法依次處理這些子隊列；算法依

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

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

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

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

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

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

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

27、，進程進程A、B的申請如下的申請如下：掃描儀掃描儀進程進程A進程進程B占用占用請求請求阻塞阻塞死鎖打印機打印機(1)競爭非剝奪性資源的例子競爭非剝奪性資源的例子 一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因1 1、競爭資源引起的死鎖、競爭資源引起的死鎖執(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); 進程進程P2進程進程P3進程進程P1臨時性資源S3臨時性資源S1臨時性資源S2請求產(chǎn)生產(chǎn)生請求產(chǎn)生請求(2)競爭臨時性資源：競爭臨時性資源： 臨時性資源臨時性資源是指由一個進程產(chǎn)生的被另一進程使用一短暫是指由一個進程產(chǎn)生的被另一進程使用一短暫時間后便無用的資源。也稱時間后便無用的資源。也稱消耗性資源消耗性資源。如消息如消息, ,中斷信號，同中斷信號，同步信號等步信號等不會不會 “死鎖死鎖”“死鎖死鎖”（1）進程推進順序合法：）進程推進順序合法：如如按曲線按曲線 、和不會產(chǎn)生和不會產(chǎn)生“死鎖死鎖” 2. 進程推進順序不當(dāng)引起的死鎖進程推進順序不當(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）進程推進順序非法：）進程推進順序非法：如如曲線，產(chǎn)生曲線，產(chǎn)生“死鎖死鎖”。 死鎖點死鎖點區(qū)域區(qū)域D D稱為稱為“死鎖區(qū)死鎖區(qū)”P2P12. 進程推進順序不當(dāng)引起的死鎖進程推進順序不當(dāng)引起的死鎖一一. .產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因二二. 產(chǎn)生死鎖的必要

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

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

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

33、）安全狀態(tài)定義）安全狀態(tài)定義 所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序(P1, P2, ，Pn)(稱稱P1, P2, , Pn序列為安全序列序列為安全序列)，來為每個進程，來為每個進程Pi分分配其所需資源，直至滿足每個進程對資源的最大需求，使每個配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(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、例 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程程P1、 P2和和P3，共有，共有12臺磁帶機臺磁帶機。進程。進程P1總共要求總共要求10臺磁帶臺磁帶機，機，P2和和P3分別要求分別要求4臺和臺和9臺。假設(shè)在臺。假設(shè)在T0時刻，進程時刻，進程P1、P2和和P3已分別獲得已分別獲得5臺、臺、2臺和臺和2臺磁帶機，尚有臺磁帶機，尚有3臺空閑未分配，如臺空閑未分配，如下表所示：下表所示： 進進 程程 最最 大大 需需 求求 T0時已時已 分分 配配還需要還需要可可 用用 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)進如果不按照安全順序分配資源，則系統(tǒng)可能由安全狀態(tài)進入不安全狀態(tài)。入不安全狀態(tài)。例：例：假定系統(tǒng)有三個進程假定系統(tǒng)有三個進程P1、P2和和P3，有，有12臺磁帶機。臺磁帶機。進程進程 最大需求量最大需求量 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P3 9 2 在在T0時刻時刻P3又申請了一臺磁帶機，若將剩余又申請了一臺磁帶機，若將剩余3臺中的一臺分臺中的一臺分配給配給P3 則系統(tǒng)會進入不安全狀態(tài)。則系統(tǒng)會進

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

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

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

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

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

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

42、避免死鎖避免死鎖從進程集合中找到一個能滿足下述條件的進程：從進程集合中找到一個能滿足下述條件的進程： 1） Finishi=false; 2）Needi,jWorkj； 若找到，若找到， 執(zhí)行步驟執(zhí)行步驟 ， 否則，執(zhí)行步驟否則，執(zhí)行步驟 ； 當(dāng)進程當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放獲得資源后，可順利執(zhí)行，直至完成，并釋放 出分配給它的資源，故應(yīng)執(zhí)行：出分配給它的資源，故應(yīng)執(zhí)行： Workj = Finishi = go to step ; 如果所有進程的如果所有進程的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)中有五個進程假定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源和三類資源A, B, C，各種資源的數(shù)量分別為，各種資源的數(shù)量分別為10、5、7，在，在T0時刻的資時刻的資源分配情況如圖所示。源分配情況如圖所示。 （1 1）T T0 0時刻的安全性；時刻的安全性；（2 2）P1P1請求資源：請求資源：Request1Request1（1 1，0 0，2 2）；）；A B CA

44、 B CA B CA B CAvailableNeedAllocationMax 進程進程資源資源情況情況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進程進程資源資源情況情況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 進程進程資源資源情況情況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時刻存在安全序列時刻存在安全序列P1, P3, P4, P2, P0,故此時系統(tǒng)是安全的。故此時系統(tǒng)

46、是安全的。A B CA B CA B CA B CAvailableNeedAllocationMax 進程進程資源資源情況情況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請求資源：請求資源：Request1（1，0，2）時：）時： 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)。 對試分配后狀態(tài)進行安全性檢查

47、：對試分配后狀態(tài)進行安全性檢查： 3, 0, 20, 2, 02, 3, 0 WorkNeedAllocationWork+AllocationA B CA B CA B CA B C進程進程資源資源情況情況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 進程進程資源資源

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由于此時存在安全序列由于此時存在安全序列P1, P3, P4, P2, P0,故系統(tǒng)是安全的，可為故系統(tǒng)是安全的，可為P1分配上述資源。分配上述資源。A B CA B CA B CA B CAvailableNeedAllocationMax 進程進程資源資源情況情況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請求資源：請求資源：Request4（3，3，0）時：）時： 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 進程進程資源資源情況情況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請求資源：請求資源：Request0（0，2，0）時：）時： 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)。 對試分配后的狀態(tài)進行安全性檢查：由于對試分配后的狀態(tài)進行安全性檢查：由于Available（2,1,0）已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，所以不能為已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(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個，個，B類資源類資源14個，當(dāng)前個，當(dāng)前系統(tǒng)的資源分配情況如下表所示。根據(jù)分配表，回答下面系統(tǒng)的資源分配情況如下表所示。根據(jù)分配表，回答下面兩個問題：兩個問題： 請?zhí)顚懴到y(tǒng)的需求矩陣。請?zhí)顚懴到y(tǒng)的需求矩陣。 使用銀行家的算法，確定系統(tǒng)是否死鎖狀態(tài)？如果不使用銀行家的算法，確定系統(tǒng)是否死鎖狀態(tài)？如果不死鎖給出安全序列，如果死鎖給出死鎖的四個條件。死鎖給出安全序列，如果死鎖給出死鎖的四個條件。進程進程AllocationA BMaxA BNeedA BAvailableA BP02 02 42 7P13 210 2P21 45 4P32 13 1P40 04 20 47 04 01 04 2需求矩陣如下：需求矩陣如下： 進程進程 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)。安全序列為：安全序列為