文章目录
1。银行家算法是什么?
银行家算法是操作系统的经典算法之一,用于避免死锁情况。
最初是为了让银行(因此得名)决定借钱是否安全,然后决定是否放贷。
在银行,客户申请的贷款数量是有限的。每位客户在首次申请贷款时必须申报完成项目所需的最高资金金额。当满足所有贷款要求后,客户应及时归还。只要申请的贷款数量不超过其拥有的最大限额,银行家就应该尽力满足客户的需求。
用在操作系统中时,银行家、借贷资金、客户分别对应操作系统、资源、申请资源的流程。
每个新进程进入系统时,必须声明其所需资源的最大数量,且其数量不能超过系统拥有的资源总量。当一个进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。如果是,它会进一步计算将这些资源分配给进程是否会使系统处于不安全状态。如果没有,那么就会给它分配资源,否则就让进程等待。
2.银行家算法中的数据结构
为了实现银行家算法,系统中必须建立以下四种数据结构:
1)可用向量:系统中可用资源的数量
2) 最大矩阵:每个进程对每种资源的最大需求
3)分配矩阵:分配给每个进程的各种资源数量
4)需求矩阵:每个进程还需要的各种资源数量
三个矩阵之间有如下关系:
需要[i,j] = 最大[i,j] – 分配[i, j]
算法逻辑:
令Requesti为进程Pi的请求向量。如果Requesti[j]=K,则表示进程Pi需要K个类型为Rj的资源。当Pi发出资源请求时,系统按照以下步骤进行检查:
(1) 如果Requesti[j] ≤ Need[i,j],则转向(2),否则认为错误(因为它需要的资源数量已经超过了它公布的最大值)。
(2) 如果Requesti[j]≤Available[j],则转(3),否则必须等待(表现为进程Pi被阻塞)。
(3)系统尝试分配资源来处理Pi并修改以下数据结构中的值:
Available[j]=Available[j] – Requesti[j]
Allocation[i ,j] = 分配[i,j] + 请求i[j]
需要[i,j] = 需要[i,j] –请求i[j]
(4) 试分配后,执行安全算法,检查本次分配后系统是否处于安全状态。如果安全,则正式分配;否则,试分配无效,进程Pi将等待。
3。流程图
4。代码实现
#包括
#包括
#define PN 5//进程数
#define RN 4//资源类型个数
typedef struct//定义结构体类型pcb
{
char name[3];//进程名,如p0
int max[RN];//最大资源值
int Allocation[RN];//分配的资源数量
int need[RN];//所需资源数量
}印刷电路板;
struct//定义为结构体类型,方便赋值
{
int flag[PN];//进程检测标志,1表示通过
int safes[PN];//存储进程号并作为安全序列输出
}fs0,fs;//fs0保存初始值,fs用于工作
struct//定义为结构体类型,方便赋值
{
int available[RN];//系统可用资源向量
}av0,av,avx;//av0保存初始值,av和avx用于工作
pcb proc0[PN],proc[PN];//proc0保存初始值,proc用于工作int request[RN];//处理请求资源向量
void init();//初始化,输入数据
void output(pcb*);//输出数据
void cur_state();//判断系统当前状态
void req_state();//分析进程发出的请求是否可以响应
void back0();//返回初始值
void back1(int);//返回到分配前
int check(int*);//进程需要向量和可用向量的比较
intbanker();//银行家算法
int main()
{
整数;
printf("[银行家算法]\n");
printf("进程数:%d\n",PN);
printf("资源数量:%d\n",RN);
printf("================\n");
在里面();
output(proc0);//输出初始资源分配情况
printf("[当前系统状态分析]\n");
cur_state();
printf("================================================== =======\n\n");
printf("选择操作顺序号(0:结束程序;1:资源请求分析)\n");
printf("请输入序列号:");
scanf("%d",#);getchar();
同时(1)
{
开关(编号)
{
case 1:printf("\n[进程资源请求分析]\n");req_state();break;
默认值:printf("\n======分析结束!======\n");return 0;
}
printf("\n");
printf("================================================== =======\n");
printf("\n");printf("选择操作顺序号(0:结束程序;1:资源请求分析)\n");
printf("请输入序列号:");
scanf("%d",#);getchar();
}
}
无效初始化()
{//初始化
整数 i,j;
for(i=0;i
printf("\n请输入进程名称:");
获取(proc0[i].name);
printf("输入最大值:");
for(j=0;j//输出资源分配情况。如果觉得麻烦的话可以忽略。
整数 i,j;
printf("\n");printf("================================================== ===================================\n");
printf("标志位|进程名称|最大值\t|已分配\t|所需值\t|可用数量\n");
printf("------------------------------------------------------------ --- --------------------------------\n");
for(i=0;i
printf(" %-5d",fs.flag[i]);
printf("|");
printf(" %-5s",p[i].name);
printf(“|”);
for(j=0;j//银行家算法
int i,j,t=0,k,f;k=0;//计数器,查找满足条件的进程数
f=1;//标志位,每轮搜索标志。当f=0时,本轮没有找到合适的进程,搜索结束
while(f==1&&k
f=0;//本轮搜索标志置0
for(i=0;i//查找满足条件的进程
f=1;//本轮搜索标志置1
fs.flag[i]=1;//设置进程标志为1
for(j=0;j//当前流程需求向量与可用向量的比较
整数我;
for(i=0;iav.available[i])return 0;//如果测试失败,返回0
return 1;//测试通过
}
无效 cur_state()
{//检测系统当前状态
整数我;
如果(银行家())
{
printf("分析结果:当前系统处于安全状态,存在安全序列");
for(i=0;i//进程提出的资源请求,判断分配的可行性
整数 i,j,n;
printf("请输入请求的进程号n:p");
scanf("%d",&n);
printf("输入请求资源向量请求:");
for(i=0;iproc[n].need[i]||请求[i]>av.available[i])
{
printf("分析结果:请求非法,系统不会响应!");
for(j=0;j//尝试分配并修改allocation、need和available的值
av.available[i]-=request[i];
proc[n].need[i]-=request[i];
proc[n].分配[i]+=请求[i];
}
avx=av;//avx保存分配后可用的值
//output(proc);//输出分配后的资源分配状态
if(banker())//调用银行家算法寻找安全序列
{
printf("分析结果:当前系统处于安全状态,存在安全序列");for(i=0;i
printf("分析结果:不存在安全序列,系统无响应,进程被阻塞!\n");
//output(proc);//输出分析完成后的情况(检查标志位和可用状态)
back1(n);//取消分配并返回分配前
printf("解除分配,返回分配前\n");
}
printf("\n\n");
printf("输入“y”返回初始状态,请选择(y/n)\n");
printf("请输入:");
getchar();//吸收上一次输入生成的回车符
if(getchar()=='y')
{
返回0();
printf("返回初始状态\n");
}
}
无效 back0()
{//恢复初始值
整数我;
fs=fs0;
av = av0;
for(i=0;i//撤销分配,返回分配前
整数我;
fs=fs0;
for(i=0;i
av.available[i]=avx.available[i]-request[i];
proc[m].need[i]+=request[i];
proc[m].分配[i]-=请求[i];
}
}