首页 > 代码库 > 银行家算法学习笔记

银行家算法学习笔记

     上周操作系统的实验,就是模拟实现银行家算法,首先我们还是应该对银行家算法熟悉一下。

     银行家算法是最具代表性的避免死锁的算法。因为该算法原本是为银行系统设计的,以确保银行在发放现金贷款时,不会发生不满足所有客户需求的情况。在OS中也可它来实现避免死锁。

算法概述:

    为实现银行家算法,每一个进程在进入系统时,它必须申明在运行过程中,可能需要每种资源类型的最大单元数目,其数目不应超过系统所拥有的资源总量,当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。若有,再进一步计算在将这组资源分配给进程后,是否会使系统处于不安全状态。如果不会,才将资源分配给它,否则让进程等待。


系统安全状态的定义
  1.安全状态
  在避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程;否则,令进程等待。
  虽然并非所有的不安全状态都必然会转为死锁状态,但当系统进入不安全状态后,便有可能进而进入死锁状态;反之,只要系统处于安全状态,系统便可避免进入死锁状态。
因此,避免死锁的实质在于:系统在进行资源分配时,如何使系统不进入不安全状态。

利用银行家算法避免死锁
 1.银行家算法中的数据结构
  (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当前已分得R j类资源的数目为K。
    (4) 需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要R j类资源K个,方能完成其任务。

      上述三个矩阵间存在下述关系:
       Need[i, j]=Max[i, j]-Allocation[i, j]
    
       根据上面的描述,我们可以实现:设定其中的数据结构,用C语言描述:
      
typedef struct //按照书本上的描述,3种资源
{
    int A;
    int B;
    int C;
} Resource;
const int m=5; //进程个数
Resource Available;//可利用的资源
Resource Max[m];//最大需求
Resource Allocation[m];//当前已分配的资源
Resource Need[m];//还需要的各种资源
int safeseq[m]; //安全序列

2.银行家算法
  设Request i是进程Pi的请求向量,如果Request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:
  (1) 如果Request i[j]≤Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
  (2) 如果Request i[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等待。 

        根据这里的描述,我们又可以很快的写出银行家算法的构架:
       
bool banker(int process,Resource *res)
{
    if(res->A<=Need[process].A && res->B<=Need[process].B &&res->C<=Need[process].C)//请求向量需要小于need矩阵中的值
    {
        if(res->A<=Available.A && res->B<=Available.B &&res->C<=Available.C)//请求的资源需要小于available矩阵的值
        {
            Probealloc(process,res);//试探分配
            if(security())//安全性判断
            {
                return true;
            }
            else
            {
                printf("分配失败,原因:系统将进入不安全状态,有可能引起死锁。\n");
                rollbock(process,res);//回滚
            }
        }
        else
        {
            printf("安全性检查失败。原因:请求向量大于可利用资源向量。\n");
        }
    }
    else
    {
        printf("安全性检查失败。原因:请求向量大于需求向量。\n");
    }
    return false;
}

涉及到的试探分配和回滚:
void Probealloc(int process,Resource *res)//试探分配
{
    Available.A-=res->A;
    Available.B-=res->B;
    Available.C-=res->C;

    Allocation[process].A+=res->A;
    Allocation[process].B+=res->B;
    Allocation[process].C+=res->C;

    Need[process].A-=res->A;
    Need[process].B-=res->B;
    Need[process].C-=res->C;
}
void rollbock(int process,Resource *res)//若分配失败就进行回滚
{
    Available.A+=res->A;
    Available.B+=res->B;
    Available.C+=res->C;

    Allocation[process].A-=res->A;
    Allocation[process].B-=res->B;
    Allocation[process].C-=res->C;

    Need[process].A+=res->A;
    Need[process].B+=res->B;
    Need[process].C+=res->C;
}

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

  (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[j]+Allocation[i,j];
          Finish[i]:=true;
          go to step (2);

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

         上面的银行家算法构架中就已经包含安全性的判断了,这里直接根据描述给出安全性算法的实现:
         
bool security()//安全性算法
{
    Resource work=Available;
    bool finish[m]= {false,false,false,false,false};
    int i,j=0;
    for(i=0; i<m; i++)
    {
        if(finish[i]==false)
        {
            if(Need[i].A<=work.A&&Need[i].B<=work.B&&Need[i].C<=work.C)//判断是否有足够的资源可以进行分配
            {
                work.A+=Allocation[i].A;
                work.B+=Allocation[i].B;
                work.C+=Allocation[i].C;
                finish[i]=true; //说明可以进行分配
                safeseq[j++]=i;//记录安全序列的位置
                i=-1;
            }
        }
    }
    for(int i=0; i<m; i++) //如果全部分配完全,则为安全状态。
    {
        if(finish[i]==false)
            return false;
    }
    return true;
}


4.银行家算法实例

  假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图示。 (先忽略P1第二行的括号)

 (1) T0时刻的安全性:利用安全性算法对T0时刻的资源分配情况进行分析如下图可知,在T0时刻存在着一个安全序列{P1,P3,P4,P2,P0},故系统是安全的。
(2) ?P1请求资源:P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查:
  ① Request1(1,0,2)≤Need1(1,2,2)
  ② Request1(1,0,2)≤Available1(3,3,2)
  ③ 系统先假定可为P1分配资源,并修改Available,Allocation1和Need1向量,形成的资源变化情况如下图圆括号所示
④ 再利用安全性算法检查此时系统是否安全。如图所示。
  (3) ?P4请求资源:P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查:
  ① Request4(3,3,0)≤Need4(4,3,1);
  ② Request4(3,3,0)≥Available(2,3,0),让P4等待。

  (4) ?P0请求资源:P0发出请求向量Requst0(0,2,0),系统按银行家算法进行检查:
  ① Request0(0,2,0)≤Need0(7,4,3);
  ② Request0(0,2,0)≤Available(2,3,0);
  ③ 系统暂时先假定可为P0分配资源,并修改有关数据,如图所示。
  (5) 进行安全性检查:可用资源Available(2,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。

        根据上面的实例测试编写的银行家算法:
      
      完整程序代码:  http://download.csdn.net/detail/u014253173/8233559
       参考文献    http://blog.csdn.net/cout_sev/article/details/24980627

银行家算法学习笔记