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

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

2、塊 在實(shí)際的系統(tǒng)中，會(huì)根據(jù)實(shí)際需要設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。例如：進(jìn)程管理主要管理的機(jī)構(gòu)：PCB、就緒隊(duì)列和各種等待隊(duì)列,5.3資源分配策略5.3.1 概述,資源分配有兩種方式： 靜態(tài)分配：當(dāng)一個(gè)進(jìn)程（或程序）運(yùn)行前，將它要求的資源一次分配加該進(jìn)程，直到該進(jìn)程終止，釋放其占用的所有資源。這種分配方法效率太低； 動(dòng)態(tài)分配：當(dāng)一個(gè)進(jìn)程要求使用某個(gè)（類）資源時(shí)，向系統(tǒng)提出資源的請(qǐng)求，系統(tǒng)響應(yīng)程序的請(qǐng)求將某種資源分配給請(qǐng)求者，這種方法使得系統(tǒng)資源的利用率提高，但有可能造成死鎖,5.3資源分配策略5.3.1 概述,幾種分配策略： 1、先請(qǐng)求先服務(wù)（FIFO） 2、優(yōu)先調(diào)度 3、針對(duì)設(shè)備特性的調(diào)度,5.4 死鎖

3、5.4.1 死鎖的概念,例1：有兩個(gè)進(jìn)程PA和PB，它們?cè)谶\(yùn)行的過程中要共享使用兩個(gè)獨(dú)占設(shè)備R1和R2。設(shè)SR1：表示設(shè)備R1可用，初值為1；SR2表示設(shè)備R2可用，兩個(gè)進(jìn)程并發(fā)執(zhí)行的程序如下,5.4 死鎖5.4.1 死鎖的概念,在這兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，當(dāng)PA進(jìn)程占有R1、PB進(jìn)程占用R2時(shí)，PA要求R2，由于PB已占R2有而得不到，PA進(jìn)程只有等待；PB申請(qǐng)R1，由于PA已占有R1，而得不到，PB進(jìn)程只有等待，就出現(xiàn)了死等的情況,5.4 死鎖5.4.1 死鎖的概念,例2：三個(gè)進(jìn)程共享使用一臺(tái)打印機(jī)的程序若有一個(gè)進(jìn)程少寫了一個(gè)V操作,5.4 死鎖5.4.1 死鎖的概念 例3：生產(chǎn)者消費(fèi)者問題,

4、當(dāng)緩沖區(qū)滿時(shí)，生產(chǎn)者仍可順利執(zhí)行p(mutex)操作，于是它對(duì)緩沖區(qū)有控制權(quán)，然后，當(dāng)它執(zhí)行p(empty)時(shí)，由于沒有空緩沖區(qū)被掛起。能將這個(gè)生產(chǎn)者釋放的是有一個(gè)消費(fèi)者從緩沖區(qū)中取走一個(gè)產(chǎn)品，并執(zhí)行v(empty)操作，但由于緩沖區(qū)已被生產(chǎn)者占用，出現(xiàn)了死鎖,5.4 死鎖5.4.1 死鎖的概念,死鎖簡(jiǎn)單的定義： 死鎖就是兩個(gè)或兩個(gè)以上的進(jìn)程等候著一個(gè)永遠(yuǎn)不會(huì)發(fā)生的事件時(shí)所處的一種系統(tǒng)狀態(tài)。 教材上關(guān)于死鎖的定義： 兩個(gè)或兩個(gè)以上并發(fā)進(jìn)程，如果每個(gè)進(jìn)程持有某種資源，而又等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時(shí)，每個(gè)進(jìn)程都占用了一定的資源，但又都不能向前推進(jìn)。這種現(xiàn)象

5、稱為死鎖,5.4 死鎖5.4.2 死鎖的起因,計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng),5.4 死鎖5.4.2 死鎖的起因,產(chǎn)生死鎖的四個(gè)必要條件： 1、互斥條件 2、不可剝奪條件 3、部分分配條件 4、環(huán)路等待條件,互斥條件： 進(jìn)程對(duì)所分配的資源進(jìn)行排他性使用。 不可剝奪條件： 進(jìn)程已經(jīng)獲得資源，在未使用完之前，不能被剝奪，只能等到使用完成時(shí)由自己釋放,5.4 死鎖5.4.2 死鎖的起因,部分分配條件： 進(jìn)程已經(jīng)保持了至少一個(gè)資源，但是又提出了新的資源請(qǐng)求，而該資源又已經(jīng)被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但對(duì)其已獲資源保持不放。 環(huán)路等待條件： 發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的環(huán)

6、形鏈，即進(jìn)程集p1, p2, p3pn中，p1等待p2資源，p2等待p3資源,5.4 死鎖5.4.2 死鎖的起因,一、解決死鎖問題的幾個(gè)策略 為了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個(gè)必要條件之一。 條件1：難以否定，但可采用相應(yīng)的技術(shù)，如利用假脫機(jī)技術(shù)，即用可共享使用的設(shè)備模擬非共享的設(shè)備； 條件2：容易否定，可制定相應(yīng)的規(guī)則即可，例如，當(dāng)一個(gè)進(jìn)程（程序）申請(qǐng)某資源被拒絕，則必須釋放已占用的資源，如需要再與其它所需資源一起申請(qǐng)。對(duì)CPU還可進(jìn)行可剝奪分配,5.4 死鎖 5.4.3 解決死鎖問題的策略,條件3：也是很容易否定的，只要分配策略上規(guī)定一個(gè)進(jìn)程（或程序）一次將所需資源一次申請(qǐng)到位。用

7、完后釋放。可以全部用完后，統(tǒng)一釋放，也可使用完后立即釋放，只要是一次申請(qǐng)到的，系統(tǒng)就不會(huì)出現(xiàn)死鎖。 條件4：實(shí)際上系統(tǒng)不采用部分分配，也就破壞了環(huán)路條件。 二、解決死鎖的基本方法 1、預(yù)防死鎖； 2、避免死鎖； 3、檢測(cè)死鎖和解除死鎖,5.4 死鎖 5.4.3 解決死鎖問題的策略,一、靜態(tài)資源分配法 預(yù)先分配一個(gè)進(jìn)程要用的所有資源是防止死鎖的一種安全而簡(jiǎn)單的方法，但設(shè)備的使用效率太低。其缺點(diǎn)也是明顯的： 1、一個(gè)用戶（進(jìn)程）在程序運(yùn)行之前很難提出將要使用的全部設(shè)備； 2、設(shè)備（資源）的浪費(fèi)太大，有些資源在進(jìn)程運(yùn)行過程中可能只有很少的時(shí)間才用到，有的甚至不會(huì)用到，例如，一個(gè)分支語(yǔ)句,5.4 死鎖

8、 5.4.3 死鎖的預(yù)防,5.4 死鎖 5.4.3 死鎖的預(yù)防,二、有序資源分配法 這種算法資源按某種規(guī)則系統(tǒng)中的所有資源統(tǒng)一編號(hào)（例如打印機(jī)為1、磁帶機(jī)為2、磁盤為3、等等），申請(qǐng)時(shí)必須以上升的次序。 系統(tǒng)要求申請(qǐng)進(jìn)程： 1、對(duì)它所必須使用的而且屬于同一類的所有資源，必須一次申請(qǐng)完； 2、在申請(qǐng)不同類資源時(shí)，必須按各類設(shè)備的編號(hào)依次申請(qǐng),5.4 死鎖 5.4.3死鎖的預(yù)防,例如：進(jìn)程PA，使用資源的順序是R1，R2； 進(jìn)程PB，使用資源的順序是R2，R1； 若采用動(dòng)態(tài)分配有可能形成環(huán)路條件，造成死鎖。 采用有序資源分配法：R1的編號(hào)為1，R2的編號(hào)為2； PA：申請(qǐng)次序應(yīng)是：R1，R2 PB

9、：申請(qǐng)次序應(yīng)是：R1，R2 這樣就破壞了環(huán)路條件，預(yù)防了死鎖的發(fā)生,為了提高設(shè)備的利用率，應(yīng)采用動(dòng)態(tài)的設(shè)備分配方法，但應(yīng)設(shè)法避免發(fā)生死鎖，若存在發(fā)生死鎖的可能性，則拒絕分配。 預(yù)防死鎖： 采用的分配策略本身就否定了產(chǎn)生死鎖的四個(gè)必要條件之一，這就保證了不會(huì)發(fā)生死鎖； 死鎖避免： 是在動(dòng)態(tài)分配資源的策略下采用某種算法來(lái)預(yù)測(cè)可能發(fā)生的死鎖，從而拒絕可能產(chǎn)生死鎖的某個(gè)資源的請(qǐng)求,5.4 死鎖 5.4.4 死鎖的避免,5.4 死鎖 5.4.4 死鎖的避免,銀行算法 避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法： 該算法需要檢查申請(qǐng)者對(duì)資源的最大需求量，如果系統(tǒng)

10、現(xiàn)存的各類資源可以滿足申請(qǐng)者的請(qǐng)求，就滿足申請(qǐng)者的請(qǐng)求。 這樣申請(qǐng)者就可很快完成其計(jì)算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生,5.4 死鎖 5.4.4 死鎖的避免,例子：假定系統(tǒng)有10個(gè)資源（為了說明問題的簡(jiǎn)單，不管它是什么資源），目前分配的情況如上表： 此時(shí)，系統(tǒng)中只剩下2個(gè)資源，這時(shí)就要考察能滿足哪個(gè)進(jìn)程，不能滿足P和R的最大要求，能滿足Q，于是將剩下的2個(gè)資源分配給Q，Q就能完成，然后釋放所占用的6個(gè)資源。 可滿足P，也可滿足R，這時(shí)不論分給誰(shuí)都能保證完成,1、概念 安全狀態(tài)：系統(tǒng)按照某種序列為多個(gè)進(jìn)程分配資源直到最大需求，如果能夠保證所有進(jìn)程全

11、部順利執(zhí)行完畢，則稱系統(tǒng)是安全的,5.4 死鎖 5.4.4 死鎖的避免,銀行家算法：實(shí)例1單一資源的銀行家算法,系統(tǒng)中有P1, P2, P3三個(gè)進(jìn)程，需要12臺(tái)某設(shè)備 P1需要的最大資源數(shù)量為10臺(tái)，P2為4臺(tái)，P3為9臺(tái) 在T0時(shí)刻： 在T0時(shí)刻，有安全序列（P2, P1, P3）則稱在此時(shí)刻系統(tǒng)是安全狀態(tài)。 從安全狀態(tài)到不安全狀態(tài)的轉(zhuǎn)化： 如果P3再申請(qǐng)1臺(tái)資源,2、采取的數(shù)據(jù)結(jié)構(gòu) （1）可利用資源量Available:向量，Availablej = k,表示Rj資源有k個(gè)，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)改變。 （2）最大需求矩陣Max：進(jìn)程對(duì)資源的需求量。maxI, j = k, 表

12、示Pi對(duì)Rj的最大需求為k個(gè)。 （3）分配矩陣Allocationi： Allocationi, j = k，Rj資源已經(jīng)分配了k個(gè)給Pi （4）需求矩陣Needi ：還需要的資源數(shù)。 NeedIi, j = k,Pi尚需要Rj資源k個(gè)。 （5）請(qǐng)求矩陣Requesti 其中存在如下關(guān)系： Max need allocation,5.4 死鎖 5.4.4 死鎖的避免,3、銀行家算法 設(shè)request：是Pi進(jìn)程的請(qǐng)求向量，當(dāng)Pi發(fā)了資源請(qǐng)求后，系統(tǒng)按下述步驟檢查： （1）如果Requesti= Needi，則轉(zhuǎn)向步驟（2）；否則出錯(cuò); （2）若Requesti = Available，則轉(zhuǎn)向步

13、驟（3）；否則出錯(cuò); （3）系統(tǒng)試探性地把要求的資源分配給進(jìn)程Pi，并修改以下數(shù)據(jù)結(jié)構(gòu)的值：Available=Available-Requesti； Allocationi= Allocationi+ Requesti； Needi= Needi- Requesti； （4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給Pi進(jìn)程，完成本次分配；否則，試探性分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，Pi進(jìn)程進(jìn)入等待狀態(tài),5.4 死鎖 5.4.4 死鎖的避免,4、安全性算法 （1）設(shè)置兩個(gè)向量：工作向量work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，

14、執(zhí)行安全性算法開始時(shí)，work初值=Available；finish表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始時(shí)，finishi=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，令finishi=true； （2）從進(jìn)程集合中找到滿足下述條件的進(jìn)程： finishi= false； Needi = work；若找到執(zhí)行（3），否則執(zhí)行（4）； （3）當(dāng)進(jìn)程Pi獲得資源后，順序執(zhí)行直到完成，并釋放它的資源，執(zhí)行： work= work+ Allocationi； finishi= true； go to step(2); （4）若所有進(jìn)程的finishi= true，則系統(tǒng)處于安全狀態(tài)，否則，

15、處于不安全狀態(tài),5.4 死鎖 5.4.4 死鎖的避免,例：系統(tǒng)有五個(gè)進(jìn)程P0，P1，P2，P3，P4，三種類型的資源A，B，C，各種資源數(shù)量分別為10，5，7，在T0時(shí)刻資源分配情況如下表,5.4 死鎖 5.4.4 死鎖的避免,1、T0時(shí)刻的安全性,5.4 死鎖 5.4.4 死鎖的避免,2、P1發(fā)出Request（1，0，2），能分配資源給它嗎？ 執(zhí)銀行家算法： （1）Request(1,0,2)=Need(1,2,2) （2）Request(1,0,2)= Available (3,3,2) （3）試探性分配，修改數(shù)據(jù)結(jié)構(gòu) Available=Available-Request=(3,3,2

16、)-(1,0,2)=(2,3,0)； Allocation= Allocation+ Request=(2,0,0)+(1,0,2)=(3,0,2)； Need= Need- Request=(1,2,2)-(1,0,2)=(0,2,0,5.4 死鎖 5.4.4 死鎖的避免,新時(shí)刻分配狀態(tài),5.4 死鎖 5.4.4 死鎖的避免,新時(shí)刻安全性檢查： 所以系統(tǒng)是安全的，系統(tǒng)為P1分配資源成功,5.4 死鎖 5.4.4 死鎖的避免,3、P4發(fā)出Request（3，3，0），能分配資源給它嗎？ 執(zhí)銀行家算法： （1）Request(3,3,0) Available (2,3,0) 所以不能分配資源給它

17、，它必須等待。 4、P0發(fā)出Request（0，2，0），能分配資源給它嗎？(若Request（0，1，0），如何,5.4 死鎖5.4.5 死鎖的檢測(cè)和恢復(fù),死鎖檢測(cè)與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時(shí)，該機(jī)構(gòu)能夠檢測(cè)到死鎖發(fā)生的位置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進(jìn)程從死鎖狀態(tài)中解脫出來(lái),5.4 死鎖5.4.5 死鎖的檢測(cè)和恢復(fù),死鎖的檢測(cè)： 很難找到切實(shí)可行的辦法 通常的方法是程序員的經(jīng)驗(yàn)，如UNIX系統(tǒng)中，可考察進(jìn)程的運(yùn)行時(shí)間。在UNIX系統(tǒng)中有命令PS可顯示進(jìn)程占用CPU的時(shí)間，若發(fā)現(xiàn)有一組進(jìn)程在一段時(shí)間內(nèi)沒有占用CPU，就認(rèn)為這類進(jìn)程出現(xiàn)了死鎖,5.4 死

18、鎖5.4.5 死鎖的檢測(cè)和恢復(fù),一、死鎖檢測(cè)方法：化簡(jiǎn)資源分配圖法 1、資源分配圖G = (V, E)。式中，V是頂點(diǎn)的集合，E是邊的集合。頂點(diǎn)集合可分為兩部分：P=p1, p2, , pn，它由系統(tǒng)中所有活動(dòng)進(jìn)程組成；R=r1, r2, , rm，它由系統(tǒng)中全部資源類型組成。 有向邊pi rj稱為申請(qǐng)邊(請(qǐng)求邊)；而有向邊rj pi稱為賦給邊。 在資源分配圖中，通常用圓圈表示每個(gè)進(jìn)程，用方框表示每種資源類型,5.4 死鎖5.4.5 死鎖的檢測(cè)和恢復(fù),2資源分配圖示例,5.4 死鎖5.4.5 死鎖的檢測(cè)和恢復(fù),3環(huán)路與死鎖 如果每類資源的實(shí)體都只有一個(gè)，那么圖中出現(xiàn)環(huán)路就說明死鎖了。 如果每類資源的實(shí)體不止一個(gè)