[Linux]死鎖

死鎖是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵持狀態時，若無外力作用，它們都將無法再向前推進。之前信號量的時候我們知道，如果多個進程等待，主要體現在占有鎖的問題上。死鎖也可以被定義為：一組競爭系統資源或互相通信的進程間相互的永久阻塞。當一組進程中的所有進程都在等待一個事件，而只有在進程集合中的其他阻塞的進程才可以觸發該事件，這時就稱一組進程死鎖。因為沒有事件觸發，因此死鎖是永久性的。

產生死鎖的原因有：

（1）競爭資源。當系統中供多個進程共享的資源如打印機、公用隊列等，其數目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。

（2）進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。

詳細分析一下產生死鎖的原因哦。

（1）可剝奪和非剝奪性資源

可剝奪性資源指某進程在獲得這類資源后，該資源可以再被其他進程或系統剝奪。如優先級高的可以剝奪優先級低的進程的處理機。非剝奪性資源是當這類資源分配給某進程后，再不能強行收回，只能在進程用完后自行釋放。

（2）競爭非剝奪性資源

由于它們的數量不能滿足諸進程運行的需要，會使進程在運行過程中，因剝奪這些資源而陷入僵局。

比如，系統中有一臺打印機R1和一臺磁帶機R2，供進程P1,P2共享。如果P1占用了打印機，P2占用了磁帶機。此時如果P1想使用磁帶機，而P2想使用打印機，這就使P1和P2都在等待對方的資源被釋放，而陷入僵局。從而也使P1和P2得不到自己的資源而不能釋放現有的資源，最后進入死鎖狀態。

（3）競爭臨時性資源

上述的打印機資源屬于順序性重復使用的資源，屬于永久性資源。還有一種是臨時性資源，是一個進程產生，由另一進程使用短暫時間后無用的資源。也可能產生死鎖。

（4）推進順序不當。P1—>Request(R2),p2—>Request(R1)時產生死鎖。

產生死鎖的必要條件

如果發生死鎖，則有四個產生死鎖的必要條件：

（1）互斥條件。一次只有一個進程使用資源，其他進程不能訪問已分配的資源。

（2）請求和保持條件（也稱占有且等待）。指進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其他進程占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放。

（3）不剝奪條件（非搶占）。指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完自己釋放。

（4）環路等待（循環等待）。指存在一個封閉的進程鏈，使得每個資源至少占有此鏈中下一個進程所需要的一個資源。在發生死鎖時，必然存在一個進程，資源的環形鏈，即P0，P1，P2….Pn，則P0在等待P1占有的資源，P1占有P2的，….Pn占有P0的。

說完死鎖之后，我們應該想想如何處理這種死鎖呢。處理死鎖的基本方法有：預防死鎖，避免死鎖，檢測死鎖，解除死鎖。

預防死鎖是使四個必要條件中的第2,3,4個中的一個不成立來避免不發生死鎖。為預防死鎖，可以使請求和保持條件中，可以要求進程一次性地請求所有需要的資源，并且阻塞這個進程直到所有請求都同時滿足。對于非搶占式的預防死鎖的方法，如果占有某些資源的一個進程進行進一步資源請求被拒絕，則該進程必須釋放它最初占用的資源，如果有必要，可以再次請求此類資源。還有一種情況是，如果一個進程請求當前被另一個進程占有的一個資源，則操作系統可以搶占另一個進程，要求它釋放資源。（這類情況適合具有不同優先級的進程）

死鎖避免

解決死鎖問題的另一種方法是死鎖避免。與死鎖預防的差距也不大。這里有倆種死鎖避免的方法，

1.如果一個進程的請求會導致死鎖，則不啟動此進程
2.如果一個進程增加資源的請求導致死鎖，則不允許此分配

這里解決死鎖問題的方法有：銀行家算法

銀行家算法通過已分配的資源和可用資源數等來獲取安全序列，如果存在安全序列，就可以分配請求資源，不存在則說明不可以請求資源，這樣就可以有效的避免死鎖。

（1）請求資源，發出請求向量
（2）假定可為P1分配資源，修改Available,Allocation和Need向量
（3）利用安全性算法檢查此時系統是否安全

銀行家算法需求分析：

允許進程動態地申請資源，系統在每次實施資源分配之前，先計算資源分配的安全性，若此次資源分配安全（即資源分配后，系統能按某種順序來為每個進程分配其所需的資源，直至最大需求，使每個進程都可以順利地完成），便將資源分配給進程，否則不分配資源，讓進程等待。
功能實現：
理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。所以，在系統設計、進程調度等方面注意如何能夠不讓這四個必要條件成立，如何確定資源的合理分配算法，避免進程永久占據系統資源。此外，也要防止進程在處于等待狀態的情況下占用資源,在系統運行過程中，對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，并根據檢查結果決定是否分配資源，若分配后系統可能發生死鎖，則不予分配，否則予以分配。因此，對資源的分配要給予合理的規劃。
1) 可利用資源向量Available。這是一個含有m個元素的數組，其中的而每一個元素代表一類可利用資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態的改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。
2) 最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K；則表示進程i需要Rj類資源的最大數目為K。
3) 分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K，則表示進程i當前已分得Rj類資源的數目為K。
4) 需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K,則表示進程i還需要Rj類資源K個，方能完成任務。
上述三個矩陣間存在下述關系：Need[i,j]=Max[i,j]-Allocation[i,j]

#define _CRT_SECURE_NO_WARNINGS 1
extern "C"
#include<stdio.h>
#include<stdlib.h>
#define W 10
int Available[W];           //可使用資源
int Max[W][W];             //最大需求資源數
int Allocation[W][W];      //已分配資源
int Need[W][W];            //需求資源
int Work[W];              //工作向量
int Finish[W];           //是否有足夠的資源分配，狀態標志
int Request[W][W];        //進程申請資源向量
int Temp[W];             //暫存可用資源數
int AllReSourceNum[W];        //各類資源總數
int i, j;
int ResourceNum;              //系統資源總數
int ProcessNum;               //總的進程數
int a;                       //當前申請的進程號
int l, e;                     
int b = 0, c = 0, f = 0, g;  //c: 統計對于每一個進程，成功分配的資源類別數
int  SecurityCheck()     //安全性檢測
{printf("\n\n");printf("\t\t\t 安全性檢測 \n\n");printf("          工作向量       尚需求量       已分配      工作向量+已分配\n進程 ");for (c = 1; c <= 4; c++){for (j = 1; j <=ResourceNum; j++){printf("  %d類", j);}}for (i = 1; i <=ProcessNum; i++){Temp[i] = Available[i];    //Temp[i]只是一個暫時寄存的中間變量，為防止在下面安全性檢查時修改到Available[i]而代替的一維數組Finish[i] = false;}for (g = 1; g <=ProcessNum; g++){for (i = 1; i <=ProcessNum; i++){b = 0;                 //計數器初始化Finish[i] == false;for (j = 1; j <=ResourceNum; j++){if (Need[i][j] <= Temp[j]){b = b + 1;}if (Finish[i] == false && b ==ResourceNum){Finish[i] = true;printf("\nP[%d] ", i);        //依次輸出進程安全序列  for (l = 1; l <=ResourceNum; l++){printf("  %2d ", Temp[l]);}for (j = 1; j <=ResourceNum; j++){printf("  %2d ",Need[i][j]);}for (j = 1; j <=ResourceNum; j++){//Allocation[i][j]=Temp[j]-Need[i][j];printf("  %2d ", Allocation[i][j]);}for (j = 1; j <=ResourceNum; j++){printf("  %2d ", Temp[j] + Allocation[i][j]);}for (l = 1; l <=ResourceNum; l++){Temp[l] = Temp[l] + Allocation[i][l];        }}}}}printf("\n\n");for (i = 1; i <=ProcessNum; i++){if (Finish[i] == true) f = f + 1;  //統計Finish[i]＝＝true的個數}if (f ==ProcessNum){printf("安全序列");printf("\n\n系統剩余資源量：");for (i = 1; i <=ResourceNum; i++){printf("   %d ", Available[i]);}f = 0;       //將計數器f重新初始化，為下一次提出新的進程申請做準備return 1;}else{printf("不安全序列");return 0;}
}
void Initialize()    //初始化
{printf("請輸入系統的資源種類數：");scanf("%d", &ResourceNum);for (i = 1; i <=ResourceNum; i++){printf("第%d類資源總數：", i);scanf("%d", &AllReSourceNum[i]);}printf("請輸入進程總數：");scanf("%d", &ProcessNum);for (i = 1; i <=ProcessNum; i++){for (j = 1; j <=ResourceNum; j++){printf("進程P[%d]對第%d類資源的最大需求量：", i, j);scanf("%d", &Max[i][j]);}}for (i = 1; i <=ProcessNum; i++){for (j = 1; j <=ResourceNum; j++){printf("進程P[%d]對第%d類資源已分配數：", i, j);scanf("%d", &Allocation[i][j]);Need[i][j] = Max[i][j] - Allocation[i][j];}}for (i = 1; i <=ResourceNum; i++){for (j = 1; j <=ProcessNum; j++){AllReSourceNum[i] -= Allocation[j][i];}}for (i = 1; i <=ResourceNum; i++)Available[i] = AllReSourceNum[i];SecurityCheck();
}
void RequestResource()  //進程申請資源
{printf("請輸入申請資源的進程：");scanf("%d", &a);for (i = 1; i <=ResourceNum; i++){printf("請輸入進程P[%d]對%d類資源的申請量：", a, i);scanf("%d", &Request[a][i]);if (Request[a][i] >Need[a][i]){printf("\n出錯！進程申請的資源數多于它自己申報的最大需求量\n");return;}if (Request[a][i] > Available[i]){printf("\nP[%d]請求的資源數大于可用資源數，必須等待\n", a);return;}}for (i = 1; i <=ResourceNum; i++){//以下是試探性分配Available[i] = Available[i] - Request[a][i];Allocation[a][i] = Allocation[a][i] + Request[a][i];Need[a][i] =Need[a][i] - Request[a][i];}int ret=SecurityCheck();if (ret == 1){int key = 0;for (j = 1; j <=ResourceNum; j++){if (Need[a][j] == 0){key++;}}if (key ==ResourceNum){for (j = 1; j <=ResourceNum; j++){Available[j] += Allocation[a][j];Allocation[a][j] = 0;}}}
}void ResourceState()
{printf("\n\n");printf("          已分配       最大需求量       尚需要量 \n進程");for (i = 1; i <= 3; i++){for (j = 1; j <=ResourceNum; j++){printf("  %d類", j);}}for (i = 1; i <=ProcessNum; i++){printf("\nP[%d]", i);for (j = 1; j <=ResourceNum; j++){printf("  %2d ", Allocation[i][j]);}for (j = 1; j <=ResourceNum; j++){printf("  %2d ", Max[i][j]);}for (j = 1; j <=ResourceNum; j++){printf("  %2d ",Need[i][j]);}}printf("\n\n系統剩余資源量：   ");for (i = 1; i <=ResourceNum; i++){printf("   %d ", Available[i]);}printf("\n");
}void menu()
{printf("\n\t-------------銀行家算法---------------\n");printf("             1、初始化                \n");printf("             2、進程請求資源          \n");printf("             3、資源分配狀態          \n");printf("             4、退出                  \n");printf("\t--------------------------------------\n");printf("\n請輸入你的選擇: ");
}
//BankerAlth.cpp
#include"BankerAlth.h"
int main()
{int select = 0;printf("\n\n");while (1){menu();scanf("%d", &select);printf("\n\n");switch (select){case 1:Initialize();break;case 2:RequestResource();break;case 3:ResourceState();break;case 4:printf("\nSee you Next time !\n\n");system("pause");return 0;}}system("pause");return 0;
}