操作系统--银行家算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统--银行家算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.产生死锁的原因及必要条件

1.1产生死锁的原因

1.2产生死锁的必要条件

2.处理死锁的方法

3.银行家算法

4.安全性算法

5.算法实现

1.产生死锁的原因及必要条件

如果一个进程集合里面的每个进程都在等待这个集合中的其他一个进程（包括自身）才能继续往下执行，若无外力他们将无法推进，这种情况就是死锁，处于死锁状态的进程称为死锁进程。

1.1产生死锁的原因

1.因竞争资源发生死锁现象：系统中供多个进程共享的资源的数目不足以满足全部进程的需要时，就会引起对资源的竞争而发生死锁现象；
       （1）可剥夺资源和不可剥夺资源：可剥夺资源是指某进程在获得该类资源时，该资源同样可以被其他进程或系统剥夺，不可剥夺资源是指当系统把该类资源分配给某个进程时，不能强制收回，只能在该进程使用完成后自动释放
       （2）竞争不可剥夺资源：系统中不可剥夺资源的数目不足以满足诸进程运行的要求，则发生在运行进程中，不同的进程因争夺这些资源陷入僵局。
        举例说明：资源A,B；进程C,D
   资源A,B都是不可剥夺资源：一个进程申请了之后，不能强制收回，只能进程结束之后自动释放。内存就是可剥夺资源
   进程C申请了资源A，进程D申请了资源B。
   接下来C的操作用到资源B，D的资源用到资源A。但是C,D都得不到接下来的资源，那么就引发了死锁。
（3）竞争临时资源
2.进程推进顺序不当发生死锁

1.2产生死锁的必要条件

（1）互斥条件：进程对所分配到的资源不允许其他进程进行访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源
（2）请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此事请求阻塞，但又对自己获得的资源保持不放

（3）不可剥夺条件：是指进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用完后自己释放
（4）环路等待条件：是指进程发生死锁后，必然存在一个进程–资源之间的环形链

2.处理死锁的方法

(1)预防死锁。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。预防死锁实现的方法，是一-已种被较广泛易使用。但由于所施加的限制条件太严格，因而可能会导致系统资源利用率和系统吞吐量降低。

(2)避免死锁。该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件,而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件,便可获得较高的资源利用率及系统吞吐量,但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。

(3)检测死锁。这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源;采取适当措施，从系统中将已发生的死锁清除掉。

(4)解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。

3.银行家算法

① 如果Request≤Need,则转向 ②；否则出错，因为所需的资源数已超过它所宣布的最大值。

② 如果Request≤Available，则转向 ③；否则表示尚无足够的资源，该进程需等待

③ 系统试探性分配请求的资源给进程

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];

④ 系统再执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，进程Pi等待。

4.安全性算法

① 设置两个参数

工作向量Work；表示系统可提供给进程继续运行所需的各类资源数目，初始时，Work=Available；

标志变量Finish：表示系统是否有足够资源分配给进程 (True有；False没有) 。初始化为False。

② 若Finish[i]=False&&Need<=Work，则执行 ③；否则执行 ④ (i ii 为资源类别)

③ 进程 P PP 获得第i类资源，则顺利执行直至完成，并释放资源： Work=Work+Allocation；Finish[i]=true；转 ② 。

④ 若所有进程的Finish[i]=true，则表示系统安全；否则，不安全！

5.算法实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define m 3//进程数
#define n 2//资源数
#define False 0
#define True 1



void input();//输入
void bank();//银行家算法
void predistribution();//预分配
void security();//安全性算法
void show1();//输出资源初始情况
void show2();//输出预分配



char str1[m];//进程名
int str2[n];//进程个数
int Max[m][n];//最大需求矩阵
int Allocation[m][n];//分配矩阵
int Need[m][n];//需求矩阵
int Available[n];//可利用资源向量

int Request[n];//进程请求向量
int p;//p进程请求

int Finish[m] = {0};
int Work[n];
int _Allocation[m][n];//分配矩阵
int _Need[m][n];//需求矩阵
int _Available[n];//可利用资源向量


int main()
{
	input();
	printf("执行安全性算法，判断当前系统是否安全\n");
	security();
	while (1)
	{
		bank();	
	}
	return 0;
}


void input()
{
	printf("系统中进程数为:%d\n系统中资源种数为:%d\n", m, n);

	printf("请输入各个资源的名称：");
	for (int i = 0;i < n;i++)
		scanf("%s", str1);

	printf("请输入系统各个资源的个数：");
	for (int i = 0;i < n;i++)
		scanf("%d", &str2[i]);

	printf("请输入各个进程所需的各类资源的最大需求数量：");
	for (int i = 0;i < m;i++)
		for (int j = 0;j < n;j++)
			scanf("%d", &Max[i][j]);

	printf("请输入各个进程当前所分配各类资源的数量：");
	for (int i = 0;i < m;i++)
		for (int j = 0;j < n;j++)
			scanf("%d", &Allocation[i][j]);

	printf("输出各个进程所需的各类资源数量：\n");
	for (int i = 0;i < m;i++)
	{
		for (int j = 0;j < n;j++)
		{
			Need[i][j] = Max[i][j] - Allocation[i][j];
			printf("%d ", Need[i][j]);
		}
		printf("\n");
	}

	printf("输出系统中目前各个资源的可利用数量：\n");
	for (int j = 0;j < n;j++)
	{
		int sum = 0;
		for (int i = 0;i < m;i++)
		{
			sum = sum + Allocation[i][j];
		}
		Available[j] = str2[j] - sum;
		printf("%d ", Available[j]);
	}
	printf("\n");

	printf("系统的各个进程资源分配图：\n");
	show1();

    for(int i=0;i<m;i++)     //初始化
		for (int j=0;j < n;j++)
		{
			_Allocation[i][j] = Allocation[i][j];
			_Need[i][j] = Need[i][j];
		}
	for (int j = 0;j < n;j++)
	{
		_Available[j] = Available[j];
	}


}


void bank()
{
	/*---------------------------------------------------*/
	printf("请输入需要提出请求的进程下标号：");
	scanf("%d", &p);
	printf("请输入该进程提出的请求向量：");
	for (int i = 0;i < n;i++)
		scanf("%d", &Request[i]);

	int flag = True;//标志位
	for (int i = 0;i < n;i++)
	{
		if (Request[i] > Need[p][i])
		{
			printf("所需的请求资源已经超过该进程的最大需求,该进程%d等待\n", p);
			flag=False;
			break;
		}
		else
		{
			if (Request[i] > Available[i])
		    {
			printf("尚且没有足够资源分配给该进程%d\n", p);
			flag=False;
			break;
		    }

		}
	}


	if (flag)
	{
		predistribution(); 
		security();
		printf("输出进程p%d分配后各个进程的资源分配表：\n",p);
        show2();  
	}

}
void predistribution()
{
	for (int j = 0;j < n;j++)
	{
		_Available[j] = Available[j] - Request[j];
	}
	for (int i = 0;i < m;i++) //预分配
	{
		if (i == p)
			for (int j = 0;j < n;j++)
			{
				_Allocation[i][j] = Allocation[i][j] + Request[j];
				_Need[i][j] = Need[i][j] - Request[j];
			}
	}
	
}

void security()
{
   
	for (int i = 0;i < n;i++)
	{
		Work[i] = _Available[i];
	}
	for (int i = 0;i < m;i++)
	{
			Finish[i] = 0;
	}



	int security[m];//记录查找序列编号
	int a = 0,b;//a为记录查找次数
	int i = 0;
	while (a <m)
	{ 

		b = finish();
		if (b != -1)
		{
			security[i++] = b;
			a++;
		}
		else
		{
			printf("找不到满足条件的进程\n");
			break;
		}
	}	
	if (a!= m)
	{
       printf("找不到安全序列，系统处于不安全状态。\n");
	   for (int i = 0;i < m;i++) //修改为之前的值
	   {
		  for (int j = 0;j < n;j++)
		  {
				_Available[j] = Available[j];
				_Allocation[i][j] = Allocation[i][j] ;
				_Need[i][j] = Need[i][j];   
		  }
	   }

	}	
	else
	{
		printf("找到安全序列，系统处于安全状态。\n");
		for (int i = 0;i < m;i++)
		{
			printf("%d ", security[i]);
		}
		printf("\n");

		for (int i = 0;i < m;i++)// 修改各个矩阵
			for (int j = 0;j < n;j++)
			{
				Need[i][j] = _Need[i][j];
				Allocation[i][j] = _Allocation[i][j];
			}
        for (int j = 0;j < n;j++)
			{
				Available[j] = _Available[j];
			}
		/*无死锁存在安全状态，若该进程执行完毕，资源返还给系统*/
		int k=0;
		for (int j = 0;j < n;j++)
		{
			if (Need[p][j] == 0)
			{
				k++;
				if (k == n)     //存在进程已经结束
				for (int j = 0;j < n;j++)
				{
					Available[j] = Available[j] + Allocation[p][j];//已分配资源返回给系统
					Allocation[p][j] = 0;
					Max[p][j] = 0;
				}	
			}

		}
	}
	printf("\n");


}

int finish()//one
{
	
	for (int i = 0;i < m;i++)
	{
		int r = 0;
		for (int j = 0;j < n;j++)
		{
			if (Finish[i] == 0 && _Need[i][j] <= Work[j])
			{
				r++;
				if (r == n)
				{
					Finish[i] = 1;
					for (int k = 0;k < n;k++)
					{
						Work[k] = Work[k] + _Allocation[i][k];
					}
					return i;
				}
			}
		}
	}
	return - 1;
}

void show1()
{
	printf("\t---------------------------------------------------------\t\n");
	printf("\tMax\t\tAllocation\tNeed\t\tAvailable\n");
	for (int i = 0;i < 4;i++)
		printf("\tA B C\t");
	printf("\n");
	for (int i = 0;i < m;i++)
	{
		printf("进程p%d  ", i);
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Max[i][j]);
			
		}
		printf("\t\t");
		for (int j = 0;j < n;j++)
		{
            printf("%d ", Allocation[i][j]);
		}
		printf("\t\t");
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Need[i][j]);
		}
		printf("\t\t");
		if(i==p)
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Available[j]);
		}
		printf("\n");
	
	}
	printf("\t---------------------------------------------------------\t\n");
}
void show2()
{
	
	printf("\t*************************************************************\t\n");
	printf("\tMax\t\tAllocation\tNeed\t\tAvailable\tFinish\n");
	for (int i = 0;i < 4;i++)
		printf("\tA B C\t");
	printf("\n");
	for (int i = 0;i < m;i++)
	{
		printf("进程p%d  ", i);
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Max[i][j]);
			
		}
		printf("\t\t");
		for (int j = 0;j < n;j++)
		{
            printf("%d ", Allocation[i][j]);
		}
		printf("\t\t");
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Need[i][j]);
		}
		printf("\t\t");
		if(i==p)
		for (int j = 0;j < n;j++)
		{
			printf("%d ", Available[j]);
		}
		printf("\t\t");
		printf("%d ",Finish[i]);
		printf("\n");
	
	}
}

/*
测试样例:
A B C

10 5 7

7 5 3
3 2 2
9 0 2
2 2 2
4 3 3

0 1 0
2 0 0
3 0 2
2 1 1
0 0 2

1

1 0 2

4

3 3 0

1

1 3 0

1

0 2 0

*/





/*
A B

6 8

3 5
2 4
4 2

2 3
0 1
2 2

*/




///*检测出安全序列后 检查此时系统所有进程的need是否存在一个进程小于available*/
//		int count=0;//资源数
//		int num = 0;//进程数
//		for (int i = 0;i < m;i++)
//		{
//			for (int j = 0;j < n;j++)
//			{
//				if (Need[i][j] < Available[j])
//
//				{
//					count++;
//					
//				}
//				else
//				{
//					num++;
//					break;
//				}
//			}
//			if (num== m)
//			{
//				show2();
//				printf("此时系统的可利用资源不能满足所以进程\n");
//				printf("此时系统进入死锁状态。\n");
//				
//			    exit(1);
//			}
				
		//}

测试结果：

样例1（课本）：