您现在的位置是：首页 > 诗句大全

银行家算法（C++实现）

作者：利杜鹃时间：2024-05-14 16:45:22分类：诗句大全

简介　　文章浏览阅读2w次，点赞53次，收藏522次。操作系统实验内容，银行家算法的实现，基于C++语言_银行家算法c++

点击全文阅读

目录

一、银行家算法概述

二、银行家算法需要的数组结构

三、算法概述

1.安全性算法

2.银行家算法

四、代码实现

五、实验结果验证

一、银行家算法概述

银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

二、银行家算法需要的数组结构

1）可利用资源向量Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j] = K，则表示系统中现有Rj类资源K个。

2）最大需求矩阵Max：这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj类资源的最大数目为K。

3）分配矩阵Allocation：这也是一个n*m的矩阵，它定义了系统中的每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j] = K，则表示进程i当前已分得Rj类资源的数目为K。

4）需求矩阵Need：这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。

其中三个矩阵间存在下述关系：

Need[i,j] = Max[i,j] - allocation[i,j]

三、算法概述

1.安全性算法

系统所执行的安全性算法可描述如下：

（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［i］+Allocation［i,j］;
        Finish［i］=true;
        go to step 2;

（4）如果所有进程的Finish[i]=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

2.银行家算法

设Requesti是进程Pi的请求向量，如果Requset_i[j]表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

%20

(1)%20如果 ≤%20Need[i,j]，转向步骤(2)，否则认为出错，因为它所需的资源数目已超过它所宣布的最大值。

%20

(2)%20若%20 ≤%20Available[j]，转向步骤(3)，否则表示尚无足够资源，Pi必须等待。

%20

(3)%20系统尝试把资源分配给进程Pi，并修改下面数据结构中的数值：
%20Available[j]%20=%20Available[j]%20– 
%20Allocation[i,j]%20=%20Allocation[i,j]%20+ 
%20Need[i,j]%20=%20Need[i,j]%20– 

%20

(4)%20系统执行安全性算法，检查此次分配后系统是否处于安全状态。若安全，才正式分配给Pi，完成此次分配；否则，此次试分配作废，恢复原来资源的分配状态，进程Pi等待。

%20四、代码实现%20
#include<iostream>using%20namespace%20std;const%20int%20p=5;//进程数const%20int%20r=4;//资源种类int%20num%20=%201;//需要分配资源的进程序号void%20init_request(int%20request[r]){%20%20%20%20//初始化request矩阵%20%20%20%20cout<<"Input%20the%20number%20of%20request:"<<endl;%20%20%20%20cin>>num;%20%20%20%20num-=1;//下标减1%20%20%20%20cout<<"Input%20the%20request%20vector:"<<endl;%20%20%20%20for(int%20i=0;i<r;i++)%20%20%20%20%20%20%20%20cin>>request[i];}void%20init_matrix(int%20maximum[p][r],int%20allocation[p][r],int%20need[p][r],int%20available[r],int%20request[r]){%20%20%20%20//初始化函数%20%20%20%20cout<<"Input%20the%20Allocation%20matrix:"<<endl;%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20cin>>allocation[i][j];%20%20%20%20cout<<"Input%20the%20Need%20matrix:"<<endl;%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20cin>>need[i][j];%20%20%20%20//cout<<"Input%20the%20Max%20matrix:"<<endl;%20%20%20%20//Max矩阵可以由Need和Allocation矩阵推导得出%20%20%20%20//Max[i,j]=%20Need[i,j]+Allocation[i,j]%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20maximum[i][j]=need[i][j]+allocation[i][j];%20%20%20%20cout<<"Input%20the%20available%20vector:"<<endl;%20%20%20%20for(int%20i=0;i<r;i++)%20%20%20%20%20%20%20%20cin>>available[i];}void%20output_func(int%20allocation[p][r],int%20need[p][r],int%20available[r]){%20%20%20%20//输出函数%20%20%20%20cout<<endl<<"%20%20%20%20%20"<<"Allocation"<<"%20%20%20%20%20Need"<<"%20%20%20%20%20%20%20%20Available"<<endl;%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20{%20%20%20%20%20%20%20%20cout<<"P"<<i+1<<"%20%20%20:";%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20cout<<allocation[i][j]<<'%20';%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20cout<<"%20%20%20%20%20";%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20cout<<need[i][j]<<'%20';%20%20%20%20%20%20%20%20if(i==0)%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20cout<<"%20%20%20%20%20";%20%20%20%20%20%20%20%20%20%20%20%20for(int%20k=0;k<r;k++)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout<<available[k]<<'%20';%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20cout<<endl;%20%20%20%20}%20%20%20%20cout<<endl;}bool%20compare(int%20need[],int%20work[]){%20%20%20%20bool%20flg%20=%201;%20%20%20%20for(int%20i=0;i<r;i++)%20%20%20%20{%20%20%20%20%20%20%20%20//检查是否有大于的情况存在%20%20%20%20%20%20%20%20if(need[i]>work[i])%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20flg=0;%20%20%20%20%20%20%20%20%20%20%20%20break;%20%20%20%20%20%20%20%20}%20%20%20%20}%20%20%20%20return%20flg;}int%20check_security(int%20allocation[p][r],int%20need[p][r],int%20available[r]){%20%20%20%20//安全性检查函数%20%20%20%20int%20finish[p]%20=%20{0};//初始化finish向量%20%20%20%20int%20work[r];%20%20//拷贝available%20%20%20%20int%20lis[p];//用来记录安全时的队列%20%20%20%20int%20cnt=0;%20%20%20%20for(int%20i=0;i<r;i++)%20%20%20%20%20%20%20%20work[i]%20=%20available[i];//初始化work向量%20%20%20%20//序列分配%20%20%20%20//循环p次%20%20%20%20for(int%20m=0;m<p;m++)%20%20%20%20{%20%20%20%20%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20//如果当前进程执行完成，跳过%20%20%20%20%20%20%20%20%20%20%20%20if(finish[i]%20==%201)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue;%20%20%20%20%20%20%20%20%20%20%20%20//找到finish[i]%20=%20false%20%20%20%20%20%20%20%20%20%20%20%20else{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20//如果Need[i,j]<=Work[j]%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(compare(need[i],work))%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20work[j]+=allocation[i][j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20finish[i]%20=%201;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lis[cnt++]%20=%20i+1;//将该状态放入安全状态队列中%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20}%20%20%20%20}%20%20%20%20int%20flag=1;%20%20%20%20for(int%20i=0;i<r;i++)%20%20%20%20{%20%20%20%20%20%20%20%20if(finish[i]==0)%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20flag%20=%200;%20%20%20%20%20%20%20%20%20%20%20%20break;%20//如果存在F的进程，表明系统处于不安全状态%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20else%20%20%20%20%20%20%20%20%20%20%20%20continue;%20%20%20%20}%20%20%20%20if(flag)%20%20%20%20{%20%20%20%20%20%20%20%20%20cout<<"系统处于安全状态！"<<endl;%20%20%20%20%20%20%20%20%20cout<<"安全序列为:";%20%20%20%20%20%20%20%20%20for(int%20i=0;i<p;i++)%20%20%20%20%20%20%20%20%20%20%20%20cout<<lis[i]<<'%20';%20%20%20%20%20%20%20%20%20cout<<endl;%20%20%20%20}%20%20%20%20else%20cout<<"系统处于不安全状态！"<<endl;%20%20%20%20return%20flag;}void%20banker(int%20allocation[p][r],int%20need[p][r],int%20available[r],int%20request[r],int%20n){%20%20%20%20if(!compare(request,need[n]))%20%20%20%20{%20%20%20%20%20%20%20%20//如果存在Requesti[j]>Need[i][j],认为出错%20%20%20%20%20%20%20%20cout<<"出错！所需资源已超过所宣布的最大值！"<<endl;%20%20%20%20%20%20%20%20return%20;%20%20%20%20}%20%20%20%20else{%20%20%20%20%20%20%20%20//银行家算法(1)没有出错%20%20%20%20%20%20%20%20if(!compare(request,available))%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20//如果存在Requesti[j]>Available[j]，认为出错%20%20%20%20%20%20%20%20%20%20%20%20cout<<"尚无足够资源，必须等待！"<<endl;%20%20%20%20%20%20%20%20%20%20%20%20return%20;%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20else{%20%20%20%20%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20available[j]-=request[j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20allocation[n][j]+=request[j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20need[n][j]-=request[j];%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20%20%20%20%20if(check_security(allocation,need,available))%20%20%20%20%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout<<"安全！将资源正式分配"<<endl;%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20%20%20%20%20else%20%20%20%20%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout<<"不安全！资源分配作废！恢复以前状态"<<endl;%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for(int%20j=0;j<r;j++)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20{%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20need[n][j]+=request[j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20allocation[n][j]-=request[j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20available[j]+=request[j];%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20}%20%20%20%20}%20%20%20%20output_func(allocation,need,available);}int%20main(){%20%20%20%20int%20maximum[p][r],allocation[p][r],need[p][r];%20%20%20%20int%20available[r],request[r];%20%20%20%20init_matrix(maximum,allocation,need,available,request);%20%20%20%20cout<<endl<<"检查T0时刻系统是否处于安全状态..."<<endl;%20%20%20%20check_security(allocation,need,available);%20%20%20%20int%20flag%20=%201;%20%20%20%20while(flag)%20%20%20%20{%20%20%20%20%20%20%20%20cout<<endl<<"对请求资源进行银行家算法检查..."<<endl;%20%20%20%20%20%20%20%20init_request(request);//初始化request矩阵%20%20%20%20%20%20%20%20banker(allocation,need,available,request,num);%20%20%20%20%20%20%20%20cout<<"是否继续输入？(输入0退出):";%20%20%20%20%20%20%20%20cin>>flag;%20%20%20%20}%20%20%20%20return%200;}/*测试数据0%200%203%2021%200%200%2001%203%205%2040%203%203%2020%200%201%2040%200%201%2021%207%205%2002%203%205%2060%206%205%2021%206%205%2061%206%202%202*/
%20五、实验结果验证%20

1.能安全分配的情况

%20
 

 

2.分配不安全情况（注意一定要恢复原来的状态）

 3.需要的资源超过自己需要的最大值

 4.尚无足够资源，需等待分配

 

点击全文阅读

郑重声明：

本站所有活动均为互联网所得，如有侵权请联系本站删除处理

上一篇：Linux 系统中安装并设置Kubectl

下一篇：返回列表

随便看看

我来说两句

本栏最新

本栏热门

全站热门

Copyright 2018 Inc. AllRights Reserved. Design by 一句子网 豫ICP备2022018965号-7

一句子 www.hlwxy.com