MENU

银行家算法

June 15, 2020 • Read: 2319 • 学习记录

临近期末,加上感觉没啥写的,就只能水一水了(不,读书人的事情,怎么能说水呢

前言


这个是当初学操作系统课写的一个课外作业,写的有点粗糙(不,是非常粗糙),望大家多多包涵。

银行家算法


银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

运行结果展示


image-20200615223350728.png

代码展示

 下面代码是一个简单实现的java版本,仅供萌新参考(我自己也是),代码里面有详细的注释介绍,如有错误,欢迎给位大佬指点。

Demo1.java

import java.io.*;
import java.util.*;

/**
 * @author psl
 */
public class Demo1 {
    //已经拥有的资源
    static Map<String,Integer> C = new HashMap<>();
    //最大需求的资源
    static Map<String,Integer> R = new HashMap<>();
    //总的资源
    static int sum = 10;
    //可以利用的资源
    static int A = 10;

    public static void main(String[] args) throws IOException {
//        File algorithm = new File("banker's algorithm");
//        BufferedReader reader = new BufferedReader(new FileReader("banker's algorithm"));
        //往banker's algorithm.txt文档里面写入各种分配的状态
        BufferedWriter writer = new BufferedWriter(new FileWriter(new File("banker's algorithm.txt"),true));
        //已经拥有的资源
        C.put("A",0);
        C.put("B",0);
        C.put("C",0);
        C.put("D",0);
        //最大需求的资源
        R.put("A",6);
        R.put("B",5);
        R.put("C",4);
        R.put("D",7);
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入请求人");
        String people = sc.nextLine().toUpperCase();
        System.out.println("请输入请求数量");
        Integer count = sc.nextInt();
        writer.write("请求人   " + "请求数量   " + "请求状态");
        writer.newLine();
        writer.flush();
        while(true){
            //判断分配后是不是安全状态
            boolean flag = judge(people, count);
            if (flag){
                Integer cnt = C.get(people);
                //如果请求资源已经满足自己最大的需要,就释放所有的资源
                if (cnt + count < R.get(people)){
                    C.put(people,cnt+count);
                    A = A - count;
                }else {
                    C.put(people,0);
                    A = A + cnt;
                }

                System.out.println("请求成功");
                writer.write(people + "        " + count + "          成功");
                writer.newLine();
                System.out.println("剩余的资源为"+A);
            }else {
                System.out.println("请求失败");
                writer.write(people + "        " + count + "          失败");
                writer.newLine();
            }
            sc.nextLine();
            System.out.println("请输入请求人,如果输入N,表示结束循环,否则表示继续");
            people = sc.nextLine().toUpperCase();
            if (people.equalsIgnoreCase("n")){
                break;
            }
            System.out.println("请输入请求数量");
             count = sc.nextInt();
             writer.flush();
        }
        writer.close();
    }

    /**
     * 判断是不是安全状态的方法
     * @param people
     * @param count
     * @return
     */
    public static boolean judge(String people,Integer count){
        if (count > A) {
            return false;
        }
        //空闲的资源
        int spare = A - count;
        Set<String> keys = new HashSet<>(R.keySet());
        //用来计数已经满足的进程
        int cnt = 0;
        int size = keys.size();
        int i = 0;
        while ( true ) {
            Set<String> keys1 = new HashSet<>(keys);

//            keys1.addAll(keys);

            for(String key : keys1){
                //总的需要的资源
                Integer value = R.get(key);
                //目前需要的资源
                int need = 0;
                if (people .equals(key)){
                     need = value - C.get(key) - count;
                }else {
                     need = value - C.get(key);
                }
                //判断剩余的资源是否能够满足需要的资源
                if (need <= spare){
                    //如果满足的是当前请求的资源就走if,否则走else
                    if (people .equals(key)){
                        spare += count + C.get(key);
                    }else {
                        spare += C.get(key);
                    }
                    //移除已经满足的进程
                    keys.remove(key);
                    cnt++;
                }
                //如果满足的进程 = 所有的进程数,就直接返回
                if (cnt == size){
                    return true;
                }
            }
            //一旦cnt = i 就是这一次一个就没满足,所以就失败
            if (cnt == i ){
                return false;
            }
            i++;

        }
    }
}

参考


计算机操作系统(机械工业出版,那本黑皮书)

Last Modified: October 8, 2020