1、第5章 資源分配與調(diào)度,主要內(nèi)容： 1資源管理概述 2資源分配機(jī)構(gòu) 3資源分配策略 4死鎖,51概述,實(shí)際上，操作系統(tǒng)進(jìn)行資源管理時(shí)，可以采用某種技術(shù)，使一些相互競爭的進(jìn)程共享有的限資源。,有限資源,眾多的請求分配資源,如何滿足？,511資源管理的目的和任務(wù),1 資源管理的目的 為計(jì)算機(jī)用戶提供一種簡單而有效地使用資源的方法，充分發(fā)揮各種資源的作用。其應(yīng)達(dá)到的目的是： 1） 保證資源的高利用率； 2） 在“合理”的時(shí)間內(nèi)使所有用戶有獲得所需資源的機(jī)會； 3） 對不可共享的資源施行互斥； 4） 防止由資源分配不當(dāng)而引起的死鎖。,2 資源管理的任務(wù) 1）解決資源分配問題； 2）資源分配中防止出現(xiàn)死

2、鎖； 3）解決資源的存取、使用方法問題； 4）提供資源的存取的控制和實(shí)施安全保護(hù)措施。,512資源的分類方法,1 物理和程序資源 2 單入口和多入口資源 3 等同資源 4 虛擬資源,513資源管理的的機(jī)構(gòu)和策略 機(jī)構(gòu) 包括描述資源的數(shù)據(jù)結(jié)構(gòu)、資源共享和互斥的技術(shù)等。 策略 給出資源管理的的機(jī)構(gòu)的使用方法，即給出資源的使用方法。,52資源分配機(jī)制,521資源描述器 1描述各類資源的最小分配單位的數(shù)據(jù)結(jié)構(gòu)稱為資源描述器rd（resource descriptor 2.資源描述器rd的內(nèi)容(見左)：,522資源信息塊rid (resource information block),53資源分配策略,

3、531概述 對計(jì)算機(jī)資源進(jìn)行分配，我們一般考慮三方面的情況： 1 如何管理請求資源的隊(duì)列； 2 如何對等同資源的選擇； 3 如何確定實(shí)施資源分配時(shí)機(jī) （1） 處理機(jī)空閑； （2） 存儲區(qū)釋放為空閑區(qū)； （3）外部設(shè)備發(fā)生中斷；,532先請求先服務(wù)FIFO（First In First Out）,按請求的先后次序,先,后,533優(yōu)先調(diào)度1（優(yōu)先級高為先）,單就緒隊(duì)列,533優(yōu)先調(diào)度2（優(yōu)先級高為先）,多就緒隊(duì)列,優(yōu)先級,高,534針對設(shè)備特性的調(diào)度,硬盤圖示,534針對設(shè)備特性的調(diào)度（實(shí)例）,例如，對磁盤同時(shí)有5個(gè)訪問請求如左表示。,OK?,移臂調(diào)度：,改進(jìn)1：如果當(dāng)前移動臂位于1號柱面，按右表

4、順序訪問，則移動臂將從1號柱面移到2 號柱面，再移到5 號柱面，然后到40號柱面。,移臂調(diào)度：在滿足一個(gè)磁盤請求時(shí)，總是選取與當(dāng)前移動臂前進(jìn)方向上最短的那個(gè)請求，使移臂距離最短。,旋轉(zhuǎn)調(diào)度,改進(jìn)2：由于5 號柱面要進(jìn)行3次訪問，所以可以調(diào)整訪問順序，減少旋轉(zhuǎn)圈數(shù)。,旋轉(zhuǎn)調(diào)度：在滿足一個(gè)磁盤請求時(shí)，總是選取與當(dāng)前讀寫磁頭旋轉(zhuǎn)方向上最近的那個(gè)請求，使旋轉(zhuǎn)圈數(shù)最少。,54死鎖（deadlock ）,541死鎖的概念 死鎖是兩個(gè)或多個(gè)進(jìn)程無止境地等候著永遠(yuǎn)不會成立的條件的一種系統(tǒng)狀態(tài)。也可以說，死鎖是兩個(gè)或兩個(gè)以上的進(jìn)程中的每一個(gè)都在等待其中另一個(gè)進(jìn)程釋放資源而被封鎖，它們都無法向前推進(jìn)，這種現(xiàn)象稱為

5、死鎖。,死鎖的表示,死鎖可以用有向圖來表示，有向圖形成環(huán)路則形成死鎖。例如，有P1，P2兩個(gè)進(jìn)程，共享一臺打印機(jī)資源R1和一臺輸入機(jī)R2，在工作使用時(shí)，共享資源被獨(dú)占。死鎖的有向示意圖,例 進(jìn)程推進(jìn)順序不當(dāng)產(chǎn)生死鎖。 設(shè)系統(tǒng)有打印機(jī)、讀卡機(jī)各一臺，它們被進(jìn)程和共享。兩個(gè)進(jìn)程并發(fā)執(zhí)行，它們按下列次序請求和釋放資源：,請求 讀卡機(jī),請求 打印機(jī),釋放 讀卡機(jī),釋放 打印機(jī),請求 打印機(jī),請求 讀卡機(jī),釋放 讀卡機(jī),釋放 打印機(jī),進(jìn)程,進(jìn)程Q,說明： 由于進(jìn)程P 和Q 執(zhí)行時(shí)，相對速度無法預(yù)知，當(dāng)出現(xiàn)進(jìn)程占用了讀卡機(jī)，進(jìn)程占用了打印機(jī)后，進(jìn)程又請求打印機(jī)，但因打印機(jī)被進(jìn)程占用，故進(jìn)程處于等待資源狀態(tài)

6、； 這時(shí)，進(jìn)程執(zhí)行，它又請求讀卡機(jī)，但因讀卡機(jī)被進(jìn)程占用而也只好處于等待資源狀態(tài)。 它們分別等待對方占用的資源，致使無法結(jié)束這種等待，產(chǎn)生了死鎖。 但是如果它們速度有快有慢，避免了上述僵局是可以不產(chǎn)生死鎖的。,例 PV 操作使用不當(dāng)產(chǎn)生死鎖。 設(shè)進(jìn)程Q1 和Q2 共享兩個(gè)資源r1 和r2，s1 和s2 是分別代表資源r1 和r2 能否被使用的信號量。 假定兩個(gè)進(jìn)程都要求使用兩個(gè)資源，由于資源是共享的，必須互斥使用，所以s1 和s2 的初值均為1。它們的程序編制如下：,進(jìn)程Q1 P(s1); 使用r1; P(s2); 使用r2; V(s1); 釋放r1; V(s2); 釋放r2; ,進(jìn)程Q2 P

7、(s2); 使用r2 P(s1); 使用r1 V(s2); 釋放r2; V(s1); 釋放r1; ,產(chǎn)生死鎖嗎？,(分析)由于Q1 和Q2 并發(fā)執(zhí)行，于是可能產(chǎn)生這樣的情況： 進(jìn)程Q1 執(zhí)行了P(s1)后，在執(zhí)行P(s2)之前，進(jìn)程Q2 執(zhí)行了P(s2)，當(dāng)進(jìn)程Q1 再執(zhí)行P(s2)時(shí)將等待，此時(shí)，Q2再繼續(xù)執(zhí)行P(s1)，也處于等待。 這種等待都必須由對方來釋放，顯然，這不可能的，產(chǎn)生了死鎖。 注意這里發(fā)生死鎖未涉及到資源，而是P 操作安排不當(dāng)，所以，死鎖也可能在不包括資源的情況下產(chǎn)生。,例 同類資源分配不當(dāng)引起死鎖 若系統(tǒng)中有m個(gè)資源被n個(gè)進(jìn)程共享，當(dāng)每個(gè)進(jìn)程都要求k個(gè)資源，而m n*k時(shí)

8、（即資源數(shù)小于進(jìn)程所要求的總數(shù)時(shí)），如果分配不得當(dāng)就可能引起死鎖。,例如，m=3，n=3，k=2，采用的分配策略是為每個(gè)進(jìn)程輪流分配。首先，為每個(gè)進(jìn)程輪流分配一個(gè)資源，這時(shí)，系統(tǒng)中的資源都已分配完了；于是第二輪分配時(shí)，各進(jìn)程都處于等待狀態(tài)，導(dǎo)致了死鎖。,缺1個(gè),例 對臨時(shí)性資源使用不加限制引起死鎖 進(jìn)程通信時(shí)使用的信件可以看作是一種臨時(shí)性資源。如果對信件的發(fā)送和接收不加限制的話，則可能引起死鎖。,比如，進(jìn)程P1 等待進(jìn)程P3 的信件S3 ，之后再向進(jìn)程P2 發(fā)送信件S1； P2 又要等待P1 的信件S1 ，之后再向P3 發(fā)送信件S2； 而P3 也要等待P2 的信件S2 ，之后才能發(fā)出信件S3。

9、 在這種情況下就形成了循環(huán)等待，永遠(yuǎn)結(jié)束不了，產(chǎn)生死鎖。,542死鎖的起因,1、死鎖的起因 死鎖的起因是并發(fā)進(jìn)程的資源競爭。產(chǎn)生死鎖的根本原因， 系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所需要的該類資源數(shù)和進(jìn)程推進(jìn)順序非法。 我們可以采用適當(dāng)?shù)馁Y源分配算法，以達(dá)到消除死鎖的目的。,死鎖的圖解,說明：R1、R2各只有1個(gè)。且兩進(jìn)程只有同時(shí)擁有R1和R2才可以完成任務(wù)！,2、產(chǎn)生死鎖的四個(gè)必要條件 （1） 互斥條件：在一段時(shí)間內(nèi)，一個(gè)資源只能由一個(gè)進(jìn)程獨(dú)占使用，若別的進(jìn)程也要求該資源，則須等待直至其占用者釋放； （2） 部分分配：允許進(jìn)程在不釋放其已分得的資源的情況下請求并等待分配新的資源；,（3）不剝奪性

10、：進(jìn)程所獲得的資源在未使用完之前，不能被其它進(jìn)程強(qiáng)行奪走，而只能由其自行釋放； （4）環(huán)路條件（循環(huán)等待）：存在一個(gè)等待進(jìn)程集合，P0正在等待一個(gè)P1占用的資源，P1正在等待一個(gè)P2占用的資源，Pn正在等待一個(gè)P0占用的資源。,3、關(guān)于死鎖的進(jìn)一步說明 （1）死鎖是進(jìn)程之間的一種特殊關(guān)系，是由資源競爭引起的僵局關(guān)系，因此，當(dāng)我們提到死鎖時(shí)，至少涉及到兩個(gè)進(jìn)程。 雖然單個(gè)進(jìn)程也可能鎖住自己，但那是程序設(shè)計(jì)錯(cuò)誤而不是死鎖； （2）當(dāng)出現(xiàn)死鎖時(shí)，首先要弄清楚被鎖的是哪些進(jìn)程因競爭哪些資源被鎖；,（3）在多數(shù)情況下，一系統(tǒng)出現(xiàn)死鎖，是指系統(tǒng)內(nèi)的一些而不是全部進(jìn)程被鎖，它們是因競爭某些而不是全部資源而進(jìn)

11、入死鎖。 若系統(tǒng)的全部進(jìn)程都被鎖住，我們稱系統(tǒng)處于癱瘓狀態(tài)； （4）系統(tǒng)癱瘓意味著所有進(jìn)程都進(jìn)入了睡眠（阻塞）狀態(tài)，但所有進(jìn)程都睡眠了，如果其中至少有一個(gè)進(jìn)程可由I/O中斷喚醒的話，這并不一定就是癱瘓狀態(tài)。,543解決死鎖問題的策略,產(chǎn)生死鎖的四個(gè)必要條件 （1）破壞互斥條件：可采用假脫機(jī)技術(shù)。 （2）破壞部分分配：可采用一次性滿足請求，即靜態(tài)預(yù)先分配。 （3）破壞不剝奪性：可采用可剝奪方法。 （4）破壞環(huán)路條件：可采用檢測是否可能出現(xiàn)死鎖，再決定是 否進(jìn)行分配。,這些條件并不完全獨(dú)立。但單獨(dú)考慮每個(gè)條件是有用的，只要能破壞這四個(gè)必要條件之一，死鎖就可防止。,說明： 1、以上前三個(gè)條件是死鎖存

12、在的必要條件，但不是充分條件。 2、第四個(gè)條件是前三個(gè)條件同時(shí)存在時(shí)產(chǎn)生的結(jié)果。,3、破壞第一個(gè)條件（互斥條件），使資源可同時(shí)訪問而不是互斥使用，是個(gè)簡單的辦法，磁盤可用這種辦法管理，但有許多資源往往是不能同時(shí)訪問的，所以，這種做法許多場合行不通。,4、采用剝奪式調(diào)度方法可以破壞第三個(gè)條件（不剝奪條件），但剝奪調(diào)度方法目前只適用于對主存資源和處理器資源的分配，當(dāng)進(jìn)程在申請資源未獲準(zhǔn)許的情況下，如能主動釋放資源（一種剝奪式），然后才去等待，以后再一起向系統(tǒng)提出申請，也能防止死鎖，但這些辦法不適用于所有資源。,解決死鎖問題的三個(gè)策略（1）,1靜態(tài)分配資源 靜態(tài)分配是指一個(gè)進(jìn)程必須在執(zhí)行前就申請它所

13、要的全部資源，并且直到它所要的資源都得到滿足后才開始執(zhí)行。 無疑的，所有并發(fā)執(zhí)行的進(jìn)程要求的資源總和不超過系統(tǒng)擁有的資源數(shù)。,采用靜態(tài)分配后，進(jìn)程在執(zhí)行中不再申請資源，因而，不會出現(xiàn)占有了某些資源再等待另一些資源的情況，即破壞了第二個(gè)條件（占有和等待條件）的出現(xiàn)。靜態(tài)分配策略實(shí)現(xiàn)簡單，被許多操作系統(tǒng)采用。但這種策略嚴(yán)重地降低了資源利用率。,2動態(tài)分配資源 既進(jìn)行分配資源時(shí)，阻止第四個(gè)條件（循環(huán)等待條件）的出現(xiàn)。 如：有序資源分配策略。 把系統(tǒng)的所有資源排列成一個(gè)順序，例如，系統(tǒng)若共有n個(gè)進(jìn)程，共有m個(gè)資源，用ri 表示第i個(gè)資源，于是這m個(gè)資源是： r1,r2,rm; 規(guī)定如果進(jìn)程不得在占用資

14、源ri(1im)后再申請rj(ji)。,解決死鎖問題的三個(gè)策略（2）,用反證法可以證明按序分配不會產(chǎn)生死鎖! 事實(shí)上，若在時(shí)刻t1，進(jìn)程P1處于等資源rk1的狀態(tài)，則rk1必為另一進(jìn)程(假定是P2)所占用，若P2在有限時(shí)間里可以運(yùn)行結(jié)束，P1就不會處于永遠(yuǎn)等待狀態(tài)； 所以，一定在某個(gè)時(shí)刻t2，進(jìn)程P2占有了資源rk1 而處于永遠(yuǎn)等待資源rk2狀態(tài)。 如此推下去，按假定系統(tǒng)只有有限個(gè)進(jìn)程，即必有某個(gè)n，在時(shí)刻tn時(shí)，進(jìn)程Pn永遠(yuǎn)等待資源rkn的狀態(tài)，而rkn必為前面的某一個(gè)進(jìn)程Pi占用（1in）。,于是，按照上述的按序分配策略，當(dāng)P2占用了rk1后再申請rk2必有：k1k2 依此類推，可得： k

15、2k3kikn 但是，由于進(jìn)程Pi是占有了rkn卻要申請資源rki，那么，必定有：knki, 這就產(chǎn)生了矛盾。 所以，按序分配策略可以防止死鎖。,3.檢測出死鎖，并設(shè)法修復(fù),解決死鎖問題的三個(gè)策略（3）,系統(tǒng)合理狀態(tài)的分析方法,系統(tǒng)狀態(tài)的改變，是由進(jìn)程對資源的請求、占有、釋放引起的。因此我們只要考慮某時(shí)刻系統(tǒng)中的進(jìn)程對資源的請求和占有情況。 具體方法(6個(gè)步驟)如下：,設(shè)系統(tǒng)t時(shí)刻包含n個(gè)并發(fā)進(jìn)程和所需m類競爭資源。,1登記n個(gè)并發(fā)進(jìn)程為：P=P1,P2,Pn 2登記m類資源為：R=R1,R2,Rm 3. 登記相應(yīng)各類資總數(shù)目源為:W=W1, W2,Wm 4登記t時(shí)刻資源請求矩陣為:Q(t)=

16、(Qij)nxm,其中Qij表示Pi請 求j類資源的數(shù)目 5登記t時(shí)刻已分配資源矩陣為:A(t)=(Aij)nxm，其中Aij表示Pi占有j類資源的數(shù)目,6 系統(tǒng)合理狀態(tài)的三個(gè)條件 （1） 如果存在某個(gè)QijWj （2） AijW1+W2+Wm （3）進(jìn)程不能占有它未曾申請的資源 如t時(shí)刻系統(tǒng)滿足（1）、（2）、（3）三個(gè)條件，則我們說t時(shí)刻的系統(tǒng)狀態(tài)為合理狀態(tài)。當(dāng)系統(tǒng)為合理狀態(tài)時(shí)，系統(tǒng)不可能出現(xiàn)死鎖。 死鎖預(yù)防的方法：靜態(tài)預(yù)防、動態(tài)避免,544死鎖的靜態(tài)預(yù)防,死鎖預(yù)防的方法主要是打破造成死鎖的四個(gè)必要條件中的一個(gè)，如允許進(jìn)程同時(shí)訪問某些資源，然而，這種方法不能解決訪問那些不允許被同時(shí)訪問的資

17、源帶來的死鎖問題，比如打印機(jī)等。 另一種方法則是打破資源的部分分配這個(gè)死鎖產(chǎn)生的必要條件。即預(yù)先分配各并發(fā)進(jìn)程所需要的全部資源。,另一種死鎖的預(yù)防方法是打破死鎖的環(huán)路條件。即把資源分類按順序排列，使進(jìn)程在申請、保持資源時(shí)不形成環(huán)路。 如有M中資源，則列出R1R2Rm。若進(jìn)程Pi保持了資源Ri，則它只能申請比Ri級別更高的資源Rj(RiRj）。釋放資源時(shí)必須是Rj先于Ri被釋放，從而避免環(huán)路的產(chǎn)生。 靜態(tài)預(yù)防方法就是采用預(yù)先分配進(jìn)程所需的全部資源的方法。,545死鎖的動態(tài)避免,動態(tài)避免方法就是在進(jìn)行分配資源時(shí)，采用某種算法來判斷是否會發(fā)生死鎖的方法，如可能出現(xiàn)死鎖，系統(tǒng)就拒絕分配資源。 （1）

18、有序資源分配法：計(jì)算機(jī)系統(tǒng)中的每一項(xiàng)資源都給它進(jìn)行唯編號 ，且編號唯一；進(jìn)程申請不同類資源時(shí)，必須按編號從小到大申請；進(jìn)程申請同類資源時(shí)，必須一次申請完。,（2） 靜態(tài)預(yù)先分配所有資源，又稱為銀行家算法（bankers algorithm）1968年由Dijkstra提出: 該算法需要檢查申請者對資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源可以滿足申請者的請求，就滿足申請者的請求。 這樣申請者就可很快完成其計(jì)算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生。,此時(shí)，系統(tǒng)中只剩下2個(gè)資源，這時(shí)就要考察能滿足哪個(gè)進(jìn)程，不能滿足P和R的最大要求，能滿足Q，于是將剩下的2個(gè)資源分配給Q。 Q完成后釋放所占用的6個(gè)資源。 6個(gè)資源可滿足P，也可滿足R，這時(shí)不論分給誰都能保證完成。,例子：假定系統(tǒng)有某類資源10個(gè)，目前分配的情況如下表：,546死鎖的檢測與恢復(fù) 死鎖的檢測算法當(dāng)進(jìn)程進(jìn)行資源請求時(shí)檢查并發(fā)進(jìn)程組是否