银行家算法+银行家算法流程图+具体代码【转】

计算机操作系统>一书中详细有解.

1. 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.
所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j<i)所占的资源之和.
2.不安全状态可能产生死锁.
目前状态 最大需求 尚需
P1 3 9 6
P2 5 10 5
P3 2 4 2

在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.
3.银行家算法的思路:
1),进程一开始向系统提出最大需求量.
2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.
4.银行家算法的数据结构.
1),系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.
2),各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i
类资源最大需求.
3),已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.
4),剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.
5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1),判定E[n]是否大于D[j][n],若大于,表示出错.
2),判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.
3),若以上两步没有问题,尝试分配,即各变量作调整.
4),按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.
6."安全性检测"算法
1),先定义两个变量,用来表示推算过程的数据.
F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.
J[n]=False表示推算过程中各进程是否假设"已完成"
2),流程:
在"剩余"的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]<=F[n]的进程,找到后令J[j]=True
(假设该进程完成),F[n]+D[j][n](该进程所占资源释放),如此循环执行.
若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.
算法的实现

一、初始化

由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。

 

二、银行家算法

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。

(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。

(3)系统试探分配资源，修改相关数据：

         AVAILABLE[i]-=REQUEST[cusneed][i];

         ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

         NEED[cusneed][i]-=REQUEST[cusneed][i];

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

 

三、安全性检查算法

(1)设置两个工作向量Work=AVAILABLE;FINISH

(2)从进程集合中找到一个满足下述条件的进程，

FINISH==false;

NEED<=Work;

如找到，执行(3)；否则，执行(4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work+=ALLOCATION;

Finish=true;

GOTO 2

(4)如所有的进程Finish= true，则表示安全；否则系统不安全。

 

初始化算法流程图：

 

银行家算法流程图：

 

 

 

 

安全性算法流程图：

 

 

源程序清单

 

#include <iostream>
using namespace std;
#define MAXPROCESS 50                        /*最大进程数*/
#define MAXRESOURCE 100                        /*最大资源数*/
int AVAILABLE[MAXRESOURCE];                    /*可用资源数组*/
int MAX[MAXPROCESS][MAXRESOURCE];            /*最大需求矩阵*/
int ALLOCATION[MAXPROCESS][MAXRESOURCE];    /*分配矩阵*/
int NEED[MAXPROCESS][MAXRESOURCE];            /*需求矩阵*/
int REQUEST[MAXPROCESS][MAXRESOURCE];        /*进程需要资源数*/
bool FINISH[MAXPROCESS];                        /*系统是否有足够的资源分配*/
int p[MAXPROCESS];                             /*记录序列*/
int m,n;                                    /*m个进程,n个资源*/

void Init();
bool Safe();
void Bank();
int main()
{
    Init();
    Safe();
    Bank();
}

void Init()                /*初始化算法*/
{
    int i,j;
    cout<<"请输入进程的数目:";
    cin>>m;
    cout<<"请输入资源的种类:";
    cin>>n;
    cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl;
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
    cin>>MAX[i][j];
    cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>ALLOCATION[i][j];
            NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
            if(NEED[i][j]<0)
            {
                cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl;
                j--;
                continue;
            }
        }
    }
    cout<<"请输入各个资源现有的数目:"<<endl;
    for(i=0;i<n;i++)
    {
        cin>>AVAILABLE[i];
    }
}

void Bank()                /*银行家算法*/
{
    int i,cusneed;
    char again;
    while(1)
    {
        cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;
        cin>>cusneed;
        cout<<"请输入进程所请求的各资源的数量"<<endl;
        for(i=0;i<n;i++)
        {
            cin>>REQUEST[cusneed][i];
        }
        for(i=0;i<n;i++)
        {
            if(REQUEST[cusneed][i]>NEED[cusneed][i])
            {
                cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;
                continue;
            }
            if(REQUEST[cusneed][i]>AVAILABLE[i])
            {
                cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl;
                continue;
            }
        }
        for(i=0;i<n;i++)
        {
            AVAILABLE[i]-=REQUEST[cusneed][i];
            ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
            NEED[cusneed][i]-=REQUEST[cusneed][i];
        }
        if(Safe())
        {
            cout<<"同意分配请求!"<<endl;
        }
        else
        {
            cout<<"您的请求被拒绝!"<<endl;
            for(i=0;i<n;i++)
            {
                AVAILABLE[i]+=REQUEST[cusneed][i];
                ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
                NEED[cusneed][i]+=REQUEST[cusneed][i];
            }
        }
        for(i=0;i<m;i++)
        {
            FINISH[i]=false;
        }
        cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl;
        cin>>again;
        if(again=='y'||again=='Y')
        {
            continue;
        }
        break;
        }
}

bool Safe()                                    /*安全性算法*/
{
    int i,j,k,l=0;
    int Work[MAXRESOURCE];                    /*工作数组*/
    for(i=0;i<n;i++)
    Work[i]=AVAILABLE[i];
    for(i=0;i<m;i++)
    {
        FINISH[i]=false;
    }
    for(i=0;i<m;i++)
    {   
        if(FINISH[i]==true)
        {
            continue;
        }
        else
        {
            for(j=0;j<n;j++)
            {
                if(NEED[i][j]>Work[j])
                {
                    break;
                }
            }
            if(j==n)
            {
                FINISH[i]=true;
                for(k=0;k<n;k++)
                {
                    Work[k]+=ALLOCATION[i][k];
                }
                p[l++]=i;
                i=-1;
            }
            else
            {
                continue;
            }
        }
        if(l==m)
        {
            cout<<"系统是安全的"<<endl;
            cout<<"安全序列:"<<endl;
            for(i=0;i<l;i++)
            {
                cout<<p[i];
                if(i!=l-1)
                {
                    cout<<"-->";
                }
            }
            cout<<""<<endl;
            return true;
        }
    }
    cout<<"系统是不安全的"<<endl;
    return false;