避免死锁的银行家算法C++程序实现
本篇博文为追忆以前写过的算法系列第二篇(20081021)
温故知新
目的:具有代表性的死锁避免算法是Dijskstra给出的银行家算法。本实验是基于银行家算法的思想通过编写C++程序实现银行家算法的计算机程序化。使其更有用。同一时候也加深了有关自愿申请、避免死锁等概念,体会避免死锁的实际实现过程与方法。
要求: 1.设定进程p对各类资源r合理的最大需求max及初值确定;2.设定系统提供资源初始状况allocation。3.设定每次某个进程对各类资源的申请表示need;4.编制C++程序。基于银行家算法思想。决定申请是否被同意。
说明:
1.数据结构
如果有p个进程r类资源,则有例如以下数据结构:
max[p][r] p个进程对r类资源的最大需求量
allocation[p][r] p个进程已经得到r类资源的资源量
need[p][r] p个进程还须要r类资源的资源量
available[r] 当前系统对r类资源的可用资源数
2.银行家算法
设进程I提出请求request[r],则银行家算法按例如以下规则进行推断。
(1)假设request[r]<=need[p][r],则转(2);否则,出错。
(2)假设request[r]<=available
[r],则转(3);否则,出错。
(3)系统试探分配资源,改动相关数据:
available[r]= available [r]-request[r]
allocation[pn][r]=allocation[pn]+request[r]
need[pn][r]=need[pn][r]-request[r]
当中,pn指第pn行申请资源。
(4)系统运行安全性检查,如安全,则分配成立。否则试探险性分配作废,系统恢复原状,进程等待。
3.安全性检查
(1)设置两个工作向量work=available;finish[p]=0;
(2)从进程集合中找到一个满足下述条件的进程。
finish[i]=0
need<=work
如找到,运行(3)。否则,运行(4)
(3)设进程获得资源。可顺利运行,直至完毕,从而释放资源:
work=work+allocation
finish[i]=1
转(2);
(4)如全部的进程finish[p]=1,则表示安全;否则系统不安全。
算法流程:
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ3VqaW5qaW5zZXU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
算法程序:
// gujinjin 08/10/05_06
// 避免死锁银行家算法的C++ 编程实现 #include<iostream>
using namespace std; // p 进程数,r 资源种类
#define p 4
#define r 3 /*-----------------------------------------------*/
/*输入函数*/
/*-----------------------------------------------*/
//a-max,b-allocation,c-need,d-available
void input(int a[p][r],int b[p][r],int c[p][r],int d[r])
{
int i,j;
cout<<"* input max data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>a[i][j];
cout<<"* input allocation data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>b[i][j];
cout<<"* input need data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>c[i][j];
cout<<"* input available data:\n";
for(j=0;j<r;j++)cin>>d[j];
} /*-----------------------------------------------*/
/*比較函数*/
/*-----------------------------------------------*/
//比較结果为m中的元素全大于n中的元素返回1,否则返回0
int com(int m[r],int n[r])
{
int i,flag=0;
for(i=0;i<r;i++)
if(m[i]<n[i])
{
flag=1;
break;
}
if(flag==1) return(0);
else return(1);
} /*-----------------------------------------------*/
/*安全性检验函数*/
/*-----------------------------------------------*/
//b、c、d意义同上
int stest(int b[p][r],int c[p][r],int d[r])
{
int i,j,k,l,flag=0,flag1=0;
int t[r],finish[p],dd[r];
for(i=0;i<p;i++)finish[i]=0;//finish为1即表示available满足某一进程并让事实上现 for(i=0;i<r;i++)dd[i]=d[i];
cout<<"分配序列:\n";
for(k=0;k<p;k++) //全搜索。直至实现或不可能实现
{
for(i=0;i<p;i++)
{
if(finish[i]==1)continue;
else
{
for(j=0;j<r;j++)t[j]=c[i][j];
if(com(dd,t))
{
finish[i]=1;
cout<<i+1<<'\t';
flag=1;
for(l=0;l<r;l++)dd[l]=dd[l]+b[i][l];
break;
}
}
if(flag==1)break;
}
}
cout<<'\n';
for(l=0;l<p;l++)
{
//cout<<finish[l]<<endl;
if(finish[l]==0)flag1=1;
}
//cout<<flag1<<endl;
if(flag1==0)return(1); //flag1为记录finish是否有0存在的标记,当flag1=0时,安全
else return(0);
} /*-----------------------------------------------*/
/*申请进程后的安全性检验函数*/
/*-----------------------------------------------*/
//req-request,n-第n个进程申请资源
void rtest(int b[p][r],int c[p][r],int d[r],int req[r],int n)
{
int i,j;
int t[r];
n=n-1;
for(i=0;i<r;i++)t[i]=c[n][i];
if(com(d,req)&&com(t,req))//对available,request进行比較
{
for(j=0;j<r;j++)
{
b[n][j]=b[n][j]+req[j];
c[n][j]=c[n][j]-req[j];
d[j]=d[j]-req[j];
}
if(stest(b,c,d))cout<<"同意"<<n+1<<"个进程申请资源! \n";
else
{
cout<<"不同意"<<n+1<<"个进程申请资源!\n"; cout<<"恢复曾经状态!\n";
for(j=0;j<r;j++)
{
b[n][j]=b[n][j]-req[j];
c[n][j]=c[n][j]+req[j];
d[j]=d[j]+req[j];
}
}
} else cout<<"申请资源量出错! \n";
} /*-----------------------------------------------*/
/*主函数*/
/*-----------------------------------------------*/
void main()
{
int j,n; //n-第n个资源申请
int max[p][r],allocation[p][r],need[p][r];
int available[r],request[r];
input(max,allocation,need,available); if(stest(allocation,need,available)==1)cout<<"初始状态安全。\n";
else cout<<"初始状态不安全。\n"; cout<<" input request data:\n";
for(j=0;j<r;j++)cin>>request[j]; cout<<"第n个进程申请资源——n的值\n";
cin>>n; rtest(allocation,need,available,request,n);
}
结果演示:
最新文章
- OCP笔记001
- svn服务器搭建与使用
- CSS3 功能
- SparkSQL External Datasource简易使用之AVRO
- 用python写makefile
- 大礼包!ANDROID内存优化(大汇总)
- Keil C51程序调试过程
- 从零开始学习jquery (一)
- HttpClient使用具体解释
- Http Pipeline详细分析(下)
- Oracle Sql优化之Merge 改写优化Update
- Linux操作系统位数查看
- 为什么选择使用Sass而不是Less?
- Android 自定义View -- 简约的折线图
- SpringBoot整合Swagger2,再也不用维护接口文档了!
- react-fetch数据发送请求
- mysql 查询优化 ~ 多表查询基础知识
- nginx配置2
- mybatis 转义
- PyPDF2详解