admin 管理员组文章数量: 887021
银行家算法
什么是银行家算法?
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
(1) 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
(2) 最大需求矩阵Max。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
(3) 分配矩阵 Allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。
(4) 需求矩阵Need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
上述三个矩阵间存在下述关系:
Need[i,j] = Max[i,j] - allocation[i, j]
银行家算法详述：
设 Request；是进程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] = Allocation[i,j] + Requesti[j];
Need[i,j] = Need[i,j] - Requesti[j];
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
安全性算法:
系统所执行的安全性算法可描述如下:
(1) 设置两个向量:①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work = Available；② Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] = false；当有足够资源分配给进程时，再令Finish[i] = true。
(2) 从进程集合中找到一个能满足下述条件的进程
① Finish[i] = false;
② Need[i,j] ≤ Work[j];
若找到，执行步骤(3)，否则，执行步骤(4)。
(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
Work[j] = Work[j] + Allocation[i,j];
Finish[i] = true;
go to step 2;(goto语句不推荐使用 _ )
(4)如果所有进程的 Finish[i] =true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
代码运行过程：
1.输入进程数量，生成对应数量的进程，并且进程的Max，Need，Allocation随机分配有值，然后可用资源Available也随机分配有值；
2.运用DFS算法遍历进程，搜索是否能有完成所以进程的序列。有的话输出序列，否则输出不能被完成的进程；
3.模拟系统提出request，输入进程号及对应的需求向量，执行安全性算法，检查需求满足需求后是否能执行完剩下的进程；
4.所有的进程完成后，程序结束。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<vector>
using namespace std;
const int N=1005;
struct process{
int A,B,C;
}Max[N],allocation[N],need[N],available,request,temp;
int processSize,vis[N],flag,num,finishedProcess;
vector<int>safeList,badProcess;
void checkAvailable(process Available){//检查可用资源向量available是否可分配
if(flag) return;
if(safeList.size()==processSize){
flag=1;
return;
}
int fg=0;
for(int i=0;i<processSize;i++){
if(vis[i]==0){
if(Available.A>=need[i].A&&Available.B>=need[i].B&&Available.C>=need[i].C){
fg=1;
vis[i]=1;
safeList.push_back(i);
process temp = (process){
Available.A+allocation[i].A,Available.B+allocation[i].B,Available.C+allocation[i].C
};
checkAvailable(temp);
if(flag) return;
safeList.pop_back();
vis[i]=0;
}
}
}
if(fg==0){
badProcess.clear();
for(int i=0;i<processSize;i++){
if(vis[i]==0){
badProcess.push_back(i);
}
}
}
}
int checkSafe(){//检查资源分配情况并输出
printf("\n可用资源Available(A,B,C)为(%d, %d, %d)\n",available.A,available.B,available.C);
printf("\n检查T%d时刻资源分配情况是否安全:\n...............\n\n",num);
flag=0;
memset(vis,0,sizeof(vis));
safeList.clear();
badProcess.clear();
temp=available;
checkAvailable(available);
if(flag==0){
printf("T%d时刻资源分配 不安全，不能得到充足资源的进程有:{",num);
for(int i=0;i<badProcess.size();i++){
printf("P%d",badProcess[i]);
if(i!=badProcess.size()-1) printf(", ");
else printf("}\n");
}
return 0;
}
printf("T%d时刻资源分配 安全，此时的一个安全序列是:{",num++);
for(int i=0;i<safeList.size();i++){
printf("P%d",safeList[i]);
if(i!=safeList.size()-1) printf(", ");
else printf("}\n");
}
printf("进程\t Work\t\t Need\t\t Allocation\t Work+Allocation\t Finish\n");
for(int i=0;i<safeList.size();i++){
int x = safeList[i];
printf("P%d\t %-2d %-2d %-2d\t %-2d %-2d %-2d\t %-2d %-2d %-2d\t %-2d %-2d %-2d \t\t true\n",safeList[i],temp.A,temp.B,temp.C, need[x].A,need[x].B,need[x].C,
allocation[x].A,allocation[x].B,allocation[x].C, temp.A+allocation[x].A,temp.B+allocation[x].B,temp.C+allocation[x].C
);
temp.A+=allocation[x].A;
temp.B+=allocation[x].B;
temp.C+=allocation[x].C;
}
return 1;
}
void init(){//初始化，输入数据
printf("\n\t\t\t\t模拟银行家算法\n\n");
srand((unsigned)time(NULL));
printf("请输入进程数量：");
scanf("%d",&processSize);
printf("进程\t Max(最大需求)\t Allocation(分配)\t Need(需求)\t\n");
for(int i=0;i<processSize;i++){
allocation[i].A=rand()%20;//随机生成
allocation[i].B=rand()%20;
allocation[i].C=rand()%20;
need[i].A=rand()%20;
need[i].B=rand()%20;
need[i].C=rand()%20;
Max[i].A=allocation[i].A+need[i].A;
Max[i].B=allocation[i].B+need[i].B;
Max[i].C=allocation[i].C+need[i].C;
printf("p%d\t %-2d %-2d %-2d\t %-2d %-2d %-2d\t\t %-2d %-2d %-2d\t\n",i,Max[i].A,Max[i].B,Max[i].C,allocation[i].A,allocation[i].B,allocation[i].C,need[i].A,need[i].B,need[i].C);
}
available.A=rand()%20+rand()%10;//随机生成资源向量available
available.B=rand()%20+rand()%10;
available.C=rand()%20+rand()%10;
}
void putRequest(){//输入请求向量
while(true){
printf("\n\n***模拟系统请求资源***\n");
printf("请输入4个数，分别表示请求资源进程号和进程的三个资源:\n");
int req;
scanf("%d %d %d %d",&req,&request.A,&request.B,&request.C);
if(request.A>need[req].A||request.B>need[req].B||request.C>need[req].C){
printf("请求资源量大于进程最大需求资源量，请重新输入！\n");
}
else if(request.A>available.A||request.B>available.B||request.C>available.C){
printf("请求资源量大于可用进程资源量，请重新输入！\n");
}
else {
available.A-=request.A;
available.B-=request.B;
available.C-=request.C;
need[req].A-=request.A;
need[req].B-=request.B;
need[req].C-=request.C;
allocation[req].A+=request.A;
allocation[req].B+=request.B;
allocation[req].C+=request.C;
printf("\n进程'P%d'的信息为：\n",req);
printf("进程\t Max(最大需求)\t Allocation(分配)\t Need(需求)\t\n");
printf("p%d\t %-2d %-2d %-2d\t %-2d %-2d %-2d\t\t %-2d %-2d %-2d\t\n",req,Max[req].A,Max[req].B,Max[req].C,allocation[req].A,allocation[req].B,allocation[req].C,need[req].A,need[req].B,need[req].C);
if(need[req].A==0&&need[req].B==0&&need[req].C==0){
finishedProcess++;
available.A+=allocation[req].A;
available.B+=allocation[req].B;
available.C+=allocation[req].C;
if(finishedProcess==processSize){
printf("\n所有进程都已分配资源，结束任务！");
return;
}
}
if(checkSafe()==0){
printf("可用资源已不满足任何进程的需求，故系统进入不安全状态，此时系统不分配资源！");
return;
}
}
}
}
int main ()
{
init();
if(!checkSafe()) exit(0);
putRequest();
return 0;
}
版权声明：本文标题：操作系统实验——实现模拟银行家算法（避免死锁） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727376504h1110885.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论