用Java实现的银行家算法

应操作系统老师的要求：下节课我们来一起讨论一下银行家算法的实现，银行家算法的优化，银行家算法在各个领域的具体实现方式和优化；上来讲的人，我会在他期末考试成绩上直接加5分。

 

这些可爽了我，虽然我已经可以加5分，但是争取吧，所以也些了个模拟银行家算法，但是...可惜，可惜...没上去讲，又不甘心自己就这样白写了，所以贴出来大家一起看看：

 

package com.littleworks.bankerAlgorithm;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Banker {

    List<Borrower> safeSequence = new ArrayList<Borrower>();
    List<Resource> resources = new ArrayList<Resource>();
    List<Borrower> borrowers = new ArrayList<Borrower>();

    /**
     * Constructor
     */
    Banker() {
        init();
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Banker banker = new Banker();
        banker.think();

    }

    /**
     * 初始化
     * 在这里添加借贷者和资源，可以手动在这里修改借贷者里的各个属性，可以设置allocation
     */
    private void init() {
        Resource resource1 = new Resource("resource1", 3);
        this.addResource(resource1);
        Resource resource2 = new Resource("resource2", 2);
        this.addResource(resource2);
        Borrower borrower1 = new Borrower("borrower1");
        this.addBorrower(borrower1);
        Borrower borrower2 = new Borrower("borrower2");
        this.addBorrower(borrower2);
    }

    /**
     * 往银行里增加资源的种类
     *
     * @param resource
     */
    public void addResource(Resource resource) {
        this.resources.add(resource);

        Borrower b = null;
        for (int i = 0; i < this.borrowers.size(); i++) {
            b = borrowers.get(i);
            b.need.put(resource, 0);
            b.allocation.put(resource, 0);
            b.max.put(resource, 0);
            b.request.put(resource, 0);
        }
    }

    /**
     * 往银行里增加借贷者的人数
     *
     * @param borrower
     */
    public void addBorrower(Borrower borrower) {

        int j = 0;
        for (int i = 0; i < resources.size(); i++) {
            j = 0;
            InputStreamReader isr = new InputStreamReader(System.in);
            System.out.println("请输入借贷者" + borrower.name + "对资源"
                    + resources.get(i).getName() + "请求的数量:");

            try {
                j = isr.read() - 48;
            } catch (IOException e) {
                e.printStackTrace();
            }

            borrower.need.put(resources.get(i), j);
            borrower.max.put(resources.get(i), j);
            borrower.allocation.put(resources.get(i), 0);
            borrower.request.put(resources.get(i), j);

        }

        this.borrowers.add(borrower);
    }

    /**
     * 银行家算法
     */
    public void think() {

        for (Borrower borrower : borrowers) {
            for (Resource resource : resources) {
                // 1. 如果request向量比need还大，则意味着出错：进程请求的资源多余它自身的需求量
                if (borrower.request.get(resource) > borrower.need
                        .get(resource)) {
                    System.out.println("好你小子，吃着碗里的看着锅里的是吧......看我不灭了你");
                    this.deleteBorrowerByName(borrower.name);
                }

                // 2. 如果request向量比系统目前有的资源量多，则不能满足，让你先等待
                else if (borrower.request.get(resource) > resource
                        .getAvailable()) {
                    System.out.println(borrower.name
                            + "，你先等一等，目前你的资源不能全部满足，我看看怎么分配比较好...");
                }
            }
        }

        List<Resource> work = new ArrayList<Resource>();
        for (Resource r : resources) {
            work.add(r);
        }
        List<Borrower> finish = new ArrayList<Borrower>();
        for (Borrower b : borrowers) {
            finish.add(b);
        }

        while (true) {

            boolean isOver = true;
            Resource resource = null;
            Borrower borrower = null;
            boolean has = true;
            out: for (int i = 0; i < finish.size(); i++) {
                borrower = finish.get(i);

                if (!borrower.status) {
                    for (int j = 0; j < work.size(); j++) {
                        resource = work.get(j);
                        if (finish.get(i).need.get(resource) > resource
                                .getAvailable()) {
                            has = false;
                            break;
                        }
                    }
                    if (has) {
                        break out;
                    }
                }
            }

            if (has && safeSequence.size() != finish.size()) {
                resource.setAvailable(resource.getAvailable()
                        + borrower.allocation.get(resource));
                borrower.status = true;
                safeSequence.add(borrower);
                System.out.println(borrower.name);
                continue;
            } else {

                for (Borrower b : safeSequence) {
                    if (!b.status) {
                        isOver = false;
                        break;
                    }
                }
                if (isOver && safeSequence.size() != 0) {
                    System.out.println("此状态安全！");
                } else
                    System.out.println("此状态不安全！");
                break;
            }
        }

    }

    /**
     * 根据名字从借贷者链表中删掉
     *
     * @param name
     */
    public void deleteBorrowerByName(String name) {
        int position = 0;
        for (; position < borrowers.size(); position++) {
            if (borrowers.get(position).name.equals(name)) {
                break;
            }
        }
        borrowers.remove(position);
    }
}

class Borrower {

    // 借贷者的名字
    String name;
    // 改借贷者当前是否完成任务, true为完成
    boolean status = false;

    // 当前还需要各种资源的数量
    Map<Resource, Integer> need = new HashMap<Resource, Integer>();

    // 对资源的最大请求量
    Map<Resource, Integer> max = new HashMap<Resource, Integer>();

    // 已经被分配的各资源量
    Map<Resource, Integer> allocation = new HashMap<Resource, Integer>();

    // 当前对银行请求的量
    Map<Resource, Integer> request = new HashMap<Resource, Integer>();

    Borrower(String name) {
        this.name = name;
    }
}

class Resource {
   
    // 资源的名字
    private String name;

    // 该资源可用量
    private int available;

    Resource(String name, int available) {
        this.available = available;
        this.name = name;
    }

    public int getAvailable() {
        return available;
    }

    public void setAvailable(int available) {
        this.available = available;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

 

 

这个还是有点问题的，因为我把借贷者的allocation都最开始就设置为了0，所以如果有安全序列，则安全序列输出的顺序一定是你往借贷者链表中加入的顺序，不过这完全可以改，在init方法中你可以自己手动设置各个借贷者的已分配的资源数量allocation

还有一个就是，也是由于初始化为0的缘故，就是条件1是永远都到不了的，也就是说:好你小子，吃着碗里的看着锅里的是吧......看我不灭了你，这句话永远不会输出，因为添加借贷者时，need和reuest都是被初始化为了同一个值，但是也是可以修改的，在init方法中你可以自己手动设置各个借贷者的request或者need

 

 

 

就写这些了，谢谢大家耐心的看！

评论

4 楼 sekiyika 2010-04-26  

rchild 写道

这样你操作系统不几乎满分？

呃……还好吧~最后是94，呵呵

3 楼 rchild 2010-04-23  

这样你操作系统不几乎满分？

2 楼 sekiyika 2009-04-23  

jmu 写道

下次一定要上去讲，不要给任何人机会！ 任何人！

e...好吧，听你的，不要给别人机会
不给别人机会就是对自己的仁慈！

1 楼 jmu 2009-04-23  

下次一定要上去讲，不要给任何人机会！ 任何人！