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

1、linux處理機(jī)調(diào)度與死鎖2S2P1S3P3S1P2圖 7-1 進(jìn)程之間通信時(shí)的死鎖 n死鎖的定義:死鎖是一組并發(fā)進(jìn)程,它們共享系統(tǒng)的某些資源,該組進(jìn)程中每個(gè)進(jìn)程都已經(jīng)占有了部分資源,但都在不釋放自己占有資源的情況下要求獲得被其它進(jìn)程已經(jīng)占有的資源,從而造成它們相互等待,永遠(yuǎn)不能繼續(xù)推進(jìn)的狀態(tài).n說(shuō)明：n參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）。n參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源。n參與死鎖的所有進(jìn)程都在等待事件。n參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集。7.3.2 資源分配圖(2) 凡屬于E中的一個(gè)邊eE，都連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，e=pi, rj是資源請(qǐng)求邊

2、，由進(jìn)程pi指向資源rj， 它表示進(jìn)程pi請(qǐng)求一個(gè)單位的rj資源。e=rj, pi是資源分配邊，由資源rj指向進(jìn)程pi, 它表示把一個(gè)單位的資源rj分配給進(jìn)程pi。P1P2r1r2該圖是由一組結(jié)點(diǎn)V和一組邊E所組成的：G=（V，E），具有以下形式的定義和限制：（1）V被分為兩個(gè)互斥的子集，一組進(jìn)程結(jié)點(diǎn)P=p1,p2,pn,一組資源結(jié)點(diǎn)R=r1,r2,rn,7.3.3 產(chǎn)生死鎖的原因 n產(chǎn)生死鎖的根本原因是:n資源不足，引起資源競(jìng)爭(zhēng)n進(jìn)程推進(jìn)順序不合理例:設(shè)有兩個(gè)進(jìn)程Pa和Pb,它們都需要使用系統(tǒng)內(nèi)的打印機(jī)和輸入機(jī).它們的算法設(shè)計(jì)如下:設(shè)信號(hào)量s1代表輸入機(jī)資源可用數(shù)量,s1=1設(shè)信號(hào)量s2代表

3、打印機(jī)資源可用數(shù)量,s2=1Pa:P(s2)P(s1)V(s2)V(s1)Pb:P(s1)P(s2)V(s1)V(s2)7.3.4 死鎖產(chǎn)生的必要條件n互斥條件。進(jìn)程要求對(duì)所分配的資源進(jìn)行排他性使用，即在一段時(shí)間內(nèi)某資源僅為一個(gè)進(jìn)程所占用。n不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來(lái)釋放。n請(qǐng)求和保持條件。進(jìn)程每次申請(qǐng)所需要的一部分資源，在等待新資源的同時(shí)，進(jìn)程繼續(xù)占有已分配到的資源。n循環(huán)等待條件。存在進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得資源，同時(shí)被鏈中的下一個(gè)進(jìn)程所請(qǐng)求。7.4 預(yù)防死鎖n解決死鎖問(wèn)題的基本方法有：預(yù)防死鎖、

4、避免死鎖、檢測(cè)死鎖和解除死鎖。除此之外還有鴕鳥(niǎo)算法和綜合措施。n預(yù)防死鎖是指通過(guò)某種策略來(lái)限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都不滿(mǎn)足死鎖的必要條件。n就是在設(shè)計(jì)操作系統(tǒng)時(shí)，通過(guò)設(shè)置某些限制條件，去破壞死鎖四個(gè)必要條件中的一個(gè)或多個(gè)，來(lái)防止死鎖，使系統(tǒng)能預(yù)先排除死鎖的可能性。 摒棄請(qǐng)求和保持條件n采用設(shè)備的靜態(tài)預(yù)先分配辦法,具體作法:作業(yè)調(diào)度程序在選擇作業(yè)時(shí),只選擇那些系統(tǒng)能滿(mǎn)足其運(yùn)行時(shí)所需的全部資源的作業(yè)投入運(yùn)行,并且在作業(yè)運(yùn)行前,將其所需的全部資源一次性地分配給該作業(yè).n該方法的優(yōu)點(diǎn)和缺點(diǎn)如下：n簡(jiǎn)單、安全、易于實(shí)現(xiàn)。n程序在運(yùn)行之前很難提出將要使用的全部設(shè)備。n直到所有資源滿(mǎn)足才能

5、運(yùn)行，實(shí)際上某些資源可能要到運(yùn)行后期才會(huì)用到。n一個(gè)進(jìn)程運(yùn)行期間，對(duì)某些設(shè)備的使用時(shí)間很短，甚至不會(huì)用到。n作業(yè)的周轉(zhuǎn)時(shí)間被加長(zhǎng),系統(tǒng)資源的使用率被降低摒棄不剝奪條件n為了破壞不可剝奪條件，我們采用這樣的策略，一個(gè)已擁有資源的進(jìn)程，若它再提出新資源要求而不能立即得到滿(mǎn)足時(shí)，它必須釋放已經(jīng)擁有的所有資源，以后需要時(shí)再重新申請(qǐng)。擁有資源的進(jìn)程在運(yùn)行過(guò)程中其資源可能被剝奪，從而破壞了不可剝奪條件。該方法實(shí)現(xiàn)復(fù)雜，被剝奪資源的進(jìn)程前期工作失效，重復(fù)申請(qǐng)和釋放資源給系統(tǒng)增加了開(kāi)銷(xiāo)，系統(tǒng)要付出很大的代價(jià)。摒棄環(huán)路等待條件n為了破壞環(huán)路等待條件，采用有序資源分配策略。 n對(duì)申請(qǐng)資源的進(jìn)程規(guī)定：同類(lèi)資源需一次

6、申請(qǐng)，在獲得資源后，只能申請(qǐng)較高級(jí)號(hào)的資源，無(wú)權(quán)申請(qǐng)低級(jí)號(hào)資源和同類(lèi)資源。對(duì)于低級(jí)號(hào)資源和同類(lèi)資源申請(qǐng)，必須先釋放所有高級(jí)號(hào)的資源，然后再申請(qǐng)，否則不予分配。n優(yōu)點(diǎn)：同前兩法相比，其資源利用率和系統(tǒng)吞吐量有較明顯的改善。n缺點(diǎn)：進(jìn)程實(shí)際需要資源的順序不一定與資源的編號(hào)一致，因此仍會(huì)造成資源浪費(fèi)，系統(tǒng)增加新設(shè)備較困難。摒棄互斥條件n互斥條件是由于設(shè)備本身特性所決定的,不能簡(jiǎn)單的把其打破;只有通過(guò)改造設(shè)備特性實(shí)現(xiàn).具體辦法采用Spooling技術(shù),把獨(dú)占設(shè)備改造成共享設(shè)備來(lái)實(shí)現(xiàn).7.5 避免死鎖n死鎖的避免是動(dòng)態(tài)的預(yù)防措施,系統(tǒng)允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源,如果措施得當(dāng),可以使系統(tǒng)獲得較為滿(mǎn)意的系統(tǒng)性能

7、.n具體的辦法是:系統(tǒng)為進(jìn)程分配資源之前,首先對(duì)系統(tǒng)的安全性進(jìn)行計(jì)算,如果為進(jìn)程分配了所需資源后,系統(tǒng)仍處于安全狀態(tài),那么就把資源分配給該進(jìn)程,反之則不為該進(jìn)程分配資源.n銀行家算法:該問(wèn)題是研究一個(gè)銀行家如何將其總數(shù)一定的現(xiàn)金,安全的借給若干個(gè)顧客,使這些顧客既能滿(mǎn)足對(duì)資金的要求又能完成其交易,也使銀行家可以收回自己的資金不至于破產(chǎn).n系統(tǒng)的安全狀態(tài)和不安全狀態(tài) n安全狀態(tài):是指系統(tǒng)能按某種進(jìn)程推進(jìn)順序(p1,p2,pn),來(lái)為每個(gè)進(jìn)程分配其所需資源,直至最大需求,使每個(gè)進(jìn)程都能順利完成其任務(wù).只要系統(tǒng)存在這樣的安全序列,則系統(tǒng)處于安全狀態(tài).n安全狀態(tài)的例子 n假定系統(tǒng)有三個(gè)進(jìn)程p1,p2和

8、p3,共有12臺(tái)磁帶機(jī),進(jìn)程p1、p2、p3分別要求10臺(tái)、4臺(tái)和9臺(tái)，設(shè)在T0時(shí)刻p1、p2、p3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)，尚有3臺(tái)空閑磁帶機(jī)未分配出去，分配情況如下所示：進(jìn)程最大需求已分配可用磁帶機(jī)P11053P242P392n經(jīng)分析，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇嬖谝粋€(gè)安全序列n向不安全狀態(tài)的轉(zhuǎn)換n若在T0時(shí)刻，p3請(qǐng)求1臺(tái)磁帶機(jī)，若滿(mǎn)足其要求，則系統(tǒng)進(jìn)入不安全狀態(tài)。7.5.3 利用銀行家算法避免死鎖n銀行家算法中的數(shù)據(jù)結(jié)構(gòu)n可利用資源向量Available(R1,R2Rm)。它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類(lèi)全部可用資源

9、數(shù)目。其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。n最大需求矩陣Max。這是個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源的最大需求。如果Maxi，jk，表示進(jìn)程Pi需要Rj類(lèi)資源的最大數(shù)目為k。n分配矩陣Allocation。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每個(gè)進(jìn)程的資源數(shù)。如果Allocationi，jk，表示進(jìn)程Pi當(dāng)前已分得Rj類(lèi)資源的數(shù)目為k。n需求矩陣：Need。它是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)，如果Needi，jk，表示進(jìn)程Pi還需要Rj類(lèi)資源k個(gè)，方能完成其任務(wù)。n上述三個(gè)矩陣間存在下述關(guān)系：nNeedi，j=Maxi，

10、j-Allocationi，jn銀行家算法n設(shè)Requesti（r1,r2,rm)是進(jìn)程Pi的請(qǐng)求向量。如果Requestijk，表示進(jìn)程Pi只需要k個(gè)Rj類(lèi)型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：n如果Requesti=Needi，則執(zhí)行步驟；否則，認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。n如果Requesti，=Availablei，則執(zhí)行步驟；否則，表示系統(tǒng)中尚無(wú)足夠的資源，Pi等待。n系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：nAvailablej=Availablej-Requestij；nAllocationi，j=Allocat

11、ioni，j+Requestij；nNeedi，j=Needi，j-Requestij；n系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。n安全性算法n系統(tǒng)所執(zhí)行的安全性算法可描述如下：n設(shè)置兩個(gè)工作向量，工作向量Work。它含有m個(gè)元素，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類(lèi)資源數(shù)目，初值Work=Available。n完成標(biāo)志工作向量Finish。它含有n個(gè)元素，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，當(dāng)有足夠資源分配給進(jìn)程時(shí)，F(xiàn)inishi=tr

12、ue，初值Finishi=false。n從進(jìn)程集合中找到一個(gè)能滿(mǎn)足下述條件的進(jìn)程：nFinishi=false；nNeedi=Work；n如找到，執(zhí)行步驟；否則，執(zhí)行步驟。n當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，系統(tǒng)回收這些資源，故修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：nWorkj=Workj+Allocationi，j；nFinishi=true；n轉(zhuǎn)步驟。n如果所有進(jìn)程的Finishi=true ，則表示存在這樣一個(gè)安全序列，系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。銀行家算法之例n如表7-4所示T0時(shí)刻的資源分配表，假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1，P2，P3，P4和三

13、種類(lèi)型的資源A，B，C，每一種資源的數(shù)量分別為10、5、7。 如表7-5所示，對(duì)T0時(shí)刻進(jìn)行安全性檢查，可以找到一個(gè)安全序列P1，P3，P4，P2，P0，系統(tǒng)是安全的。 nP1發(fā)出請(qǐng)求Request(1，0，2)，執(zhí)行銀行家算法。n如表7-6所示，進(jìn)行安全性檢查，通過(guò)第一步和第二步檢查，并找到一個(gè)安全序列P1，P3，P4，P2，P0，系統(tǒng)是安全的，可以分配P1的請(qǐng)求。nP4發(fā)出請(qǐng)求Request(3，3，0)，執(zhí)行銀行家算法。nAvailable=(2，3，0)，不能通過(guò)第二步檢查（RequestiAvailable），所以P4等待。nP0請(qǐng)求資源，Request（0，2，0），執(zhí)行銀行家算法

14、。n進(jìn)行安全性檢查，通過(guò)第一步和第二步檢查，如表7-7所示，Available2，1，0已不能滿(mǎn)足任何進(jìn)程需要，所以系統(tǒng)進(jìn)入不安全狀態(tài)，P0的請(qǐng)求不能分配。7.6 檢測(cè)死鎖并解除死鎖7.6.1 檢測(cè)死鎖（這是一種事后處理的措施）n具體方法是：n1、判斷是否構(gòu)成環(huán)路條件n采用有限狀態(tài)轉(zhuǎn)移圖法2、周期性檢測(cè)方法：類(lèi)似銀行家算法死鎖定理 n1、死鎖定理：S為死鎖狀態(tài)的充分必要條件是當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可化簡(jiǎn)的。n2、資源分配圖的化簡(jiǎn)原則：n(1)在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)pi。在順利情況下，pi可獲得所需資源而繼續(xù)執(zhí)行，直至運(yùn)行完畢，再釋放其所占有的全部資源。這相當(dāng)

15、于消去pi所有的請(qǐng)求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。n（2）p1釋放資源后，便可使p2獲得資源而繼續(xù)運(yùn)行，直到p2完成后又釋放出它所占有的全部資源，而形成圖（c)所示的情況。n（3）、在進(jìn)行一系列簡(jiǎn)化后，若能消去圖中所有邊，使所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱(chēng)該圖是可完全簡(jiǎn)化的；若不能通過(guò)任何過(guò)程使該圖完全簡(jiǎn)化，則稱(chēng)該圖是不可完全簡(jiǎn)化的。假定某系統(tǒng)當(dāng)時(shí)的資源分配圖如下所示：（1）分析當(dāng)時(shí)系統(tǒng)是否存在死鎖。（2）若進(jìn)程P3 再申請(qǐng)R3 時(shí)，系統(tǒng)將發(fā)生什么變化，說(shuō)明原因。3. 3. 死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available，它表示了m類(lèi)資源中每一類(lèi)資源的可用數(shù)目

16、。 (2) 把不占用資源的進(jìn)程(向量Allocation=0)記入L表中， 即LiL。 (3) 從進(jìn)程集合中找到一個(gè)RequestiWork的進(jìn)程，做如下處理： 將其資源分配圖簡(jiǎn)化，釋放出資源，增加工作向量Work=Work+Allocationi。 將它記入L表中。 (4) 若不能把所有進(jìn)程都記入L表中， 便表明系統(tǒng)狀態(tài)S的資源分配圖是不可完全簡(jiǎn)化的。 因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。 Work =Available; L =Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work =W

17、ork+Allocationi; LiL; end end deadlock = (L=p1, p2, , pn); 7.6.3 解除死鎖n方法如下：n系統(tǒng)重新啟動(dòng)。n撤消所有死鎖進(jìn)程n退回到前一檢查點(diǎn)并從此點(diǎn)重新啟動(dòng)進(jìn)程.n逐個(gè)撤消死鎖進(jìn)程,直到死鎖不存在n逐個(gè)搶占死鎖進(jìn)程資源直到死鎖不存在7.6.4 處理死鎖的綜合措施n較理想的處理死鎖綜合措施如下：n內(nèi)部資源：系統(tǒng)本身使用的資源。如I/O通道、進(jìn)程控制塊，設(shè)備控制塊，系統(tǒng)保留區(qū)等。對(duì)內(nèi)部資源通過(guò)破壞循環(huán)等待條件，即對(duì)此類(lèi)資源使用有序資源分配法預(yù)防死鎖。n內(nèi)存資源：可以按幀或段分配給進(jìn)程的存儲(chǔ)空間。對(duì)內(nèi)存實(shí)行可剝奪式方法預(yù)防死鎖是最適合的策

18、略。當(dāng)一個(gè)進(jìn)程被剝奪后，它僅僅被換到外存，釋放空間以解決死鎖。n進(jìn)程資源：用于進(jìn)程的可分配設(shè)備，如打印機(jī)、文件等。對(duì)這類(lèi)資源，死鎖避免策略常常是很有效的，這是因?yàn)檫M(jìn)程可以事先聲明他們將需要的這類(lèi)資源。也可以采用有序資源分配法預(yù)防策略。n交換空間：進(jìn)程交換所使用的外存交換區(qū)。通過(guò)要求一次性分配所有請(qǐng)求的資源來(lái)預(yù)防死鎖。也可以采用死鎖避免措施。n復(fù)習(xí)思考題復(fù)習(xí)思考題n一 選擇題n1.銀行家算法是一種算法。nA.死鎖解除 B死鎖避免 C.死鎖預(yù)防 D死鎖檢測(cè)n2.在下列解決死鎖的方法中，屬于死鎖預(yù)防策略的是。nA.銀行家算法 B.資源有序分配法nC.死鎖檢測(cè)法 D.資源分配圖化簡(jiǎn)法n3.在為多道程序

19、所提供的可共享的系統(tǒng)資源不足時(shí)，可能出現(xiàn)死鎖。但是，不適當(dāng)?shù)囊部赡墚a(chǎn)生死鎖。nA.進(jìn)程優(yōu)先權(quán) B.資源的線(xiàn)性分配 C.進(jìn)程推進(jìn)順序 D.分配隊(duì)列優(yōu)先權(quán)n4.采用資源剝奪法可解除死鎖，還可以采用方法解除死鎖。nA.執(zhí)行并行操作 B.撤消進(jìn)程 C.拒絕分配新資源 D.修改信號(hào)量n5.資源的按序分配可以破壞條件。nA.互斥使用資源 B.占有且等待資源nC.非搶奪資源 D.循環(huán)等待資源n6.在的情況下，系統(tǒng)出現(xiàn)死鎖。nA.計(jì)算機(jī)系統(tǒng)發(fā)生了重大故障nB.有多個(gè)封鎖的進(jìn)程同進(jìn)存在nC.若干進(jìn)程因競(jìng)爭(zhēng)資源而無(wú)休止地相互等待他方釋放已占有的資源nD.資源數(shù)大大小于進(jìn)程數(shù)或進(jìn)程同時(shí)申請(qǐng)的資源大大超過(guò)資源總數(shù)n7.產(chǎn)生死鎖的四個(gè)必