银行家算法

临近期末，加上感觉没啥写的，就只能水一水了（不，读书人的事情，怎么能说水呢@(你懂的)）

前言

---

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

银行家算法

---

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

运行结果展示

---

代码展示

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

[collapse title="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++;

        }
    }
}

[/collapse]

参考

---

计算机操作系统（机械工业出版，那本黑皮书）