银行家算法

2019年10月29日 0 条评论 334 次阅读 1 人点赞

定义


所谓死锁,是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。

产生死锁的必要条件

1.互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。

2.请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。

3.不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

4.环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

常见死锁相关算法

银行家算法:避免死锁
资源有序分配法:预防死锁
资源分配图化简法:检测死锁
撤销进程法:解决死锁

银行家算法


算法思想

银行家算法:银行家算法是从当前状态出发,按照系统各类资源剩余量逐个检查各进程需要申请的资源量,找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源,假定P1完成工作后归还其占有的所有资源,更新系统剩余资源状态并且移除进程列表中的P1,进而检查下一个能完成工作的客户,......。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。若找不到这样的安全序列,则当前状态不安全。

相关数据结构

  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当前已分得Rj类资源的数目为K。
  4. 需求矩阵Need。这也是一个n*m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成任务。 上述三个矩阵间存在下述关系:Need[i,j]=Max[i,j]-Allocation[i,j]
例子

当前系统状态

从图中数据我们可以利用银行家算法的四个数据结构,来描述当前的系统状态:

因为系统总资源R=(17,5,20),所以可以计算出可利用资源向量Available=R-Allocation(P1,P2,P3,P4,P5)=(2,3,3)

分配资源

根据目前状态,用Available向量每一个进程的Need向量相比,发现Available>=P5.Need,所以可以将目前的资源分配给P5向量(P4也可以,不唯一)。当P5获得所需的所有向量后执行完毕,之后释放其占有的所有资源。此时更新系统资源:

Available=R-Allocation(P1,P2,P3)=(7,4,11)
按照上述同样的方法,P4 也可以安全运行,以及P3,P2,P1也能按顺序运行。因此,在T0时刻,存在安全序列:P5,P4,P3,P2,P1(并不唯一)

死锁的算法实现

#include<stdafx.h>
#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();  
void showdata(int,int);  
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,flag = 0;  
    char again;  
    while(1)  
    {  
        showdata(n,m);////////////////////////////////////////////////////////////////////  
        cout<<endl;  
input:  
        cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;  
        cin>>cusneed;  
        if (cusneed > m)  
        {  
            cout<<"没有该进程,请重新输入"<<endl;  
            goto input;  
        }  
        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])//如果用户选择的线程的第i个资源请求数>该线程该资源所需的数量  
            {  
                cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;  
                goto input;  
            }  
            if(REQUEST[cusneed][i]>AVAILABLE[i])//如果用户选择的线程的第i个资源请求数>系统现有的第i个资源的数量  
            {  
                cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl;  
                goto input;  
            }  
        }  
        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())//AVAILABLE  ALLOCATION  NEED变动之后,是否会导致不安全  
        {  
            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<n;i++)  
        {  
            if (NEED[cusneed][i] <= 0)  
            {  
                flag++;  
            }  
        }  
        if (flag == n)//如果该进程各资源都已满足条件,则释放资源  
        {  
            for (i=0;i<n;i++)  
            {  
                AVAILABLE[i] += ALLOCATION[cusneed][i];  
                ALLOCATION[cusneed][i] = 0;  
                NEED[cusneed][i] = 0;  
            }  
            cout<<"线程"<<cusneed<<" 占有的资源被释放!"<<endl;  
            flag = 0;  
        }  
        for(i=0;i<m;i++)//分配好了以后将进程的标识FINISH改成false  
        {  
            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;//FINISH记录每个进程是否安全  
    }  
    for(i=0;i<m;i++)  
    {     
        for(j=0;j<n;j++)//循环查找第i个进程需要的各个资源数 是否 超过系统现有的对应的资源数  
        {  
            if(NEED[i][j]>Work[j])//第i个进程需要的第j个资源数 > 系统现有的第j个资源数  
            {  
                break;  
            }  
        }  
        if(j==n)//如果第i个进程所需的各个资源数都没有超过系统现有的对应资源数  
        {   
            FINISH[i]=true;//给该进程的FINISH标记为true  
            for(k=0;k<n;k++)  
            {  
                Work[k]+=ALLOCATION[i][k];//将Work赋值为 第i个进程各个已分配资源数+系统现有的对应资源数(因为当改进程全部资源数都满足时线程结束并将资源返还给系统)  
            }  
            p[l++]=i;//记录进程号  
        }  
        else//如果超过继续循环下一个进程  
        {  
            continue;   
        }  
        if(l==m)//当所有进程都能够被满足运行时  
        {  
            cout<<"系统是安全的"<<endl;  
            cout<<"安全序列:"<<endl;  
            for(i=0;i<l;i++)//改了146行的i值,显示资源分配给进程的顺序  
            {  
                cout<<p[i];  
                if(i!=l-1)  
                {  
                    cout<<"-->";  
                }  
            }  
            cout<<""<<endl;           
            return true;  
        }  
    }//for循环  
    cout<<"系统是不安全的"<<endl;  
    return false;  
}  
  
void showdata(int n,int m)   //显示  
{  
    int i,j;  
    cout<<endl;    
    cout<<"-------------------------------------------------------------"<<endl;    
    cout<<"系统可用的资源数为:    ";  
    for   (j=0;j<n;j++)         
        cout<<"    "<<AVAILABLE[j];        
    cout<<endl;     
    cout<<"各进程还需要的资源量:"<<endl;   
    for   (i=0;i<m;i++)     
    {  
        cout<<"    进程"<<i<<":";     
  
        for   (j=0;j<n;j++)  
            cout<<"     "<<NEED[i][j];     
        cout<<endl;     
    }     
  
    cout<<endl;     
    cout<<"各进程已经得到的资源量:    "<<endl<<endl;     
  
    for   (i=0;i<m;i++)     
    {  
        cout<<"    进程"<<i<<":";     
  
        for   (j=0;j<n;j++)  
            cout<<"     "<<ALLOCATION[i][j];  
        cout<<endl;     
    }    
    cout<<endl;   
}   
chao

chao

这个人太懒什么东西都没留下

文章评论(0)

你必须 登录 才能发表评论