OS之进程管理 --- 死锁
什么是死鎖
在正常操作模式下,進(jìn)程按如下順序來使用資源:
- 申請:進(jìn)程請求資源
- 使用:進(jìn)程對資源進(jìn)行操作
- 釋放:進(jìn)程釋放資源
當(dāng)一組進(jìn)程中的每一個(gè)進(jìn)程度在等待一個(gè)事件,而這事件只能有一組進(jìn)程的另一個(gè)進(jìn)程引起,那么這組進(jìn)程就處于死鎖狀態(tài)。
死鎖的特征
我們來看一個(gè)例子:互斥鎖的死鎖
采用互斥鎖的多線程Pthreads程序可能發(fā)生死鎖。函數(shù)pthread_mutex_init()將一個(gè)互斥鎖初始化為未加鎖。函數(shù)pthread_mutex_lock()和pthread_mutex_unlock()分別獲得和釋放互斥鎖,當(dāng)一個(gè)線程試圖獲得一個(gè)已加鎖的互斥鎖時(shí),它會(huì)堵塞,知道該互斥鎖的所有者調(diào)用pthread_mutex_unlock()
創(chuàng)建兩個(gè)互斥鎖:
創(chuàng)建兩個(gè)線程,即thread_one和thread_two,這些線程都能訪問這兩個(gè)互斥鎖,thread_one和thread_two分別運(yùn)行在do_work_one()和do_work_two()中:
void *do_work_one(void *param) {pthread_mutex_lock(&first_mutex);pthread_mutex_lock(&second_mutex);pthread_mutex_unlock(&second_mutex);pthread_mutex_unlock(&first_mutex);pthread_exit(0); }void *do_work_two(void *param) {pthread_mutex_lock(&second_mutex);pthread_mutex_lock(&first_mutex);pthread_mutex_unlock(&first_mutex);pthread_mutex_unlock(&second_mutex);pthread_exit(0); }這個(gè)例子中因?yàn)閮蓚€(gè)線程獲取和釋放互斥鎖的順序不同,有可能造成死鎖。注意:即使有可能死鎖,但是不一定會(huì)發(fā)生。
必要條件
如果一個(gè)系統(tǒng)中下面四個(gè)條件同時(shí)成立,那么就會(huì)引起死鎖:
- 互斥:至少有一個(gè)資源必須處于非共享模式,即一次只有一個(gè)進(jìn)程可以使用。
- 占有并等待:一個(gè)進(jìn)程應(yīng)占有至少一個(gè)資源,并等待另一個(gè)資源,而該資源為其他進(jìn)程所占有。
- 非搶占:資源不能被搶占,即資源只能被進(jìn)程完成任務(wù)后自愿釋放。
- 循環(huán)等待:有一組進(jìn)程 {P0P_0P0?,P1P_1P1?,…,PnP_nPn?},P0P_0P0?等待的資源為P1P_1P1?占有,P1P_1P1?等待的資源為P2P_2P2?所占有,…,Pn?1P_{n-1}Pn?1?等待的資源被PnP_nPn?所占有。
強(qiáng)調(diào):只有這四個(gè)條件同時(shí)成立時(shí)才會(huì)出現(xiàn)死鎖。
資源分配圖
資源分配圖是一種有向圖,該圖包括一個(gè)節(jié)點(diǎn)集合V和一個(gè)邊集合E。節(jié)點(diǎn)集合V可以分為兩種類型:P={P1P_1P1?,P2P_2P2?,…,PnP_nPn?}(系統(tǒng)中所有活動(dòng)進(jìn)程的集合)和R={R1R_1R1?,R2R_2R2?,…,RmR_mRm?}(系統(tǒng)中所有資源類型的集合).
從進(jìn)程PiP_iPi?到資源類型RjR_jRj?的有向邊記為PiP_iPi?→\rightarrow→RjR_jRj?,他表示進(jìn)程PiP_iPi?已經(jīng)申請了資源類型RjR_jRj?的一個(gè)實(shí)例,并且正在等待這個(gè)資源;RjR_jRj?→\rightarrow→PiP_iPi?表示資源的一個(gè)實(shí)例已經(jīng)分配給進(jìn)程PiP_iPi?了。有向邊PiP_iPi?→\rightarrow→RjR_jRj?稱為申請邊,RjR_jRj?→\rightarrow→PiP_iPi?稱為分配邊。
具體的資源分配圖詳解:資源分配圖
根據(jù)資源分配圖的定義,可以證明:如果分配圖沒有環(huán),那么系統(tǒng)沒有進(jìn)程死鎖。如果分配圖中存在環(huán),那么可能存在死鎖。
如果每個(gè)資源類型剛好有一個(gè)實(shí)例,那么有環(huán)就意味著已經(jīng)出現(xiàn)死鎖。如果環(huán)上每個(gè)類型只有一個(gè)實(shí)例,那么就出現(xiàn)了死鎖。換上的進(jìn)程就死鎖。在這種情況下圖中的環(huán)就是死鎖存在的充分且必要條件。
如果每個(gè)資源類型有多個(gè)實(shí)例,那么有環(huán)并不意味這已經(jīng)出現(xiàn)了死鎖,在這種情況下,圖中的環(huán)就是死鎖存在的必要不充分條件。
死鎖的處理方法
一般來說,處理死鎖的問題有三種:
- 通過協(xié)議來預(yù)防或避免死鎖,確保系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。
- 可以允許系統(tǒng)進(jìn)入死鎖狀態(tài),然后檢測并加以恢復(fù)
- 可以忽視這個(gè)問題,認(rèn)為死鎖不可能在系統(tǒng)內(nèi)發(fā)生。
第三種方法被大多數(shù)操作系統(tǒng)所采用,包括Linux和Windows。
死鎖預(yù)防
互斥
互斥條件必須成立,也就是說,至少一個(gè)資源應(yīng)該是非共享的。實(shí)際當(dāng)中,操作系統(tǒng)中一定需要互斥資源,所有通過解決互斥來打破死鎖的四個(gè)條件是不合理的。
持有且等待
當(dāng)每個(gè)進(jìn)程申請一個(gè)資源的時(shí)候,它不能占有其他資源。
一種可以采用的協(xié)議:每個(gè)進(jìn)程在執(zhí)行前申請并獲得所有的資源。即要求進(jìn)程申請資源的系統(tǒng)調(diào)用在其他系統(tǒng)調(diào)用之前完成。
另外一種協(xié)議:允許進(jìn)程僅在沒有資源時(shí)才可申請資源。一個(gè)進(jìn)程可申請一些資源并使用他們,在申請更多的其他資源之前,它應(yīng)該釋放現(xiàn)在已經(jīng)分配的資源。
兩者的差異:第一種要求在進(jìn)程執(zhí)行前申請執(zhí)行所需的所有的資源,在執(zhí)行過程中不能夠在申請,執(zhí)行完成后釋放所占有的所有資源;第二種要求先分配給進(jìn)程當(dāng)前可以執(zhí)行的資源數(shù)量,進(jìn)程執(zhí)行過程中如果缺少資源進(jìn)請求,在請求時(shí)先釋放自己占有的資源。
缺點(diǎn):
- 資源利用率比較低
因?yàn)樵S多資源坑你已經(jīng)分配,但是很長時(shí)間沒有使用 - 可能發(fā)生饑餓
一個(gè)進(jìn)程如需要多個(gè)常用資源,可能必須永久等待,因?yàn)樵谒枰馁Y源中至少有一個(gè)已經(jīng)分配給其他進(jìn)程。
無搶占
打破“不能搶占已分配的資源”,為了保證這個(gè)條件不成立,采用協(xié)議:如果一個(gè)進(jìn)程持有資源并申請另外一個(gè)不能立即分配的資源(也就是說,這個(gè)進(jìn)程應(yīng)該等待),那么他現(xiàn)在分配的資源都可被搶占。可以理解為這些資源都被隱式的釋放了。被搶占資源添加到進(jìn)程等待的資源列表中。只有當(dāng)進(jìn)程獲得其原有資源和申請的新資源時(shí),他才可以重新執(zhí)行。
循環(huán)等待
確保循環(huán)等待條件不成立的一個(gè)方法是:對所有資源類型進(jìn)行完全排序,而且要求每個(gè)進(jìn)程按遞增順序來申請資源。
假設(shè)資源類型的集合是R={R1R_1R1?, R2R_2R2?,…,RmR_mRm?},為每個(gè)資源類型分配一個(gè)唯一整數(shù),這樣可以比較兩個(gè)資源以確定他們的先后順序。
我們采用如下協(xié)議:每個(gè)進(jìn)程只能按遞增順序申請資源。即一個(gè)進(jìn)程開始可申請任何數(shù)量的資源類型RiR_iRi?的實(shí)例。換句話說,要求當(dāng)一個(gè)進(jìn)程申請資源類型RjR_jRj?時(shí),他應(yīng)該先釋放所有資源RiR_iRi?(F(RjR_jRj?) ≤\leq≤ F(RiR_iRi?))。如果需要同一類型的多個(gè)實(shí)例,那么應(yīng)該一起申請。
死鎖避免
死鎖避免算法動(dòng)態(tài)的檢查資源分配狀態(tài),以便確保遵化你等待條件不能成立。
安全狀態(tài)
如果系統(tǒng)能夠按一定順序來為每個(gè)進(jìn)程分配資源,仍然避免死鎖,那么系統(tǒng)的狀態(tài)就是安全的。更正式的說,只有存在一個(gè)安全序列,系統(tǒng)才處于安全狀態(tài)。
進(jìn)程序列<P1P_1P1?, P2P_2P2?, … , PnP_nPn?>在當(dāng)前分配狀態(tài)下為安全序列是指:對于每個(gè)PiP_iPi?,PiP_iPi?仍然可以申請資源數(shù)小于當(dāng)前可用資源加上所有進(jìn)程PjP_jPj?(j < i)所占有的資源。在這種情況下,進(jìn)程PiP_iPi?需要的資源即使不能立即可用,那么PiP_iPi?可以等待直到所有PjP_jPj?釋放資源。當(dāng)他們完成后,PiP_iPi?可得到需要的所有資源完成給定任務(wù),返回分配的資源,最后終止。當(dāng)PiP_iPi?終止時(shí),Pi+1P_{i+1}Pi+1?可得到他需要的資源,如此進(jìn)行,如果沒有這樣的序列存在,那么系統(tǒng)狀態(tài)就是非安全的。
安全狀態(tài)不是死鎖狀態(tài),相反,死鎖狀態(tài)是非安全狀態(tài)。然而不是所有的非安全狀態(tài)都能導(dǎo)致死鎖狀態(tài)。非安全狀態(tài)可能導(dǎo)致死鎖。只有在安全狀態(tài)下,操作系統(tǒng)就能避免非安全(和死鎖)狀態(tài)。在非安全狀態(tài)下,操作系統(tǒng)不能阻止進(jìn)程申請資源,因而可能死鎖。進(jìn)程行為控制了非安全狀態(tài)。
資源分配圖算法
除了申請邊和分配邊,引入需求邊,需求邊PiP_iPi?→\rightarrow→RjR_jRj?表示進(jìn)程PiP_iPi?可能在將來某個(gè)時(shí)候申請資源RjR_jRj?。當(dāng)進(jìn)程PiP_iPi?申請資源時(shí)RjR_jRj?時(shí),需求邊PiP_iPi?→\rightarrow→RjR_jRj?變成了申請邊,類似當(dāng)進(jìn)程PiP_iPi?釋放RjR_jRj?時(shí),分配邊RjR_jRj?→\rightarrow→PiP_iPi?變成了需求邊PiP_iPi?→\rightarrow→RjR_jRj?。
現(xiàn)在假設(shè)進(jìn)程PiP_iPi?申請資源RjR_jRj?,只有在將申請邊PiP_iPi?→\rightarrow→RjR_jRj?變成分配邊RjR_jRj?→\rightarrow→PiP_iPi?并且不會(huì)導(dǎo)致資源分配圖形成環(huán)時(shí),才能允許申請。
如果沒有環(huán)存在,那么資源的分配會(huì)使系統(tǒng)處于安全狀態(tài)。如果有環(huán)存在,那么分配會(huì)導(dǎo)致系統(tǒng)處于非安全狀態(tài),這種情況下,進(jìn)程PiP_iPi?應(yīng)該等待資源申請。
銀行家算法
設(shè)n為系統(tǒng)進(jìn)程的數(shù)量,m為資源類型的種類。定義數(shù)據(jù)結(jié)構(gòu):
Available:長度為m的向量,表示每種資源的可用實(shí)例數(shù)量,如果Available[j]=k,那么資源類型RjR_jRj?有k個(gè)可用實(shí)例。
Max:n×\times×m矩陣,定義每個(gè)進(jìn)程的最大需求。如果Max[i][j]=k,那么進(jìn)程PiP_iPi?最多可申請?jiān)搭愋?span id="ze8trgl8bvbq" class="katex--inline">RjR_jRj?的k個(gè)實(shí)例
Allocation:n×\times×m矩陣,定義每個(gè)進(jìn)程現(xiàn)在分配的每種資源類型的實(shí)例數(shù)量,如果Allocation[i][j]=k,那么進(jìn)程PiP_iPi?現(xiàn)在已分配了資源類型RjR_jRj?的k個(gè)實(shí)例。
Need:n×\times×m矩陣,表示每個(gè)進(jìn)程還需要的剩余資源。如果Need[i][j]=k,那么進(jìn)程PiP_iPi?還可能申請k個(gè)資源類型RjR_jRj?的實(shí)例。
注意:Need[i][j]=Max[i][j] - Allocation[i][j]。
安全算法
通過安全算法以求出系統(tǒng)是否處于安全狀態(tài),描述如下:
a. Finish[i] == false
b. NeediNeed_iNeedi? ≤\leq≤Work
如果沒有這樣的i存在,那么轉(zhuǎn)到第4步
Finish[i]=true
返回第2步
這個(gè)算法可能需要m ×\times× n2n^2n2數(shù)量級(jí)的操作,以確定系統(tǒng)狀態(tài)是否安全。
資源請求算法
現(xiàn)在描述是否安全允許請求的算法:
設(shè)RequestiRequest_iRequesti?為進(jìn)程PiP_iPi?的請求向量。如果RequestiRequest_iRequesti?[j]==k,那么進(jìn)程PiP_iPi?需要的資源類型RjR_jRj?的實(shí)例數(shù)量為k,當(dāng)進(jìn)程PiP_iPi?做出這一資源請求時(shí),采取如下動(dòng)作:
Available = Available - RequestiRequest_iRequesti?
AllocationiAllocation_iAllocationi? = AllocationiAllocation_iAllocationi? + RequestiRequest_iRequesti?
NeediNeed_iNeedi? = NeediNeed_iNeedi? - RequestiRequest_iRequesti?
如果新的資源分配狀態(tài)是安全的,那么交易完成且進(jìn)程PiP_iPi?可分配到需要的資源。然而,如果新狀態(tài)不安全,那么進(jìn)程PiP_iPi?應(yīng)等待RequestiRequest_iRequesti?并恢復(fù)到原來的資源分配狀態(tài)。
死鎖檢測
如果一個(gè)系統(tǒng)既不采用死鎖預(yù)防算法也不采用死鎖避免算法,那么死鎖可能出現(xiàn),在這種情況下,系統(tǒng)可以提供:
- 一個(gè)用來檢查系統(tǒng)狀態(tài)從而確定是否出現(xiàn)死鎖的算法
- 一個(gè)用來從死鎖狀態(tài)恢復(fù)的算法
每個(gè)資源類型只有單個(gè)實(shí)例
如果所有資源類型只有單個(gè)實(shí)例,那么可以通過等待圖來作為死鎖檢測算法。
等待圖就是從資源分配圖中,刪除所有資源類型節(jié)點(diǎn),合并適當(dāng)邊,從而得到等待圖
當(dāng)且僅當(dāng)在等待圖中有一個(gè)環(huán),系統(tǒng)死鎖。為了檢測死鎖,系統(tǒng)需要維護(hù)等待圖,并周期調(diào)用用于搜索圖中環(huán)的算法。
注意:等待圖算法不適用于每種資源類型可有多個(gè)實(shí)例的資源分配系統(tǒng)
每種資源類型可有多個(gè)實(shí)例
定義如下數(shù)據(jù)結(jié)構(gòu):
Available:長度為m的向量,表示各種資源的可用實(shí)例數(shù)量
Allocation:n×\times×m矩陣,表示每個(gè)進(jìn)程的每種資源的當(dāng)前分配數(shù)量
Request:n×\times×m矩陣,表示當(dāng)前每個(gè)進(jìn)程的每種資源的當(dāng)前請求,如果Request[i][j]=k,那么PiP_iPi?現(xiàn)在正在請求資源類型RjR_jRj?的k個(gè)實(shí)例。
可以看出該算法和銀行家算法類似,可以進(jìn)行比較理解,該算法的描述如下:
a. Finish[i]=false
b. RequestiRequest_iRequesti? ≤\leq≤ Work
如果沒有這樣的i,則轉(zhuǎn)到第4步
Finish[i] = true
轉(zhuǎn)到第2步
死鎖恢復(fù)
進(jìn)程終止
通過終止進(jìn)程來消除死鎖,有兩種方法,都是通過允許系統(tǒng)回收終止進(jìn)程的所有分配資源:
- 終止所有死鎖進(jìn)程
這種方法代價(jià)很大。這些死鎖進(jìn)程可能已經(jīng)計(jì)算了較長時(shí)間,這些部分計(jì)算的結(jié)果也要放棄,并且以后可能還要重新計(jì)算 - 一次終止一個(gè)進(jìn)程,知道消除死鎖循環(huán)為止
這種方法的開銷相當(dāng)大,因?yàn)槊看谓K止一個(gè)進(jìn)程,都要調(diào)用死鎖檢測算法,以確定是否仍有進(jìn)程處于死鎖。
資源搶占
通過資源搶占來消除死鎖,我們不斷搶占一些進(jìn)程的資源以便給其他進(jìn)程使用,直到死鎖循環(huán)被打破為止。如果要采用搶占來處理死鎖,需要考慮三個(gè)問題:
- 選擇犧牲進(jìn)程
- 回滾
被搶占的進(jìn)程不能繼續(xù)正常執(zhí)行,我們應(yīng)將該進(jìn)程回滾到某個(gè)安全狀態(tài),以便從該狀態(tài)重啟進(jìn)程。 - 饑餓
即如何保證資源不會(huì)總是從同一進(jìn)程中被搶占
參見:《操作系統(tǒng)概念》(第九版)
轉(zhuǎn)載于:https://www.cnblogs.com/lishanlei/p/10707691.html
總結(jié)
以上是生活随笔為你收集整理的OS之进程管理 --- 死锁的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Qt高级——QTestLib单元测试框架
- 下一篇: 分布式之redis