死鎖---銀行家算法

----

- 死鎖
- 死鎖的四個必要條件
- 避免死鎖
- 避免死鎖算法
- - 銀行家算法

死鎖

死鎖是指子啊一組程序中的各個程序均占有不會釋放的資源，但因互相申請被其它程序所占用不會釋放的資源而處于的一種永久等待狀态。

死鎖的四個必要條件

互斥條件：一個資源每次隻能被一個執行流使用；
請求與保持條件：一個執行流因請求資源而阻塞時，對已獲得的資源保持不放；
不可剝奪條件：一個執行流已獲得的資源，在未使用完之前，不能強行剝奪；
循壞等待條件：若幹執行流之間形成一種頭尾相接的循環等待資源的關系；

避免死鎖

破壞死鎖的四個必要條件；
加鎖順序；
避免鎖未釋放的場景；
資源一次性配置設定

避免死鎖算法

銀行家算法

銀行家算法是最著名的死鎖避免算法。它提出的思想是：把作業系統看做是銀行家，作業系統管理的資源相當于銀行家管理的資金，程序向作業系統請求配置設定資源相當于使用者向銀行家貸款。作業系統按照銀行家制定的規則為程序配置設定資源，當程序首次申請資源時，要測試該程序對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按目前的申請量配置設定資源，否則就推遲配置設定。當程序在執行中繼續申請資源時，先測試該程序已占用的資源數與本次申請的資源數之和是否超過了該程序對資源的最大需求量。若超過則拒絕配置設定資源，若沒有超過則再測試系統現存的資源能否滿足該程序尚需的最大資源量，若能滿足則按目前的申請量配置設定資源，否則也要推遲配置設定。

執行步驟

設Request i是程序Pi的請求向量，如果Request i[j]=K，表示程序P i需要K個R j類型的資源。當P i發出資源請求後，系統按下述步驟進行檢查：

　　(1) 如果Request i[j]≤Need[i,j]，便轉向步驟(2)；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。

　　(2) 如果Request i[j]≤Available[j]，便轉向步驟(3)；否則，表示尚無足夠資源，Pi須等待。

　　(3) 系統試探着把資源配置設定給程序P i，并修改下面資料結構中的數值：

Available[j]:= Available[j]-Request i[j]；

Allocation[i,j]:= Allocation[i,j]+Request i[j]；

Need[i,j]:= Need[i,j]-Request i[j]；

　　(4) 系統執行安全性算法，檢查此次資源配置設定後系統是否處于安全狀态。若安全，才正式将資源配置設定給程序Pi，以完成本次配置設定；否則，将本次的試探配置設定廢棄，恢複原來的資源配置設定狀态，讓程序Pi等待。
安全性算法設計

系統所執行的安全性算法可描述如下：

　　(1) 設定兩個向量：

　　 ① 工作向量Work，它表示系統可提供給程序繼續運作所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work:=Available。

　　 ② Finish，它表示系統是否有足夠的資源配置設定給程序，使之運作完成。開始時先做Finish[i]:=false；當有足夠資源配置設定給程序時，再令Finish[i]:=true。

　　(2) 從程序集合中找到一個能滿足下述條件的程序：

　　 ① Finish[i]=false；

　　 ② Need[i,j]≤Work[j]；若找到，執行步驟(3)，否則，執行步驟(4)。

　　(3) 當程序Pi獲得資源後，可順利執行，直至完成，并釋放出配置設定給它的資源，故應執行：

Work[j]:= Work[j]+Allocation[i,j]；

Finish[i]:=true；

go to step （2）；

　　(4) 如果所有程序的Finish[i]=true都滿足，則表示系統處于安全狀态；否則，系統處于不安全狀态。
資料結構

(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目前已分得R j類資源的數目為K。

(4) 需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個程序尚需的各類資源數。如果Need[i,j]=K，則表示程序i還需要R j類資源K個，方能完成其任務。

上述三個矩陣間存在下述關系：Need[i, j]=Max[i, j]-Allocation[i, j]

死鎖---銀行家算法

實作代碼：

# define _CRT_SECURE_NO_WARNINGS 1
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>

# define TRUE 1         //狀态位
# define FAULSE 0       //狀态位
# define PCB_NUM 5      //程序數
# define RESOURCE_NUM 5 //資源種類

size_t Menu();          //菜單
void InitPCB();         //初始化程式
size_t SafeCheck();      //安全性算法
void RequestResource();  //發出資源請求

size_t g_max[PCB_NUM][RESOURCE_NUM] = { 0 };        //最大需求矩陣
size_t g_allocation[PCB_NUM][RESOURCE_NUM] = { 0 }; //已配置設定矩陣
size_t g_need[PCB_NUM][RESOURCE_NUM] = { 0 };       //需求矩陣
size_t g_available[RESOURCE_NUM] = { 0 };    //可利用資源向量
size_t g_work[RESOURCE_NUM] = { 0 };         //可利用資源數目
size_t g_finish[RESOURCE_NUM];               //狀态
size_t g_safe_order[PCB_NUM];                //安全序列
size_t g_request[RESOURCE_NUM] = { 0 };      //請求向量
size_t g_pcb_num = 0, g_resource_type = 0;   //實際的程序數和資源種類

//菜單函數
size_t Menu()
{
	size_t choose = 0;
	printf("\t*-*-*-*-*-*- BankerAlgorthm -*-*-*-*-*-*-*-*\n");
	printf("\t*-*-*-                                -*-*-*\n");
	printf("\t*-*-*-       1. 初始化程序            -*-*-*\n");
	printf("\t*-*-*-       2. 安全性算法            -*-*-*\n");
	printf("\t*-*-*-       3. 銀行家算法            -*-*-*\n");
	printf("\t*-*-*-       0. 退      出            -*-*-*\n");
	printf("\t*-*-*-                                -*-*-*\n");
	printf("\t*-*-*-*--*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\n\n");
	printf("請選擇->: ");
	scanf("%d", &choose);

	return choose;
}

//檢查初始化是否正确
static int _CheckInit()
{
	size_t i = 0, j = 0;
	for (i = 0; i < g_pcb_num; i++)
	{
		for (j = 0; j < g_resource_type; j++)
		{
			if (g_allocation[i][j] + g_need[i][j] > g_max[i][j])
			{
				return -1;
			}
		}
	}
	return 1;
}

//初始化程式
void InitPCB()
{
	size_t i = 0, j = 0;

	printf("\n請輸入程序數量和資源種類的個數：\n");
	fflush(stdin);//清空緩沖區
	scanf("%d%d", &g_pcb_num, &g_resource_type);
	printf("pcb_num = %d  resource_type = %d \n", g_pcb_num, g_resource_type);

	printf("\n輸入各個程序的最大需求矩陣Max：\n");
	fflush(stdin);
	for (i = 0; i < g_pcb_num; i++)
	{
		printf("P[%d]:", i);
		for (j = 0; j < g_resource_type; j++)
		{
			scanf("%d", &g_max[i][j]);
		}
	}
	printf("輸入各個程序的已配置設定矩陣All：\n");
	fflush(stdin);
	for (i = 0; i < g_pcb_num; i++)
	{
		printf("P[%d]:", i);
		for (j = 0; j < g_resource_type; j++)
		{
			scanf("%d", &g_allocation[i][j]);
		}
	}
	printf("輸入各個程序的需求矩陣Need：\n");
	fflush(stdin);
	for (i = 0; i < g_pcb_num; i++)
	{
		printf("P[%d]:", i);
		for (j = 0; j < g_resource_type; j++)
		{
			scanf("%d", &g_need[i][j]);
		}
	}
	//求Available
	printf("輸入剩餘各類資源Avali：\n");
	fflush(stdin);
	for (i = 0; i < g_resource_type; i++)
	{
		printf("R[%d]:", i);
		scanf("%d", &g_available[i]);
	}

	int ret = _CheckInit();
	if (-1 == ret)
	{
		printf("初始化失敗，配置設定矩陣與需求矩陣之和大于最大需求矩陣！\n\n");
	}
	else
		printf("初始化成功！\n\n");
}

//列印安全序列
static void _Print()
{
	size_t i = 0;
	printf("\n在該時刻存在一個安全序列： ");
	for (i = 0; i < g_pcb_num; i++)
	{
		printf("P[%d]", g_safe_order[i]);
		if (i != g_pcb_num - 1)
			printf("->");
	}
	printf("\n\n");
}

//安全性算法
size_t SafeCheck()
{
	size_t i = 0, j = 0, k = 0;
	size_t count, flag;
	size_t suffix = 0;           //安全序列的下标

	//初始化向量Work和Finish
	for (i = 0; i < g_resource_type; i++)
		g_work[i] = g_available[i];
	for (j = 0; j < g_pcb_num; j++)
		g_finish[j] = FAULSE;
	//查找安全序列
	while (1)
	{
		for (i = 0; i < g_pcb_num; i++)
		{
			count = 0;
			flag = 0;

			for (j = 0; j < g_resource_type; j++)
			{
				if (g_work[j] >= g_need[i][j])
					count++;
				else
					break;
			}

			//可以進行配置設定并完成該程序
			if ((count == g_resource_type) && (g_finish[i] != TRUE))
			{
				flag = 1;
				for (k = 0; k < g_resource_type; k++)
				{
					g_work[k] = g_work[k] + g_allocation[i][k];
				}
				g_finish[i] = TRUE;
				g_safe_order[suffix++] = i ;

				if (suffix == g_pcb_num)
				{
					_Print();
					return 1;
				}
			}
		}
		//周遊完之後沒有符合的程序則跳出循環
		if (0 == flag)
		{
			printf("\n不存在安全序列!\n\n");
			return 0;
		}
		else
			i = 0;
	}
}

//列印配置設定後的程序資源表
static void _PrintPcbList()
{
	size_t i = 0, j = 0;
	printf("程序\tMax\tAll\tNeed\tAvail\n");
	for (i = 0; i < g_pcb_num; i++)
	{
		printf("P[%d]：", i);
		for (j = 0; j < g_resource_type; j++)
		{
			printf("%d ", g_max[i][j]);
		}
		printf("\t");
		for (j = 0; j < g_resource_type; j++)
		{
			printf("%d ", g_allocation[i][j]);
		}
		printf("\t");
		for (j = 0; j < g_resource_type; j++)
		{
			printf("%d ", g_need[i][j]);
		}
		printf("\t");
		if (0 == i)
		{
			for (j = 0; j < g_resource_type; j++)
			{
				printf("%d ", g_available[j]);
			}
		}
		printf("\n");
	}
	printf("\n\n");
}

//試配置設定
static void _TryAllocation(size_t PCB_ORDER)
{
	size_t i = 0, j = 0;
	size_t ret;
	for (i = 0; i < g_resource_type; i++)
	{
		g_available[i] -= g_request[i];
		g_allocation[PCB_ORDER][i] += g_request[i];
		g_need[PCB_ORDER][i] -= g_request[i];
	}
	ret = SafeCheck();
	//配置設定失敗
	if (0 == ret)
	{
		printf("該配置設定不安全\n\n", PCB_ORDER);

		for (i = 0; i < g_resource_type; i++)
		{
			g_need[PCB_ORDER][i] += g_request[i];
			g_allocation[PCB_ORDER][i] -= g_request[i];
			g_available[i] += g_request[i];
		}
	}
	//列印配置設定後的程序資源表 
	_PrintPcbList();
}

//發出資源請求
void RequestResource()
{
	size_t i = 0;
	size_t PCB_ORDER = 0;

	printf("\n請輸入發出資源請求的程序名：\n");
	scanf("%d", &PCB_ORDER);
	fflush(stdin);
	for (i = 0; i < g_resource_type; i++)
	{
		printf("Request_%c:", 65 + i);
		scanf("%d", &g_request[i]);
	}

	for (i = 0; i < g_resource_type; i++)
	{
		//當Request>Need的情況
		if (g_request[i]>g_need[PCB_ORDER][i])
		{
			printf("\n需要的資源已經超出所需的最大值！\n\n");
			return;
		}
		//當Request>Available的情況
		if (g_request[i]>g_available[i])
		{
			printf("\n尚無足夠資源\n\n");
			return;
		}
	}

	//試配置設定
	_TryAllocation(PCB_ORDER);

}

int main()
{
	size_t ret = 0;
	while (1)
	{
		switch (ret = Menu())
		{ 
		case 1:
			InitPCB();
			break;
		case 2:
			SafeCheck();
			break;
		case 3:
			RequestResource();
			break;
		case 0:
			exit(EXIT_SUCCESS);
			break;
		default:
			break;
		}
	}
	system("pause");
	return 0;
}

死鎖---銀行家算法

----

死鎖

死鎖的四個必要條件

避免死鎖

避免死鎖算法

銀行家算法

繼續閱讀

windbg調試驅動自旋鎖死鎖

Java Thread Dump 死鎖分析

計算機作業系統還能這樣玩？這一篇計算機作業系統的總結為你保駕護航（零風險、高品質、萬字長文、建議收藏）

Linux下開機、重新開機和使用者登入登出

SQL Server死鎖問題：事務(程序 ID x)與另一個程序被死鎖在鎖 | 通信緩沖區資源上并且已被選作死鎖犧牲品。請重新運作該事務。

作業系統學習筆記——第三章死鎖和第四章存儲管理

死鎖的3種死法

Linux指令之 free （buffer與cache差別）

三 python并發程式設計之多線程-理論

Java: 寫一個死鎖的程式

分門别類總結Java中的各種鎖，讓你徹底記住

了解golang中關鍵字-chan&select

Linux安裝Nginx詳解前言安裝步驟

LInux 配置yum源

程序管理邏輯圖

LockSupper是什麼？他和Lock、Synchroized有什麼關系？解決了什麼？