當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

OS之进程管理 --- 死锁

發(fā)布時(shí)間：2025/3/15 编程问答 14 豆豆

生活随笔收集整理的這篇文章主要介紹了 OS之进程管理 --- 死锁小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

什么是死鎖

在正常操作模式下，進(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è)互斥鎖：

pthread_mutex_t first_mutex; pthread_mutex_t second_mutex;pthread_mutex_init(&first_mutex, NULL); pthread_mutex_init(&second_mutex, NULL);

創(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)程 { $P_0$ ， $P_1$ ，…， $P_n$ }， $P_0$ 等待的資源為 $P_1$ 占有， $P_1$ 等待的資源為 $P_2$ 所占有，…， $P_{n-1}$ 等待的資源被 $P_n$ 所占有。

強(qiáng)調(diào)：只有這四個(gè)條件同時(shí)成立時(shí)才會(huì)出現(xiàn)死鎖。

資源分配圖

資源分配圖是一種有向圖，該圖包括一個(gè)節(jié)點(diǎn)集合V和一個(gè)邊集合E。節(jié)點(diǎn)集合V可以分為兩種類型：P={ $P_1$ , $P_2$ ,…, $P_n$ }(系統(tǒng)中所有活動(dòng)進(jìn)程的集合)和R={ $R_1$ , $R_2$ ,…, $R_m$ }(系統(tǒng)中所有資源類型的集合).
從進(jìn)程 $P_i$ 到資源類型 $R_j$ 的有向邊記為 $P_i$ $→\rightarrow$ $R_j$ ，他表示進(jìn)程 $P_i$ 已經(jīng)申請了資源類型 $R_j$ 的一個(gè)實(shí)例，并且正在等待這個(gè)資源； $R_j$ $→\rightarrow$ $P_i$ 表示資源的一個(gè)實(shí)例已經(jīng)分配給進(jìn)程 $P_i$ 了。有向邊 $P_i$ $→\rightarrow$ $R_j$ 稱為申請邊， $R_j$ $→\rightarrow$ $P_i$ 稱為分配邊。

具體的資源分配圖詳解：資源分配圖

根據(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={ $R_1$ , $R_2$ ,…, $R_m$ }，為每個(gè)資源類型分配一個(gè)唯一整數(shù)，這樣可以比較兩個(gè)資源以確定他們的先后順序。
我們采用如下協(xié)議：每個(gè)進(jìn)程只能按遞增順序申請資源。即一個(gè)進(jìn)程開始可申請任何數(shù)量的資源類型 $R_i$ 的實(shí)例。換句話說，要求當(dāng)一個(gè)進(jìn)程申請資源類型 $R_j$ 時(shí)，他應(yīng)該先釋放所有資源 $R_i$ （F( $R_j$ ) $≤\leq$ F( $R_i$ )）。如果需要同一類型的多個(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)程序列< $P_1$ , $P_2$ , … , $P_n$ >在當(dāng)前分配狀態(tài)下為安全序列是指：對于每個(gè) $P_i$ ， $P_i$ 仍然可以申請資源數(shù)小于當(dāng)前可用資源加上所有進(jìn)程 $P_j$ （j < i）所占有的資源。在這種情況下，進(jìn)程 $P_i$ 需要的資源即使不能立即可用，那么 $P_i$ 可以等待直到所有 $P_j$ 釋放資源。當(dāng)他們完成后， $P_i$ 可得到需要的所有資源完成給定任務(wù)，返回分配的資源，最后終止。當(dāng) $P_i$ 終止時(shí)， $P_{i+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)。

資源分配圖算法

除了申請邊和分配邊，引入需求邊，需求邊 $P_i$ $→\rightarrow$ $R_j$ 表示進(jìn)程 $P_i$ 可能在將來某個(gè)時(shí)候申請資源 $R_j$ 。當(dāng)進(jìn)程 $P_i$ 申請資源時(shí) $R_j$ 時(shí)，需求邊 $P_i$ $→\rightarrow$ $R_j$ 變成了申請邊，類似當(dāng)進(jìn)程 $P_i$ 釋放 $R_j$ 時(shí)，分配邊 $R_j$ $→\rightarrow$ $P_i$ 變成了需求邊 $P_i$ $→\rightarrow$ $R_j$ 。
現(xiàn)在假設(shè)進(jìn)程 $P_i$ 申請資源 $R_j$ ，只有在將申請邊 $P_i$ $→\rightarrow$ $R_j$ 變成分配邊 $R_j$ $→\rightarrow$ $P_i$ 并且不會(huì)導(dǎo)致資源分配圖形成環(huán)時(shí)，才能允許申請。
如果沒有環(huán)存在，那么資源的分配會(huì)使系統(tǒng)處于安全狀態(tài)。如果有環(huán)存在，那么分配會(huì)導(dǎo)致系統(tǒng)處于非安全狀態(tài)，這種情況下，進(jìn)程 $P_i$ 應(yīng)該等待資源申請。

銀行家算法

設(shè)n為系統(tǒng)進(jìn)程的數(shù)量，m為資源類型的種類。定義數(shù)據(jù)結(jié)構(gòu)：
Available：長度為m的向量，表示每種資源的可用實(shí)例數(shù)量，如果Available[j]=k,那么資源類型 $R_j$ 有k個(gè)可用實(shí)例。

Max：n $×\times$ m矩陣，定義每個(gè)進(jìn)程的最大需求。如果Max[i][j]=k，那么進(jìn)程 $P_i$ 最多可申請?jiān)搭愋?span id="ze8trgl8bvbq" class="katex--inline"> $R_j$ 的k個(gè)實(shí)例

Allocation：n $×\times$ m矩陣，定義每個(gè)進(jìn)程現(xiàn)在分配的每種資源類型的實(shí)例數(shù)量，如果Allocation[i][j]=k，那么進(jìn)程 $P_i$ 現(xiàn)在已分配了資源類型 $R_j$ 的k個(gè)實(shí)例。

Need：n $×\times$ m矩陣，表示每個(gè)進(jìn)程還需要的剩余資源。如果Need[i][j]=k，那么進(jìn)程 $P_i$ 還可能申請k個(gè)資源類型 $R_j$ 的實(shí)例。
注意：Need[i][j]=Max[i][j] - Allocation[i][j]。

安全算法

通過安全算法以求出系統(tǒng)是否處于安全狀態(tài)，描述如下：

令Work和Finish分別為長度m和n的向量，對于i=0,1,…,n-1，初始化Work=Available和Finish[i]=false。

查找這樣的i使其滿足：
a. Finish[i] == false
b.

Need_i

≤\leq

Work
如果沒有這樣的i存在，那么轉(zhuǎn)到第4步

Work=Work+

Allocation_i

Finish[i]=true
返回第2步

如果對所有i，Finish[i]=true，那么系統(tǒng)處于安全狀態(tài)。

這個(gè)算法可能需要m $×\times$ $n^2$ 數(shù)量級(jí)的操作，以確定系統(tǒng)狀態(tài)是否安全。

資源請求算法

現(xiàn)在描述是否安全允許請求的算法：
設(shè) $Request_i$ 為進(jìn)程 $P_i$ 的請求向量。如果 $Request_i$ [j]==k，那么進(jìn)程 $P_i$ 需要的資源類型 $R_j$ 的實(shí)例數(shù)量為k，當(dāng)進(jìn)程 $P_i$ 做出這一資源請求時(shí)，采取如下動(dòng)作：

如果

Request_i

≤\leq

Need_i

，轉(zhuǎn)到第二步。否則生成出錯(cuò)條件，進(jìn)程

P_i

已超過了其最大需求。

如果

Request_i

≤\leq

Available，轉(zhuǎn)到第三步，否則

P_i

應(yīng)等待，這是因?yàn)闆]有資源可用。

嘉定系統(tǒng)可以分配給

P_i

請求的資源，并案如下方式修改狀態(tài)：
Available = Available -

Request_i

Allocation_i

Allocation_i

Request_i

Need_i

Need_i

Request_i

如果新的資源分配狀態(tài)是安全的，那么交易完成且進(jìn)程

P_i

可分配到需要的資源。然而，如果新狀態(tài)不安全，那么進(jìn)程

P_i

應(yīng)等待

Request_i

并恢復(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，那么 $P_i$ 現(xiàn)在正在請求資源類型 $R_j$ 的k個(gè)實(shí)例。

可以看出該算法和銀行家算法類似，可以進(jìn)行比較理解，該算法的描述如下：

令Work和Finish分別為長度m和n的向量，初始化Work=Available。對于i=0,1,…,n-1，如果

Allocation_i

不為0，則Finish[i]=false，否則Finish[i]=true。

找到這樣的i，同時(shí)滿足：
a. Finish[i]=false
b.

Request_i

≤\leq

Work
如果沒有這樣的i，則轉(zhuǎn)到第4步

Work = Work +

Allocation_i

Finish[i] = true
轉(zhuǎn)到第2步

如果對某個(gè)i(0

≤\leq

≤\leq

n)，Finish[i] == false，則系統(tǒng)死鎖，并且如果Finish[i] == false，則進(jìn)程

P_i

死鎖。

死鎖恢復(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)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： Qt高级——QTestLib单元测试框架
下一篇：分布式之redis