> 文档中心 > 操作系统 实验 银行家算法C++

操作系统 实验 银行家算法C++


操作系统 银行家算法

以下算法介绍为书本P100页内容

1.银行家算法中的数据结构

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

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

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

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

上述三个矩阵间存在下述关系:need[i, j]=max[i, j]-allocation[i,j]

2. 银行家算法

设request i是进程Pi的请求向量,如果request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:

(1) 如果requesti[j]>=need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果requesti[j]≤available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。

(3) 系统试探着把资源分配给进程P i,并修改下面数据结构中的数值:

available[j]:= available[j]-request i[j];allocation[i,j]:= allocation[i,j]+request i[j];need[i,j]:= need[i,j]-request i[j];

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

3.安全性算法

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

(1) 设置两个向量:

① 工作向量work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有n个元素,在执行安全算法开始时,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);

(4) 如果所有进程的finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

实验内容

操作系统 实验 银行家算法C++

代码实现

#includeusing namespace std;const int N=1010;int Allocation[5][4]={3,0,1,1,0,1,0,0,1,1,1,0,1,1,0,1,0,0,0,0};//初始化矩阵,题目给的数据int Max[5][4]={4,1,1,1,0,2,1,2,4,2,1,0,1,1,1,1,2,1,1,0};//最大需求矩阵int Need[5][4];//需求矩阵,需要根据最大需求和分配矩阵自己计算int Available[]={6,3,4,2};//可利用资源char name[]={'A','B','C','D','E'};//进程名字int Work[N];bool Finish[N],request[50][50];int n=5,m=4;int p[N];//存安全序列bool bank_safe(){//安全性算法    int len=0;    for(int i=0;i<m;i++) {//最开始的时候 Work=Available Work[i]=Available[i];    }    for(int i=0;i<n;i++) Finish[i]=false;    for(int i=0;i<n;i++){ if(Finish[i]) continue;//先判断前两步 else{     int j=0;     for(j=0;j<m;j++){  if(Need[i][j]>Work[j]) break;     }     if (j==m){  Finish[i] = true;  for (int k = 0; k < m; k++)      Work[k] += Allocation[i][k];  p[len++] = i;//记录进程号  i = -1;     }     else continue; }    }    if(len==n) {//存在长度为n的安全序列,说明系统的是安全的。 cout<<"系统是安全的"<<endl; cout<<"存在安全序列为"<<endl; for(int i=0;i<len;i++){     cout<<p[i]<<" "; } cout<<endl; return true;    }    return false;}void banker(){//银行家算法    // 判断请求向量是否合理 cout << "请输入要申请的进程号"<<endl;    char c;    cin >> c;    int cusneed=c-'A';    if (cusneed > m)    { cout << "没有该进程,请重新输入"<<endl;    }    cout << "请输入进程所请求的各资源数" << endl;    for (int i = 0; i < m; i++) cin >> request[cusneed][i];    for (int i = 0; i < m; i++){ if (request[cusneed][i] > Need[cusneed][i]){     cout << "你输入的资源请求数超过进程数需求量!请重新输入"<<endl;     continue; } if (request[cusneed][i] > Available[i]){     cout << "你输入的资源请求数超过系统当前资源拥有数!" << endl;     break; }    }    //系统假定先给进程分配资源,然后判断系统是否安全。    for (int i = 0; i < m; i++){ Available[i] -= request[cusneed][i];//可用资源减去成功申请的 Allocation[cusneed][i] += request[cusneed][i];//已分配资源加上成功申请的 Need[cusneed][i] -= request[cusneed][i];//进程还需要的减去成功申请的}    if(bank_safe()){ cout<<"分配后,系统安全,可以分配"<<endl;    }    else{ cout << "你的请求被拒绝! !!"<<endl; //把刚刚进行的分配进行还原 for (int i = 0; i < m; i++){     Available[i]+= request[cusneed][i];     Allocation[cusneed][i] -= request[cusneed][i];     Need[cusneed][i] += request[cusneed][i]; }    }}void Init1(){//初始化矩阵cout << "请输入进程的数目:";cin >> n; cout << "请输入资源的数目:";cin >> m;cout << "请输入每个进程最多所需的各资源数,按照"<<m<<'X'<<n<<"矩阵格式输入"<<endl;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> Max[i][j]; cout << "请输入每个进程已分配的各资源数,按照" << m << 'X' << n << "矩阵格式输入" << endl;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++){cin >> Allocation[i][j];Need[i][j] = Max[i][j] - Allocation[i][j];//注意这里的need可能小于0;要进行报错并重新输入,可以用continue来跳出当前循环if (Need[i][j] < 0){cout << "你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题!\n请重新输入!";j--;//忽略这个资源数continue;//跳出本次循环}} cout << "请输入各个资源现有的数目"<<endl;for (int i = 0; i < m; i++){cin >> Available[i];}}void Init2(){//采用自带的数据    for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){Need[i][j] = Max[i][j] - Allocation[i][j];//注意这里的need可能小于0;要进行报错并重新输入,可以用continue来跳出当前循环if (Need[i][j] < 0){cout << "你的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题!";j--;//忽略这个资源数continue;//跳出本次循环}}    }}void print(){    cout << endl << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;cout << "系统可用的资源数为 Available:";for (int i = 0; i < m; i++){cout << Available[i] << "";} cout << endl << "各进程还需要的资源量(Need矩阵):" << endl;for (int i = 0; i < n; i++){cout << "进程" << i << ":";for (int j = 0; j < m; j++)cout << "" << Need[i][j];cout << endl;}  cout << endl << "各进程已经得到的资源 (Allocation矩阵):" << endl;for (int i = 0; i < n; i++){cout << "进程" << i << ":";for (int j = 0; j < m; j++){cout << "" << Allocation[i][j];}cout << endl;} cout << endl << endl;}int main(){    cout<<"采用自带数据,还是手动输入数据,输入(0/1),0表示自带数据,1表示手动输入"<<endl;    int op;    cin>>op;    if(op==1) Init1();//采用自己的数据    else Init2();//采用自己输入的数据    print();//展示当前资源情况,分配和需求    bool is_safe=bank_safe();//在银行家算法之前检测系统安全    banker();//如果又多次资源分配请求,可以多次调用银行家算法    }

注:代码有些内容借用了,这篇博客,大部分还是自己写的,详细代码中也加了一些自己对于银行家算法的理解和注释。