实验五---银行家算法的模拟与实现

银行家算法

作者：葛帅帅
学号：1405010304
班级：三班

1、实验目的

(1) 进一步了解进程的并发执行。
(2) 加强对进程死锁的理解。
(3) 掌握使用银行家算法避免死锁问题。

2、实验内容

本实验的内容是要通过编写和调试一个模拟系统动态分配资源的银行家算法程序，有效地防止
和避免死锁发生。具体要求如下：
（1） 初始化时让系统拥有一定的资源；
（2） 用键盘输入的方式允许进程动态申请资源；
（3） 如果预分配后，系统处于安全状态，则修改系统的资源分配情况，正式分配资源；
（4） 如果预分配后，系统处于不安全状态，则提示不能满足请求，恢复原状态。银行家算法. 顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不当，就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进在整个执行过程中总共要申请的资源量。显然，每个进程的资源求总量不能超过系统拥有的资源总数,使用银行算法进行资源分配可以避免死锁.

3、 银行家算法中的数据结构与流程图

数据结构
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。
4）需求矩阵Need.
这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=k,则表示进程i还需要Rj类资源k个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
流程图（见图5-8）

4、 银行家算法编程实现

源程序 main.c

#include <stdio.h>
#include <string.h>
#include "banker.h"
//试探分配
void ProbeAlloc(int process,RESOURCE *res)
{
    Available.A -= res->A;
    Available.B -= res->B;
    Available.C -= res->C;
    Allocation[process].A += res->A;
    Allocation[process].B += res->B;
    Allocation[process].C += res->C;
    Need[process].A -= res->A;
    Need[process].B -= res->B;
    Need[process].C -= res->C;
}
//若试探分配后进入不安全状态，将分配回滚
void RollBack(int process,RESOURCE *res)
{
    Available.A += res->A;
    Available.B += res->B;
    Available.C += res->C;
    Allocation[process].A -= res->A;
    Allocation[process].B -= res->B;
    Allocation[process].C -= res->C;
    Need[process].A += res->A;
    Need[process].B += res->B;
    Need[process].C += res->C;
}
//安全性检查
bool SafeCheck()
{
    RESOURCE    Work = Available;
    bool        Finish[PROCESSES_NUMBER] = {false,false,false,false,false};
    int     i;
    int     j = 0;
    for (i = 0; i < PROCESSES_NUMBER; i++)
    {
        //是否已检查过
        if(Finish[i] == false)
        {
            //是否有足够的资源分配给该进程
            if(Need[i].A <= Work.A && Need[i].B <= Work.B && Need[i].C <= Work.C)
            {
                //有则使其执行完成，并将已分配给该进程的资源全部回收
                Work.A += Allocation[i].A;
                Work.B += Allocation[i].B;
                Work.C += Allocation[i].C;
                Finish[i] = true;
                safe[j++] = i;
                i = -1;             //重新进行遍历
            }
        }
    }
    //如果所有进程的Finish向量都为true则处于安全状态，否则为不安全状态
    for (i = 0; i < PROCESSES_NUMBER; i++)
    {
        if (Finish[i] == false)
        {
            return false;
        }
    }
    return true;
}
//资源分配请求
bool request(int process,RESOURCE *res)
{
    //request向量需小于Need矩阵中对应的向量
    if(res->A <= Need[process].A && res->B <= Need[process].B && res->C <= Need[process].C)
    {
        //request向量需小于Available向量
        if(res->A <= Available.A && res->B <= Available.B && res->C <= Available.C)
        {
            //试探分配
            ProbeAlloc(process,res);
            //如果安全检查成立，则请求成功，否则将分配回滚并返回失败
            if(SafeCheck())
            {
                return true;
            }
            else
            {
                printf("安全性检查失败。原因：系统将进入不安全状态，有可能引起死锁。\n");
                printf("正在回滚...\n");
                RollBack(process,res);
            }
        }
        else
        {
            printf("安全性检查失败。原因：请求向量大于可利用资源向量。\n");
        }
    }
    else
    {
        printf("安全性检查失败。原因：请求向量大于需求向量。\n");
    }
    return false;
}
//输出资源分配表
void PrintTable()
{
    printf("\t\t\t*********资源分配表*********\n");
    printf("Process       Max          Allocation          Need          Available\n");
    printf("          A    B    C     A    B    C       A    B    C      A    B    C\n");
    printf("  P0      %d    %d    %d     %d    %d    %d       %d    %d    %d      %d    %d    %d\n",Max[0].A,Max[0].B,Max[0].C,Allocation[0].A,Allocation[0].B,Allocation[0].C,Need[0].A,Need[0].B,Need[0].C,Available.A,Available.B,Available.C);
    printf("  P1      %d    %d    %d     %d    %d    %d       %d    %d    %d\n",Max[1].A,Max[1].B,Max[1].C,Allocation[1].A,Allocation[1].B,Allocation[1].C,Need[1].A,Need[1].B,Need[1].C);
    printf("  P2      %d    %d    %d     %d    %d    %d       %d    %d    %d\n",Max[2].A,Max[2].B,Max[2].C,Allocation[2].A,Allocation[2].B,Allocation[2].C,Need[2].A,Need[2].B,Need[2].C);
    printf("  P3      %d    %d    %d     %d    %d    %d       %d    %d    %d\n",Max[3].A,Max[3].B,Max[3].C,Allocation[3].A,Allocation[3].B,Allocation[3].C,Need[3].A,Need[3].B,Need[3].C);
    printf("  P4      %d    %d    %d     %d    %d    %d       %d    %d    %d\n",Max[4].A,Max[4].B,Max[4].C,Allocation[4].A,Allocation[4].B,Allocation[4].C,Need[4].A,Need[4].B,Need[4].C);
    printf("\n");
}
int main()
{
    int ch;
    printf("先检查初始状态是否安全。\n");
    if (SafeCheck())
    {
        printf("系统处于安全状态。\n");
        printf("安全序列是{P%d,P%d,P%d,P%d,P%d}。\n",safe[0],safe[1],safe[2],safe[3],safe[4]);
    }
    else
    {
        printf("系统处于不安全状态。程序将退出...\n");
        goto over;
    }
    do 
    {
        int     process;
        RESOURCE    res;
        PrintTable();
        printf("请依次输入请求分配的进程和对三类资源的请求数量：");
        scanf("%d%d%d%d",&process,&res.A,&res.B,&res.C);
        if (request(process,&res))
        {
            printf("分配成功。\n");
            printf("安全序列是{P%d,P%d,P%d,P%d,P%d}。\n",safe[0],safe[1],safe[2],safe[3],safe[4]);
        }
        else
        {
            printf("分配失败。\n");
        }
        printf("是否继续分配？(Y/N):");
        fflush(stdin);              //虽然C标准不支持这种用法，但是VC++支持
        ch = getchar();
    } while (ch == 'Y' || ch == 'y');
over:
    printf("执行完毕。");
    return 0;
}

头文件 banker.h
定义一个结构体
数据初始化三个矩阵和一个向量。

typedef int bool;
#define false 0
#define true !false
//系统中所有进程数量
#define PROCESSES_NUMBER    5
typedef struct {
    int A;
    int B;
    int C;
}RESOURCE;
//最大需求矩阵
RESOURCE Max[PROCESSES_NUMBER] = 
{
    {7,5,3},
    {3,2,2},
    {9,0,2},
    {2,2,2},
    {4,3,3}
};
//已分配资源数矩阵
RESOURCE Allocation[PROCESSES_NUMBER] = 
{
    {0,1,0},
    {2,0,0},
    {3,0,2},
    {2,1,1},
    {0,0,2}
};
//需求矩阵
RESOURCE Need[PROCESSES_NUMBER] = 
{
    {7,4,3},
    {1,2,2},
    {6,0,0},
    {0,1,1},
    {4,3,1}
};
//可用资源向量
RESOURCE Available = {3,3,2};
int safe[PROCESSES_NUMBER];

5、 实验结果与分析

运行结果见图 5-9

6、 实验总结

了解避免死锁方法--银行家算法
首先要定义一些结构体
结构体里面的三个域分别表示三种资源的数量。
数据初始化三个矩阵和一个向量。
为了能够输出安全状态时的安全序列，还可以添加一个记录安全序列的数组int SafeSequence[PROCESSED_NUMBER]。

　　因为银行家算法使用的是试探分配的策略，如果进程请求分配的资源既不大于自己尚需的资源，又不大于系统现存的资源，那就可以先试探着将资源分配给该进程，然后测试分配后是不是有可能造成死锁，如果不会引起死锁（即安全状态）就可以完成分配，否则（即不安全状态）就将试探分配的资源回收回来让其等待。那么根据上面定义的数据就可以很容易的写出试探分配和回收资源的函数。
　　接下来就是安全性检查函数了，在这个函数中还需要设置一个Work向量和一个Finish向量，函数实现主要就是通过一个for循环检查试探分配后系统的可用资源数是否能满足所有进程的需求，若能满足某一个进程的需求，则假设分配其所需资源使之完成运行，然后就可以将资源回收以分配给其它进程，如果依照这种方法所有的进程都可以成功执行，那么现在的状态就是安全状态，否则即为不安全状态，有可能引起死锁。
　　有了以上三个函数就可以写出请求分配资源的函数了。