死锁问题的避免——银行家算法

• 银行家算法的数据结构
• 银行家算法
• 安全算法

银行家算法的数据结构

• 可利用资源向量Available
• 最大需求矩阵Max
• 已分配矩阵Allocation
• 仍然需求矩阵Need

银行家算法

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

a) 如果Requesti[j] <=Need[I,j],便转向步骤（b）；否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。

b) 如果Requesi[j] <=Available[j],便转向步骤（c）；否则，表示尚无足够的资源，Pi须等待。

c) 系统试探着把资源分配给进程Pi，并修改下面的数据结构中的数值：

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];

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

安全算法

（1） 设置两个向量：

① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work :=Available。

② Finish，他表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish := 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 step2;

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

#include<bits/stdc++.h>
using namespace std;
#define maxsize 10

char Res[maxsize]={0};                  //资源名
int Available[maxsize]={0};             //可利用资源
int Max[maxsize][maxsize]={0};          //最大需求矩阵
int Allocation[maxsize][maxsize]={0};   //已分配矩阵
int Need[maxsize][maxsize]={0};         //需求矩阵

int Work;                               //资源数

bool Finish[maxsize]={false};           

int main(){
    cout<<"请按顺序输入:资源种类,数目(q to quit)(max<=10)"<<endl;
    char ch;
    int Resnum=0;
    while(cin>>ch&&ch!='q'){
        Res[Resnum]=ch;
        cin>>Available[Resnum++];
    }
    cout<<"当前资源目录："<<endl;
    cout<<"资源类型     资源数目"<<endl;
    for(int i=0;i<Resnum;++i){
        cout<<"   "<<Res[i]<<"            "<<Available[i]<<endl;
        Work+=Available[i];
    }
    int n;
    cout<<"请输入进程个数(max<=10)"<<endl;
    cin>>n;
    for(int i=0;i<n;++i){
        cout<<"请按顺序输入第"<<i+1<<"个进程所需的资源类型、资源数目";
        int ch1;
        int num;
        cin>>ch1>>num;
        Need[i][ch1]=num;
        if(Need[i][ch1]<=Available[ch1-1]){           //Need[i][ch1]表示第i个进程所需ch1资源的个数
            Available[ch1-1]-=Need[i][ch1];
            Finish[i]=true;
        }
    }
    int flag=0;
    for(int i=0;i<n;++i){
        if(!Finish[i])
            flag=1;
    }
    if(flag)
        cout<<"不安全";
    else
        cout<<"安全";


}