醫(yī)軟11大三第一學(xué)期第5章1

1、第五章 操作系統(tǒng)的資源管理操作系統(tǒng)的資源管理5.1資源管理的機(jī)制與策略5.2死鎖及其解決方法5.3處理機(jī)管理（2學(xué)時(shí)）5.4主存管理（2學(xué)時(shí)）5.5設(shè)備管理（2學(xué)時(shí)）5.6文件系統(tǒng)（2學(xué)時(shí)）1操作系統(tǒng)的資源管理 主要內(nèi)容5.1資源管理的機(jī)制與策略5.2死鎖及其解決方法操作系統(tǒng)的資源管理 (1) 2資源管理概述資源分配機(jī)構(gòu)和策略死鎖41. 資源管理功能資源數(shù)據(jù)結(jié)構(gòu)的描述 包含資源的物理名、邏輯名、類型、地址、分配狀態(tài)等信息。確定資源的分配原則 (調(diào)度原則) 決定資源應(yīng)分給誰，何時(shí)分配，分配多少等問題。實(shí)施資源分配 執(zhí)行資源分配；資源收回工作。存取控制和安全保護(hù) 對(duì)資源的存取進(jìn)行控制并對(duì)資源實(shí)施安

2、全保護(hù)措施。操作系統(tǒng)的資源管理 (1) 5.1.1資源管理概述 52. 資源的靜態(tài)分配和動(dòng)態(tài)分配資源的靜態(tài)分配 系統(tǒng)對(duì)作業(yè)一級(jí)采用資源靜態(tài)分配方法。 系統(tǒng)在調(diào)度作業(yè)時(shí)，根據(jù)作業(yè)所需資源進(jìn)行分配；并在作 業(yè)運(yùn)行完畢 時(shí)，收回所分配的全部資源。這種分配通常稱 為資源的靜態(tài)分配。資源的動(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)行資源 的動(dòng)態(tài)分配和回收。這種分配通常稱為資源的動(dòng)態(tài)分配。操作系統(tǒng)的資源管理 (1) 5.1.1資源管理概述 105.1.4. 資源分配策略常用的資源分配策略先請(qǐng)求先服務(wù)每一個(gè)新產(chǎn)生的請(qǐng)求均排在隊(duì)尾；當(dāng)資源可用時(shí)，取隊(duì)首元素，并

3、滿足其需要。 排序原則：按請(qǐng)求的先后次序排序。 表頭按請(qǐng)求的先后次序先后按自然順序排列的隊(duì)列操作系統(tǒng)的資源管理 (1) 資源分配機(jī)構(gòu)與策略 11優(yōu)先調(diào)度 對(duì)每一個(gè)進(jìn)程指定一個(gè)優(yōu)先級(jí)；每一個(gè)新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插到相應(yīng)的位置；當(dāng)資源可用時(shí)，取隊(duì)首元素，并滿足其需要。 排序原則：按優(yōu)先級(jí)的高低排序。 表頭按按優(yōu)先級(jí)的高低排序高低按優(yōu)先級(jí)高低排列的就緒隊(duì)列操作系統(tǒng)的資源管理 (1) 資源分配機(jī)構(gòu)與策略 12針對(duì)設(shè)備特性的調(diào)度策略調(diào)度的目標(biāo) 例如： 當(dāng)有大量I/O請(qǐng)求時(shí)，降低完成這些I/O服務(wù)的總時(shí)間。 操作系統(tǒng)的資源管理 (1) 資源分配機(jī)構(gòu)與策略 下面發(fā)生了什么情況？10進(jìn)程P1 進(jìn)程P

4、2 請(qǐng)求資源R1 請(qǐng)求資源R2 請(qǐng)求資源R2 請(qǐng)求資源R1 釋放資源R1 釋放資源R2 釋放資源R2 釋放資源R1 R1R2 兩個(gè)進(jìn)程死鎖的典型情況 15死鎖的例設(shè)備共享 進(jìn)程 p1、p2共享一臺(tái)打印機(jī)和一臺(tái)輸入機(jī) 時(shí)刻 t1：進(jìn)程 p1 占用打印機(jī)， 進(jìn)程 p2 占用輸入機(jī)； 時(shí)刻 t2：進(jìn)程 p1 又請(qǐng)求輸入機(jī)， 進(jìn)程 p2 又請(qǐng)求打印機(jī)。 1. 什么是死鎖操作系統(tǒng)的資源管理 (1) 5.2死鎖 16用信號(hào)燈的P、V操作描述死鎖 設(shè)進(jìn)程p1與進(jìn)程p2共享一臺(tái)打印機(jī)(r1) 和一臺(tái)輸入機(jī)(r2)， 用信號(hào)燈的p、v操作表示資源的申請(qǐng)和釋放。 信號(hào)燈設(shè)置 s1：表示r1可用，初值為1 s2：表

5、示r2可用，初值為1 討論兩種資源請(qǐng)求序列，哪種情況可能產(chǎn)生互相死等的 局面。操作系統(tǒng)的資源管理 (1) 死鎖 17用信號(hào)燈的P、V操作描述死鎖 進(jìn)程p1 進(jìn)程p2 進(jìn)程p1 進(jìn)程p2 p(s1)； p(s2)； p(s1)； p(s2)； 占用r1 占用r2 占用r1 占用r2 v(s1)； v(s2)； p(s2)； p(s1)； 又占用r2 又占用r1 p(s2)； p(s1)； 占用r2 占用r1 v(s1)； v(s2)；v(s2)； v(s1)； v(s2)； v(s1)； 操作系統(tǒng)的資源管理 (1) 死鎖 死鎖啦！18什么是死鎖在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程持有某種 資源而

6、又都等待著別的進(jìn)程釋放它或它們現(xiàn)在保持 著的資源，否則就不能向前推進(jìn)。此時(shí)，稱這一組 進(jìn)程產(chǎn)生了死鎖。2. 死鎖的起因和條件引起死鎖的原因系統(tǒng)資源不足進(jìn)程推進(jìn)順序非法操作系統(tǒng)的資源管理 (1) 死鎖 19死鎖圖解N0A1B1C1D1A2B2C2D2P1進(jìn)程P2進(jìn)程A1： p1 request (r1) B1： p1 request (r2) C1： p1 release (r1) D1： p1 release (r2) A2： p2 request (r2) B2： p2 request (r1) C2： p2 release (r2) D2： p2 release (r1)操作系統(tǒng)的資源管理

7、 (1) 死鎖 20互斥條件涉及的資源是非共享的，即為臨界資源。不剝奪條件進(jìn)程所獲得的資源在未使用完畢之前，不能被其 他進(jìn)程強(qiáng)行奪走。產(chǎn)生死鎖的必要條件操作系統(tǒng)的資源管理 (1) 死鎖 21部分分配進(jìn)程每次申請(qǐng)它所需要的一部分資源。在等待一新 資源的同時(shí)，進(jìn)程繼續(xù)占用已分配到的資源。環(huán)路條件存在一種進(jìn)程的循環(huán)鏈，鏈中的每一個(gè)進(jìn)程已獲得 的資源同時(shí)被鏈中下一個(gè)進(jìn)程所請(qǐng)求。操作系統(tǒng)的資源管理 (1) 死鎖 產(chǎn)生死鎖的必要條件3.處理死鎖的基本方法破壞產(chǎn)生死鎖的四個(gè)必要條件之一(1) 預(yù)防死鎖。 (2) 避免死鎖。 (3) 檢測(cè)死鎖。(4) 解除死鎖。(5)忽略不見。234. 死鎖的預(yù)防靜態(tài)預(yù)防死鎖

8、的方法在作業(yè)調(diào)度時(shí)為選中的作業(yè)分配它所需要的所有資 源，當(dāng)資源一旦分配給該作業(yè)后，在其整個(gè)運(yùn)行期 間這些資源為它獨(dú)占。動(dòng)態(tài)預(yù)防死鎖的方法避免死鎖有序資源分配法系統(tǒng)中所有資源都給定一個(gè)唯一的編號(hào)，所有分配請(qǐng) 求必須以上升的次序進(jìn)行。當(dāng)遵守上升次序的規(guī)則 時(shí)，若資源可用，則予以分配；否則，請(qǐng)求者等待。銀行家算法 操作系統(tǒng)的資源管理 (1) 死鎖 20為了說明死鎖避免的策略，我們把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，引入了安全狀態(tài)的定義：所謂安全狀態(tài)是指如果系統(tǒng)中的所有進(jìn)程能夠按照某一種次序依次執(zhí)行完，則說系統(tǒng)處于安全狀態(tài)，否則稱系統(tǒng)處于不安全狀態(tài)。 只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。

9、因此，避免死鎖的實(shí)質(zhì)在于如何保證系統(tǒng)處于安全狀態(tài)。1）系統(tǒng)安全狀態(tài)避免死鎖-銀行家算法詳解2）安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示： 在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。避免死鎖-銀行家算法詳解223）利用銀行家算法避免死鎖 最具有代表性的避免死鎖的算法稱為銀行家算法。這種算法要求事先知道每個(gè)進(jìn)程對(duì)資源的最大需求量。 基本思想：當(dāng)一個(gè)新進(jìn)

10、程進(jìn)入系統(tǒng)時(shí)，它必須申明其資源的最大需求量，即每個(gè)資源類各需多少資源，當(dāng)進(jìn)程發(fā)出資源申請(qǐng)命令而且系統(tǒng)能夠滿足該請(qǐng)求時(shí)，在分配資源前，系統(tǒng)先要進(jìn)行一個(gè)序列檢查，以判斷如果分配資源，系統(tǒng)的狀態(tài)是否為安全，如果安全則分配資源，并讓申請(qǐng)者繼續(xù)執(zhí)行；否則，不分配資源，并讓申請(qǐng)者等待。避免死鎖-銀行家算法詳解23 銀行家算法是通過動(dòng)態(tài)地檢測(cè)系統(tǒng)中資源分配情況和進(jìn)程對(duì)資源的需求情況來決定如何分配資源的，在能確保系統(tǒng)處于安全狀態(tài)時(shí)才把資源分配給申請(qǐng)者，從而避免系統(tǒng)發(fā)生死鎖。 避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例假定系統(tǒng)中有5個(gè)進(jìn)程 P0、P1、P2、P3、P4和三種類型的資源A、B、C，數(shù)量分別

11、為10、5、7，在T0時(shí)刻的資源分配情況如下所示。 資源情況進(jìn)程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例T0時(shí)刻的安全性利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析，可得如下所示的T0時(shí)刻的安全性分析。 避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例T0

12、時(shí)刻的安全性檢查：Need0：7,4,3 Need1：1,2,2 Need2：6,0,0 Need3：0,1,1 Need4：4,3,1Alloc0： 0,1,0 Alloc1： 2,0,0 Alloc2：3,0,2 Alloc3： 2,1,1 Alloc4：0,0,2Avail 332 true true true true true Finish 5 3 2 2 0 01 2 2 3 3 2 P17 5 5 0 1 07 4 37 4 5 P010 5 7 3 0 2 6 0 07 5 5 P2 7 4 5 0 0 2 4 3 1 7 4 3 P4 A B C A B CA B CA B

13、C 7 4 3 2 1 1 0 1 1 5 3 2 P3Work+Alloc AllocNeed Work 資源情況進(jìn)程避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例T0時(shí)刻是安全的從上述分析得知，T0時(shí)刻存在著一個(gè)安全序列，故系統(tǒng)是安全的。避免死鎖-銀行家算法詳解4.死鎖的避免銀行家算法例P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1 (1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：1）Request1(1，0，2) Need1(1，2，2)2）Request1(1，0，2) Available(3，3，2)3）系統(tǒng)先假定可為P1分配資源，并修改Available、Allocation1 、N

14、eed1向量，由此形成的資源變化情況如下所示。 避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例4）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全，可得如下所示的安全性分析。 資源情況進(jìn)程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 2 3 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1為P1試分配資源后避免死鎖-銀行家算法詳解4.死鎖的避免銀行家算法例P1申請(qǐng)資源后的安全性

15、檢查：Need0：7,4,3 Need1：0,2,0 Need2：6,0,0 Need3：0,1,1 Need4：4,3,1Alloc0：1,1,0 Alloc1：3,0,2 Alloc2： 3,0,2 Alloc3： 2,1,1 Alloc4：0,0,2Avail 230 true true true true true Finish 5 3 2 3 0 20 2 0 2 3 0 P110 5 7 3 0 26 0 07 5 5 P27 5 5 0 1 0 7 4 37 4 5 P0 7 4 5 0 0 2 4 3 1 7 4 3 P4 A B C A B CA B CA B C 7 4 3

16、 2 1 1 0 1 1 5 3 2 P3Work+Alloc Alloc Need Work資源情況進(jìn)程避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例可以為P1分配資源：從上述分析得知，可以找到安全序列，系統(tǒng)安全，可以分配。避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例P4請(qǐng)求資源P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：1）Request4(3，3，0) Need4(4，3，1)2）Request4(3，3，0) Available(2，3，0)，讓P4等待。避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例P0請(qǐng)求資源P0發(fā)出請(qǐng)求向量Request

17、0 (0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：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ù)，如下所示。 避免死鎖-銀行家算法詳解4）死鎖的避免銀行家算法例4）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。從上表中可以看出，可用資源Available（2，1，0 ）已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。 資源情況進(jìn)程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0

18、3 0 7 2 3 2 1 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1為P0試分配資源后避免死鎖-銀行家算法詳解5. 銀行家算法實(shí)現(xiàn)1）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有R j類資源K個(gè)。(2) 最大需求矩陣Max。這是一個(gè)nm的矩陣，

19、它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 避免死鎖-銀行家算法詳解(3) 分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得R j類資源的數(shù)目為K。(4) 需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要R j類資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣間存在下述關(guān)系：Needi, j=Maxi, j-Allocationi, j 避免

20、死鎖-銀行家算法詳解2）銀行家算法設(shè)Request i是進(jìn)程Pi的請(qǐng)求向量，如果Request ij=K，表示進(jìn)程P i需要K個(gè)R j類型的資源。當(dāng)P i發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1) 如果Request ijNeedi,j，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。(2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。 避免死鎖-銀行家算法詳解(3) 系統(tǒng)試探著把資源分配給進(jìn)程P i，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej:= Availablej-Request ij；Allocationi,j:= Allocationi,j+Request ij；Needi,j:= Needi