实验内容：
编程实现银行家算法中的安全性检查子算法，要求：
(1) 本程序要能描述 n 个并发进程共享 m 类资源，在某一时刻的资源分配状态；
n、m 自定，但都不能小于 3；
(2) 本程序功能：
① 联机输入：系统拥有的每类资源的最大数量(即可利用资源向量的初值)、
n 个进程的最大需求矩阵、当前时刻 n 个进程的已分配资源矩阵；
② 如果①中出现不合理的输入，直接检查指出，并不进行后续步骤，程序
结束；
③ 计算并输出系统当前时刻的可利用资源向量；
④ 计算并输出当前时刻 n 个进程的还需要资源矩阵；
⑤ 根据安全性检查算法，判定当前系统状态是否安全，输出检查结论。
注意：
(1) 这里所指的“不合理的输入”是：某进程对某资源的最大需求大于系统拥有
该类资源的最大数量；某进程在某类资源上，已分配资源大于它的最大需求等。
(2) 这个算法是“银行家算法”的子算法，其中用到的数据结构必须采用与银行
家算法相同的数据结构(见教材)，以方便下次实验使用
设计、运行程序，记录设计程序的源代码；
运行时的输入数据，应该包含合理输入和不合理输入两种情况；
观察并记录运行结果。
/*这里模拟的是3个进程申请3个资源*/
要用.cpp的格式保存下列代码
#include <stdio.h>
#define N 3 //进程数目
#define M 3 //资源类数
#define M 3 //资源类数
int Available[M]; //空闲资源向量Available
int Max[N][M]; //最大需求矩阵Max
int Allocation[N][M]; //分配矩阵Allocation
int Need[N][M]; //需求矩阵Need
int Max[N][M]; //最大需求矩阵Max
int Allocation[N][M]; //分配矩阵Allocation
int Need[N][M]; //需求矩阵Need
bool bankSecurable(int allocation[N][M],int available[M]){
STEP1:
int finish[N];
int work[M];
int i=0; //第i个进程
int j=0; //第j个资源
int finish[N];
int work[M];
int i=0; //第i个进程
int j=0; //第j个资源
for( i=0;i<N;i++){
finish[i]=false;
}
for( j=0;j<M;j++){
work[j]=available[j];
}
finish[i]=false;
}
for( j=0;j<M;j++){
work[j]=available[j];
}
STEP2:
for( i=0;i<N;i++){
if(finish[i]==false&&Need[i][0]<=work[0]&&Need[i][1]<=work[1]&&Need[i][2]<=work[2]){
goto STEP3;
}else{
if(i==N-1){
//从进程集合中找不到一个进程能满足条件时
goto STEP4;
}
}
}
for( i=0;i<N;i++){
if(finish[i]==false&&Need[i][0]<=work[0]&&Need[i][1]<=work[1]&&Need[i][2]<=work[2]){
goto STEP3;
}else{
if(i==N-1){
//从进程集合中找不到一个进程能满足条件时
goto STEP4;
}
}
}
STEP3:
finish[i]=true;
work[0]=work[0]+allocation[i][0];
work[1]=work[1]+allocation[i][1];
work[2]=work[2]+allocation[i][2];
goto STEP2;
finish[i]=true;
work[0]=work[0]+allocation[i][0];
work[1]=work[1]+allocation[i][1];
work[2]=work[2]+allocation[i][2];
goto STEP2;
STEP4:
bool alltrue=true;
for( i=0;i<N;i++){
if(finish[i]==false){
alltrue=false;
break;
}
}
bool alltrue=true;
for( i=0;i<N;i++){
if(finish[i]==false){
alltrue=false;
break;
}
}
return alltrue;
}
}
int main(int argc,char* argv[])
{
/* 1、初始化*/
int k; //用在判断进程对资源的最大需求数目超过了当前可用资源数目处
int m,n; //用在3个进程的对3类资源的各自最大需求资源数目处
int x,y; //用在3类资源的已分配资源数目处
int v,w; //用在3个进程对3类资源的还需求数目处
int a=0;
int b,c;
int max_Available[3]={0,0,0};//未初始化的可利用最大资源数目
int g=0; //用作循环以确定当前的可利用资源
printf("请依次输入3类资源的可用资源数目的最大值(中间以空格隔开)：\n");
scanf("%d%d%d",&max_Available[0],&max_Available[1],&max_Available[2]);
printf("请依次输入3个进程的对3类资源的各自最大需求资源数目(中间以空格隔开)：\n");
for(m=0;m<3;m++){
for(n=0;n<3;n++)
scanf("%d",&Max[m][n]);
//scanf("%d,%d,%d",&Max[m][0],&Max[m][1],&Max[m][2]);
}
for(k=0;k<3;k++)
{
if(Max[k][0]>=max_Available[0]||Max[k][1]>=max_Available[1]||Max[k][2]>=max_Available[2])
{
printf("error:进程对资源的最大需求数目超过了可用资源数目的最大数目!!\n");
return 0;
}
}
printf("请依次输入3类资源的已分配资源数目(中间以空格隔开)：\n");
for(x=0;x<3;x++)
for(y=0;y<3;y++)
scanf("%d",&Allocation[x][y]);
for(;g<3;g++)
Available[g]=max_Available[g]-Allocation[0][g]-Allocation[1][g]-Allocation[2][g];
printf("当前可利用资源的数目分别为：\n");
for(g=0;g<3;g++)
printf("%d\t",Available[g]);
printf("\n");
for( v=0;v<N;v++)
{
for(w=0;w<M;w++)
Need[v][w]=Max[v][w]-Allocation[v][w];
}
printf("3个进程对3类资源的还需求数目如下：\n");
for(b=0;b<3;b++)
{
for(c=0;c<3;c++)
{
printf("%d\t", Need[b][c]);
a+=1;
}
if(a==3) //控制换行
{
a=0;
printf("\n");
}
}
{
/* 1、初始化*/
int k; //用在判断进程对资源的最大需求数目超过了当前可用资源数目处
int m,n; //用在3个进程的对3类资源的各自最大需求资源数目处
int x,y; //用在3类资源的已分配资源数目处
int v,w; //用在3个进程对3类资源的还需求数目处
int a=0;
int b,c;
int max_Available[3]={0,0,0};//未初始化的可利用最大资源数目
int g=0; //用作循环以确定当前的可利用资源
printf("请依次输入3类资源的可用资源数目的最大值(中间以空格隔开)：\n");
scanf("%d%d%d",&max_Available[0],&max_Available[1],&max_Available[2]);
printf("请依次输入3个进程的对3类资源的各自最大需求资源数目(中间以空格隔开)：\n");
for(m=0;m<3;m++){
for(n=0;n<3;n++)
scanf("%d",&Max[m][n]);
//scanf("%d,%d,%d",&Max[m][0],&Max[m][1],&Max[m][2]);
}
for(k=0;k<3;k++)
{
if(Max[k][0]>=max_Available[0]||Max[k][1]>=max_Available[1]||Max[k][2]>=max_Available[2])
{
printf("error:进程对资源的最大需求数目超过了可用资源数目的最大数目!!\n");
return 0;
}
}
printf("请依次输入3类资源的已分配资源数目(中间以空格隔开)：\n");
for(x=0;x<3;x++)
for(y=0;y<3;y++)
scanf("%d",&Allocation[x][y]);
for(;g<3;g++)
Available[g]=max_Available[g]-Allocation[0][g]-Allocation[1][g]-Allocation[2][g];
printf("当前可利用资源的数目分别为：\n");
for(g=0;g<3;g++)
printf("%d\t",Available[g]);
printf("\n");
for( v=0;v<N;v++)
{
for(w=0;w<M;w++)
Need[v][w]=Max[v][w]-Allocation[v][w];
}
printf("3个进程对3类资源的还需求数目如下：\n");
for(b=0;b<3;b++)
{
for(c=0;c<3;c++)
{
printf("%d\t", Need[b][c]);
a+=1;
}
if(a==3) //控制换行
{
a=0;
printf("\n");
}
}
/* 2、安全性检查*/
bool secure=bankSecurable(Allocation,Available);
bool secure=bankSecurable(Allocation,Available);
/* 3、结果输出*/
if(secure)printf("the sequence is securable...\n");
else printf("the sequence is not securable!!!\n");
if(secure)printf("the sequence is securable...\n");
else printf("the sequence is not securable!!!\n");
return 0;
}
}
相关知识点：
(1) 算法中的数据结构
可利用资源向量 Available：
这是一个含有 m 个元素的一维数组，其中的每一个数组元素代表
系统中某一类资源当前的空闲数目。其初始值是系统中所配置的该类
(惠州学院 刘宇芳 2016)
全部(最多)可用资源的数目； 其数值随该类资源的分配和回收而动态地
改变。如 Available[j] = K，则表示系统中目前 j 类资源空闲 K 个。
系统中某一类资源当前的空闲数目。其初始值是系统中所配置的该类
(惠州学院 刘宇芳 2016)
全部(最多)可用资源的数目； 其数值随该类资源的分配和回收而动态地
改变。如 Available[j] = K，则表示系统中目前 j 类资源空闲 K 个。
最大需求矩阵 Max：
矩阵的每一行是一个进程的最大需求向量。第 i 行的第 j 个元素代
表进程 i 生命周期中需要 j 类资源的最大数量；例如：Max[i，j] = K，
则表示进程 i 需要 j 类资源的最大数目为 K。
由系统中目前并发执行的 n 个进程的最大需求向量组成 Max，这
是一个 n×m 的矩阵。 它定义了系统中 n 个进程中的每一个进程对系统
的 m 类资源的最大需求。
表进程 i 生命周期中需要 j 类资源的最大数量；例如：Max[i，j] = K，
则表示进程 i 需要 j 类资源的最大数目为 K。
由系统中目前并发执行的 n 个进程的最大需求向量组成 Max，这
是一个 n×m 的矩阵。 它定义了系统中 n 个进程中的每一个进程对系统
的 m 类资源的最大需求。
已分配矩阵 Allocation：
矩阵的每一行是一个进程的已分配资源向量，第 i 行的第 j 个元素
代表目前系统已经给 i 进程分配 j 类资源的数量； 如果 Allocation[i， j] =
K，则表示进程 i 当前已获得 j 类资源的数目为 K。
由系统中目前并发执行的 n 个进程的已分配资源向量组成
Allocation，这也是一个 n×m 的矩阵。它定义了系统中每一类资源当
前已分配给每一进程的资源数。
代表目前系统已经给 i 进程分配 j 类资源的数量； 如果 Allocation[i， j] =
K，则表示进程 i 当前已获得 j 类资源的数目为 K。
由系统中目前并发执行的 n 个进程的已分配资源向量组成
Allocation，这也是一个 n×m 的矩阵。它定义了系统中每一类资源当
前已分配给每一进程的资源数。
需求矩阵 Need：
矩阵的每一行是一个进程的还需要资源向量， 它的第 j 个元素代表
该进程 i 继续运行至完成还需要 j 类资源的数量；如果 Need[i，j]=K，
则表示进程 i 还需要 j 类资源 K 个，方能完成其任务。
这也是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源
数。上述三个矩阵存在如下关系：
(惠州学院 刘宇芳 2016)
Need[i，j]= Max[i，j] –Allocation[i，j]
以上四个数据结构描述了系统当前资源分配的一个状态。
该进程 i 继续运行至完成还需要 j 类资源的数量；如果 Need[i，j]=K，
则表示进程 i 还需要 j 类资源 K 个，方能完成其任务。
这也是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源
数。上述三个矩阵存在如下关系：
(惠州学院 刘宇芳 2016)
Need[i，j]= Max[i，j] –Allocation[i，j]
以上四个数据结构描述了系统当前资源分配的一个状态。
安全性检查算法----通过找一个安全序列，判断系统目前是否安全：
步骤 1：另设置两个向量，并给它们赋初值：
1 工作向量 Work，它是一个含有 m 个分量的一维数组，它表示系统
目前可提供给进程继续运行使用的各类资源(空闲的)数目， 在开始执行
安全性检查算法时，赋初值 Work：=Available；
2 完成向量 Finish，它是一个含有 n 个分量的一维逻辑型数组，它表
示系统目前是否有足够的资源分配给系统目前的 n 个进程，使之运行
直到完成。 当系统目前有足够资源分配给进程 i 时， 令 Finish[i]： =true；
算法开始时先给 Finish 赋初值，对每个进程 i，Finish[i]：=false；
目前可提供给进程继续运行使用的各类资源(空闲的)数目， 在开始执行
安全性检查算法时，赋初值 Work：=Available；
2 完成向量 Finish，它是一个含有 n 个分量的一维逻辑型数组，它表
示系统目前是否有足够的资源分配给系统目前的 n 个进程，使之运行
直到完成。 当系统目前有足够资源分配给进程 i 时， 令 Finish[i]： =true；
算法开始时先给 Finish 赋初值，对每个进程 i，Finish[i]：=false；
步骤 2：从进程集合中找一个同时能满足下述两条件的进程 i：
① 进程 i 的 Finish[i] = false；
② 进程 i 的每个 Need[i，j] ≤ Work[j]；
若能找到，执行步骤(3)；否则，执行步骤(4)；
② 进程 i 的每个 Need[i，j] ≤ Work[j]；
若能找到，执行步骤(3)；否则，执行步骤(4)；
步骤 3：由于当进程 i 获得资源后，可顺利执行，直至完成；完成后可
（惠州学院 刘宇芳 2016）
释放出分配给它的资源，故可以执行：
① Finish［i］ ：= true；/*将进程 i 放入推进序列*/
② 每个 Work［j］ ：=Allocation［i，j］+ Work［j］ ；/*回收进程 i 的全
部资源*/
③ go to 步骤 2；
释放出分配给它的资源，故可以执行：
① Finish［i］ ：= true；/*将进程 i 放入推进序列*/
② 每个 Work［j］ ：=Allocation［i，j］+ Work［j］ ；/*回收进程 i 的全
部资源*/
③ go to 步骤 2；
步骤 4：
经过逐一计算，如果所有进程都满足：Finish[i] = true，进入了进
程推进序列，这个序列就是安全序列，这表示系统目前处于安全状态；
否则， 说明有若干个进程无法进入推进序列， 系统处于不安全状态。 (经
过逐一计算后，如果是由于不满足步骤 2 的条件①而结束循环，则找
到了一个安全序列；如果是由于不满足步骤 2 的条件②而结束循环，
则没有找到安全序列；)
程推进序列，这个序列就是安全序列，这表示系统目前处于安全状态；
否则， 说明有若干个进程无法进入推进序列， 系统处于不安全状态。 (经
过逐一计算后，如果是由于不满足步骤 2 的条件①而结束循环，则找
到了一个安全序列；如果是由于不满足步骤 2 的条件②而结束循环，
则没有找到安全序列；)