死锁的避免主要包含安全性检查算法和银行家算法两个部分，在书上介绍的较为清晰了
【实验目的】
为了解系统的资源分配情况，假定系统的任何一种资源在任一时刻只能被一个进程使用。任何进程已经占用的资源只能由进程自己释放，不能被其他进程抢占。当申请的资源不足的时候，只能等待。因此只要资源分配算法能保证进程的资源请求，且不出现循环等待，就不会出现死锁
【实验原理】
1.编写一个随机算法，只要系统当前剩余资源满足进程的当前要求，就立即把资源分配给进程，以观察死锁产生的情况。
2.编写一个银行家算法，避免死锁的产生
3.银行家算法的原理：每一个新的进程进入系统的时候，需声明运行所需要的每种资源的最大单元数目（不得超过系统拥有的资源总量），当进程进一步请求一组资源时，系统需要首先确定是否有足够的资源分配给该进程，若有再进一步计算这些资源分配后是否会使系统处于不安全状态。若不会，再把资源分配给它，否则等待
【实验代码】
//死锁的避免
//build by W in 11/9
//随机分配算法，检查资源是否满足当前申请即可，然后改变标志位
//安全性算法可以检查是否处于处于安全状态，那么不处于安全状态就是有可能发生死锁
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define M 5 //五个进程
#define N 3 //三类资源
int p[M];
using namespace std;
// int Id[M]; //五个进程号
int Request[M][N]; //当前请求量
int Max[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//最大需求矩阵
int Need[M][N]; //还需要资源矩阵
int Allocation[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//已分配矩阵
bool Finish[M];//一开始全为false
int Available[N]={3,3,2};//可用资源向量
void NEED() //计算Need矩阵
{
int i,j;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
}
}
int Safe()//安全性算法
{
int Work[N],temp[M];//temp[]表示安全序列
int i,j,m,k=0,count;
for(i=0;i<M;i++)
Finish[i]=false;//一开始都置为false
for(j=0;j<N;j++)
Work[j]=Available[j];//安全性算法开始的时候 work=available;
for(i=0;i<M;i++)
{
count=0; //记录符合条件的资源数量
for(j=0;j<N;j++)
{
if(Finish[i]==false &&Need[i][j]<=Work[j])
count++;
}
if(count==N)//当三类资源的请求都可以满足
{
for(m=0;m<N;m++)
{
Work[m]=Work[m]+Allocation[i][m]; //将该进程的各类资源全部收回
}
Finish[i]=true;
temp[k]=i;//记录下满足条件的进程
k++;
i=-1; //将i置为-1 进行i++ 变为0 从头开始循环
}
}
//-----------输出安全序列------------
for(i=0;i<M;i++)
if(Finish[i]==false)
{
cout<<"没有安全序列"<<endl;
return 1;//返回值为1的时候设定为不安全
}
printf("\n");
cout<<"经安全性检查，系统安全"<<endl;
printf("\n");
//打印安全序列
cout<<"本次安全序列是："<<endl;
for(i=0;i<M;i++)//输出安全序列
{
cout<<" "<<temp[i];
}
cout<<endl;
//---------------------------------
return 0;
}
int bank()
{
int mi,i;
Safe();//银行家算法安全性检查
while (1)
{
cout<<"输入要申请资源的进程号："<<endl;
cin>>mi;//输入进程0~4之间一个
cout<<"请输入进程请求资源的数量\n";
for (i=0;i<N;i++)
cin>>Request[mi][i];
for (i=0;i<N;i++)
{
if (Request[mi][i]>Need[mi][i])
{
cout<<"所请求资源数超过进程的需求量！\n";
return 0;
}
else if (Request[mi][i]>Available[i])
{
cout<<"所请求资源数超过系统所有的资源数！\n";
return 0;
}
}
for (i=0;i<N;i++)
{
Available[i]-=Request[mi][i];
Allocation[mi][i]+=Request[mi][i];
Need[mi][i]-=Request[mi][i];
}
if (Safe()==0)//
cout<<"同意分配请求\n";
else
{
cout<<"分配失败\n";
for (i=0;i<N;i++)
{
Available[i]+=Request[mi][i];
Allocation[mi][i]-=Request[mi][i];
Need[mi][i]+=Request[mi][i];
}
}//返还虚拟分配的资源
}
return 0;
}
int random()
{
int mi,i;
while (1)
{
cout<<"输入要申请的资源的进程号："<<endl;
cin>>mi;
cout<<"输入进程所请求的各个资源的数量"<<endl;
for (i=0;i<N;i++)
cin>>Request[mi][i];
for (i=0;i<N;i++)
{
if (Request[mi][i]>Need[mi][i])
{
cout<<"所请求资源数超过进程的需求量！\n";
return 0;
}
if (Request[mi][i]>Available[i])
{
cout<<"所请求资源数超过系统所有的资源数！\n";
return 0;
}
}
for (i=0;i<N;i++)
{
Available[i]-=Request[mi][i];
Allocation[mi][i]+=Request[mi][i];
Need[mi][i]-=Request[mi][i];
}
if (Safe()==1)//safe安全性算法用来检测是否发生死锁，返回值为1表示不存在安全性算法
{
cout<<"没有安全序列，可能会发生死锁\n";
return 0;
}
}
}
void print() //输出
{
int i = 0,j=0;
cout<<"当前可利用资源总量:"<<endl;
cout<<"[";
for(i=0;i<N;i++)
cout<<Available[i]<<" ";
cout<<"]"<<endl<<endl;
cout<<"进程号"<<" "<<"NEED"<<" "<<"MAX"<<" "<<"ALLOCATION"<<endl;
for(i=0;i<M;i++)
{
cout<<i<<" ";
for(j=0;j<N;j++)
cout<<Need[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Max[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<endl;
}
}
int main()
{
int n;
cout<<" 银行家算法和随机分配算法 "<<endl;
cout<<"输入1选择银行家算法，输入2选择随机算法"<<endl;
NEED();//初始化Need矩阵
print();//输出系统中可以调用的矩阵
cin>>n;
if(n == 1)
{
bank();
print();
}
else if(n == 2)
{
random();
print();
}
else cout<<"选择错误，请重新选择"<<endl;
return 0;
}
/*
实验使用数据
银行家算法：P1申请 1 0 2个资源
随机算法：P0申请 3 3 2个资源
*/
【实验结果】
银行家算法
银行家算法查找安全序列
随机算法
【小结或讨论】
银行家算法是书上的一个重点知识，提出的本因是为了预防死锁，银行家算法中亦包含着安全性算法检查，所以这次的实验又一次捋清楚了很多细节。我认为银行家算法中最重要的部分是数据结构，里面有很多涉及到矩阵，向量的运算。所幸的是在书本上给我们指明这些数据结构。包括可利用资源向量，最大需求矩阵，分配矩阵等，这些矩阵的行代表进程编号，列为各类资源数量。有时候算法记得，编程的时候就忘记了。安全性算法去求安全队列是关注比较多的点，但是后面的分配步骤也很重要，书本P114面就详细列举了各种情况。
网友评论