windows操作系統(tǒng)概述

,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第十講 死鎖,目的與要求,：,了解死鎖的定義，掌握死鎖預(yù)防，了解死鎖避免，死鎖檢測，死鎖恢復(fù)的方法。,重點與難點,：,死鎖預(yù)防法則的使用。,作業(yè),：21，22,4.4 死鎖,4.4.1 死鎖示例,日常生活中的例子,進(jìn)程死鎖的例子,競爭外部設(shè)備,競爭輔存空間,編程錯的例子,4.4.2 死鎖定義及性質(zhì),死鎖定義,在一個進(jìn)程集合中，若,每個進(jìn)程,都在等待某些事件（指：,釋放資源,）的發(fā)生，而這些事件又必須由,這個進(jìn)程集合,中的某些進(jìn)程來產(chǎn)生，就稱該進(jìn)程集合處于死鎖狀態(tài),。,死鎖定義及性質(zhì),出現(xiàn)死鎖的系統(tǒng)必須同時滿足下列四個必要條件,互斥,：必須存在需要互斥使用的資源,占有等待：,一定有占有資源而又等待其它資源的進(jìn)程,非剝奪：,系統(tǒng)中進(jìn)程占有的資源未主動釋放時不可以剝奪,循環(huán)等待：,進(jìn)程集合P0,P1,Pn，Pi等待Pi+1，Pn等待P0,死鎖定義及性質(zhì),資源分配圖定義,資源分配圖由如下部件組成：,如果各類資源數(shù)為1，則系統(tǒng)出現(xiàn)死鎖的充要條件是資源分配圖含圈,Pi,.,.,.,.,死鎖研究的主要內(nèi)容,死鎖防止,死鎖避免,死鎖檢測,死鎖恢復(fù),無死鎖系統(tǒng),允許死鎖、,出現(xiàn)排除,4.4.3 死鎖防止,邏輯公式：,DC1C2C3C4,C1,C2,C3,C4,D,破壞互斥占用條件,讓資源都能共享使用（但有些資源必須互斥使用）,破壞占有等待條件,將進(jìn)程所要資源一次性分給進(jìn)程，要么沒分到一個資源，要么全部滿足（適合廉價資源的分配,如外存空間分配）,進(jìn)程在下一輪申請資源時，釋放所占的所有資源(用完一個再用下一個),破壞非剝奪條件(用于內(nèi)存管理、CPU管理等),當(dāng)進(jìn)程Pi申請ri類資源時，若有則分配，若沒有則剝奪（釋放）Pi占有的所有資源；,當(dāng)進(jìn)程Pi申請ri類資源時，若有則分配，若無則剝奪（淘汰）占有ri類資源進(jìn)程所占的ri類資源分配給Pi；或看占用ri類資源的Pk處于什么狀態(tài)，若處于等資源狀態(tài)，則剝奪其資源，否則讓Pi等待,等于剝奪Pi的資源。,破壞循環(huán)等待條件,采用資源順序分配方法：給每類資源編號，進(jìn)程只能按序號由小到大的順序申請資源，若不滿足則拒絕分配。,反證：若出現(xiàn)循環(huán)等待，則必會有小序號資源序號大序號資源序號。,4.4.4 死鎖避免,銀行家算法,(,在系統(tǒng)處理資源申請時，判斷在滿足申請時，系統(tǒng)是否還處于安全狀態(tài)？是則滿足本次資源申請，否則拒絕。依此引導(dǎo)進(jìn)程運行次序),單類資源系統(tǒng)安全狀態(tài)定義：設(shè)系統(tǒng)中有n個進(jìn)程，若存在一個序列P1，2n使得Pi(i1，2n)以后還需要的資源可以通過系統(tǒng)現(xiàn)有資源加上所有Pj(ji)占有的資源來滿足，則稱這個系統(tǒng)處于,安全狀態(tài),序列，n稱為,安全序列,。,舉例,設(shè)銀行家有10萬貸款，P,Q,R分別需要8,3,9萬元搞項目（假設(shè)任何人滿足資金總額后都會歸還所有貸款），如果P已申請到了4萬，Q要申請2萬，顯然，如果滿足Q的申請，有安全序列 /。,但如果R要申請4萬，顯然，如果滿足R的申請，則不存在安全序列。,擴(kuò)展的銀行家算法描述,n：系統(tǒng)中的進(jìn)程個數(shù)。m：系統(tǒng)中的資源類型數(shù)。,Available(1:m):現(xiàn)有資源向量,。Available(j)=k表示有k個未分配的j類資源。,Max(1:n,1:m):資源最大申請量矩陣,。Max(i,j)=k表示第i個進(jìn)程對第j類資源的最大申請量為k.,Allocation(1:n,1:m):資源分配矩陣,。,Allocation(i,j)=k表示進(jìn)程i已占有k個j類資源。,Need(1:n,1:m):進(jìn)程以后還需要的資源矩陣。,Need(i,j)=k表示第i個進(jìn)程以后還需要k個第j類資源。顯然Need=Max-Allocation,Request(1:n,1:m):進(jìn)程申請資源矩陣,。Request(i,j)=k表示進(jìn)程i申請k個第j類資源。,資源分配程序的工作過程：,當(dāng)進(jìn)程提出資源申請時，系統(tǒng)首先檢查該進(jìn)程對資源的申請量是否超過其最大需求量及系統(tǒng)現(xiàn)有資源能否滿足進(jìn)程需要。若能則進(jìn)一步檢查：若把資源分給該進(jìn)程系統(tǒng)能否處于安全狀態(tài)。若安全則分配，否則置該進(jìn)程為等待資源狀態(tài)。,為簡單起見，記Ai為,A(i,1),A(i,2)A(i,m)。其中A為nm矩陣。,定義長度為m的向量 X、Y間的關(guān)系為：,XY當(dāng)且僅當(dāng)X(i)Y(i)(i=1,2m),1、如果Request,i,Need,i,則報錯返回。,2、如果Request,i,Available,則進(jìn)程i進(jìn)入等待,資源狀態(tài)，返回。,3、假設(shè)進(jìn)程i的申請已獲準(zhǔn)，于是修改系統(tǒng)狀態(tài)：,Available=Available-Request,i,Allocation,i,=Allocation,i,+Request,i,Need,i,=Need,i,-Request,i,4、調(diào)用安全狀態(tài)檢查算法。,設(shè)進(jìn)程i申請資源，申請資源向量為Request,i,，則有如下的資源分配過程：,（續(xù)）,5、若系統(tǒng)處于安全狀態(tài)，則將進(jìn)程i申請的資源分配給進(jìn)程i，返回。,6、若系統(tǒng)處于不安全狀態(tài)，則進(jìn)程i進(jìn)入等待資源狀態(tài)，并恢復(fù)系統(tǒng)狀態(tài)后返回：,Available=Available+Request,i,Allocation,i,=Allocation,i,-Request,i,Need,i,=Need,i,+Request,i,安全狀態(tài)檢查算法,：,設(shè)Work(1:m)為臨時工作向量。初始時Work=Available.令N=1，2n,1、尋找jN使其滿足Need,j,Work,若不存,在這樣的j則轉(zhuǎn)(3),2、Work=Work+Allocation,j,N=N-j,轉(zhuǎn)(1),3、如果N為空則返回(系統(tǒng)安全)；如果N,不為空則返回(系統(tǒng)不安全)。,舉例,Allocation Max Requestavailable,P1 1 2 4 2 5 8 1 2 1 1 3 3,P2 0 3 3 4 4 4 3 0 0,P3 4 1 1 5 4 4 1 2 2,如果p1先申請，無安全序列。,如果p3申請，可有安全序列或。,4.4.5 死鎖檢測,資源分配圖的簡化過程：,1.在圖中找一個進(jìn)程頂點i,Pi的請求邊,均能立即滿足。,2.若找到這樣的Pi則將與i相連的邊全部,刪去，轉(zhuǎn)(1)；否則化簡過程結(jié)束。,采用化簡資源分配圖的方法可以檢測系統(tǒng)中有無進(jìn)程處于死鎖狀態(tài)。,如果化簡后所有的進(jìn)程頂點都成了孤立點，則稱該圖可完全化簡；否則稱該圖是不可完全化簡的。,系統(tǒng)中有死鎖的充分必要條件是資源分配圖不可完全化簡。,死鎖檢測算法,設(shè)Work(1:m)為臨時工作向量。初始時Work=Available.令N=1，2n,尋找,jN,使其滿足,Request,j,Work,若不存在這樣的,j,則轉(zhuǎn),(3),Work=,Work+Allocation,j,N=N-j,轉(zhuǎn),(1),如果,N,為空則無死鎖；如果,N,不為空,則有死鎖，,N,就是處于死鎖狀態(tài)的進(jìn)程集合,4.4.6 死鎖恢復(fù),檢測出死鎖后的處理,破壞循環(huán)等待（殺掉有關(guān)進(jìn)程）,4.4.7 死鎖的綜合處理,把系統(tǒng)中的資源分成幾大類，整體上采用資源順序分配法，再對每類資源根據(jù)其特點選擇最適合的方法。,例如：,（1）主存、處理機(jī)-剝奪法,（2）輔存 -預(yù)分配法,（3）其他 -死鎖檢測,交通死鎖的示例,讓路！,讓路！,讓路！,讓路！,進(jìn)程A進(jìn)程B,申請輸入設(shè)備申請輸出設(shè)備,申請輸出設(shè)備申請輸入設(shè)備,釋放輸入設(shè)備釋放輸出設(shè)備,釋放輸出設(shè)備釋放輸入設(shè)備,如果執(zhí)行次序為：進(jìn)程A進(jìn)程B.，,則發(fā)生死鎖。,輸入設(shè)備,輸出設(shè)備,B,A,輸入設(shè)備,輸出設(shè)備,占有,占有,等待,等待,A在干什么？,B在干什么？,競爭外設(shè)死鎖示例,A,B,C,D,E,L,M,N,O,P,Q,F,G,H,I,J,K,A,A,B,B,C,C,D,D,F,G,H,I,L,L,M,M,N,N,O,O,F,G,H,I,SPOOLing,系統(tǒng)死鎖示例,輸出井,進(jìn)程,B,進(jìn),程,C,滿啦！,不夠！,不夠！,不夠！,進(jìn)程,A,