如何避免死锁（死锁检测算法） —— 银行家算法

Myth丶恋晨 2022-12-16 09:19 313阅读 0赞

# 一，死锁概念 #

**死锁指的是两个或两个以上的进程在对临界资源竞争或者通信过程中， 因为某些处理不当，而造成各个进程彼此等待，无法继续向下推进，此使系统处于死锁状态， 这些互相等待的进程成为死锁进程。**

# 二，死锁产生必要条件 #

## 1. 互斥条件 ##

指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进 程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

## 2. 请求和保持条件 ##

指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程 阻塞，但又对自己已获得的其它资源保持不放。

## 3. 不剥夺条件 ##

指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

## 4. 环路等待条件 ##

指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合\{P0，P1，P2，···，Pn\}中的P0正 在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

# 三，死锁避免 #

**破坏死锁产生的必要条件就可以避免、预防和解除死锁。**

在系统设计、进程调度等方面注意如何能够不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。

此外，也要防止进程在处于等待状态的情况下占用资源

在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。

因此，对资源的分配要给予合理的规划。

换句话说，避免死锁的实质在于：**系统在进行资源分配时，如何使系统不进入不安全状态。**

# 四，银行家算法 #

操作系统按照银行家制定的规则为进程分配资源。

当**进程首次申请资源**时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。

当**进程在执行中继续申请资源**时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

例：有5个进程\{P1,P2,P3,P4,P5\} 。4类资源\{R1,R2,R3,R4\} 各自数量为6、3、4、2  
T0时刻各进程分配资源情况如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]

T0时刻为安全状态，存在安全序列\{P4，P1，P2，P3，P5\} 如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center 1]  
**银行家算法需要在进程运行前就知道其所需资源的最大值，且进程数也通常不是固定的，因此使用有限**，但从思想上可以提供了解，可以转换地应用在其他地方

案例分析  
M=3种类型的资源（A,B,C,） 进程个数n=5 Available=(2,3,3);  
已分配资源数 资源需求量  
A B C A B C  
P1 2 1 2 3 4 7  
P2 4 0 2 1 3 4  
P3 3 0 5 0 0 3  
P4 2 0 4 2 2 1  
P5 3 1 4 1 1 0  
请求序列如下：  
a：进程P2请求资源（0，3，4）  
b：进程P4请求资源（1，0，1）  
c：进程P1请求资源（2，0，1）  
d：进程P3请求资源（0，0，2）

#include<iostream>
    #include<string>
    using namespace std;
    #define n 5
    #define m 3
    int available[m] = {
         2,3,3 }, alloc[n][m], need[n][m], request[n][m];
    void init()
    {
        
    	alloc[0][0] = 2;  alloc[0][1] = 1;  alloc[0][2] = 2;
    	alloc[1][0] = 4;  alloc[1][1] = 0;  alloc[1][2] = 2;
    	alloc[2][0] = 3;  alloc[2][1] = 0;  alloc[2][2] = 5;
    	alloc[3][0] = 2;  alloc[3][1] = 0;  alloc[3][2] = 4;
    	alloc[4][0] = 3;  alloc[4][1] = 1;  alloc[4][2] = 4;
     
    	need[0][0] = 3;  need[0][1] = 4;  need[0][2] = 7;
    	need[1][0] = 1;  need[1][1] = 3;  need[1][2] = 4;
    	need[2][0] = 0;  need[2][1] = 0;  need[2][2] = 3;
    	need[3][0] = 2;  need[3][1] = 2;  need[3][2] = 1;
    	need[4][0] = 1;  need[4][1] = 1;  need[4][2] = 0;
     
    	request[0][0] = 2;  request[0][1] = 0;  request[0][2] = 1;
    	request[1][0] = 0;  request[1][1] = 3;  request[1][2] = 4;
    	request[2][0] = 0;  request[2][1] = 0;  request[2][2] = 2;
    	request[4][0] = 1;  request[3][1] = 0;  request[3][2] = 1;
    	
    }
    void display()
    {
        
    	cout << "资源 可分配" << endl;
    	for (int i = 0; i < m; i++)
    	{
        
    		cout << (char)('A' + i) << "      " << available[i] << endl;
    	}
    	cout << endl;
    	cout << "进程 资源 已分配 需求"<<endl;
    	for (int i = 0; i < n; i++)
    	{
        
     
    		for (int j = 0; j < m; j++)
    		{
        
    			cout << i+1<< "     " <<(char)('A' + j)<< "     " << alloc[i][j] << "     " << need[i][j] << endl;
    		}
    	}
    	cout << endl;
    }
    bool judge()
    {
        
    	int i, j, tag = n;
    	bool non;
    	int work[m], finish[n];
    	for (i = 0; i<m; i++) work[i] = available[i]; 
    	for (i = 0; i<n; i++) finish[i] = 0;            
    	while (tag--)
    	{
        
    		for (i = 0; i<n; i++)    
    		{
        
    			if (finish[i] == 0) 
    			{
        
    				non = true;
    				for (j = 0; j < m; j++)
    				{
        
    					if (need[i][j] > work[j]) non = false; 
    				}
    				if(non)
    				{
        
    					for (j = 0; j < m; j++)  
    					{
        
    						work[j] = work[j] + alloc[i][j];
    						finish[i] = 1;
    					}
    				}
    			}
    		}
    	}
    	non = true;
    	for (i = 0; i < n; i++)
    	{
        
    		if (finish[i] != 1) non = false;
    	}
    	if (non) return 1;
    	else return 0;
    }
    void deal(int k)
    {
        
    	for (int j = 0; j < m; j++)
    	{
        
    		if (request[k][j] > need[k][j])
    		{
        
    		//	cout << request[k][0] << " " << request[k][1] << " " << request[k][2];
    			cout << " 非法！！！" << endl;
    			return;
    		}
    	}
    	for (int j = 0; j < m; j++)
    	{
        
    		if (request[k][j] > available[j])
    		{
        
    		//	cout << request[k][0] << " " << request[k][1] << " " << request[k][2];
    			cout << " 阻塞！！！" << endl;
    			return;
    		}
    	}
    	for (int j = 0; j < m; j++)  //试探性分配
    	{
        
    		available[k] -= request[k][j];
    		alloc[k][j] += request[k][j];
    		need[k][j] -= request[k][j];
    	}
    	if (judge())
    	{
        
         //   cout << request[k][0] << " " << request[k][1] << " " << request[k][2];
    		cout << " 资源分配成功！！！" << endl << endl;
    		display();
    	}
    	else
    	{
        
    	//	cout << request[k][0] << " " << request[k][1] << " " << request[k][2];
    		cout << " 资源分配后系统处于不安全状态！！！" << endl;
    		for (int j = 0; j < m; j++)  //试探性分配还原
    		{
        
    			available[k] += request[k][j];
    			alloc[k][j] -= request[k][j];
    			need[k][j] += request[k][j];
    		}
    	}
    	cout << endl;
    }
    int main()
    {
        
    	init();
    	display();
    	cout << "a: 进程p2请求资源（0，3，4）  " ;
    	deal(1);
    	cout << "b: 进程p4请求资源（1，0，1）  " ;
    	deal(3);  
    	cout << "c: 进程p1请求资源（2，0，1）  " ;
    	deal(0);
    	cout << "d: 进程p3请求资源（0，0，2）  " ;
    	deal(2);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f60110b59ea44ab580afed087cb3d68a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/4d8ccad321524663a8b03cc97dcb707b.png