银行家算法

一、基本概念：

Dijkstra 的银行家算法是避免死锁最具有代表性的算法。起这样的名字是由于该算法原本是为银行系统设计的。以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可以用它来实现避免死锁。

二、数据结构：

（1）一个Available数组。这是一个含有M个元素的数组，其中的每一个元素均可代表可利用的资源数目。

（2）最大需求Max矩阵。这是一个n x m 的矩阵，它定义了系统中N个进程中，每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数组为K。

（3）分配矩阵Allocation。这也是一个n x m 的矩阵它定义了系统中每一类水资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程I 当前已分得Rj类资源的数目为K。

（4）需求矩阵Need。这也是一个n x m 的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个方能完成任务。

三、银行家算法实现：

设Request i是进程Pi的请求向量，如果Rquesti[j]=K,表示进程P需要K个Rj类型的资源。当Pi发出资源请求后，系统按以下步骤进行分配。

Available[j] = Available[j]-Request[j];
Allocation[i,j] = Allocation[i,j]+Request[j];
Need[i,j] = Need[i,j]-Requesti[j];

分配之后执行安全性算法检测：

安全性算法数据结构：

(1)设置一个工作向量Work 初始化为 Work = Available

(2)Finish 数组，表示系统是否有足够的资源分配给进程，使之运行完成。初始化为false，有足够资源分配给进程时再令Finish[i]=true;

安全性算法：

从进程集合中找出一个进程：满足下列条件：

1、Finish[I] = false;

2、Need[i,j] <= Work[j];

随后当进程Pi获得资源后，可顺利执行，直至完成，并释放出资源，因此需要执行：

Work[j] = Work[j]+Allocation[i,j]l;

Finish[i] = true;

然后重复以上步骤。

如果Finish数组均满足=true;则安全，否则不安全！

下面给出Javascript的实现代码。

<!DOCTYPE html>
<html>
<head>
    <title>银行家算法</title>
    <meta charset="UTF-8">
</head>
<script type="text/javascript">
    core=new Object();
    core.Max=[[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]];
    core.Allocation=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]];
    core.Need=[[7,4,3],[1,2,2],[6,0,0],[0,1,1],[4,3,1]];
    core.Available=[3,3,2];
    /*
        打印
    */
    function printCore(){
        document.write("<table border="1"><tr><th></th><th>Max</th><th>Allocation</th><th>Need</th><th>Available</th></tr>")
        for(var i=0;i<core.Max.length;i++){
            document.write("<tr>");
            document.write("<td>p"+i+"</td>");
            document.write("<td>"+core.Max[i]+"</td>");
            document.write("<td>"+core.Allocation[i]+"</td>");
            document.write("<td>"+core.Need[i]+"</td>");
            if(i==0){
                document.write("<td>"+core.Available+"</td>");
            }
            document.write("</tr>")
        }
        document.write("</table>")
    }
    /*
        request 第一次检验
    */
    function request1(p,request) {
        var sign;
        for (var i=0;i<core.Need.length;i++) {
            if(p==i){
                for(var j=0;j<core.Available.length;j++){
                    if(request[j]>core.Need[i][j]){
                        sign=1;
                        break;
                    }
                }
            }
        }
        if(sign==1){
            document.write("它所需要的资源数已经超过宣布的最大值");
        }else{
            request2(p,request);
        }
    }
    /*
        request 第二次检验
    */
    function request2(p,request){
        var sign;
        for(var i=0;i<core.Available.length;i++){
            if(request[i]>core.Available[i]){
                sign=1;
                break;
            }
        }
        if (sign==1) {
            document.write("尚无足够的资源，进程需要等待");
        }else{
            fenpei(p,request);
        }
    }
    /*
        尝试分配：
    */
    function fenpei(p,request){
        for (var i=0;i<core.Need.length;i++) {
            if(p==i){
                for(var j=0;j<core.Available.length;j++){
                    core.Available[j]=core.Available[j]-request[j];
                    core.Allocation[i][j] = core.Allocation[i][j]+request[j];
                    core.Need[i][j]=core.Need[i][j]-request[j];
                }
            }
        }
    }
    /*
        安全性检测
    */
    function secCheck(){
        var work = new Array();
        var works = new Array(core.Allocation.length);
        for(var i=0;i<works.length;i++){
            works[i] = new Array();
        }
        for(var i=0;i<core.Available.length;i++){
            work.push(core.Available[i]);
        }
        var Finish = new Array(core.Allocation.length);
        for(var i=0;i<Finish.length;i++){
            Finish[i]=false;
        }
        var find = 0;
        var arr = new Array();
        while(find!=-1){
            here: for (var i = 0; i < Finish.length; i++) {
                if (Finish[i]==false&&__sec(i,work)) {
                    find = i;
                    arr.push(find);
                    break here;
                } else {
                    find = -1;
                }
            }
            if (find != -1) {
                for (var j = 0; j < work.length; j++) {
                    work[j] = work[j] + core.Allocation[find][j];
                    Finish[find] = true;
                }
                for(var j=0;j<core.Available.length;j++){
                    works[find][j] = work[j];
                }
            }
        }
        for(var i=0;i<Finish.length;i++){
            if(Finish[i]==false) {
                document.write("<h3 style="color:#FF0000">安全性检测不通过！</h3>");
                return;
            }
        }
        document.write("<table border="1"><tr><th></th><th>Max</th><th>Need</th><th>Allocation</th><th>Work+Allocation</th><th>finish</th></tr>");
        for(var i= 0;i<Finish.length;i++){
            document.write("<tr>");
            document.write("<td>p"+arr[i]+"</td>")
            document.write("<td>"+core.Max[arr[i]]+"</td>");
            document.write("<td>"+core.Need[arr[i]]+"</td>");
            document.write("<td>"+core.Allocation[arr[i]]+"</td>");
            document.write("<td>"+works[arr[i]]+"</td>");
            document.write("<td>"+Finish[arr[i]]+"</td>");
            document.write("</tr>");
        }
        document.write("</table>");
    }
    function __sec(i,work){
        for(var j=0;j<work.length;j++){
            if(work[j]<core.Need[i][j]) return false;
        }
        return true;
    }
</script>
<body>
    <script type="text/javascript">
        document.write("<h3>T0时刻、初始化为：</h3>");
        printCore();
        document.write("<h3>T0时刻、安全检测结果为</h3>");
        secCheck();
        document.write("<h3>进程P1的request向量设置为：1，0，2。<h3>");
        request=[1,0,2];
        request1(1,request);
        document.write("<h3>T1分配后状态为：</h3>");
        printCore();
        secCheck();
        document.write("<h3>P4请求资源 request 向量设置为 3,3,0</h3>");
        request=[3,3,0];
        request1(4,request);
        document.write("<h3>p0请求资源，request向量设置为 0,2,0</h3>");
        request=[0,2,0];
        request1(0,request);
        printCore();
        secCheck();
    </script>
</body>
</html>

运行结果如下：

银行家算法-风君雪科技博客

银行家算法-风君雪科技博客