死锁避免——>银行家算法

银行家算法,死锁避免——>银行家算法 一、安全序列 所谓安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找到出一个安全序列,系统就是安全状态。当然,

死锁避免——>银行家算法

银行家算法,死锁避免——>银行家算法

一、安全序列

所谓安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找到出一个安全序列,系统就是安全状态。当然,安全序列可能有多个

如果分配了资源之后,系统中找不到任何一个安全序列,系统就进入不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然,如果有进程提前归还了一些资源,那系统也有可能重新回到安全状态,不过在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态,就一定不会发生死锁。如果系统进入了不安全状态,就可能发生死锁(处于不安全状态未必就是发生了了死锁,但发生了死锁时一定是在不安全状态)

判断是否处于安全序列?举例1:安全序列

死锁避免——>银行家算法

依次检查剩余可用资源(3,3,2)是否能满足各进程的需求

可满足p1需求,将p1加入安全序列,并更新可用资源值为(5,3,2)

依次检查剩余可用资源(5,3,2)是否能满足剩余进程(不包括已加入安全序列的进程)的需求

可满足p3需求,将p3加入安全序列,并更新可用资源值为(7,4,3)

依次检查剩余可用资源(7,4,3)是否能满足剩余进程(不包括已加入安全序列的进程)的需求

……

此次类推,共五次循环检查即可将5个进程都加入安全序列,最终可得一个安全序列。算法称为安全性算法。可以很方便地用代码实现以上流程,每一轮检查都从编号较小的进程开始检查。

在实际做题时,手算会更快速,经对比发现,(3,3,2)可以满足p1,p3,说明无论如何,这两个进程的资源需求一定是可以满足的,因此,p1,p3一定可以顺序执行完,并归还资源。可把p1,p3先加入安全序列。

(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)

剩下的p0,p2,p4都可被满足,同理,这些进程都可以加入安全序列。

于是,5个进程全部加入安全序列,说明此时系统处于安全状态,暂不可能发生死锁

判断是否处于安全序列?举例2:不安全序列

死锁避免——>银行家算法

经对比发现,(3,3,2)可以满足p1,p3,说明无论如何,这两个进程的资源需求一定是可以满足的,因此,p1,p3一定可以顺序执行完,并归还资源。可把p1,p3先加入安全序列。

(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)

剩下的p0需要(8,4,2),p2需要(6,5,0),p4需要(4,3,4)

任何一个进程都不能被安全满足

于是,无法找到任何一个安全序列,说明此时系统处于不安全状态有可能发生死锁

二、银行家算法

用于避免死锁

2.1 核心思想:

在进程提出资源申请时,先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。

死锁避免——>银行家算法

2.2 算法详述

假设系统中有n个进程m种资源

每个进程在运行前先声明对各种资源的最大需求数,则可用一个n*m的矩阵(可用二维数组实现)表示所有进程对各种资源的最大需求数,称为最大需求矩阵Max,Max[i,j]=k表示进程Pi最多需要K个资源Rj。

同理,系统可用用一个n*m的分配矩阵Allocation表示所有进程的资源分配情况。

Max-Allocation=Need矩阵,表示各进程最多还需要多少各类资源。

另外,用一个长度为m的一维数组Avaliable表示当前系统中还有多少可用资源。

某进程Pi向系统申请资源,可用一个长度为m的一维数组Request i 表示本次申请的各种资源量。

可用银行家算法预判本次分配是否会导致进入不安全状态:

(1)如果Request[ j ]<=Need[i,j](i<=j<=m)便转向(2);否则认为出错。

(2)如果Request[ j ]<=Available[ j ](i<=j<=m)便转向(3);否则表示尚无足够资源,Pi必须等待。

(3)系统试探着把资源分配给进程Pi,并修改相应的数据(并非真的分配,修改数值只是为了预判);

Available=Available-Request;

Allocation[ i,j]=Allocation[ i,j]+Request[ j ] ;

Need[i,j]=Need[i,j]-Request[ j ] ;

(4)操作系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式分配;否则,回复相应数据,让进程阻塞等待。

三、总结

数据结构:

长度为m的一维数组Available表示还有多少可用资源

n*m 矩阵Max 表示各进程对资源的最大需求数

n*m 矩阵Allocation表述已经给各进程分配了多少资源

Max-Allocation=Need 矩阵表示各进程此次申请的各种资源数

银行家算法步骤:

(1)检查此次申请是否超过了之前申明的最大需求数

(2)检查此时系统剩余的可用资源是否还能满足这次请求

(3)试探着分配,更改数据结构

(4)用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

检查当前的剩余可用资源是否能满足某个进程的嘴阀需求,如果可用,就把该进程加入安全序列,

并把该进程持有的资源全部回收。

不断重复上述过程,看最终是否能让所有进程都加入安全序列

 

系统处于不安全状态未必死锁,但死锁时一定处于不安全状态。

系统处于安全状态一定不会死锁。

五、代码:

#include <iostream>
using namespace std;

#define MAXPROCESS 50                        /*最大进程数*/
#define MAXRESOURCE 100                        /*最大资源数*/
int AVAILABLE[MAXRESOURCE];                    /*可用资源数组*/
int MAX[MAXPROCESS][MAXRESOURCE];            /*最大需求矩阵*/
int ALLOCATION[MAXPROCESS][MAXRESOURCE];    /*分配矩阵*/
int NEED[MAXPROCESS][MAXRESOURCE];            /*需求矩阵*/
int REQUEST[MAXPROCESS][MAXRESOURCE];        /*进程需要资源数*/
bool FINISH[MAXPROCESS];                        /*系统是否有足够的资源分配*/
int p[MAXPROCESS];                             /*记录序列*/
int m,n;                                    /*m个进程,n个资源*/
void Init();
bool Safe();
void Bank();
void showdata(int,int);

int main()
{
	Init();
	Safe();
	Bank();
}
void Init()                /*初始化算法*/
{
	int i,j;
	cout<<"请输入进程的数目:";
	cin>>m;
	cout<<"请输入资源的种类:";
	cin>>n;
	cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			cin>>MAX[i][j];
	cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			cin>>ALLOCATION[i][j];
			NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
			if(NEED[i][j]<0)
			{
				cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数 错误,请重新输入:"<<endl;
				j--;
				continue;
			}
		}
	}
	cout<<"请输入各个资源现有的数目:"<<endl;
	for(i=0;i<n;i++)
	{
		cin>>AVAILABLE[i];
	}
}
void Bank()                /*银行家算法*/
{
	int i,cusneed,flag = 0;
	char again;
	while(1)
	{
		showdata(n,m);
		cout<<endl;
input:
		cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;
		cin>>cusneed;
		if (cusneed > m)
		{
			cout<<"没有该进程,请重新输入"<<endl;
			goto input;
		}
		cout<<"请输入进程所请求的各资源的数量"<<endl;
		for(i=0;i<n;i++)
		{
			cin>>REQUEST[cusneed][i];
		}
		for(i=0;i<n;i++)
		{
			if(REQUEST[cusneed][i]>NEED[cusneed][i])//如果用户选择的线程的第i个资源请求数>该线程该资源所需的数量
			{
				cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;
				goto input;
			}
			if(REQUEST[cusneed][i]>AVAILABLE[i])//如果用户选择的线程的第i个资源请求数>系统现有的第i个资源的数量
			{
				cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl;
				goto input;
			}
		}
		for(i=0;i<n;i++)//如果请求合理,那么下面
		{
			AVAILABLE[i]-=REQUEST[cusneed][i];//系统可用资源减去申请了的
			ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];//线程被分配的资源加上已申请了的
			NEED[cusneed][i]-=REQUEST[cusneed][i];//线程还需要的资源减去已申请得到的
		}
		if(Safe())//AVAILABLE  ALLOCATION  NEED变动之后,是否会导致不安全
		{
			cout<<"同意分配请求!"<<endl;
		}
		else
		{
			cout<<"您的请求被拒绝!"<<endl;
			for(i=0;i<n;i++)
			{
				AVAILABLE[i]+=REQUEST[cusneed][i];
				ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
				NEED[cusneed][i]+=REQUEST[cusneed][i];
			}
		}
		for (i=0;i<n;i++)
		{
			if (NEED[cusneed][i] <= 0)
			{
				flag++;
			}
		}
		if (flag == n)//如果该进程各资源都已满足条件,则释放资源
		{
			for (i=0;i<n;i++)
			{
				AVAILABLE[i] += ALLOCATION[cusneed][i];
				ALLOCATION[cusneed][i] = 0;
				NEED[cusneed][i] = 0;
			}
			cout<<"线程"<<cusneed<<" 占有的资源被释放!"<<endl;
			flag = 0;
		}
		for(i=0;i<m;i++)//分配好了以后将进程的标识FINISH改成false
		{
			FINISH[i]=false;
		}
		cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl;
		cin>>again;
		if(again=='y'||again=='Y')
		{
			continue;
		}
		break;
	}
}

 bool Safe() /*安全性算法*/ 
 { 
	int i, j, k, l =0; 
	int Work[MAXRESOURCE]; /*工作数组*/ 
	for (i = 0; i <n; i++) 
	Work[i] = AVAILABLE[i]; 
	for (i = 0; i < m; i++) 
	{ 
		FINISH[i] = false;//FINISH记录每个进程是否安全 
	} 
	while (l<m)//正常的话,共执行m次 
	{ 
		int init_index = l; 
		for (i = 0; i< m; i++) 
		{ 
			if (FINISH[i] == true) 
			{ 
				continue; 
			} 
			for (j = 0; j < n; j++) 
			{ 
				if (NEED[i][j] > Work[j]) 
				{ 
					break; 
				} 
			} 
			if (j == n) 
			{ 
				FINISH[i] = true; 
				for (k = 0; k <n; k++) 
				{ 
					Work[k] += ALLOCATION[i][k]; 
				} 
				p[l++] = i;//记录进程号	
			} 
			else//如果超过继续循环下一个进程 
			{			
				continue; 
			} 
			} 
			if (l==init_index) 
			{ 
				cout <<"系统是不安全的" << endl; 
				return false; 
			} 
		}//for循环 
		cout<< "系统是安全的"<<endl; 
		cout<< "安全序列:" <<endl; 
		for (i = 0; i< l; i++)//改了146行的i值,显示资源分配给进程的顺序 
		{ 
			cout << p[i]; 
			if (i != l - 1) 
			{ 
				cout<<"-->";
			} 
		} 
		cout<<""<<endl;		
		return true; 
	}
void showdata(int n,int m)   //显示
{
	int i,j;
	cout<<endl;  
	cout<<"-------------------------------------------------------------"<<endl;  
	cout<<"系统可用的资源数为:    ";
	for   (j=0;j<n;j++)       
		cout<<"    "<<AVAILABLE[j];      
	cout<<endl;   
	cout<<"各进程还需要的资源量:"<<endl; 
	for   (i=0;i<m;i++)   
	{
		cout<<"    进程"<<i<<":";   
 
		for   (j=0;j<n;j++)
			cout<<"     "<<NEED[i][j];   
		cout<<endl;   
	}   
 
	cout<<endl;   
	cout<<"各进程已经得到的资源量:    "<<endl<<endl;   
 
	for   (i=0;i<m;i++)   
	{
		cout<<"    进程"<<i<<":";   
 
		for   (j=0;j<n;j++)
			cout<<"     "<<ALLOCATION[i][j];
		cout<<endl;   
	}  
	cout<<endl; 
}   

死锁避免——>银行家算法

参考博文:https://blog.csdn.net/wyf2017/article/details/80068608

https://blog.csdn.net/yaopeng_2005/article/details/6935235#commentsedit

死锁避免——>银行家算法的相关内容如下:

标题:死锁避免——>银行家算法|http://www.wc10086.cn/413505.html

本文来自网络,不代表本站立场,转载请注明出处!