一、实验目的
1、了解什么是操作系统安全状态和不安全状态；
2、了解如何避免系统死锁；
3、理解银行家算法是一种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。
二、实验内容
根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效避免死锁的发生。
三、实验原理
进程申请资源时，系统通过一定的算法判断本次申请是否不可能产生死锁（处于安全状态）。若可能产生死锁（处于不安全状态），则暂不进行本次资源分配，以避免死锁。算法有著名的银行家算法。
1、什么是系统的安全状态和不安全状态？
所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直至最大需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。
如果不存在这样的安全序列，则称系统处于不安全状态。
2、银行家算法
把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。
操作系统按照银行家制定的规则设计的银行家算法为：
（1）进程首次申请资源的分配：如果系统现存资源可以满足该进程的最大需求量，则按当前的申请量分配资源，否则推迟分配。
（2）进程在执行中继续申请资源的分配：若该进程已占用的资源与本次申请的资源之和不超过对资源的最大需求量，且现存资源能满足该进程尚需的最大资源量，则按当前申请量分配资源，否则推迟分配。
（3）至少一个进程能完成：在任何时刻保证至少有一个进程能得到所需的全部资源而执行到结束。
银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源，并能在确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁。
四、实验中用到的系统调用函数
因为是模拟程序，可以不使用系统调用函数。
五、银行家算法流程图
六、对算法所用的数据结构进行说明；
用N表示系统进程的数目，用M表示资源分类数。
available是一个长度为M的向量，它表示每类资源可用的数量。
max是一个N × M的矩阵，他表示每个进程对资源的最大需求。
allocation是一个N × M的矩阵，它表示当前分给每个进程的资源数目。
need是一个N × M的矩阵，它表示每个进程还缺少多少资源。
total_resource是一个长度为M的向量，它表示系统每类资源的总数量。
在安全性算法中：
temp是一个长度为N的向量，它用来记录进程安全执行的顺序。
work是一个长度为M的向量， 它表示系统可提供给进程的各类资源数目
finish是一个长度为N的向量， 它记录系统是否有足够的资源分配给进程，有则定义为true，反之为false。
七、源代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define false 0
#define true 1
int M; //系统资源类数
int N; //系统进程数
int **max=NULL; //N个进程对M类资源最大资源需求量
int *available=NULL; //系统可用资源数
int **allocation=NULL; //M个进程已分配的资源量
int **need=NULL; //M个进程还需要的资源数量
int *total_resource=NULL; //系统每类资源的总数量
int *temp=NULL; //用来记录进程安全执行的顺序
void init() //初始化函数
{
int i,j;
int flag=1;
int flag2=0;
M=rand()%4+4; //随机生成系统资源类数
N=rand()%4+3; //随机进程数
while(flag==1)
{
total_resource=malloc(sizeof(int) * M); //为数组分配内存
available = malloc(sizeof(int) * M);
max=(int**)malloc(sizeof(int*) * N);
allocation = (int**)malloc(sizeof(int*) * N);
need = (int**)malloc(sizeof(int*) * N);
for(i=0;i<N;i++)
{
max[i]=(int*)malloc(sizeof(int) * M);
allocation[i] = (int*)malloc(sizeof(int) * M);
need[i]=(int*)malloc(sizeof(int) * M);
}
for(i=0;i<M;i++)
{
total_resource[i]=rand()%5+5; //随机生成每类资源的总数量
available[i]=total_resource[i]; //初始化available[M]
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
int temp=0;
while(1)
{
temp=rand()%6;
if(temp<=total_resource[j]) //随机生成最大资源需求量,要小于系统总资源量
break;
}
max[i][j]=temp;
int temp2=0;
while(1)
{
temp2=rand()%4;
if(temp2<=max[i][j]) //随机生成已分配资源数，分配量要小于最大资源需求量
break;
}
allocation[i][j]=temp2;
need[i][j]=max[i][j]-allocation[i][j]; //计算出进程还需要的资源数量,有bug，出现需要资源都为0情况较多，后期要修改
}
}
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
available[i]-=allocation[j][i]; //计算出分配资源后系统可用资源量
}
}
for(i=0;i<N;i++) //保证至少一个进程能够得到全部所需资源而结束
{
flag2=1; //标志置1
for(j=0;j<M;j++)
{
if(available[j]<need[i][j])
{
flag2=0;
break; //对于某个进程，任意一种可用资源少于所需资源时，置0
}
}
if(flag2==1) //所有可用资源都满足某个进程运行
{
flag=0; //循环条件置0，退出循环
break;
}
}
}
printf("\n");
printf("进程数为:%d\n",N);
printf("资源类数为:%d\n",M);
printf("系统中每类资源的总数量依次为：");
for(i=0;i<M;i++)
{
printf("%d ",total_resource[i]);
}
printf("\n");
printf("\n");
printf("\t\t\tT0时刻资源分配表\n");
printf("--------------------------------------------------------------------\n");
printf(" Allocation\tMax\t\tNeed\t\tAvailable\n");
for(i=0;i<N;i++)
{
printf("进程%d\t",i+1);
for(j=0;j<M;j++)
{
printf("%d ",allocation[i][j]);
}
printf("\t");
for(j=0;j<M;j++)
{
printf("%d ",max[i][j]);
}
printf("\t");
for(j=0;j<M;j++)
{
printf("%d ",need[i][j]);
}
printf("\t");
if(i==N/2)
{
for(j=0;j<M;j++)
{
printf("%d ",available[j]);
}
}
printf("\n");
}
printf("--------------------------------------------------------------------\n");
}
int security(int pid) //安全性算法
{
temp = malloc(sizeof(int) * N);
int work[M]; //表示系统可提供给进程的各类资源数目
int finish[N]; //表示系统是否有足够的资源分配给进程
int i,j,k;
int count=0; //进程执行序号
for(i=0;i<N;i++)
{
finish[i]=false;
}
for(i=0;i<M;i++)
{
work[i]=available[i]; //初始化
}
temp[count++]=pid; //第一个执行的进程是pid
finish[pid]=true; //标记为已执行
count=1;
for(i=0;i<M;i++) //回收资源
{
work[i]+=allocation[pid][i];
}
//对剩下进程进行计算
while(1)
{
int flag=1;
int flag2=1;
for(i=0;i<N;i++)
{
for(k=0;k<M;k++) //检查是否need[i][j]<=work[j]
{
if(need[i][k]>work[k])
flag=0;
}
if((finish[i]==false)&&(flag==1))
{
for(j=0;j<M;j++)
work[j]+=allocation[i][j];
finish[i]=true;
temp[count++]=i; //记录执行顺序
flag2=0; //置0
}
}
if(flag2==1) //没有满足条件的进程，退出循环
break;
}
int index=1;
for(i=0;i<N;i++)
{
if(finish[i]==false) //如果存在进程不能执行，返回0
index=0;
}
return index;
}
void bank() //银行家算法
{
int i,j,Pi;
int Request[M];
int flag=1;
while(flag==1)
{
flag=0;
Pi=rand()%N; //随机选取一个进程
for(i=0;i<M;i++)
{
Request[i]=need[Pi][i]; //定义进程申请资源量等于进程资源需求量
if(Request[i]>available[i])
flag=1;
//如果现有资源无法满足该进程需求，则选择另一个进程，继续检查
}
}
printf("\n系统尝试把资源分配给进程%d\n",Pi+1);
for(i=0;i<M;i++) //分配资源
{
available[i]-=Request[i];
allocation[Pi][i]+=Request[i];
need[Pi][i]-=Request[i];
}
int flag2=security(Pi); //调用安全算法
if(flag2==0)
{
printf("\n分配资源后系统不安全，恢复分配前状态,不分配资源！\n");
for(i=0;i<M;i++) //回收资源
{
available[i]+=Request[i];
allocation[Pi][i]-=Request[i];
need[Pi][i]+=Request[i];
}
}
else //系统安全，输出安全序列
{
printf("\n分配资源后系统安全，安全序列为：start");
for(i=0;i<N;i++)
{
printf("->%d",temp[i]+1);
}
printf("\n");
int work[M];
for(i=0;i<M;i++)
{
available[i]+=Request[i];
allocation[Pi][i]-=Request[i];
need[Pi][i]+=Request[i];
work[i]=available[i];
}
printf("\n\t\t\t安全情况分析\n");
printf("------------------------------------------------------------------------\n");
printf(" Work\t\tNeed\t\tAllocation\tWork+Allocation\n");
for(i=0;i<N;i++)
{
printf("进程%d\t",temp[i]+1);
for(j=0;j<M;j++)
{
printf("%d ",work[j]);
}
printf("\t");
for(j=0;j<M;j++)
{
printf("%d ",need[i][j]);
}
printf("\t");
for(j=0;j<M;j++)
{
printf("%d ",allocation[i][j]);
}
printf("\t");
for(j=0;j<M;j++)
{
work[j]+=allocation[i][j];
printf("%d ",work[j]);
}
printf("\n");
}
printf("------------------------------------------------------------------------\n");
}
}
void release() //释放指针
{
free(available);
for(int i=0;i<N;i++)
{
free(max[i]);
free(allocation[i]);
free(need[i]);
}
free(max);
free(allocation);
free(need);
}
int main()
{
srand((unsigned int)time(NULL)); //时间种子产生随机数
init(); //初始化数据
bank(); //银行家算法
release(); //释放指针
}
八、实验结果及分析
分析：
我设计的程序初始化生成系统每类资源总数量的范围是5到9，进程最大需求量的范围是0到6，已分配资源的范围是0到4，进程申请的资源数等于进程还需要的资源数。
根据银行家算法的原理，初始化时要保证进程最大需求量不超过系统每类资源总数量，分配的资源不超过进程的最大需求量，要保证至少一个进程能够得到资源执行结束。当可用资源不足以满足进程运行时，不分配资源，避免死锁。
设计的数值范围会影响到出现不安全情况的概率。如果设计的系统总资源少时，进程对资源的申请会更加难以得到满足，所以出现不安全的概率会提高，同样，设计的进程最大需求量大时，各个进程对资源的需求相应变多，更加容易不安全，还有系统已分配资源的范围，如果已分配的资源越多，剩下可用的资源就越少，也容易导致不安全。可以通过调高系统每类资源总数量的范围、降低进程最大需求量和已分配资源的范围降低出现不安全的概率。
九、思考题
1、 如何设计程序的输入模块才能满足实验要求，请举例说明；
实验要求所有数据都要随机生成。初始化时要保证进程最大需求量不超过系统每类资源总数量，分配的资源不超过进程的最大需求量。进程还需要的资源就等于进程最大需求量减去已分配的资源，即need=max-allocation，系统可用资源就等于系统资源总数量减去已分配的资源，即available=total_resource-allocation。实验还要求至少有一个进程可以得到全部所需资源而运行结束。所以要在初始化数据时判断是否有进程能够执行，否则重新生成数据。
2、 银行家算法在实现过程中必须注意哪些资源分配细节才能避免死锁？
对比请求资源向量和系统当前可利用资源向量，如果某一类资源不满足请求则直接返回分配资源失败。
在初始化数据时判断是否有进程能够执行，否则重新生成数据。