银行家算法
相关知识点
死锁概念
多个并发进程,每个进程占有部分资源,又都等待其它进程释放所占资源,造成均不能向前推进的现象。
死锁的避免
死锁避免原理就是使系统始终处于安全状态。
安全状态：所谓安全状态是指能够找到一个安全序列，系统能够按照这个安全序列依次为进程分配资源，使所有进程都能执行完毕，如果找不到这样的安全序列，系统就处于不安全状态。
银行家算法
银行家算法的基本思想是：
始终保持系统处于安全状态，当进程提出资源请求时，系统先进行预分配，再判断系统分配后是否仍然处于安全状态。如果仍然处于安全状态，就进行实际分配；如果处于不安全状态，则撤销预分配、拒绝该进程的资源请求。
算法数据结构
统一的数据结构：
#define False 0
#define True 1
#define N 100 //作业数量，资源数量的最大值均为为100
int Max[N][N]={0};//各进程所需各类资源的最大需求
int Avaliable[N]={0};//系统可用资源向量
char name[N]={0};//资源的名称，可以根据设计定义成一维数组或二维数组
int Allocation[N][N]={0};//各进程已分配资源
int Need[N][N]={0}; //各进程还需要资源
int Request[N]={0}; //进程的请求资源向量
银行家算法
Request[i] 是进程Pi的请求向量，当Pi 发出资源请求后，系统按下述步骤进行检查：
（1）如果Request[i,j] <= Need[i,j],转向步骤（2）；否则认为出错，因为他所需要的资源数已超过它所宣布的最大值。
（2）如果Request[i,j] <= Avaliable[j], 便转向步骤（3）；否则表示尚无足够资源，Pi 须等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的值：
Avaliable[j] = Avaliable[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；Finsh：它表示系统是否有祖国的资源分配给进程，使之运行完成。开始时先做Finsh[i] = false;当有足够资源分配给进程是，再令Finsh[i] = true.
（2）从进程集合中找到一个能满足下述条件的进程：
Finsh[i] = false;
Need[i,j] <= Work[j];
若找到，执行步骤（3），否则，执行步骤（4）。
（3）当进程Pi 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j] = Work[j] + Allocation[i,j];
Finsh[i] = true;
go to step 2;
（4）如果所有进程的Finsh[i] = true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
T0 时刻的资源分配表(各种资源的数量分别为：10、5、7)
资源情况
自行设计各进程的请求向量作为输入数据，至少提出3个请求向量（合法的、不合法的都要有），验证银行家算法。
资源情况
进程 Max Allocation Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
#include<iostream>
#define False 0
#define True 1
#define resourceNum 3
#define progressNum 5
using namespace std;
int Max[progressNum][resourceNum] = {
{
7,5,3},{
3,2,2},{
9,0,2},{
2,2,2},{
4,3,3}};
int Avaliable[resourceNum] = {
3,3,2};
char name[progressNum] = {
0,1,2,3,4};
int Allocation[progressNum][resourceNum] = {
{
0,1,0},{
2,0,0},{
3,0,2},{
2,1,1},{
0,0,2}};
int Need[progressNum][resourceNum] = {
{
7,4,3},{
1,2,2},{
6,0,0},{
0,1,1},{
4,3,1}};
int Request[resourceNum] = {
0};
int temp[progressNum]= {
0}; //记录安全序列
int Work[resourceNum] = {
0,0,0};
int Finsh[progressNum] = {
0};
/* Max Need Allocation Avaliable P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 */
void showInfo(){
cout << "当前系统资源分配需求\t 剩余可分配资源为"<<endl;
for(int i = 0; i < resourceNum; i++) cout << Avaliable[i] << " ";
cout << "\n-------------------------------------------------" << endl;
cout << "name\tMax\tNeed\tAllocation\t" << endl;
for(int i= 0; i < progressNum; i++){
cout << "P" << i << "\t";
for(int j = 0;j < resourceNum; j++) cout << Max[i][j] << " ";
cout << "\t";
for(int j = 0; j < resourceNum; j++) cout << Need[i][j] << " ";
cout <<"\t";
for(int j= 0; j < resourceNum; j++) cout << Allocation[i][j] << " ";
cout << "\n";
}
}
void ShowSafeInfo(int progress){
cout << "P" <<progress << "\t";
for(int j = 0;j < resourceNum; j++) cout << Max[progress][j] << " ";
cout << "\t";
for(int j = 0; j < resourceNum; j++) cout << Need[progress][j] << " ";
cout <<"\t";
for(int j= 0; j < resourceNum; j++) cout << Allocation[progress][j] << " ";
cout << "\t\t";
for(int j = 0; j < resourceNum; j++) cout << Work[j] << " ";
cout << "\n";
}
/*检验当前进程能否分配*/
bool CanAvaliable(int progress,int Avaliable[]){
if(Finsh[progress] == 1) return false;
for(int i = 0; i < resourceNum; i++){
if(Need[progress][i] > Avaliable[i]){
return false;
}
}
return true;
}
//进行银行家算法，进行资源分配
bool isSafe(){
Finsh[progressNum] = {
0};
int progress = 0; //记录操作的进程号
int finshProgress = 0;
int Serise = 0;
int flag = 0;
cout << "Name\tMax\tNeed\tAllocation\tAllocation+Work" << endl;
for(int i = 0; i < resourceNum; i++) Work[i] = Avaliable[i];
while(finshProgress != progressNum){
//如果可以将资源分配给该进程，则更改Work 并将Finsh 的值更改，记录安全序列
if(CanAvaliable(progress,Work)){
for(int i = 0; i < resourceNum; i++) Work[i] += Allocation[progress][i];
ShowSafeInfo(progress);
Finsh[progress] = 1;
temp[Serise++] = progress;
finshProgress++;
}
progress++;
if(progress >= progressNum){
progress = progress % progressNum;
if(flag == finshProgress) break; //检验当全部遍历第二遍之后完成的进程数没有改变，则表示只能进行finshprogress个进程的分配
else flag = finshProgress ;
}
}
for(int i = 0; i < progressNum; i++) {
if(Finsh[i] == 0) {
cout << "当前系统不安全" << endl;
return false;
}
}
return true;
}
int main(){
int p;
int Request[resourceNum] ;
showInfo();
//isSafe();
cout << "\n-------------------------------------------------" << endl;
cout << "请问是那个进程请求分配资源：" ;
cin >> p;
cout << "\n请问三个资源的分别请求的数量为：";
for(int i = 0; i < resourceNum; i++) cin >> Request[i];
//初步判断是否能够分配
for(int i = 0; i < resourceNum; i++){
if(Request[i] > Avaliable[i]) {
cout << "系统处于不安全状态，原因为：空闲资源量小于请求的资源数量" << endl;
break;
}
}
for(int i = 0; i < resourceNum; i++) {
Avaliable[i] = Avaliable[i] - Request[i];
Allocation[p][i] += Request[i];
Need[p][i] = Need[p][i] - Request[i];
}
showInfo();
Finsh[resourceNum] = {
0};
cout << endl;
if(isSafe()){
cout << "\n系统处于安全状态，并且安全序列为：";
for(int i = 0; i < progressNum; i++) cout << temp[i] << " ";
}else{
cout << "系统处于不安全的状态，每一个进程不能都被分配";
}
}
京公网安备 11010502036488号