處理機(jī)調(diào)度與死鎖

1、第三組（主講人：彭鳳婷）任務(wù)列舉任務(wù)列舉全章概要全章概要死鎖產(chǎn)生的原因及條件死鎖產(chǎn)生的原因及條件死鎖的預(yù)防及銀行家算法死鎖的預(yù)防及銀行家算法解題思路及方法總結(jié)解題思路及方法總結(jié)全章概要全章概要 關(guān)于調(diào)度的兩個(gè)問題 一：系統(tǒng)一次可接納多少個(gè)作業(yè)？ 答：取決于多道程序度（允許多少個(gè)作答：取決于多道程序度（允許多少個(gè)作業(yè)同時(shí)在內(nèi)存存在）業(yè)同時(shí)在內(nèi)存存在） 二：都接納那些作業(yè)？ 答：取決于所采用的答：取決于所采用的調(diào)度算法系統(tǒng)所采用的用來決定先調(diào)入那些作業(yè)后調(diào)入那些作業(yè)的準(zhǔn)則全章概要全章概要 多道批處理系統(tǒng)調(diào)度算法多道批處理系統(tǒng)調(diào)度算法 先來先服務(wù)（先來先服務(wù)（FCFS） 作用對(duì)象：作業(yè)、進(jìn)程 對(duì)先到

2、來的作業(yè)或進(jìn)程優(yōu)先調(diào)度的算法 短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJP/F） 作用對(duì)象：作業(yè)、進(jìn)程 對(duì)短作業(yè)或進(jìn)程優(yōu)先調(diào)度的算法 高優(yōu)先權(quán)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先算法(FPF) 調(diào)度類型調(diào)度類型非搶占式非搶占式進(jìn)程一旦開始執(zhí)行就不在停下，直到完成為止進(jìn)程一旦開始執(zhí)行就不在停下，直到完成為止進(jìn)程執(zhí)行中一旦遇到優(yōu)先級(jí)比自己高的，就要讓出處理機(jī)進(jìn)程執(zhí)行中一旦遇到優(yōu)先級(jí)比自己高的，就要讓出處理機(jī)優(yōu)先權(quán)類型優(yōu)先權(quán)類型靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時(shí)決定，運(yùn)行期間保存不變創(chuàng)建進(jìn)程時(shí)決定，運(yùn)行期間保存不變隨進(jìn)程的推進(jìn)或其等待時(shí)間的增加而改變隨進(jìn)程的推進(jìn)或其等待時(shí)間的增加而改變搶占式搶占式全章總結(jié)全章總結(jié)

3、 （動(dòng)態(tài)優(yōu)先權(quán)）（動(dòng)態(tài)優(yōu)先權(quán)） 優(yōu)先權(quán)優(yōu)先權(quán)=（等待時(shí)間（等待時(shí)間+要求服務(wù)時(shí)間）要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間要求服務(wù)時(shí)間 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法時(shí)間片的確定時(shí)間片的確定 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 實(shí)時(shí)系統(tǒng)調(diào)度算法實(shí)時(shí)系統(tǒng)調(diào)度算法 最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先(EDF) 最低松弛度優(yōu)先最低松弛度優(yōu)先（LLF）請(qǐng)注意英文縮寫喲！任務(wù)列舉任務(wù)列舉全章概要全章概要死鎖產(chǎn)生的原因及條件死鎖產(chǎn)生的原因及條件死鎖的預(yù)防及銀行家算法死鎖的預(yù)防及銀行家算法解題思路及方法總結(jié)解題思路及方法總結(jié)何為死鎖？何為死鎖？一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而無限期地僵

4、持下去的局面 ，這種現(xiàn)象稱為進(jìn)程死鎖。這一組進(jìn)程就稱為死鎖進(jìn)程。死鎖定義死鎖產(chǎn)生的原因、條件、解決辦法死鎖產(chǎn)生的原因、條件、解決辦法原因原因1.競(jìng)爭(zhēng)資源2.進(jìn)程間的推進(jìn)順序非法 1.互斥條件2.請(qǐng)求和保存條件3.不剝奪條件4.環(huán)路等待條件 必要條件必要條件 1.預(yù)防死鎖2.避免死鎖3.檢測(cè)死鎖4.解除死鎖 解決辦法解決辦法 判斷題：判斷題：而具備互斥、占有和等待、不剝奪等條件卻不一定一定產(chǎn)生死鎖而具備互斥、占有和等待、不剝奪等條件卻不一定一定產(chǎn)生死鎖任務(wù)列舉任務(wù)列舉全章概要全章概要死鎖產(chǎn)生的原因及條件死鎖產(chǎn)生的原因及條件死鎖的預(yù)防及銀行家算法死鎖的預(yù)防及銀行家算法解題思路及方法總結(jié)解題思路及方

5、法總結(jié)預(yù)防死鎖的方法預(yù)防死鎖的方法1摒棄摒棄“請(qǐng)求保持條請(qǐng)求保持條件件”所有進(jìn)程在開始運(yùn)行所有進(jìn)程在開始運(yùn)行之前都必須一次性的之前都必須一次性的申請(qǐng)其在整個(gè)運(yùn)行過申請(qǐng)其在整個(gè)運(yùn)行過程所需全部資源程所需全部資源2摒棄摒棄“不剝奪條不剝奪條件件”當(dāng)一個(gè)已經(jīng)保持了某當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程，再提些資源的進(jìn)程，再提出新的資源請(qǐng)求不能出新的資源請(qǐng)求不能立即滿足，必須釋放立即滿足，必須釋放它已經(jīng)保持了的所有它已經(jīng)保持了的所有資源資源3摒棄摒棄“環(huán)路等待條環(huán)路等待條件件”系統(tǒng)所有資源按類型系統(tǒng)所有資源按類型進(jìn)行線性排隊(duì)，并賦進(jìn)行線性排隊(duì)，并賦予不同編號(hào)，所有進(jìn)予不同編號(hào)，所有進(jìn)程對(duì)資源的請(qǐng)求必須程對(duì)資

6、源的請(qǐng)求必須嚴(yán)格按照資源序號(hào)遞嚴(yán)格按照資源序號(hào)遞增的次序提出請(qǐng)求增的次序提出請(qǐng)求特別注意特別注意 如果不考慮資源分配的合理性，若要不產(chǎn)生死鎖，如果不考慮資源分配的合理性，若要不產(chǎn)生死鎖，則資源的個(gè)數(shù)必須滿足以下條件（則資源的個(gè)數(shù)必須滿足以下條件（即系統(tǒng)不會(huì)產(chǎn)即系統(tǒng)不會(huì)產(chǎn)生死鎖的最小資源數(shù)生死鎖的最小資源數(shù)）：設(shè)系統(tǒng)所擁有的資源總）：設(shè)系統(tǒng)所擁有的資源總數(shù)為數(shù)為M，共享該資源的進(jìn)程數(shù)為，共享該資源的進(jìn)程數(shù)為P，每個(gè)進(jìn)程所需，每個(gè)進(jìn)程所需使用該資源的最大需求為使用該資源的最大需求為N，則，則MP*(N-1)+1時(shí)，時(shí)，無論如何分配都不會(huì)產(chǎn)生死鎖。無論如何分配都不會(huì)產(chǎn)生死鎖。系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)

7、安全狀態(tài)安全狀態(tài)：如果系統(tǒng)能按某種順序（如：如果系統(tǒng)能按某種順序（如P2P2，P6P6，,Pn, ,Pn, 稱為安全序列）為每個(gè)進(jìn)程分配其所稱為安全序列）為每個(gè)進(jìn)程分配其所需的資源，直至所有進(jìn)程都能運(yùn)行完成，稱系統(tǒng)需的資源，直至所有進(jìn)程都能運(yùn)行完成，稱系統(tǒng)處于安全狀態(tài)。若不存在這樣一個(gè)安全序列稱系處于安全狀態(tài)。若不存在這樣一個(gè)安全序列稱系統(tǒng)處于不安全狀態(tài)。統(tǒng)處于不安全狀態(tài)。銀行家算法銀行家算法 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) Available(可利用資源可利用資源) Max（最大需求矩陣最大需求矩陣） Allocation（分配矩陣分配矩陣） Need（需求矩陣需求矩陣） 滿足關(guān)系：滿足關(guān)系： Needi

8、,j=Maxi,j-Allocationi,j Request：進(jìn)程進(jìn)程p的請(qǐng)求向量的請(qǐng)求向量 Requestj=K： 表示表示p需要需要k個(gè)個(gè)Ri類資源類資源銀行家算法銀行家算法設(shè)設(shè)Requesti是進(jìn)程是進(jìn)程Pi的請(qǐng)求向量，設(shè)的請(qǐng)求向量，設(shè)Requesti j =k，表，表示進(jìn)程示進(jìn)程Pi請(qǐng)求分配請(qǐng)求分配Rj類資源類資源k個(gè)。當(dāng)進(jìn)程個(gè)。當(dāng)進(jìn)程Pi 發(fā)出資源請(qǐng)發(fā)出資源請(qǐng)求后，系統(tǒng)按如下步驟進(jìn)行檢查：求后，系統(tǒng)按如下步驟進(jìn)行檢查：(1)如如RequestijNeedi,j,轉(zhuǎn)轉(zhuǎn)(2);否則出錯(cuò)，因?yàn)檫M(jìn)程申否則出錯(cuò)，因?yàn)檫M(jìn)程申請(qǐng)資源量超過它申明的最大量。請(qǐng)資源量超過它申明的最大量。(2)如如Re

9、questij Availablej,轉(zhuǎn)轉(zhuǎn)(3);否則表資源不夠否則表資源不夠,需需等待。等待。銀行家算法銀行家算法l3）假設(shè)系統(tǒng)可以給進(jìn)程）假設(shè)系統(tǒng)可以給進(jìn)程Pi分配所請(qǐng)求的資源，則應(yīng)對(duì)有關(guān)數(shù)據(jù)結(jié)分配所請(qǐng)求的資源，則應(yīng)對(duì)有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改：構(gòu)進(jìn)行修改：l Available = Available Requesti;l Allocationi = Allocationi + Requesti;l Needi = Needi Requesti;（4） 系統(tǒng)執(zhí)行系統(tǒng)執(zhí)行安全性算法安全性算法，查看此時(shí)系統(tǒng)狀態(tài)是否安全。如果，查看此時(shí)系統(tǒng)狀態(tài)是否安全。如果是安全的，就實(shí)際分配資源，滿足進(jìn)程是安全的

10、，就實(shí)際分配資源，滿足進(jìn)程Pi 的此次申請(qǐng)；否則，若的此次申請(qǐng)；否則，若新狀態(tài)是不安全的，則新狀態(tài)是不安全的，則Pi等待，對(duì)所申請(qǐng)資源暫不予分配，并且等待，對(duì)所申請(qǐng)資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成把資源分配狀態(tài)恢復(fù)成之前的情況。之前的情況。安全性算法安全性算法安全檢查算法：安全檢查算法：1）令令Work和和Finish分別表示長(zhǎng)度為分別表示長(zhǎng)度為m和和n的向量的向量。按如下方式進(jìn)行初始。按如下方式進(jìn)行初始化：化：Work= Available，F(xiàn)inishi=false（i=1, 2, n）。）。2）搜尋滿足下列條件的搜尋滿足下列條件的i值：值： Finishi = =false，且，

11、且NeediWork。如果沒有這樣的。如果沒有這樣的i存在，則轉(zhuǎn)向存在，則轉(zhuǎn)向步驟步驟。3）修改數(shù)據(jù)值，并返回步驟修改數(shù)據(jù)值，并返回步驟 Work=Work + Allocationi（Pi釋放所占的全部資源）釋放所占的全部資源） Finishi=true4）若若Finishi = =true對(duì)所有對(duì)所有i都成立，則系統(tǒng)處于安全狀態(tài)；否則，系都成立，則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。統(tǒng)處于不安全狀態(tài)。任務(wù)列舉任務(wù)列舉全章概要全章概要死鎖產(chǎn)生的原因及條件死鎖產(chǎn)生的原因及條件死鎖的預(yù)防及銀行家算法死鎖的預(yù)防及銀行家算法本節(jié)相關(guān)例題本節(jié)相關(guān)例題相關(guān)習(xí)題相關(guān)習(xí)題 1.某系統(tǒng)有11臺(tái)打印機(jī)，

12、N個(gè)進(jìn)程共享打印機(jī)資源，每個(gè)進(jìn)程要求3臺(tái)。當(dāng)N的取值不超過多少時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖？ 2.假設(shè)系統(tǒng)有n個(gè)進(jìn)程共享m個(gè)相同的資源，每個(gè)進(jìn)程至少請(qǐng)求一個(gè)資源。證明：當(dāng)n個(gè)進(jìn)程最多需要的資源數(shù)之和小于m+n時(shí)，該系統(tǒng)不會(huì)死鎖相關(guān)例題相關(guān)例題設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有3種類型的資源（種類型的資源（A，B，C）和）和5個(gè)進(jìn)程個(gè)進(jìn)程P1、P2、P3、P4、P5，A資源的數(shù)量為資源的數(shù)量為17，B資源的數(shù)量為資源的數(shù)量為5，C資源的數(shù)量為資源的數(shù)量為20。在在T0時(shí)刻系統(tǒng)狀態(tài)見下表（時(shí)刻系統(tǒng)狀態(tài)見下表（T0時(shí)刻系統(tǒng)狀態(tài)表）所示。系統(tǒng)采用銀時(shí)刻系統(tǒng)狀態(tài)表）所示。系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。（行家算法實(shí)施死鎖

13、避免策略。（12分）分） (T0時(shí)刻系統(tǒng)狀態(tài)表時(shí)刻系統(tǒng)狀態(tài)表)相關(guān)例題相關(guān)例題welcome to use these PowerPoint templates, New Content design, 10 years experience問問 題題1.T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。在在T0時(shí)刻若進(jìn)程時(shí)刻若進(jìn)程P2請(qǐng)求資源（請(qǐng)求資源（0，3，4），是否能實(shí)施），是否能實(shí)施資源分配？為什么？資源分配？為什么？在（在（2）的基礎(chǔ)上，若進(jìn)程）的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（請(qǐng)求資源（2，0，1），），是否能實(shí)施資源分配？為什么？是否能實(shí)施資源

14、分配？為什么？在（在（3）的基礎(chǔ)上，若進(jìn)程）的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（請(qǐng)求資源（0，2，0），），是否能實(shí)施資源分配？為什么？是否能實(shí)施資源分配？為什么？標(biāo)準(zhǔn)答案標(biāo)準(zhǔn)答案請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容Add your title請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容, 請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容Content請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容請(qǐng)?jiān)诖颂砑佣温鋬?nèi)容