银行家算法概述及Java实现

ゝ一纸荒年。 2021-09-28 14:08 342阅读 0赞

# 一、银行家算法 #

1.  **银行家算法**是一种最有代表性的避免死锁的算法。又被称为“资源分配拒绝”法。  
    在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给线程，否则进程等待。
2.  **在银行家算法中需要定义一些数据结构**  
    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\]
3.  **操作系统的两种状态**  
    **安全序列**是指一个进程序列\{P1，…，Pn\}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。  
    1） **安全状态**：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。  
    2）**不安全状态**：不存在一个安全序列。不安全状态不一定导致死锁。
4.  **示例**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]  
    首先判断一下当前的安全序列：  
    当前状态，可利用资源向量有 1 6 2 2  
    ① P0： 已分配 0 0 3 2， 还需要 0 0 1 2，当前可利用资源 1 6 2 2足够分配给P0；  
    Process Allocation Need Available（Available-Need） Available+Allocation  
    P0 0 0 4 4 0 0 0 0 1 6 1 0 1 6 5 4  
    **P0分配成功**，进入安全序列，分配完成后，**将资源还给可利用资源**  
    ② P1：已分配1 0 0 0， 还需要 1 7 5 0，当前可利用资源 1 6 5 4不够分配给P1；  
    **P1分配失败**  
    ③ P2： 已分配1 3 5 4， 还需要 2 3 5 6，当前可利用资源 1 6 5 4不够分配给P2；  
    **P2分配失败**  
    ④ P3： 已分配 0 3 3 2， 还需要 0 6 5 2，当前可利用资源 1 6 5 4足够分配给P3；  
    Process Allocation Need Available（Available-Need） Available+Allocation  
    P3 0 9 8 4 0 0 0 0 1 0 0 2 1 9 8 6  
    **P3分配成功**，进入安全序列，分配完成后，**将资源还给可利用资源**  
    ⑤ P4： 已分配 0 0 1 4， 还需要 0 6 5 6，当前可利用资源 1 9 8 6足够分配给P4；  
    Process Allocation Need Available（Available-Need） Available+Allocation  
    P4 0 6 6 10 0 0 0 0 1 3 3 0 1 9 9 10  
    **P4分配成功**，进入安全序列，分配完成后，**将资源还给可利用资源**  
    ⑥ P1： 已分配 1 0 0 0， 还需要 1 7 5 0，当前可利用资源 1 9 9 10足够分配给P1；  
    Process Allocation Need Available（Available-Need） Available+Allocation  
    P1 2 7 5 0 0 0 0 0 0 2 4 10 2 9 9 10  
    **P1分配成功**，进入安全序列，分配完成后，**将资源还给可利用资源**  
    ⑦ P2： 已分配 1 3 5 4， 还需要 2 3 5 6，当前可利用资源 2 9 9 10足够分配给P2；  
    Process Allocation Need Available（Available-Need） Available+Allocation  
    P2 3 6 10 10 0 0 0 0 0 6 4 4 3 12 14 14  
    **P4分配成功**，进入安全序列，分配完成后，**将资源还给可利用资源**

所以：当前的安全序列为： **p0-p3-p4-p1-p2**

如果在未分配的时候：  
p2请求 1 2 2 2 ，从资源池里给他分配，请问可以分配吗？  
**答**： 如果满足了P2的请求1 2 2 2 的话，要从可利用资源Available 1 6 2 2 中减去1 2 2 2，此时可利用资源为0 4 0 0 ，  
纵观全局，如果满足了P2的请求，那么别的进程的需求都不能满足，导致资源不够分配，所以P2的请求不可以分配

# 二、Java实现银行家算法 #

import java.util.Scanner;
    
    public class Banker { 
        int available[] = new int[]{ 3,3,2};//可利用的资源
        int max[][] = new int[][]{ { 7,5,3},{ 3,2,2},{ 9,0,2},{ 2,2,2},{ 4,3,3}};//每个进程最大资源数
        int allocation[][] = new int[][]{ { 0,1,0},{ 2,0,0},{ 3,0,2},{ 2,1,1},{ 0,0,2}};//每个进程目前拥有的资源数
        int need[][] = new int[][]{ { 7,4,3},{ 1,2,2},{ 6,0,0},{ 0,1,1},{ 4,3,1}};//每个进程需要的资源数
        void showData() { 
        //展示数据输出每个进程的相关数
            System.out.println("进程号 Max All Need ");
            System.out.println(" A B C A B C A B C");
            for(int i = 0;i<5;i++){ 
                System.out.print(i+" ");
                for(int m = 0;m<3;m++) System.out.print(max[i][m]+" ");
                for(int m = 0;m<3;m++) System.out.print(allocation[i][m]+" ");
                for(int m = 0;m<3;m++) System.out.print(need[i][m]+" ");
                System.out.println();
            }
        }
    
        boolean change(int inRequestNum,int inRequest[])//分配数据
        { 
            int requestNum = inRequestNum;
            int request[] = inRequest;
            // for(int i=0;i<3;i++)System.out.println("修改前available"+available[i]);
            if(!(request[0]<=need[requestNum][0]&&request[1]<=need[requestNum][1]&&request[2]<=need[requestNum][2]))
            { 
                //request[0]<=need[requestNum][0]
                //request[1]<=need[requestNum][1]
                //request[2]<=need[requestNum][2]
                //每一类请求资源小于当前线程need的资源数
                System.out.println("请求的资源数超过了所需要的最大值，分配错误");
                return false;
            }
            if((request[0]<=available[0]&&request[1]<=available[1]&&request[2]<=available[2])==false)
            { 
                //当前线程的每一类请求资源小于等于资源池对应资源的数量
                System.out.println("尚无足够资源分配，必须等待");
                return false;
            }
    
            for(int i = 0;i<3;i++)//试分配数据给请求的线程
            { 
                available[i] = available[i]-request[i];
                //资源池的每类资源减去每类请求资源数量
                allocation[requestNum][i] = allocation[requestNum][i] + request[i];
                //当前线程allocation中每类资源加上每类资源请求数量
                need[requestNum][i] = need[requestNum][i] - request[i];
                //当前线程need中每类资源数量减去每类资源的请求数量
            }
    // for(int i=0;i<3;i++)System.out.println("修改后available"+available[i]);
            boolean flag = checkSafe(available[0],available[1],available[2]);//进行安全性检查并返回是否安全
    // System.out.println("安全性检查后"+flag);
            if(flag==true)
            { 
                System.out.println("能够安全分配");
                return true;
            }
            else//不能通过安全性检查 恢复到未分配前的数据
            { 
                System.out.println("不能够安全分配");
                for(int i = 0;i<3;i++)
                { 
                    available[i] = available[i]+request[i];
                    allocation[requestNum][i] = allocation[requestNum][i] - request[i];
                    need[requestNum][i] = need[requestNum][i] + request[i];
                }
                return false;
            }
        }
        boolean checkSafe(int a,int b,int c)//安全性检查
        { 
            int work[] = new int[3];
            work[0] = a;
            work[1] = b;
            work[2] = c;
            int i=0;
            boolean finish[] = new boolean[5];
            while(i<5)//寻找一个能够满足的认为完成后才去执行下一进程
            { 
                if(finish[i]==false&&need[i][0]<=work[0]&&need[i][1]<=work[1]&&need[i][2]<=work[2])
                { //找到满足的修改work值，然后i=0，重新从开始的为分配的中寻找
                    System.out.println("分配成功的是"+i);
                    for(int m = 0;m<3;m++)
                        work[m] =work[m] + allocation[i][m];
                    finish[i] = true;
                    i=0;
                }
                else//如果没有找到直接i++
                    i++;
            }
            for(i=0;i<5;i++)//通过finish数组判断是否都可以分配
            { 
                if(finish[i]==false)
                    return false;
            }
            return true;
        }
        public static void main(String[] args)
        { 
            Banker bank = new Banker();
            bank.showData();
            //请求线程资源存放的数组
            int request[] =new int[3];
            int requestNum;
            String source[] = new String[]{ "A","B","C"};
            Scanner s = new Scanner(System.in);
            String choice = new String();
            while(true)//循环进行分配
            { 
                System.out.println("请输入要请求的进程号（0--4）：");
                requestNum = s.nextInt();
                System.out.print("请输入请求的资源数目");
                for(int i = 0;i<3;i++)
                { 
                    System.out.println(source[i]+"资源的数目：");
                    request[i] = s.nextInt();
                }
                bank.change(requestNum, request);
                System.out.println("是否再请求分配(y/n)");
                choice = s.next();
                if(choice.equals("n"))
                    break;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/7a73e51e0384471c913609f663cab276.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]: /images/20210923/cb191e160831457b8c36104ace7bb3ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 2]: /images/20210923/0c148eff3ae2402f82f414f8c8ed872c.png