操作系统之银行家算法—详解流程及案例数据

简介: 银行家是操作系统比较经典的算法之一,他比较好的防止死锁情况的出现,增加了系统的安全性.在编写银行家算法的过程中,对操作系统的银行家算法有了深入了解和心得。

要求


银行家是操作系统比较经典的算法之一,他比较好的防止死锁情况的出现,增加了系统的安全性.在编写银行家算法的过程中,对操作系统的银行家算法有了深入了解和心得。


一、实验目的



死锁会引起计算机工作僵死,因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序,了解死锁产生的条件和原因,并采用银行家算法有效地防止死锁的发生,以加深对课堂上所讲授的知识的理解。


二、实验要求



设计有n个进程共享m个系统资源的系统,进程可动态的申请和释放资源,系统按各进程的申请动态的分配资源。


系统能显示各个进程申请和释放资源,以及系统动态分配资源的过程,便于用户观察和分析;


三、数据结构



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。Allocation i表示进程i的分配向量,有矩阵Allocation的第i行构成。


4.需求矩阵Need,这是一个n×m的矩阵,用以表示每个进程还需要的各类资源的数目。如果Need(i,j)=k,表示进程i还需要Rj类资源k个,才能完成其任务。Need i表示进程i的需求向量,由矩阵Need的第i行构成。


上述三个矩阵间存在关系:Need(i,j)=Max(i,j)-Allocation(i,j);


四、安全性算法



1.设置两个向量。


Work:它表示系统可提供给进程继续运行的各类资源数目,它包含m个元素,开始执行安全性算法时,Work = Available。

Finish:它表示系统是否有足够的资源分配给进程,使之运行完成,开始Finish(I)=false;当有足够资源分配给进程Pi时,令Finish(i)=true;


2.从进程集合中找到一个能满足下述条件的进程。

Finish(i)= = false;

Need i ≤work;

如找到则执行步骤3;否则,执行步骤4;


3.当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行

Work = work Allocation i

Finish(i)=true;转向步骤2;


4.若所有进程的Finish(i)都为true,则表示系统处于安全状态;否则,系统处于不安全状态。


流程图:


个人觉得。总的来说,银行家算法就是一个模拟借钱。判断假如借钱是否安全然后考虑借不借的问题。

先放代码,和数据再说分析:


代码


import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class bank {
  static Scanner sc=new Scanner(System.in);
  static int n;
  static int m;
  static int available[];
  static int max[][];//最大需求矩阵
  static int allocation[][];//当前分配到每一个进程的
  static int need[][];//需求矩阵
  static boolean isrelesed[];//资源是否已经释放
  public static void main(String[] args) {
    // TODO 自动生成的方法存根   
    System.out.println("请输入资源种类m:");
       m=sc.nextInt();//系统资源
    initm(m);//初始相关
    System.out.println("输入进程数量");
    n=sc.nextInt();//进程数量
    initn(n);//初始相关矩阵
    //getstatus();//输出当前状态
    while(true) {
    applyresouse();//申请资源
    }
  }
  static void applyresouse()//申请资源
  {
    getstatus();//输出状态
      int request[]=new int[m];//需求量 为了节省空间写成全部变量
    System.out.println("输入你想申请资源的编号");
    int index=sc.nextInt();
    while(0>index||index>=n) {System.out.println("输入的编号不在编号范围之内,请重新输入");index=sc.nextInt(); }
    while(isrelesed[index]) 
    {System.out.println("改编号已经完成资源的释放,无法再请求资源,请重新输入");index=sc.nextInt();
    while(0>index||index>=n) {System.out.println("输入的编号不在编号范围之内,请重新输入");index=sc.nextInt(); }}
    System.out.println("请输入"+m+"个资源申请的个数(不申请的资源用0替代)");
        int team=0;
        while(team==0) {
    for(int i=0;i<m;i++)
    {
      request[i]=sc.nextInt();
      if(request[i]>available[i]) {team=1;}
      if(request[i]>max[index][i]) {team=2;}
    }
    if(team==1) {System.out.println("您的请求量超出 了系统提供量,请重新输入");team=0;}//重新循环
    else if(team==2) {System.out.println("您的请求量超出 了最大请求量max,请重新输入");team=0;}
    else team=3;//退出循环用
        }
        //赋值成功后开始
       boolean isfinish= ifallocate(index,request);
       if(isfinish) {System.out.println("所有进程完成资源分配,分配结束");System.exit(0);}
  } 
  private static boolean ifallocate(int index,int[] request) {//假设分配
    /*
     * 首先要将真的数组克隆,模拟已经给资源,然后判断这个资源是否安全
     */
    int work[]=available.clone();
    boolean finish[]=isrelesed.clone();//克隆初始状态
    int need2[][]=new int[n][m];int allocate2[][]=new int[n][m];
    for(int i=0;i<n;i++)
    {
      need2[i]=need[i].clone();
      allocate2[i]=allocation[i].clone();
    }
    for(int i=0;i<m;i++)
    {
      if(need[index][i]<request[i])request[i]=need[index][i];//可以借这么多钱但是我不需要这么多钱an
      work[i]-=request[i];//假设把钱借出去
      allocate2[index][i]+=request[i];
    }
    //需要把need2重置一下
    for(int i=0;i<m;i++)
    {
      need2[index][i]-=request[i];
    }
    boolean isallocate=issafety(work, finish, need2, allocate2);
    if(!isallocate) {System.out.println("分配造成进程不安全,取消分配"); return false;}
    else {
      System.out.println("分配成功");
      //分配成功就要分配资源
      for(int i=0;i<m;i++)
      {
        available[i]-=request[i];
        allocation[index][i]+=request[i];
        need[index][i]-=request[i];
        //System.out.println(request[i]);
      }
      if(!isrelesed[index])//判断改资源是否释放
      {
        boolean jud=false;
        for(int j=0;j<m;j++)
        {
          if(need[index][j]!=0)jud=true;
        }
        if(!jud)//资源需要释放 
        {
          isrelesed[index]=true;
          for(int j=0;j<m;j++)
          {
            available[j]+=allocation[index][j];
          }
        }
      }   
    }
    boolean isfinished=true;
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++) {
      if(need[i][j]!=0) {isfinished=false;return false;}}
    }
    return isfinished;
  }
  private static boolean issafety(int work[],boolean finish[],int need2[][],int allocate2[][])//模拟的需求和分配
  {
    //int work[]=available.clone();//不能直接等于复制。可以了解下对象克隆或者深浅复制。
      Queue<Integer>q1=new ArrayDeque<Integer>();//如果能完成的队列
      int time=0;
      while(true)
      {
        boolean loop=true;
        for(int i=0;i<n;i++)//n个进程模拟
        {
          time++;
          if(!finish[i]) {
          boolean b=false;//完成不了的
          for(int j=0;j<m;j++)
          {
            if(work[j]<need2[i][j])
            {
              b=true;//完成不了的
            }
            if(b) {break;}
          }
          if(!b) {//可以完成的,释放资源
            time=0;//重新计数
            q1.add(i);
            finish[i]=true;//已经完成
            for(int j=0;j<m;j++)
            {
              work[j]+=allocate2[i][j];//
              allocate2[i][j]+=need2[i][j];
              need2[i][j]=0;
            }
            //打印
            System.out.print("进程"+i+" max:");
            for(int j=0;j<m;j++)
            {
              System.out.print(max[i][j]+" ");
            }
            System.out.print("allocate2: ");
            for(int j=0;j<m;j++)
            {
              System.out.print(allocate2[i][j]+" ");
            }
            System.out.print("need2: ");
            for(int j=0;j<m;j++)
            {
              System.out.print(need2[i][j]+" ");
            }
            System.out.print("work: ");
            for(int j=0;j<m;j++)
            {
              System.out.print(work[j]+" ");
            }
            System.out.println();
              }
          }
        }
        boolean isfinish=false;
        for(int i=0;i<n;i++) 
        {
          if(!finish[i]) {isfinish=true;break;}
        }
        if(!isfinish) {return true;}
        if(time>n) {return false;}
      }
    //return false;
  }
  static void initm(int m)
  {
    System.out.println("请输入"+m+"种资源的最大量");
    available=new int[m];
      isrelesed=new boolean[m];
    //request=new int[m];
    for(int i=0;i<m;i++)//初始aviliable
    {
      available[i]=sc.nextInt();
    }
  }
  static void initn(int n)
  {
    max=new int[n][m];
    allocation=new int[n][m];
    need=new int[n][m];
    //finish=new boolean[n];
    for(int i=0;i<n;i++)
    {
      System.out.println("进程"+i+"的最大需求为:(输入m个数)");
      boolean jud=false;//判断输出是否有误
      for(int j=0;j<m;j++)
      {
        max[i][j]=sc.nextInt();
        if(max[i][j]>available[j]) {jud=true;}
      }
      if(jud) {System.out.println("最大需求输入有误,请重新赋值(m个数)");i--;}//i自减满足条件
    }
    System.out.println("n个线程m种资源最大需求赋值完成\n请输入当前进程已分配资源情况");//初始max
    for(int i=0;i<n;i++)//初始allocate矩阵
    {
      System.out.println("进程"+i+"已分配资源为:(输入m个数)");
      boolean jud=false;
      for(int j=0;j<m;j++)
      {
        allocation[i][j]=sc.nextInt();
        if(allocation[i][j]>max[i][j]){jud=true;}
      }
      if(jud) {System.out.println("输入有误,请重新输入");i--;}//输入有错误
    }
    System.out.println("allocate(当前已分配矩阵已经分配完毕)");
  }
  static void getstatus()//输出状态
  {
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        need[i][j]=max[i][j]-allocation[i][j];
      }
    }
    for(int i=0;i<n;i++)
    {
      System.out.print("进程"+i+"的状态为:max: ");
      for(int j=0;j<m;j++) {System.out.print(" "+max[i][j]+" ");}
      System.out.print("allocatem: ");
      for(int j=0;j<m;j++) {System.out.print(" "+allocation[i][j]+" ");}
      System.out.print("need: ");
      for(int j=0;j<m;j++) {System.out.print(" "+need[i][j]+" ");}
      System.out.print("avaliable: ");
      for(int j=0;j<m;j++) {System.out.print(" "+available[j]+" ");}
      System.out.println();
    }
  }
}


A还—>借B—>B还—>C—这样可以到最后。但是很多情况下客户是分期借的,这就要考虑安全性问题,比如A借6,6,6还剩4,4,4那么这个银行做多最多只能借2,2,2给其他人,因为一旦借多了A也无法释放,那么就造成死锁。那么这种情况就不能够借钱。所以在借钱的时候需要一个模拟的过程。


还有比较重要的是明白银行加算法各个矩阵的意义和作用非常的重要,我刚开始看银行家算法的时候因为对一些基础概念和数组矩阵的属性不够了解,茫然了很久,也走了很多的坑。那么就先介绍一下吧。


对于全局变量,我的代码中有:


20181203213123644.png


这些变量是在安全状态下的真实变量其中:


(1)n是线程的数量,m是资源的种类。

Available[]是当前还可以使用的资源。也就是银行家手中被借出去钱,手中还剩余各种钱的数量。只跟资源有关


Max[][]是最大需求矩阵,也可以理解为最终终态矩阵,因为这个max的状态就是客户想达到和满足的状态。也就是线程可以释放的状态。


Allocate[][]是已分配矩阵。就是客户已经借到的钱。也就是线程已经占有的资源量

Need[][]是还需要资源情况,由max和allcate决定。


Isrelese[]这个数组和线程有关和资源无关,它记录的就是线程是否达到终态,完成资源释放的情况,,一旦完成借钱就不需要借钱。


3:最后在具体实现的过程中。由于需要模拟过程,还是会遇到挺多坎的,在理清思路之后。在代码上还是由挺多要注意的。


第一:对象克隆(深浅拷贝),在模拟的过程中拥有初始化和真实数据一样的数组。但是如果直接赋值那么新对象指向的还是老数组的地址,会造成数据紊乱。那么对象克隆就一定要保证只赋值数据,不复制地址。


第二:模拟数值的改变,无论在申请资源,还是释放资源的时候,模拟的数值都会改变。但是不过如果模拟成功,真实数组会增加多少。这个需要尤其注意,同时,如果发现数值和预期不符合可以打断点单步调试。


附上我自己的流程图:


初始化:


20181203213728486.png


借钱:


20181203213859275.png


ps:本人有点菜,这里面可能有挺多的是错误的。。如果有大佬发现请指正。


目录
相关文章
|
1月前
|
算法 调度 UED
探索操作系统的心脏:调度算法的奥秘与影响
【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
|
1月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
60 0
|
19天前
|
存储 编解码 负载均衡
数据分片算法
【10月更文挑战第25天】不同的数据分片算法适用于不同的应用场景和数据特点,在实际应用中,需要根据具体的业务需求、数据分布情况、系统性能要求等因素综合考虑,选择合适的数据分片算法,以实现数据的高效存储、查询和处理。
|
19天前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
22天前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
26天前
|
存储 算法 搜索推荐
这些算法在实际应用中有哪些具体案例呢
【10月更文挑战第19天】这些算法在实际应用中有哪些具体案例呢
29 1
|
1月前
|
机器学习/深度学习 人工智能 算法
"拥抱AI规模化浪潮:从数据到算法,解锁未来无限可能,你准备好迎接这场技术革命了吗?"
【10月更文挑战第14天】本文探讨了AI规模化的重要性和挑战,涵盖数据、算法、算力和应用场景等方面。通过使用Python和TensorFlow的示例代码,展示了如何训练并应用一个基本的AI模型进行图像分类,强调了AI规模化在各行业的广泛应用前景。
31 5
|
1月前
|
算法 调度 UED
深入理解操作系统的进程调度算法
【10月更文挑战第7天】在操作系统的心脏——内核中,进程调度算法扮演着至关重要的角色。它不仅影响系统的性能和用户体验,还直接关系到资源的合理分配。本文将通过浅显易懂的语言和生动的比喻,带你一探进程调度的秘密花园,从最简单的先来先服务到复杂的多级反馈队列,我们将一起见证算法如何在微观世界里编织宏观世界的和谐乐章。
|
1月前
|
边缘计算 算法 调度
探究操作系统的心脏:调度算法的进化与影响
【10月更文挑战第2天】 本文深入探讨了操作系统中核心组件——调度算法的历史演变、关键技术突破及其对现代计算的影响。通过详细回顾从单任务到多任务、实时系统及分布式计算环境下调度算法的发展,文章揭示了这些算法如何塑造我们的数字世界,并对未来的趋势进行了展望。不同于传统的摘要,本文特别聚焦于技术细节与实际应用的结合点,为读者提供一幅清晰的技术演进蓝图。
46 4
|
1月前
|
算法 数据可视化 新制造
Threejs路径规划_基于A*算法案例完整版
这篇文章详细介绍了如何在Three.js中完整实现基于A*算法的路径规划案例,包括网格构建、路径寻找算法的实现以及路径可视化展示等方面的内容。
60 0
Threejs路径规划_基于A*算法案例完整版