飞道的博客

Java模拟实现银行家算法

2020-04-01 15:16 317人阅读  评论(0)

Java模拟实现银行家算法

​ 在上一文中我们详细的讨论了银行家算法，包含其数据结构、算法步骤和安全性算法，在本文中，我们使用Java语言来实现银行家算法，并以上一文中的题目来进行验证。

​ 关于银行家算法的具体细节，请参看上篇博文。

​ 首先，我们给出银行家算法的执行流程图：

​ 下面我们就步入正题，一起来看下银行家算法的实现吧：

​ 首先就是数据结构的定义，分别为可利用的资源、所有进程对资源的最大需求、系统中的资源分配、以及所有进程仍需要的资源情况。

//可利用资源变量
private List<Integer> available = new ArrayList<>();

//最大资源需求矩阵
private List<List<Integer>> max = new ArrayList<>();

//资源分配矩阵
private List<List<Integer>> allocation = new ArrayList<>();

//仍需资源需求矩阵
private List<List<Integer>> need = new ArrayList<>();

​ 对于Requesti，我们使用如下结构来定义：

@Data
public class RequestSource {

    //请求资源的进程编号
    private int id;

    //请求的资源列表
    private List<Integer> source;
}

​ 然后我们来看下银行家算法的主体代码：

//银行家算法
public void bankerAlgorithm(RequestSource request) throws Exception {
  //请求资源进程的编号
  int id = request.getId();
  //判断请求资源是否超过进程所声明的最大需求数
  for (int i = 0; i < available.size(); i++) {
    if (request.getSource().get(i) > need.get(id).get(i)) {
      throw new Exception("进程P" + id + "请求资源超过其申明的最大值，发生异常");
    }
  }
  //判断OS当前是否可以满足进程此次的资源请求
  for (int i = 0; i < available.size(); i++) {
    if (request.getSource().get(i) > available.get(i)) {
      throw new Exception("当前OS尚无足够的资源满足进程P" + id + "请求资源，发生异常");
    }
  }
  //进行资源的试探分配
  resourceAllocation(request);
  //进行安全性检查
  if (!securityCheck()) {
    rollbackAllocation(request);
    System.out.println("进程P" + id + "申请资源" + request.getSource() + "不可分配！");
  } else {
    System.out.println("进程P" + id + "申请资源" + request.getSource() + "分配成功！");
  }
}

//资源分配，直接分配，如果安全性检查不通过，进行资源回滚释放
private void resourceAllocation(RequestSource request) {
  //请求资源进程的编号
  int id = request.getId();
  List<Integer> requestSource = request.getSource();
  //当前进程已经分配的资源
  List<Integer> currentAllocation = allocation.get(id);
  //当前进程仍需的资源
  List<Integer> currentNeed = need.get(id);

  //修改可利用资源数量、已分配资源、仍需求资源
  //注：因为在前面已经判断过request<=need和available,所以资源不会变成负,不需要处理异常
  for (int i = 0; i < available.size(); i++) {
    available.set(i, available.get(i) - requestSource.get(i));
    currentAllocation.set(i, currentAllocation.get(i) + requestSource.get(i));
    currentNeed.set(i, currentNeed.get(i) - requestSource.get(i));
  }
  //更新总的分配矩阵
  allocation.set(id, currentAllocation);
  //更新总的需求矩阵
  need.set(id, currentNeed);
}

//安全性检查算法
private boolean securityCheck() {
  //步骤1：初始化临时变量work和
  List<Integer> work = new ArrayList<>();
  work.addAll(available);
  int processCount = max.size();
  List<Boolean> finish = new ArrayList<>();
  for (int i = 0; i < processCount; i++) {
    finish.add(false);
  }
  //i表示已执行多少个进程，id表示可执行的进程号，j表示资源的类型
  int i, j, id;
  //在步骤1中是否找到一个能满足条件的进程，即是否有进程可以执行完毕，释放资源
  boolean flag;
  //步骤1：从进程集合中找到满足条件的进程
  for (i = 0; i < processCount; i++) {
    flag = false;
    for (id = 0; id < processCount; id++) {
      //finish为true表示可以获得所需资源，顺利执行完毕
      if (finish.get(id)) {
        continue;
      }
      List<Integer> currentNeed = need.get(id);
      //j表示资源的类型
      for (j = 0; j < work.size(); j++) {
        if (currentNeed.get(j) > work.get(j)) {
          break;
        }
      }
      //当前进程id所需的资源可以得到满足，转而执行步骤2
      if (j == work.size()) {
        //步骤2
        List<Integer> currentAllocation = allocation.get(id);
        for (j = 0; j < work.size(); j++) {
          //进程可以顺利完成，释放资源
          work.set(j, work.get(j) + currentAllocation.get(j));

        }
        //更改标志位
        finish.set(id, true);
        flag = true;
        //跳出循环，执行步骤1
        System.out.println("此进程执行完毕：P" + id);
        break;
      }
    }
    //上接break
    //判断是否进程分配资源，扫描进程集合一遍，如未分配资源，则表示没有进程可以继续执行，
    //立刻跳出循环，转而执行步骤3
    if (!flag) {
      break;
    }
  }

  //步骤3：判断是否所有进程的finish标志位是否全为true
  for (id = 0; id < processCount; id++) {
    //如果有一个为false，则处于不安全状态
    if (!finish.get(id)) {
      return false;
    }
  }
  return true;
}

//安全性检查不通过，回滚刚才分配的资源
private void rollbackAllocation(RequestSource request) {
  //请求资源进程的编号
  int id = request.getId();
  List<Integer> requestSource = request.getSource();
  //当前进程已经分配的资源
  List<Integer> currentAllocation = allocation.get(id);
  //当前进程仍需的资源
  List<Integer> currentNeed = need.get(id);

  //修改可利用资源数量、已分配资源、仍需求资源
  //注：因为在前面已经判断过request<=need和available,所以资源不会变成负,不需要处理异常
  for (int i = 0; i < available.size(); i++) {
    available.set(i, available.get(i) + requestSource.get(i));
    currentAllocation.set(i, currentAllocation.get(i) - requestSource.get(i));
    currentNeed.set(i, currentNeed.get(i) + requestSource.get(i));
  }
  //更新总的分配矩阵
  allocation.set(id, currentAllocation);
  //更新总的需求矩阵
  need.set(id, currentNeed);
}

​ 为了方便的展示系统的资源分配情况，需要写一个print函数：

private void printResourceAllocationPic() {
  for (int i = 0; i < max.size(); i++) {
    System.out.println(max.get(i) + " " + allocation.get(i) + " " + need.get(i));
  }
  System.out.println("当前可用资源：" + available);
}

​ 最后我们使用上一篇中的例子来进行验证，题目修改后如下:

例题：假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的对应数量为10、5、7，在T0时刻的资源分配图如下图所示。

​ (1)请检查T0时刻的安全性。

​ (2)进程P1发出请求向量Request1(1, 0, 2)，为保证系统安全，系统能否将资源分配给它？

​ (3)进程P4发出请求向量Request4(3, 3, 0)，为保证系统安全，系统能否将资源分配给它？

​ (4)进程P0发出请求向量Request0(0, 2, 0)，为保证系统安全，系统能否将资源分配给它？

测试代码如下：

@Test
public void bankTest() throws Exception {
  Integer[][] maxArray = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
  for (Integer[] tmpArray : maxArray) {
    max.add(Arrays.asList(tmpArray));
  }
  Integer[][] allocationArray = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
  for (Integer[] tmpArray : allocationArray) {
    allocation.add(Arrays.asList(tmpArray));
  }
  Integer[][] needArray = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
  for (Integer[] tmpArray : needArray) {
    need.add(Arrays.asList(tmpArray));
  }
  Integer[] availableArray = {3, 3, 2};
  available = Arrays.asList(availableArray);

  //第一问
  System.out.println("第一问？");
  //printResourceAllocationPic();
  System.out.println("系统安全性检查结果为：" + securityCheck());
  // printResourceAllocationPic();

  System.out.println();
  System.out.println("第二问？");
  //第二问
  //构建进程request对象
  RequestSource request = new RequestSource();
  request.setId(1);
  List<Integer> requestSource = new ArrayList<Integer>() {{
    add(1);
    add(0);
    add(2);
  }};
  request.setSource(requestSource);
  System.out.println("申请资源前的资源分配情况：");
  printResourceAllocationPic();
  bankerAlgorithm(request);
  System.out.println("银行家算法执行后的资源分配情况：");
  printResourceAllocationPic();

  //第三问
  System.out.println();
  System.out.println("第三问？");
  try {
    request.setId(4);
    Integer[] requestArray = {3, 3, 0};
    requestSource = Arrays.asList(requestArray);
    request.setSource(requestSource);
    System.out.println("申请资源前的资源分配情况：");
    printResourceAllocationPic();
    bankerAlgorithm(request);
    printResourceAllocationPic();
  } catch (Exception e) {
    System.out.println("无法申请资源，异常原因为：" + e.getMessage());
  }

  //第四问
  System.out.println();
  System.out.println("第四问？");
  request.setId(0);
  Integer[] requestArray = {0, 2, 0};
  requestSource = Arrays.asList(requestArray);
  request.setSource(requestSource);
  System.out.println("申请资源前的资源分配情况：");
  printResourceAllocationPic();
  bankerAlgorithm(request);
  System.out.println("银行家算法执行后的资源分配情况：");
  printResourceAllocationPic();
}

执行结果如下图所示：

​ 从图中可以看到，安全序列为{P1,P3,P0,P2,P4}，因此T0时刻OS处于安全状态。

​ 从图中可以看到，资源分配后，OS中还存在安全序列为{P1,P3,P0,P2,P4}，因此通过了安全性检查，因此可以进行资源分配，分配后的资源如图中下方红框所示。

​ 因为此时系统中的Available=(2, 3, 0)，因此无法满足Request4(3, 3, 0)。

​ 由上图可知，资源试探分配给进程P0后，无法满足任何进程，因此不存在安全序列，故回滚资源。

总结

​ 本文中使用Java语言模拟实现银行家算法，上面所有所有代码放到一个类中即可实现（不包含RequestSource，需单独一个文件）。算法有较强的扩展性，资源种类可变，进程数可变，有想法的同学可考虑使用Java多线程来模拟死锁问题，并使用银行家算法来避免死锁。这一定会非常有趣。

​ 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。

​ 如有兴趣，还可以查看我的其他几篇博客，都是OS的干货，原创不易，喜欢的话还请点赞、评论加关注_。

​ 操作系统武功修炼心法


转载：https://blog.csdn.net/qq_34666857/article/details/104138640
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场