操作系統(tǒng)原理：第五章 資源分配與調(diào)度

1、操作系統(tǒng)原理 第五章 資源分配與調(diào)度1第五章 資源分配與調(diào)度5.1 資源管理概述5.1.1 資源管理的目的和任務(wù)目的：1、保證資源的高利用率；2、在“合理”時間內(nèi)使所有顧客有獲得所需資源的機(jī)會；3、對不可共享的資源實施互斥使用；4、防止由資源分配不當(dāng)而引起的死鎖。操作系統(tǒng)原理 第五章 資源分配與調(diào)度25.1 資源管理概述5.1.1 資源管理的目的和任務(wù)對資源的管理應(yīng)包括以下幾個方面：1、資源管理的描述數(shù)據(jù)結(jié)構(gòu)2、確定資源的分配原則和調(diào)度原則3、執(zhí)行資源分配（實施）4、存取控制和安全保護(hù)5.1.2 資源的幾種分類方法（自學(xué)）操作系統(tǒng)原理 第五章 資源分配與調(diào)度35.2 資源分配機(jī)構(gòu)描述資源的管理

2、和控制信息的數(shù)據(jù)結(jié)構(gòu)稱為資源分配的機(jī)構(gòu) 。在教材上列出了兩種： 資源描述器 資源信息塊在實際的系統(tǒng)中，會根據(jù)實際需要設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。例如：進(jìn)程管理主要管理的機(jī)構(gòu)：PCB、就緒隊列和各種等待隊列。操作系統(tǒng)原理 第五章 資源分配與調(diào)度45.3資源分配策略5.3.1 概述資源分配有兩種方式：靜態(tài)分配：當(dāng)一個進(jìn)程（或程序）運(yùn)行前，將它要求的資源一次分配加該進(jìn)程，直到該進(jìn)程終止，釋放其占用的所有資源。這種分配方法效率太低；動態(tài)分配：當(dāng)一個進(jìn)程要求使用某個（類）資源時，向系統(tǒng)提出資源的請求，系統(tǒng)響應(yīng)程序的請求將某種資源分配給請求者，這種方法使得系統(tǒng)資源的利用率提高，但有可能造成死鎖。操作系統(tǒng)原理 第五

3、章 資源分配與調(diào)度55.3資源分配策略5.3.1 概述幾種分配策略：1、先請求先服務(wù)（FIFO）2、優(yōu)先調(diào)度3、適應(yīng)調(diào)度4、均衡調(diào)度5、針對設(shè)備特性的調(diào)度操作系統(tǒng)原理 第五章 資源分配與調(diào)度65.4 死鎖5.4.1 死鎖的概念在這兩個進(jìn)程并發(fā)執(zhí)行時，當(dāng)PA進(jìn)程占有R1、PB進(jìn)程占用R2時，PA要求R2，由于PB已占R2有而得不到，PA進(jìn)程只有等待；PB申請R1，由于PA已占有R1，而得不到，PB進(jìn)程只有等待，就出現(xiàn)了死等的情況。操作系統(tǒng)原理 第五章 資源分配與調(diào)度75.4 死鎖5.4.1 死鎖的概念例1：有兩個進(jìn)程PA和PB，它們在運(yùn)行的過程中要共享使用兩個獨占設(shè)備R1和R2。設(shè)SR1：表示設(shè)

4、備R1可用，初值為1；SR2表示設(shè)備R2可用，兩個進(jìn)程并發(fā)執(zhí)行的程序如下：操作系統(tǒng)原理 第五章 資源分配與調(diào)度85.4 死鎖5.4.1 死鎖的概念例2：三個進(jìn)程共享使用一臺打印機(jī)的程序若有一個進(jìn)程少寫了一個V操作。操作系統(tǒng)原理 第五章 資源分配與調(diào)度95.4 死鎖5.4.1 死鎖的概念 例3：生產(chǎn)者消費者問題當(dāng)緩沖區(qū)滿時，生產(chǎn)者仍可順利執(zhí)行p(mutex)操作，于是它對緩沖區(qū)有控制權(quán)，然后，當(dāng)它執(zhí)行p(empty)時，由于沒有空緩沖區(qū)被掛起。能將這個生產(chǎn)者釋放的是有一個消費者從緩沖區(qū)中取走一個產(chǎn)品，并執(zhí)行v(empty)操作，但由于緩沖區(qū)已被生產(chǎn)者占用，出現(xiàn)了死鎖。操作系統(tǒng)原理 第五章 資源分

5、配與調(diào)度105.4 死鎖5.4.1 死鎖的概念死鎖簡單的定義：死鎖就是兩個或兩個以上的進(jìn)程等候著一個永遠(yuǎn)不會發(fā)生的事件時所取的一種系統(tǒng)狀態(tài)。教材上關(guān)于死鎖的定義：兩個或兩個以上并發(fā)進(jìn)程，如果每個進(jìn)程持有某種資源，而又等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時，每個進(jìn)程都占用了一定的資源，但又都不能向前推進(jìn)。這種現(xiàn)象稱為死鎖。操作系統(tǒng)原理 第五章 資源分配與調(diào)度115.4 死鎖5.4.2 死鎖的起因操作系統(tǒng)原理 第五章 資源分配與調(diào)度125.4 死鎖5.4.2 死鎖的起因產(chǎn)生死鎖的四個必要條件：1、互斥條件2、不可剝奪條件3、部分分配4、環(huán)路條件操作系統(tǒng)原理 第五章 資

6、源分配與調(diào)度135.4.3 解決死鎖問題的策略一、解決死鎖問題的幾個策略為了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個必要條件之一。條件1：難以否定，但可采用相應(yīng)的技術(shù)，如利用假脫機(jī)技術(shù)，即用可共享使用的設(shè)備模擬非共享的設(shè)備；條件2：容易不定，可制定相應(yīng)的規(guī)則即可，例如，當(dāng)一個進(jìn)程（程序）申請某資源被拒絕，則必須釋放已占用的資源，如需要再與其它所需資源一起申請。對CPU還可進(jìn)行可剝奪分配。操作系統(tǒng)原理 第五章 資源分配與調(diào)度145.4.3 解決死鎖問題的策略條件3：也是很容易否定的，只要分配策略上規(guī)定一個進(jìn)程（或程序）一次將所需資源一次申請到位。用完后釋放?？梢匀坑猛旰?，統(tǒng)一釋放，也可使用完后立

7、即釋放，只要是一次申請到的，系統(tǒng)就不會出現(xiàn)死鎖。條件4：實際上系統(tǒng)不采用部分分配，也就破壞了環(huán)路條件。二、系統(tǒng)狀態(tài)分析（略）操作系統(tǒng)原理 第五章 資源分配與調(diào)度155.4.4 死鎖的預(yù)防預(yù)先分配一個進(jìn)程要用的所有資源是防止死鎖的一種安全而簡單的方法，但設(shè)備的使用效率太低。其缺點也是明顯的：1、一個用戶（進(jìn)程）在程序運(yùn)行之前艱難提出將要使用的全部設(shè)備；2、設(shè)備（資源）的浪費太大，有些資源在進(jìn)程運(yùn)行過程中可能只有很少的時間才用到，有的甚至不會用到，例如，一個分枝語句。操作系統(tǒng)原理 第五章 資源分配與調(diào)度165.4.5 死鎖的避免為了提高設(shè)備的利用率，應(yīng)采用動態(tài)的設(shè)備分配方法，但應(yīng)設(shè)法避免發(fā)生死鎖，

8、若存在發(fā)生死鎖的可能性，則拒絕分配。預(yù)防死鎖：采用的分配策略本身就否定了產(chǎn)生死鎖的四個必要條件之一，這就保證了不會發(fā)生死鎖；死鎖避免：是在動態(tài)分配資源的策略下采用某種算法來預(yù)防可能發(fā)生的死鎖，從而拒絕可能產(chǎn)生死鎖的某個資源的請求。操作系統(tǒng)原理 第五章 資源分配與調(diào)度175.4.5 死鎖的避免一、有序資源分配法這種算法資源按某種規(guī)則系統(tǒng)中的所有資源統(tǒng)一編號（例如打印機(jī)為1、磁帶機(jī)為2、磁盤為3、等等），申請時必須以上升的次序。系統(tǒng)要求申請進(jìn)程：1、對它所必須使用的而且屬于同一類的所有資源，必須一次申請完；2、在申請不同類資源時，必須按各類設(shè)備的編號依次申請。操作系統(tǒng)原理 第五章 資源分配與調(diào)度1

9、85.4.5 死鎖的避免例如：進(jìn)程PA，使用資源的順序是R1，R2； 進(jìn)程PB，使用資源的順序是R2，R1；若采用動態(tài)分配有可能形成環(huán)路條件，造成死鎖。采用有序資源分配法：R1的編號為1，R2的編號為2； PA：申請次序應(yīng)是：R1，R2 PB：申請次序應(yīng)是：R1，R2 這樣就破壞了環(huán)路條件，避免了死鎖的發(fā)生。操作系統(tǒng)原理 第五章 資源分配與調(diào)度195.4.5 死鎖的避免二、銀行算法避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法： 該算法需要檢查申請者對資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源可以滿足申請者的請求，就滿足申請者的請求。這樣申請者就可很快完成

10、其計算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生。操作系統(tǒng)原理 第五章 資源分配與調(diào)度205.4.5 死鎖的避免例子：假定系統(tǒng)有10個資源（為了說明問題的簡單，不管它是什么資源），目前分配的情況如上表：此時，系統(tǒng)中只剩下2個資源，這時就要考察能滿足哪個進(jìn)程，不能滿足P和R的最大要求，能滿足Q，于是將剩下的2個資源分配給Q，Q就能完成，然后釋放所占用的6個資源?？蓾M足P，也可滿足R，這時不論分給誰都能保證完成。操作系統(tǒng)原理 第五章 資源分配與調(diào)度215.4.6 死鎖的檢測和恢復(fù)死鎖的檢測： 很難找到切實可行的辦法，教材（P126）上的方法很難實現(xiàn)； 通常的方法是程序員的經(jīng)驗，如UNIX系統(tǒng)中，可考察進(jìn)程的運(yùn)行時間。在UNIX系統(tǒng)中有命令