银行家算法

你的名字 2023-06-10 04:26 104阅读 0赞

### 银行家算法 ###

*   *  问题背景
     *  银行家算法中的数据结构
     *  银行家算法步骤
     *   *  安全状态检查算法
     *  源代码
     *   *  测试
         *   *  输出

## 问题背景 ##

**死锁**：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。  
银行家算法(Banker′s Algorithm) ——避免死锁的算法是Dijkstra在1965年提出的，被称为银行家算法

## 银行家算法中的数据结构 ##

设系统中有n个进程和m类资源，并定义以下数据结构。  
(1) 可利用资源向量Available，如Available\[j\]=k。  
(2) 最大需求距阵Max，如Max\[i,j\]=k。  
(3) 分配矩阵Allocation。如Allocation\[i,j\]=k。  
(4) 需求矩阵Need。如Need\[i,j\]=k。  
(5) 进程申请资源矩阵Request，如Request\[i,j\]=k。  
其中Max\[n,m\] = Allocation\[n,m\] + Need\[n,m\]。

## 银行家算法步骤 ##

当进程Pi申请资源时,其申请资源的个数存放在向量Request\[i\]中，则系统分配资源的算法描述如下：  
(1) 如果Request\[i\]>Need\[i\]，说明进程Pi申请的资源数目超出进程所需的资源数，则出错返回;  
(2) 如果Request\[i\]>Avaliable，说明进程Pi申请的资源数目超出系统中可用的资源数，则出错返回;。  
(3) 系统能满足进程Pi申请的资源，则假定为进程Pi分配它所需的资源，于是修改系统状态：  
Avaliable＝Avaliable－Request\[i\];  
Allocation\[i\]＝Allocation\[i\]＋Request\[i\];  
Need\[i\]＝Need\[i\]－Request\[i\];  
(4) 调用安全状态检查算法，若系统处于安全状态，则第(3)的资源分配变为事实，进程Pi申请资源成功，返回;  
(5) 因系统处于不安全状态，因此第(3)的分配失败，恢复原来的资源分配状态，让进程Pi等待。  
Avaliable＝Aaliable＋Request\[i\];  
Allocation\[i\]＝Allocation\[i\]－Request\[i\];  
Need\[i\]＝Need\[i\]＋Request\[i\];  
(6) 返回。

### 安全状态检查算法 ###

设Work为临时工作向量。初始时Work＝Available。令N={1，2，…，n}。
       (1) 寻求j∈N使其满足：Need[j]≤Work，若不存在这样的j则转(4)。
       (2) 修改参数：
             Work ＝ Work ＋ Allocation[j];
             N ＝ N－{j}; 
       (3) 如果N不为空集，则转(1);
       (4) 如果N不为空集则返回-1（系统不安全），否则，返回0（系统安全）

## 源代码 ##

// 进程默认从0开始编号
    #include<bits/stdc++.h>
    using namespace std;
    const int M = 4;//假设系统有M类资源
    const int N = 4;//假设系统有N个进程
    int Avaliable[M];//可利用资源向量
    int Max[N][M];// 最大需求矩阵
    int Allocation[N][M];//分配矩阵
    int Need[N][M];//需求矩阵
    
    void output(){ 
        printf("现在可利用系统资源为：");
        for(int i=0;i<M;++i)printf("%d ",Avaliable[i]);
        printf("\n%d个进程需要系统各类资源的最大值：\n",N);
        for(int i=0;i<N;++i){ 
            for(int j=0;j<M;++j)printf("%d ",Max[i][j]);
            printf("\n");
        }
        printf("现在对%d个进程分配系统各类资源量：\n",N);
        for(int i=0;i<N;++i){ 
            for(int j=0;j<M;++j)printf("%d ",Allocation[i][j]);
            printf("\n");
        }
        printf("%d个进程还需要系统分配各类资源：\n",N);
        for(int i=0;i<N;++i){ 
            for(int j=0;j<M;++j)printf("%d ",Need[i][j]);
            printf("\n");
        }
    }
    
    int random(int a,int b){ 
        if(a-b==0)return a;
        if(a<b)swap(a,b);
        srand(0);
        int x = rand();//x属于[0，32767]
        return x%(a-b)+a;
    }//伪随机数的概率不完全相同
    
    bool safe(){ 
        int Work[M];//临时工作向量
        bool flag[M]={ false};//初始化
        for(int i=0;i<M;++i)Work[i]=Avaliable[i];//初始化
        while(true){ 
            int index=-1;
            for(int i=0;i<N;++i){ 
                if(flag[i])continue;
                bool t=true;//
                for(int j=0;j<M;++j){ 
                    if(Need[i][j]>Work[j]){ 
                        t = false;
                        break;
                    }
                }
                if(t){ 
                    index = i;
                    break;
                }
            }//步骤1
            if(index==-1)break;//步骤3
            for(int i=0;i<M;++i)Work[i]+=Allocation[index][i];
            flag[index]=true;//步骤2
        }
        for(int i=0;i<M;++i)if(!flag[i])return false;
        return true;//步骤4
    }
    
    int Request[M];//进程申请资源向量
    void Banker(int p){ 
        for(int i=0;i<M;++i){ 
            if(Request[i]>Need[p][i]){ 
                printf("进程%i申请的资源数目超出进程所需的资源数\n",p);
                return;
            }
        }//步骤1
        for(int i=0;i<M;++i){ 
            if(Request[i]>Avaliable[i]){ 
                printf("进程%i申请的资源数目超出系统中可用的资源数\n",p);
                return;
            }
        }//步骤2
        for(int i=0;i<M;++i){ 
            Avaliable[i]-=Request[i];
            Allocation[p][i]+=Request[i];
            Need[p][i]-=Request[i];
        }//步骤3
        if(safe()){ 
            printf("系统处于安全状态, 进程%i申请资源成功\n",p);//步骤4
            output();
        }else{ 
            printf("若分配资源系统将处于不安全状态, 驳回进程%i申请资源\n",p);//步骤5
            for(int i=0;i<M;++i){ 
                Avaliable[i]+=Request[i];
                Allocation[p][i]-=Request[i];
                Need[p][i]+=Request[i];
            }
        }
    }
    
    void init1(){ 
    
    }//利用随机数进行初始化
    
    
    
    void init2(){ 
        //利用输入初始化
        for(int i=0;i<M;++i)scanf("%d",&Avaliable[i]);
        int d ;
        for(int i=0;i<N;++i){ 
            for(int j=0;j<M;++j){ 
                scanf("%d",&d);
                Max[i][j]=d;
            }
        }
        for(int i=0;i<N;++i){ 
            for(int j=0;j<M;++j){ 
                scanf("%d",&d);
                Allocation[i][j]=d;
                Need[i][j]=Max[i][j]-d;
            }
        }
        output();
    }
    
    
    int main(){ 
        //freopen("test.in","r",stdin);
        //freopen("test.out","w",stdout);
        //把文件作为标准输入输出流
        init2();
        int n,p;
        scanf("%d",&n);
        while(n--){ 
            scanf("%d",&p);
            for(int i=0;i<M;++i)scanf("%d",&Request[i]);
            printf("现在进程%d向系统申请资源为：",p);
            for(int i=0;i<M;++i)printf("%d ",Request[i]);
            printf("\n");
            Banker(p);
        }
    }

### 测试 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]  
进程P3发出资源请求(1，1，0，1)

输入文件

1 1 1 2
    
    1 3 2 2
    3 6 1 3
    2 3 1 4
    0 4 2 2
    
    1 1 0 0
    2 5 1 1
    1 2 1 1
    0 0 0 2
    
    1
    2 1 1 0 1

#### 输出 ####

现在可利用系统资源为：1 1 1 2 
    4个进程需要系统各类资源的最大值：
    1 3 2 2 
    3 6 1 3 
    2 3 1 4 
    0 4 2 2 
    现在对4个进程分配系统各类资源量：
    1 1 0 0 
    2 5 1 1 
    1 2 1 1 
    0 0 0 2 
    4个进程还需要系统分配各类资源：
    0 2 2 2 
    1 1 0 2 
    1 1 0 3 
    0 4 2 0 
    现在进程2向系统申请资源为：1 1 0 1 
    若分配资源系统将处于不安全状态, 驳回进程2申请资源

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20230531/cb19cc3f0b224f7e91d0f12b0a43b9b3.png