1、死鎖、銀行家算法,1.死鎖概念,指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。 即：一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱(chēng)為進(jìn)程死鎖，這一組進(jìn)程就稱(chēng)為死鎖進(jìn)程。,思考：,如果系統(tǒng)中有n個(gè)進(jìn)程，則在等待隊(duì)列中進(jìn)程的個(gè)數(shù)最多為（ ）個(gè) 有n個(gè)進(jìn)程的系統(tǒng)出現(xiàn)死鎖時(shí)，死鎖進(jìn)程的個(gè)數(shù)k應(yīng)滿足的條件是（）,產(chǎn)生死鎖的原因,1.競(jìng)爭(zhēng)資源（資源不足） 2.進(jìn)程的推進(jìn)順序不當(dāng),1. 競(jìng)爭(zhēng)系統(tǒng)資源,若系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)讀卡機(jī)R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會(huì)產(chǎn)生死鎖。,由于進(jìn)程的調(diào)度是獨(dú)

2、立的，請(qǐng)求和釋放操作可按如下序列進(jìn)行： Ar1, Ar2, Ar3, Ar4, Br1, Br2, Br3, Br4 Br1, Br2, Br3, Br4, Ar1, Ar2, Ar3, Ar4 Ar1, Ar2 .Br1, Ar3, Ar4, Br2, Br3, Br4 Ar1, Br1, Ar2, Br2, Ar3, Ar4, Br3, Br4 對(duì)序列三個(gè)進(jìn)程都能順利進(jìn)行，則會(huì)產(chǎn)生死鎖。,進(jìn)程A、 B對(duì)資源的請(qǐng)求和釋放,2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖,思考：,某系統(tǒng)中有3個(gè)并發(fā)進(jìn)程都需要4個(gè)同類(lèi)資源，該系統(tǒng)不會(huì)發(fā)生死鎖的最少資源是（ ）個(gè) P341 例8,2. 死鎖避免,死鎖避免定義:在系統(tǒng)

3、運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。,由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算法。,3. 安全狀態(tài)與不安全狀態(tài),安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序P1，Pn來(lái)為每個(gè)進(jìn)程Pi(1in）分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)。如果存在，則稱(chēng)序列為安全序列

4、。,說(shuō) 明,并非所有的不安全狀態(tài)都必然會(huì)轉(zhuǎn)為死鎖狀態(tài)，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便有可能進(jìn)入死鎖。 安全狀態(tài)一定是沒(méi)有死鎖發(fā)生的。 避免死鎖的實(shí)質(zhì)：系統(tǒng)進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。,2) 安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：,問(wèn)：T0時(shí)刻是否安全？,3) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。 例如，在T0時(shí)刻以后，P3又請(qǐng)求

5、1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)椋藭r(shí)也無(wú)法再找到一個(gè)安全序列， 例如，把其余的2臺(tái)分配給P2，這樣，在P2完成后只能釋放出4臺(tái)，既不能滿足P1尚需5臺(tái)的要求，也不能滿足P3尚需6臺(tái)的要求，致使它們都無(wú)法推進(jìn)到完成，彼此都在等待對(duì)方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 P3的請(qǐng)求應(yīng)拒絕。,安全狀態(tài)與不安全狀態(tài),不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)不一定導(dǎo)致死鎖,4.利用銀行家算法避免死鎖,1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu),(1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值是系

6、統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目，其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類(lèi)資源K個(gè)。,(2) 最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類(lèi)資源的最大數(shù)目為K。 (3) 分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類(lèi)資源的數(shù)目為K。,(4) 需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)。如果N

7、eedi,j=K，則表示進(jìn)程i還需要Rj類(lèi)資源K個(gè)，方能完成其任務(wù)。 Needi,j=Maxi,j-Allocationi,j,2)銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類(lèi)型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無(wú)足夠資源，Pi須等待。,(3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Av

8、ailablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。,3)安全性算法,(1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)，Work=Available; Finish: 它表示系統(tǒng)是否有

9、足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi=false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。,(2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2;,(4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)

10、。,4) 銀行家算法之例,假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類(lèi)資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-16 所示。,圖 3-16 T0時(shí)刻的資源分配表,(1) T0時(shí)刻的安全性檢查,圖 3-17 T0時(shí)刻的安全序列,(2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocatio

11、n1和Need1向量，由此形成的資源變化情況如圖 3-16 中的圓括號(hào)所示。 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如圖 3-18,圖 3-18 P1申請(qǐng)資源時(shí)的安全性檢查,(3) P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓P4等待。 (4) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)A