admin 管理员组文章数量: 887017
目录
一、银行家算法概述
二、银行家算法需要的数组结构
三、算法概述
1.安全性算法
2.银行家算法
四、代码实现
五、实验结果验证
一、银行家算法概述
银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。
二、银行家算法需要的数组结构
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]
三、算法概述
1.安全性算法
系统所执行的安全性算法可描述如下:
(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[i]+Allocation[i,j];
Finish[i]=true;
go to step 2;
(4)如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。
2.银行家算法
设Requesti是进程Pi的请求向量,如果表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:
(1) 如果 ≤ Need[i,j],转向步骤(2),否则认为出错,因为它所需的资源数目已超过它所宣布的最大值。
(2) 若 ≤ Available[j],转向步骤(3),否则表示尚无足够资源,Pi必须等待。
(3) 系统尝试把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j] = Available[j] –
Allocation[i,j] = Allocation[i,j] +
Need[i,j] = Need[i,j] –
(4) 系统执行安全性算法,检查此次分配后系统是否处于安全状态。若安全,才正式分配给Pi,完成此次分配;否则,此次试分配作废,恢复原来资源的分配状态,进程Pi等待。
四、代码实现
#include<iostream>
using namespace std;
const int p=5;//进程数
const int r=4;//资源种类
int num = 1;//需要分配资源的进程序号
void init_request(int request[r])
{
//初始化request矩阵
cout<<"Input the number of request:"<<endl;
cin>>num;
num-=1;//下标减1
cout<<"Input the request vector:"<<endl;
for(int i=0;i<r;i++)
cin>>request[i];
}
void init_matrix(int maximum[p][r],int allocation[p][r],int need[p][r],int available[r],int request[r])
{
//初始化函数
cout<<"Input the Allocation matrix:"<<endl;
for(int i=0;i<p;i++)
for(int j=0;j<r;j++)
cin>>allocation[i][j];
cout<<"Input the Need matrix:"<<endl;
for(int i=0;i<p;i++)
for(int j=0;j<r;j++)
cin>>need[i][j];
//cout<<"Input the Max matrix:"<<endl;
//Max矩阵可以由Need和Allocation矩阵推导得出
//Max[i,j]= Need[i,j]+Allocation[i,j]
for(int i=0;i<p;i++)
for(int j=0;j<r;j++)
maximum[i][j]=need[i][j]+allocation[i][j];
cout<<"Input the available vector:"<<endl;
for(int i=0;i<r;i++)
cin>>available[i];
}
void output_func(int allocation[p][r],int need[p][r],int available[r])
{
//输出函数
cout<<endl<<" "<<"Allocation"<<" Need"<<" Available"<<endl;
for(int i=0;i<p;i++)
{
cout<<"P"<<i+1<<" :";
for(int j=0;j<r;j++)
{
cout<<allocation[i][j]<<' ';
}
cout<<" ";
for(int j=0;j<r;j++)
cout<<need[i][j]<<' ';
if(i==0)
{
cout<<" ";
for(int k=0;k<r;k++)
cout<<available[k]<<' ';
}
cout<<endl;
}
cout<<endl;
}
bool compare(int need[],int work[])
{
bool flg = 1;
for(int i=0;i<r;i++)
{
//检查是否有大于的情况存在
if(need[i]>work[i])
{
flg=0;
break;
}
}
return flg;
}
int check_security(int allocation[p][r],int need[p][r],int available[r])
{
//安全性检查函数
int finish[p] = {0};//初始化finish向量
int work[r]; //拷贝available
int lis[p];//用来记录安全时的队列
int cnt=0;
for(int i=0;i<r;i++)
work[i] = available[i];//初始化work向量
//序列分配
//循环p次
for(int m=0;m<p;m++)
{
for(int i=0;i<p;i++)
{
//如果当前进程执行完成,跳过
if(finish[i] == 1)
continue;
//找到finish[i] = false
else{
//如果Need[i,j]<=Work[j]
if(compare(need[i],work))
{
for(int j=0;j<r;j++)
work[j]+=allocation[i][j];
finish[i] = 1;
lis[cnt++] = i+1;//将该状态放入安全状态队列中
break;
}
}
}
}
int flag=1;
for(int i=0;i<r;i++)
{
if(finish[i]==0)
{
flag = 0;
break; //如果存在F的进程,表明系统处于不安全状态
}
else
continue;
}
if(flag)
{
cout<<"系统处于安全状态!"<<endl;
cout<<"安全序列为:";
for(int i=0;i<p;i++)
cout<<lis[i]<<' ';
cout<<endl;
}
else cout<<"系统处于不安全状态!"<<endl;
return flag;
}
void banker(int allocation[p][r],int need[p][r],int available[r],int request[r],int n)
{
if(!compare(request,need[n]))
{
//如果存在Requesti[j]>Need[i][j],认为出错
cout<<"出错!所需资源已超过所宣布的最大值!"<<endl;
return ;
}
else{
//银行家算法(1)没有出错
if(!compare(request,available))
{
//如果存在Requesti[j]>Available[j],认为出错
cout<<"尚无足够资源,必须等待!"<<endl;
return ;
}
else{
for(int j=0;j<r;j++)
{
available[j]-=request[j];
allocation[n][j]+=request[j];
need[n][j]-=request[j];
}
if(check_security(allocation,need,available))
{
cout<<"安全!将资源正式分配"<<endl;
}
else
{
cout<<"不安全!资源分配作废!恢复以前状态"<<endl;
for(int j=0;j<r;j++)
{
need[n][j]+=request[j];
allocation[n][j]-=request[j];
available[j]+=request[j];
}
}
}
}
output_func(allocation,need,available);
}
int main()
{
int maximum[p][r],allocation[p][r],need[p][r];
int available[r],request[r];
init_matrix(maximum,allocation,need,available,request);
cout<<endl<<"检查T0时刻系统是否处于安全状态..."<<endl;
check_security(allocation,need,available);
int flag = 1;
while(flag)
{
cout<<endl<<"对请求资源进行银行家算法检查..."<<endl;
init_request(request);//初始化request矩阵
banker(allocation,need,available,request,num);
cout<<"是否继续输入?(输入0退出):";
cin>>flag;
}
return 0;
}
/*测试数据
0 0 3 2
1 0 0 0
1 3 5 4
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
2 3 5 6
0 6 5 2
1 6 5 6
1 6 2 2
*/
五、实验结果验证
1.能安全分配的情况
2.分配不安全情况(注意一定要恢复原来的状态)
3.需要的资源超过自己需要的最大值
4.尚无足够资源,需等待分配
版权声明:本文标题:银行家算法(C++实现) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1727377226h1111013.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论