1、5.1 資源管理概述5.2 資源分配機制5.3 資源分配策略5.4 死鎖5.1 資源管理的目的和任務 資源管理的目的： 1、保證資源的高利用率； 2、在“合理”時間內使所有“顧客(client)”有獲得所需資源的機會； 3、對不可共享的資源實施互斥使用； 4、防止由資源分配不當而引起的死鎖。1. 資源數據結構的描述資源數據結構的描述 構造資源分配所需的數據結構，應包含該資源的物理名、邏輯名、類型、地址、分配狀態等信息。 2. 確定資源的分配原則確定資源的分配原則 (調度原則調度原則) 確定資源分配原則，即決定資源應分給誰，何時分配，分配多少等問題。5.1.1 資源管理功能資源管理功能3. 實施

2、資源分配實施資源分配 根據所確定的資源分配原則以及用戶的要求，執行資源分配。當資源使用完畢后，收回資源以便重新分配給其他作業和進程使用。 4. 存取控制和安全保護存取控制和安全保護 對資源的存取進行控制并對資源實施安全保護措施。（eg:文件的管理文件的管理,任何一個用戶對任一文件的存取都要經過文件管理器系統中的存取控制驗證模塊的檢查）5.1.1 資源管理功能資源管理功能1. 資源描述器資源描述器 (1) 什么是資源描述器什么是資源描述器 描述各類資源的最小分配單位的數據結構稱為資源描述器 rd (resource descriptor)。 如：主存最小分配單位： 在分區分配中主存分區 磁盤最小

3、分配單位： 磁盤面中的一個扇區什么是資源描述器（resource descriptor？)資源描述器的內容資源名資源類型最小分配單位的大小最小分配單位的地址分配標志描述器鏈接信息存取權限密級最后一次存取時間記賬信息 2. 資源信息塊資源信息塊 為了對每類資源實施有效的分配，我們設置相應的資源信息塊rib（resource information blcok）,這樣一個數據結構應能說明資源、請求者、實施分配所需的必要信息。 對每一類可利用的資源，可將其組織成可利用資源的隊列。5.2 資源分配機構資源分配機構 2. 資源信息塊資源信息塊 (1) 什么是資源信息塊什么是資源信息塊 描述某類資源的請求

4、者、可用資源情況和該類資源描述某類資源的請求者、可用資源情況和該類資源分配程序等必要信息的數據結構。分配程序等必要信息的數據結構。 (2) 資源信息塊的內容資源信息塊的內容等待隊列頭指針可利用資源隊列頭指針資源分配程序入口地址 pcb1pcb2pcbkrd1rd2rdn5.2 資源分配機構資源分配機構 (3) 中央處理機資源信息塊中央處理機資源信息塊 ready-q-startrunningscheduler-addr pcb1pcb2pcbkpcb5cpu - rib5.2 資源分配機構資源分配機構5.3資源分配策略當資源可用時，滿足哪一個請求者？常用的分配策略:a.先請求先服務（FIFO）

5、b. 優先調度c.針對設備特性的調度a.先請求先服務FIFO 先請求先服務FIFO (First In First Out) 排序原則：按請求的先后次序排序。 每一個新產生的請求均排在隊尾，而當資源可用時，資源分配程序則從隊列中選取第一個請求，并滿足其需要。 先請求先服務的隊列結構a.先請求先服務FIFO 先請求先服務的隊列結構b.優先調度 在優先調度策略下，對于每一個進程要指定一個優先級，優先級反映了進程要求處理的緊迫程度。 排序原則：按優先級的高低排序。 每一個新產生的請求，按其優先級的高低插到相應的位置上。而當資源可用時，選取隊列中第一個請求，并滿足其需要。b.優先調度的隊列結構 5.4

6、 死鎖的產生 操作系統的基本特征是并發與共享。系統允許多個進程并發執行，并且共享系統的軟、硬件資源。 為了最大限度的利用計算機系統的資源，操作系統應采用動態分配系統各種資源的策略。 然而，采用這種策略時，當對某類資源的申請數目超過這類資源的入口數目入口數目，若分配不當，可能出現進程之間相互等資源又都不能向前推進的情況。即造成進程相互封鎖的危險。造成進程相互封鎖的危險。5.4.1 死鎖的概念例子：死鎖的生活中的影子AB假設有這么兩個人A，B：地位平等地位平等且自私自私。任務：每個人都獨立去植樹器具：目前只有1把鏟子和1個水桶例子：死鎖的生活中的影子要求：每個人若想獨立去把植樹完成，植樹時必須同時

7、具備1把鏟子和1個水桶場景：現在，A手中有1把鏟子，B手中有1個水桶問題：A、B兩人能否分別完成自己的任務呢？AB有鏟子有水桶缺水桶缺鏟子WaitingWaitingWaiting for dead分析什么是死鎖？ 死鎖的定義： 一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而無限期地僵持下去的局面 ，這種現象稱為進程死鎖。 這一組進程就稱為死鎖進程設S1=1，打印機可用。S2=1，讀卡機可用。OS中的例子 操作系統中的例子有二個進程P1、P2，兩個設備打印機R1，讀卡機R2 。 P(S1)； P(S2)； P(S2)； P(S1)； V(S1)； V(S2)； V(S2)

8、； V(S1)； P1P2 P(S1)； P(S2)； V(S1)； V(S2)； P(S2)； P(S1)； V(S2)； V(S1)； P1P2P1P2P1P2？ 兩種寫法，誰可能造成死鎖？申請R2S2：1-1=0占用R2申請R1S1：1-1=0占用R1申請R1，但R1被P1占用申請R2，但R2被P2占用死鎖Hold and wait 2.銀行家問題的例子 銀行共有資金10萬元，客戶u1需貸款3萬，客戶u2需貸款8萬，客戶u3需貸款9萬 。某一時刻： u2u3u1 已貸款還需資金1萬2萬2萬6萬6萬3萬銀行只剩下銀行只剩下一萬元，造一萬元，造成死鎖成死鎖。5.4.1 死鎖的概念死鎖的概念行

9、家的例子）對于客戶來說，只有所需要的所有貸對于客戶來說，只有所需要的所有貸款全部得到滿足，這樣生意才能完成，款全部得到滿足，這樣生意才能完成，之后才能把所貸款項歸還。之后才能把所貸款項歸還。貸不到款，客戶死貸不到款，客戶死貸款得不到歸還，銀行家死貸款得不到歸還，銀行家死起因：起因：1）系統資源不足）系統資源不足 系統資源數目系統資源數目 進程需求進程需求結論與問題：結論與問題：死鎖一定是系統資源不足死鎖一定是系統資源不足的，那么系統資源不足是不是一定造的，那么系統資源不足是不是一定造成死鎖呢成死鎖呢2）聯合推進路線非法）聯合推進路線非法（進程推進順序不當）（進程推進順序不當） 5.4.2產生死

10、鎖的起因和條件產生死鎖的起因和條件A2B2C2D2申請r1申請r2釋放r2釋放r1A1B1C1D1申請r1申請r2釋放r1釋放r2兩進程均占用r1兩進程均占用r2xyP2進展P1進展0A 死鎖點 5.4.2產生死鎖的起因和條件產生死鎖的起因和條件路線1路線2ttt2t1死鎖產生的條件 1971年Coffman總結出了對于可再使用資源，系統產生死鎖必定同時保持四個必要條件：1. 互斥條件（mutual exclusion）2. 占有和等待條件（hold and wait）3. 不剝奪條件（no preemption）4. 循環等待條件（circular wait）死鎖產生的條件 1. 互斥條件（

11、mutual exclusion）：進程應互斥使用資源，任一時刻一個資源僅為一個進程獨占，若另一個進程請求一個已被占用的資源時，它被置成等待狀態，直到占用者釋放資源。死鎖產生的條件 2.占有和等待條件（hold and wait）（或稱部分分配條件）：一個進程請求資源得不到滿足而等待時，不釋放已占有的資源。死鎖產生的條件 3. 不剝奪條件（no preemption）：任一進程不能從另一進程那里搶奪資源，即已被占用的資源，只能由占用進程自己來釋放。4. 循環等待條件（circular wait）：存在一個循環等待鏈，其中，每一個進程分別等待它前一個進程所持有的資源，造成永遠等待。死鎖產生的條件

12、 以上前三個條件互斥條件（mutual exclusion）占有和等待條件（hold and wait）不剝奪條件（no preemption）是死鎖存在的必要條件（necessary condition），但不是充分條件。死鎖產生的條件 第四個條件：循環等待條件（circular wait）是前三個條件同時存在時產生的結果，所以，這些條件并不完全獨立。但單獨考慮每個條件是有用的，只要能破壞只要能破壞這四個必要條件之一，死鎖就可防止這四個必要條件之一，死鎖就可防止。5.4.3 解決死鎖問題的策略-預防死鎖 一、解決死鎖問題的幾個策略 為了不發生死鎖，必須設法破壞產生死鎖的四個必要條件之一。 條

13、件1（互斥條件）：難以否定，但可采用相應的技術，如利用假脫機技術，即用可共享使用的設備模擬非共享的設備；5.4.3 解決死鎖問題的策略-預防死鎖 條件2（占有和等待條件）：容易否定也容易實現，可制定相應的規則即可，例如，當一個進程（程序）申請某資源被拒絕，則必須釋放已占用的資源，如需要再與其它所需資源一起申請。 在資源分配策略上可以采取靜態資源分配的方式一次性的把所需資源全部分配到位，否則就不分配。5.4.3 解決死鎖問題的策略-預防死鎖 條件3（不剝奪條件）：也是很容易否定的，只要分配策略上規定一個進程（或程序）一次將所需資源一次申請到位。用完后釋放。可以全部用完后，統一釋放，也可使用完后立

14、即釋放，只要是一次申請到的，系統就不會出現死鎖。5.4.3 解決死鎖問題的策略-預防死鎖條件4（循環等待條件）：通過有序資源分配法，可以破壞環路條件。實際上系統還可以不采用部分分配，也就破壞了環路等待條件。 死鎖的解決策略歸納起來，可以采用以下策略之一來解決死鎖問題： 忽略該問題 采用靜態資源分配來預防死鎖 采用有控分配方法來避免死鎖 當死鎖發生時檢測死鎖，并設法修復鴕鳥算法 象鴕鳥一樣對死鎖視而不見是最簡單的方法. 每個人對該方法的看法都不相同. 數學家認為要徹底防止死鎖的產生,不論代價有多大; 工程師們想要了解死鎖發生的頻率,系統因各種原因崩潰的頻率,以及死鎖的嚴重程度. UNIX潛在地受

15、到了一些死鎖的威協,但是這些死鎖從來沒有發生,甚至從來沒有被檢測到.處理死鎖的UNIX辦法是忽略它,由于大多數用戶寧可在極偶然的情況下產生死鎖,也不愿被限制只能創建一個進程,只能打開一個文件等等.為了研究解決死鎖的方法，可借助于有為了研究解決死鎖的方法，可借助于有向圖這一強有力的工具。圖中有兩種節向圖這一強有力的工具。圖中有兩種節點：方塊和圓圈。點：方塊和圓圈。圓圈代表進程，方塊圓圈代表進程，方塊代表資源。代表資源。 從資源節點從資源節點(方塊方塊)到進程節點到進程節點(圓圈圓圈)的的有向弧有向弧表示資源已經分配給進程表示資源已經分配給進程； 從進程到資源的有向弧表示進程從進程到資源的有向弧表

16、示進程當前正當前正處于阻塞狀態，等待資源變為可用。處于阻塞狀態，等待資源變為可用。資源分配圖資源分配圖2.資源進程有向圖 R2P1P2R1表示資源表示進程R2P1R1分配請求分配請求分配分配請求P2 5.4.2產生死鎖的起因和條件產生死鎖的起因和條件RASBTDUC(a)進程A 分配了一個資源(b)進程B 請求了一個資源(c)進程D和進程形成環路，已處于死鎖狀態資源分配圖資源分配圖5.4 死鎖的預防死鎖的預防靜態分配策略靜態分配策略 所謂所謂靜態分配靜態分配是指一個進程必須在執行前就申是指一個進程必須在執行前就申請它所要的全部資源，并且直到它所要的資源請它所要的全部資源，并且直到它所要的資源都

17、得到滿足后才開始執行。都得到滿足后才開始執行。 采用靜態分配后，進程在執行中不再申請資源采用靜態分配后，進程在執行中不再申請資源，因而，不會出現占有了某些資源再等待另一，因而，不會出現占有了某些資源再等待另一些資源的情況，即些資源的情況，即破壞了第二個條件（占有和破壞了第二個條件（占有和等待條件）等待條件）的出現。的出現。5.4 死鎖的預防死鎖的預防靜態分配策略靜態分配策略靜態分配策略實現簡單，被許多操作系統采靜態分配策略實現簡單，被許多操作系統采用。但這種策略嚴重地降低了資源利用率，用。但這種策略嚴重地降低了資源利用率，其缺點也是明顯的：其缺點也是明顯的： 一個用戶（進程）在程序運行之前很難

18、提出一個用戶（進程）在程序運行之前很難提出將要使用的全部設備；將要使用的全部設備； 用戶的作業必須等待，直到所有的資源滿足用戶的作業必須等待，直到所有的資源滿足時才能投入運行。實際上某些設備可能很晚時才能投入運行。實際上某些設備可能很晚的時候才使用的時候才使用5.4 死鎖的預防死鎖的預防靜態分配策略靜態分配策略設備（資源）的浪費太大，有些資源在進程運行過設備（資源）的浪費太大，有些資源在進程運行過程中可能只有很少的時間才用到，有的甚至不會用程中可能只有很少的時間才用到，有的甚至不會用到。到。 例如：一個分支語句，只有當程序出錯的時候才將例如：一個分支語句，只有當程序出錯的時候才將錯誤從打印機輸

19、出，但如果采用靜態資源分配策略錯誤從打印機輸出，但如果采用靜態資源分配策略的話，也要把打印機分配給這個程序，所以這種分的話，也要把打印機分配給這個程序，所以這種分配策略對系統來說是很浪費的。配策略對系統來說是很浪費的。5.4 死鎖的預防死鎖的預防層次分配層次分配 在層次分配策略下，資源被分成多個層次，一個進程得到某一層的一個資源后，它只能再申請在較高一層的資源；當一個進程要釋放某層的一個資源時，必須先釋放所占用的較高層的資源。 層次分配層次分配策略將阻止第四個條件（循環等待條件）的出現。5.4 死鎖的預防死鎖的預防層次分配層次分配 這種策略的一個變種是按序分配策略。把系統的所有資源排列成一個順

20、序，例如，系統若共有n個進程，共有m個資源，用ri表示第i個資源，于是這m個資源是：r1,r2,rm 規定如果進程不得在占用資源ri(1im)后再申請rj(ji)，即這種算法資源按申請多項資源時必須以上升的次序依次申請。5.4有序資源分配法 例如：進程P1，使用資源的順序是R1，R2； 進程P2，使用資源的順序是R2，R1； 若采用動態分配有可能形成環路條件，造成死鎖。5.4有序資源分配法 采用有序資源分配法：R1的編號為1，R2的編號為2； P1：申請次序應是：R1，R2 P1：申請次序應是：R1，R2 這樣就破壞了環路條件，避免了死鎖的發生。5.4.5 死鎖的避免 為了提高設備的利用率，應

21、采用動態的設備分配方法，但應設法避免發生死鎖，若存在發生死鎖的可能性，則拒絕分配。5.4.5 死鎖的避免 預防死鎖： 采用的分配策略本身就否定了產生死鎖的四個必要條件之一，這就保證了不會發生死鎖； 死鎖避免： 與預防死鎖相反，它允許系統中同時存在四個必要條件，如果能掌握并發進程中與每個進程有關的資源動態申請情況，做出明智和合理的選擇，仍然可以避免死鎖的發生。5.4.5 死鎖的避免 死鎖避免不是通過對進程隨意強加一些規則，而是通過對每一次資源申請進行認真的分析來判斷它是否能安全地分配。5.4.5 死鎖的避免 問題是：是否存在一種算法總能做出正確的選擇從而避免死鎖？ 答案是肯定的，但條件是必須事先

22、獲得與進程有關的一些特定信息。本節將討論使用銀行家算法（銀行家算法（bankers algorithm）避免死鎖的方法。銀行家算法銀行家算法 避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法：它的模型基于一個小城鎮的銀行家，現將該算法描述如下：假定一個銀行家擁有資金，數量為，被N個客戶共享。銀行家對客戶提出下列約束條件：銀行家算法銀行家算法 每個客戶必須預先說明自己所要求的最大資金量； 每個客戶每次提出部分資金量申請和獲得分配； 如果銀行滿足了某客戶對資金的最大需求量，那么，客戶在資金運作后，應在有限時間內全部歸還銀行。銀行家算法銀行家算法 在銀行家算法中

23、，客戶可看作進程，資金可看作資源，銀行家可看作操作系統，這里敘述的是單資源銀行家算法，單資源的銀行家算法單資源的銀行家算法 在上圖a中列出了4個客戶，每個客戶都有一個貸款額度，銀行家知道不可能所有客戶同時都需要最大貸款額，所以，他只保留10個單位的資金來為客戶服務，而不是22個單位。 圖（b）所示的狀態是客戶們各做自己的生意，在某些時刻需要貸款?？蛻粢勋@得的貸款（已分配的資源）和可用的最大數額貸款稱為與資源分配相關的系統狀態。單資源的銀行家算法 一個狀態被稱為是安全的，其條件是存在一個狀態序列狀態序列能夠使所有的客戶均得到其所有的貸款(即所有的進程得到所需的全部資源并終止)。單資源的銀行家算法

24、 圖b所示的狀態是安全的,why? 因為在有2個單位資金可用的情況下，銀行家可以延遲除Marvin之外的所有請求，這樣便可以使Marvin運行結束，然后釋放所有的4個單位資金。如此這樣下去便可以滿足Snganne或者Barbarn的請求，等等。 安全貸款序列：Marvin， Sugzanne， Barbarn ,Andy單資源的銀行家算法 圖c所示的狀態，該狀態是不安全的。如果忽然所有的客戶都申請，希望得到最大貸款額，而銀行家無法滿足其中任何一個的要求，則發生死鎖。 不安全狀態并不一定導致死鎖，因為顧客有可能不需要它的全部貸款額，但銀行家不能指望這種情況發生，不敢抱這種僥幸心理。 單資源的銀行

25、家算法單資源的銀行家算法總結 銀行家算法就是對每一個請求進行檢查，檢查如果滿足它是否會導致不安全狀態。 若是，則不滿足該請求；否則便滿足。 檢查狀態是否安全的方法是看他是否有足夠的資源滿足一個距最大需求最近的客戶滿足一個距最大需求最近的客戶。 如果可以，則這筆投資認為是能夠收回的，然后接著檢查下一個距最大需求最近的客戶，如此反復下去。如果所有投資最終都被收回，則該狀態是安全的，最初的請求可以批準。 單資源銀行家算法總結 單資源銀行家算法可陳述如下： 當一個進程提出資源請求時，當一個進程提出資源請求時，假定分配假定分配給它，給它，并檢查并檢查系統因此是否仍處于安全系統因此是否仍處于安全狀態。狀態

26、。如果安全如果安全，則滿足它的請求。，則滿足它的請求。否否則，推遲它的請求則，推遲它的請求。5.4.6 死鎖的檢測和恢復 死鎖的檢測： 死鎖的檢測代價很高； 通常的方法是程序員的經驗，如UNIX系統中，可考察進程的運行時間。在UNIX系統中有命令PS可顯示進程占用CPU的時間，若發現有一組進程在一段時間內沒有占用CPU，就認為這類進程出現了死鎖。5.4.6 死鎖的檢測和恢復 死鎖排除的方法： 1、撤消陷于死鎖的全部進程； 2、逐個撤消陷于死鎖的進程，直到死鎖不存在； 3、從陷于死鎖的進程中逐個強迫放棄所占用的資源，直至死鎖消失。一道考研題一道考研題 下列關于銀行家算法的敘述中，正確的是（ ）。

27、 A. 銀行家算法可以預防死鎖 B. 當系統處于安全狀態時，系統中一定無死鎖進程 C. 當系統處于不安全狀態時，系統中一定會出現死鎖進程 D. 銀行家算法破壞了死鎖必要條件中的“請求和保持”條件一道考研題 某時刻進程的資源使用情況如下所示。進程已分配資源尚需資源可用資源R1R2R3R1R2R3R1 R2 R3P1200001021P2120132P3011131P4001200 此時的安全序列是（）。（11年聯考） A. P1, P2, P3, P4 B. P1, P3, P2, P4 C. P1, P4, P3, P2 D. 不存在一道考研題 假設5個進程P0、P1、P2、P3、P4共享三類

28、資源R1、R2、R3，這些資源總數分別為18、6、22。T0時刻的資源分配情況如下表所示，此時存在的一個安全序列是（）。（12年聯考）進程已分配資源資源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424 A. P0, P1, P2, P3, P4 B. P1, P0, P3, P4, P2 C. P2, P1, P0, P3, P4 D. P3, P4, P2, P1, P0回顧：資源競爭產生死鎖回顧：資源競爭產生死鎖 m個資源被個資源被n個進程共享，每個進程要求個進程共享，每個進程要求k個資個資源，則當源，則當 m=n*(k-

29、1) 時，如果分配不當就可能發時，如果分配不當就可能發生死鎖。生死鎖。 死鎖的定義：在兩個或多個并發進程中，如果死鎖的定義：在兩個或多個并發進程中，如果每個進程持有某種資源而又都等待著別的進程釋放每個進程持有某種資源而又都等待著別的進程釋放它或它們現在保持著的資源，否則就不能向前推進。它或它們現在保持著的資源，否則就不能向前推進。此時每個進程都占用了一定的資源但又都不能向前此時每個進程都占用了一定的資源但又都不能向前推進，稱這一組進程產生可死鎖。推進，稱這一組進程產生可死鎖。 某計算機系統中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是（ ）。

30、 A. 2B. 3C. 4D. 5死鎖的避免死鎖的避免 1. 1. 有序資源使用法有序資源使用法 系統中的所有資源類都分給一個唯一的序系統中的所有資源類都分給一個唯一的序號，并要求每個進程均應嚴格按照遞增的次序號，并要求每個進程均應嚴格按照遞增的次序請求資源。請求資源。 有序資源使用法破壞了產生死鎖的環路條有序資源使用法破壞了產生死鎖的環路條件，從而不可能產生死鎖。件，從而不可能產生死鎖。 缺點：對于實際資源使用順序與資源序號缺點：對于實際資源使用順序與資源序號不一致的作業仍存在著資源浪費現象。不一致的作業仍存在著資源浪費現象。 例如：例如：進程進程PA，使用資源的順序是，使用資源的順序是R1，R2； 進程進程P