银行家算法【学习算法】

前言
版权
推荐
银行家算法

7.避免死锁

7.1 系统安全状态
7.2 利用银行家算法避免死锁

Java算法实现

代码
结果

最后

前言

2023-8-14 18:18:01

银行家算法

7.避免死锁

7.1 系统安全状态

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

1安全状态

在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。

2由安全状态向不安全状态的转换

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

在建立了系统安全状态的概念后便可知道避免死锁的基本思想，就是确保系统始终处于安全状态。一个系统开始是处于安全状态的，当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。

7.2 利用银行家算法避免死锁

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

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

(2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。

(4) 需求矩阵Need。这也是一个nm矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。

上述三个矩阵间存在下述关系：

Need[i,j]=Max[i,j]-Allocation[i,j]

2银行家算法

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果Requesti[j]≤Need[i服务器托管网,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3) 系统试探着把资源分配给进程Pi，并修改数据结构中的数值。

(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3安全性算法

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

(1) 设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令F服务器托管网inish[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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

Java算法实现

代码

package os.chapter3._3_6_1;

import java.util.Arrays;

public class BankerAlgorithm {
    private final int[][] max; // 最大需求矩阵
    private final int[][] allocation; // 已分配矩阵
    private final int[][] need; // 剩余需求矩阵
    private final int[] available; // 可用资源向量
    private final int processNum; // 进程数量
    private final int resourceNum; // 资源数量

    public BankerAlgorithm(int[][] max, int[][] allocation, int[] available) {
        this.max = max;
        this.allocation = allocation;
        this.need = new int[max.length][max[0].length];
        this.available = available;
        this.processNum = max.length;
        this.resourceNum = max[0].length;
        initNeed();
    }

    public void initNeed(){
        for (int i = 0; i need[p][j]){
                System.out.println("P"+p+"所需要的资源已超过它所宣布的最大值");
                return;
            }
        }

        System.out.println("检查是否满足条件2");
        for(int j=0;javailable[j]){
                System.out.println("尚无足够资源，P"+p+"必须等待");
                return;
            }
        }

        System.out.println("==========================================");

        //试探分配
        System.out.println("开始试探分配");
        System.out.println("P"+p+":"+Arrays.toString(request));
        for(int j=0;j work[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] max = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
        int[][] allocation = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
        int[] available = {3, 3, 2};

        BankerAlgorithm banker = new BankerAlgorithm(max, allocation, available);


        int[] request1={1,0,2};
        banker.bankerAlgorithm(request1,1);

        int[] request4={3,3,0};
        banker.bankerAlgorithm(request4,4);

        int[] request0={0,2,0};
        banker.bankerAlgorithm(request0,0);


    }
}

结果

==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P1:[1, 0, 2]
开始安全检查
可以分配P1:[1, 0, 2]
==========================================
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
尚无足够资源，P4必须等待
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P0:[0, 2, 0]
开始安全检查
不能分配P0:[0, 2, 0]
==========================================

Process finished with exit code 0

最后

2023-8-14 18:20:16

我们都有光明的未来

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 从达梦数据库到Oracle数据库的性能测试数据迁移和导入优化

为了在同样的数据基础上对比达梦数据库和Oracle数据库的业务性能，我们需要将达梦数据库的数据导入到Oracle数据库中。本文将提供一种思路来解决导入过程中遇到的问题及存在问题记录。数据库版本信息源数据库：达梦数据库（DM） V8 目标数据库：Oracle…