实验三预防进程死锁的银行家算法
1、需求分析
(1) 输入的形式和输入值的范围
首先输入进程个数,然后再输入资源类型数,接着输入每种资源的可用数目,然后输入每个进程所需要的各种资源最大值,然后输入进程已经分配的资源,银行家算法初始化的输入完成。
输入进程是否继续,如果继续则输入请求的进程的应用,然后输入进程的请求量。
(2) 输出的形式
状态安全则输出安全的序列,不安全则输出提示信息。不管安全与否都会提醒用户是否继续输入。
3)程序所能达到的功能
假设系统中有n个进程P1, … ,Pn,有m类可分配的资源R1, … ,Rm,在T0时刻,进程Pi分配到的j类资源为Allocationij个,它还需要j类资源Need ij个,系统目前剩余j类资源Workj个,现采用银行家算法进行进程资源分配预防死锁的发生。设计程序模拟预防进程死锁的银行家算法的工作过程。
4) 测试数据
2.概要设计
int Available[MaxNumber];
int Max[MaxNumber][MaxNumber];
int Allocation[MaxNumber][MaxNumber];
int Need[MaxNumber][MaxNumber];
int Request[MaxNumber];
int SafeOrder[MaxNumber];
输入资源类型
数目
输入每种资源
的可用数目
输入每个进程所需各种资源
的最大值
输入每个进程已经分配的资源输入要申请的进程号
输入所请求的资源量
是否再次申请是
输入进程个数
3.详细设计
1)安全性算法
用于检测当前时刻系统的安全性
步骤:
1. 从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false
②Need[i,j]<=Work[j] 若找到执行步骤2,找不
到执行步
骤3
2. 进程满足上述条件,进程能完成且释放资源,故
Work[j]+=Allocation[i,j]
Finish[i]=true;
返回步骤1
3. 如果所有进程满足Finish[i]=true,则系统处于安全状态,否
则系统处于不安全状态
2)银行家算法
在该函数内,建立一个while(1)的循环,在循环内首先输入要申请的进程号和一个for语句判断Request[number][i]是否小于Need[number][i],不小于等于则出错,接着判断Request[number][i]是否小于Available[i],如果不小于等于则出错,接着系统把资源分配给所申请的进程号,并修改如下数据Available[i]=Available[i]-Request[number][i]
Allocation[number][i]+=Request[number][i];
Need[number][i]-=Request[number][i];
接着进行安全性算法检查,算法返回true则为安全,否则为不安全
接着输入y表示还要继续分配,否则结束分配
4、调试分析
1)调试过程中遇到的问题以及解决方法,设计与实现的回顾
讨论和分析
在调试过程中将请求量容易输入错误,会造成不同的结果。
2)算法的性能分析(包括基本操作和其它算法的时间复杂度
和空间复杂度的分析)及其改进设想
该算法主要是进行数组的加减运算和排序的处理。
5、用户使用说明
先输入进程个数
再输入资源类型数
再输入每种资源可用数目
输入每个进程的需要的各种资源的最大值
输入每个进程已经分配的资源数目
输入要申请的进程号
输入所请求的资源量
6、测试结果
7、附录
// 实验3.cpp : 定义控制台应用程序的入口点。//
#include
#include
using namespace std;
struct Sign{
string name;
int order;
bool finish;
};
int main()
{
int i=0;
int j=0;
cout<<"请输入进程的个数"<int Num_Progress;
cin>>Num_Progress;
cout<<"请输入资源的个数"<int Num_Source;
cin>>Num_Source;
//定义进程和资源情况的表格
int **progress=new int*[Num_Progress];
for(i=0;i{
progress[i]=new int[2*Num_Source];
}
//定义进程的名字
Sign *sign=new Sign[Num_Progress];
cout<<"请输入进程的名称"<for(i=0;i{
cin>>sign[i].name;
sign[i].order=0;
sign[i].finish=false;
}
//定义Available
int *available=new int[Num_Source];
cout<<"请输入Available的资源的值"<for(i=0;i{
cin>>available[i];
}
//初始化数据
for(i=0;i{
cout<<"请先输入"<for(j=0;j<2*Num_Source;j++)
{
cin>>progress[i][j];
}
}
//初始化work
int *work=new int[Num_Source];
for(i=0;i{
work[i]=available[i];
}
//记录完成的顺序
int progressOrder=1;
//记录当前的检查次数
int currentTime=0;
//开始算法
while(currentTime!=Num_Progress)
{
for(i=0;i{
if(sign[i].finish==false)
{
bool all_well=true;
for(j=0;j{
if(work[j]