死鎖的產(chǎn)生因素

一、死鎖的概念

操作系統(tǒng)中的死鎖是指：

如果在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能有該集合中的其它進(jìn)程才能引起的事件，而無(wú)限期陷入僵持的局面稱為死鎖。

二、死鎖的產(chǎn)生因素

1、系統(tǒng)擁有的資源數(shù)量

2、資源分配策略

3、進(jìn)程對(duì)資源的使用要求

4、并發(fā)進(jìn)程的推薦順序

三、死鎖的必要條件

1、互斥條件

進(jìn)程互斥使用資源，一旦某個(gè)資源被占用，欲使用該資源的進(jìn)程必須等待。

2、占有和等待條件（部分分配條件）

進(jìn)程申請(qǐng)新資源得不到滿足而等待時(shí)，不釋放已占有資源。

3、不剝奪條件

一個(gè)進(jìn)程不能搶奪其它進(jìn)程占有的資源。

4、循環(huán)等待條件（環(huán)路條件）

存在一組進(jìn)程循環(huán)等待資源的現(xiàn)象。

前三個(gè)條件是死鎖產(chǎn)生的必要條件，不是充分條件。第四個(gè)條件是前三個(gè)條件同時(shí)存在時(shí)產(chǎn)生的結(jié)果。只要破壞這四個(gè)條件之一，死鎖就可防止。

四、死鎖防止

死鎖防止通過(guò)破壞產(chǎn)生死鎖的四個(gè)條件之一來(lái)實(shí)現(xiàn)。

1、破壞互斥條件

使資源可同時(shí)訪問(wèn)而不是互斥使用。

該辦法對(duì)于磁盤適用，對(duì)于磁帶機(jī)、打印機(jī)等多數(shù)資源不僅不能破壞互斥使用條件，還要加以保證。

2、破壞占有和等待條件

靜態(tài)分配可以破壞占有和等待條件。

靜態(tài)分配是指一個(gè)進(jìn)程必須在執(zhí)行前就申請(qǐng)它所需要的全部資源，并且直到它所需要的資源都得到滿足后才開(kāi)始執(zhí)行。資源利用率低。

3、破壞不剝奪條件

采用剝奪式調(diào)度方法。

當(dāng)進(jìn)程申請(qǐng)資源未獲準(zhǔn)許時(shí)，在等待前主動(dòng)釋放資源。剝奪調(diào)度方法目前只適用于內(nèi)存資源和處理器資源。

4、破壞循環(huán)等待條件

采用層次分配策略可以破壞循環(huán)等待條件。

層次分配策略將資源被分成多個(gè)層次，進(jìn)程按照由低到高的層次順序申請(qǐng)和得到資源，按照由高到低的層次順序釋放資源。當(dāng)進(jìn)程得到某一層的一個(gè)資源后，如果需要申請(qǐng)?jiān)搶拥牧硪粋€(gè)資源，則必須先釋放該層中的已占資源。

五、死鎖避免

1、避免死鎖的策略

死鎖避免方法允許系統(tǒng)中同時(shí)存在死鎖的三個(gè)必要條件，即互斥、占有且等待和非搶占；

每當(dāng)進(jìn)程提出資源申請(qǐng)時(shí)，系統(tǒng)分析滿足該資源請(qǐng)求時(shí)系統(tǒng)是否會(huì)發(fā)生死鎖，若不會(huì)發(fā)生則實(shí)施分配，否則拒絕分配。

銀行家算法就是避免死鎖的一種方法。

2、銀行家算法思想

一個(gè)銀行家擁有資金M，被N個(gè)客戶共享，銀行家對(duì)客戶提出下列約束條件：

① 每個(gè)客戶必須預(yù)先說(shuō)明自己所要求的最大資金量；

② 每個(gè)客戶每次提出部分資金量申請(qǐng)和獲得分配；

③ 如果銀行滿足了客戶對(duì)資金的最大需求量，則客戶在資金運(yùn)作后一定可以很快歸還資金。

3、銀行家算法在死鎖問(wèn)題上的應(yīng)用

步驟：

① 系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合；

② 在安全狀態(tài)下對(duì)進(jìn)程請(qǐng)求的資源進(jìn)行試探性分配；

③ 系統(tǒng)用剩余的可用資源和進(jìn)程集合中其它進(jìn)程還要的資源數(shù)作比較，找到剩余資源能滿足最大需求量的進(jìn)程A，保證A運(yùn)行完畢并歸還全部資源；

④ 把進(jìn)程A從集合中去掉，相當(dāng)于回收其資源。如果進(jìn)程集合非空，則返回②；

⑤ 若進(jìn)程集合為空，則系統(tǒng)處于安全狀態(tài)，可實(shí)施本次分配；否則，系統(tǒng)處于不安全狀態(tài)，本次資源分配暫不實(shí)施，申請(qǐng)進(jìn)程等待。

安全狀態(tài)與不安全狀態(tài)：

如果系統(tǒng)能夠按某種進(jìn)程順序（P1，P2，… … ，Pn）（稱< P1，P2，… … ，Pn >序列為安全序列），為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都能順利完成，則稱系統(tǒng)處于安全狀態(tài)。

如果找不到這樣的安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

例：

4、銀行家算法的缺點(diǎn)

① 使用銀行家算法時(shí)，很難在進(jìn)程運(yùn)行前知道其所需的資源最大量；② 算法要求系統(tǒng)中的進(jìn)程必須是無(wú)關(guān)的，相互間沒(méi)有同步要求；③ 進(jìn)程的個(gè)數(shù)和分配的資源數(shù)目應(yīng)該是固定的；這些要求事先難以滿足，因而銀行家算法缺乏實(shí)用價(jià)值。

六、死鎖檢測(cè)與解除

1、死鎖檢測(cè)策略

死鎖檢測(cè)和解除對(duì)資源分配不加任何限制，也不采取死鎖避免措施，但系統(tǒng)定時(shí)運(yùn)行一個(gè)“死鎖檢測(cè)”程序，如果檢測(cè)到系統(tǒng)發(fā)生了死鎖，再采取措施解除它。

進(jìn)程-資源分配圖是描述進(jìn)程和資源間申請(qǐng)與分配關(guān)系的一種有向圖，可用以檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)。

2、進(jìn)程-資源分配圖的結(jié)構(gòu)

進(jìn)程-資源分配圖由進(jìn)程結(jié)點(diǎn)P、資源結(jié)點(diǎn)R和有向邊組成。

有向邊：

① 請(qǐng)求邊：

從進(jìn)程指向資源的有向邊Pi→Rj為請(qǐng)求邊，表示進(jìn)程Pi申請(qǐng)資源類Rj中的一個(gè)資源。

② 分配邊：

從資源指向進(jìn)程的有向邊Rj→Pi為分配邊，表示Rj類中的一個(gè)資源已分配給進(jìn)程Pi。

3、進(jìn)程-資源分配圖與死鎖判斷的關(guān)系

① 如果進(jìn)程-資源分配圖中無(wú)環(huán)路

——>則此時(shí)系統(tǒng)沒(méi)有發(fā)生死鎖

② 如果進(jìn)程-資源分配圖中有環(huán)路，且每個(gè)資源類中僅有一個(gè)資源

——>則系統(tǒng)中發(fā)生了死鎖，此時(shí)，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程

③ 如果進(jìn)程-資源分配圖中有環(huán)路，且涉及的資源類中有多個(gè)資源

——>則環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件

4、死鎖的檢測(cè)和解除方法

死鎖定理

系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程-資源分配圖是不可完全簡(jiǎn)化的。該充分條件稱為死鎖定理。

簡(jiǎn)化進(jìn)程-資源分配圖

① 從進(jìn)程-資源分配圖中找到一個(gè)既不阻塞又非獨(dú)立的進(jìn)程，消去所有與該進(jìn)程相連的有向邊，相當(dāng)于該進(jìn)程能夠執(zhí)行完成而釋放資源，回收資源使之成為孤立結(jié)點(diǎn)。

② 然后將所回收的資源分配給其它進(jìn)程，再?gòu)倪M(jìn)程-資源分配圖中找到下一個(gè)既不阻塞又非獨(dú)立的進(jìn)程，消去所有與該進(jìn)程相連的有向邊，使之成為孤立結(jié)點(diǎn)。

③ 不斷重復(fù)該過(guò)程，直到所有進(jìn)程成為孤立結(jié)點(diǎn)，則稱該圖是可完全化簡(jiǎn)的；否則稱該圖是不可完全化簡(jiǎn)的。

死鎖檢測(cè)實(shí)例：

問(wèn)題求解：

解決思路：無(wú)法應(yīng)用死鎖判定原則，需要化簡(jiǎn)。按照P1、P2和P3的順序逐一考察每個(gè)進(jìn)程，判斷其是否孤立和阻塞。

① P1、P2和P3三個(gè)進(jìn)程均不孤立，接下來(lái)需要判斷它們是否阻塞。

② P1：該進(jìn)程請(qǐng)求資源R1，而R1僅有的一個(gè)資源已經(jīng)分配給P2，所以P1阻塞；

③ 該進(jìn)程請(qǐng)求資源R2，而R2僅有的一個(gè)資源已經(jīng)分配給P3，所以P2阻塞。

④ 該進(jìn)程請(qǐng)求資源R3，而R3的兩個(gè)資源已經(jīng)分別分配給P1和P2，所以P3阻塞。

結(jié)論：進(jìn)程-資源分配圖無(wú)法完全化簡(jiǎn)，因此進(jìn)程集合發(fā)生死鎖。

5、死鎖檢測(cè)算法與死鎖避免算法比較

① 死鎖檢測(cè)算法考慮了檢查每個(gè)進(jìn)程還需要的所有資源能否滿足要求；

死鎖避免算法則僅根據(jù)進(jìn)程的當(dāng)前申請(qǐng)資源量來(lái)判斷系統(tǒng)是否進(jìn)入了不安全狀態(tài)。

② 死鎖檢測(cè)算法處理的進(jìn)程-資源圖中可以同時(shí)存在多個(gè)進(jìn)程的請(qǐng)求邊。

在銀行家算法中，一次僅允許一個(gè)進(jìn)程提出資源請(qǐng)求，做安全分析并分配資源后，才允許下一個(gè)進(jìn)程提出資源請(qǐng)求。

6、死鎖的解除方法

① 立即結(jié)束所有進(jìn)程的執(zhí)行，并重新啟動(dòng)操作系統(tǒng)。以前工作全部作廢，損失可能很大。

② 剝奪陷于死鎖的進(jìn)程占用的資源，但并不撤銷它，直至死鎖解除。

③ 撤銷陷于死鎖的所有進(jìn)程，解除死鎖繼續(xù)運(yùn)行。

④ 逐個(gè)撤銷陷于死鎖的進(jìn)程，回收其資源，直至死鎖解除。

⑤ 根據(jù)系統(tǒng)保存的檢查點(diǎn)，使所有進(jìn)程回退，直到足以解除死鎖。

⑥ 當(dāng)檢測(cè)到死鎖時(shí)，如果存在某些未卷入死鎖的進(jìn)程，且它們會(huì)進(jìn)一步建立一些新的抑制進(jìn)程能執(zhí)行到結(jié)束，則它們可能釋放足夠的資源來(lái)解除死鎖。