实验二、银行家算法

一、目的与要求

1）本实验目的是通过使用银行家算法实现系统资源的分配和安全性检查模拟，提高学生对操作系统资源分配功能的深刻理解；

2）实验前必须认真阅读和理解银行家算法的基本原理和实现方法；

3）独立使用C或VC++编程语言编写银行家算法模拟程序；

4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）

二、实验内容或题目

1）设计五个进程{P0，P1，P2，P3，P4}共享三类资源{A，B，C}的系统，{A，B，C}的资源总数量分别为10，5，7。（参考书上用例）

2）并行进程可动态地申请资源和释放资源（程序交互输入申请或释放资源数量），系统按各进程的申请动态地分配资源。

3）每当进程动态申请资源或释放资源时，模拟程序应能及时显示或打印各个进程在此时刻的资源分配表、系统可用资源量和安全序列等资源分配信息和安全检查信息。

三、详细分析

该模拟系统主要使用银行家算法实现系统资源的分配和安全性检查，

• 主要的数据结构如下：

max[]:进程的最大需求；

Allocation[][]:已经为进程分配的资源数

Need[]：进程还需要的资源数

Available[][]:系统还剩下的资源数

Work_all[]：存储每个进程的work

Work_sum: 存储每个进程的work+allocation

编写了4个主要的函数：

bank_calculate(int ,int[])是银行家算法;

check()是安全性检查；

print()是打印系统的资源分配情况；

print1(int [], int[])是打印安全性检查情况；

????????1、bank_calculate(int ,int[]) (银行家算法)

? ? ? ?（1） 首先系统对请求进行验证，满足request<=need且request<=available ,都成立系统进入试分配，否则请求失败(即如果请求量>进程还需要的资源数，则报错 请求失败；请求量>系统可用资源，进程阻塞，请求失败）；????????

????（2）系统进入试分配，先对原先的资源数进行临时保存，然后修改相应的数据结构：available=available-request、allocation=allocation+request、need=need-request,再进入安全性检查；????????

? ? ? （3）在安全性检查中返回? r=1指找到一条安全序列，进行正式分配，同时检查该进程所需的资源是否全部分配，如果是就释放该进程的所有资源，该进程结束；若r=0指找不到一条安全序列，撤销试分配，恢复系统原先资源。

????????2、check()是安全性检查

（1） 初始化数据?finish[]=false，work[]=available[]，寻找符合条件的进程，只有当finish[i]=false 且need[][]<=work[] 都成立时将该进程号存放到list[]（存放安全序列），同时修改数据finish[]=true,work=work+allocation,再保存数据当前进程的work和work+allocation ?(即work_all=work和work_sum=work+allocation )；

（2）如果finish全为true，则r=1 代表成功找到一条安全序列，否则r=0 代表找不到一条安全的序列。

????????3、print()是打印系统的资源分配情况

????????4、print1(int [], int[])是打印安全性检查情况

四、源代码

详细源代码如下（c语言版）

/*need 还需要的资源数，work=work+allocation（已经分配的资源），request，进程请求的资源数
MAX是进程的最大需求，allocation（已经分配的资源），need 还需要的资源数，available 是还剩下的资源数
如果work<need
银行家算法：
request<=Need and request<=availabe true--->
need[i][j]=max-allocation
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string>
#include <unistd.h>

#define m 100 //数组最大下标

void input();

void bank_calculate(int, int[]);

void check();

void print(); //打印资源数

void print1(int[], int[]); //打印安全状态表
int p_sum;                 //进程数

int m_sum; //资源数

int r; //用于判断系统是否安全

//可手动输入初始化
//每个进程的最大资源数
int max[m][m];

// allocation:每个进程已经分配的资源
int allocation[m][m];

// need 每个进程还需要的资源数
int need[m][m];

// available 是还剩下的总的资源数
int available[m];

bool finish[m];

int work_all[m][m];

int work_sum[m][m];

//固定初始值初始化
// int p_sum = 5; //进程数
// int m_sum = 3; //资源数
// int r;         //用于判断系统是否安全

// //每个进程的最大资源数
// int max[5][3] = {
//     {7, 5, 3},
//     {3, 2, 2},
//     {9, 0, 2},
//     {2, 2, 2},
//     {4, 3, 3}};
// // allocation:每个进程已经分配的资源
// int allocation[5][3] = {
//     {0, 1, 0},
//     {2, 0, 0},
//     {3, 0, 2},
//     {2, 1, 1},
//     {0, 0, 2}};
// // need 每个进程还需要的资源数
// int need[5][3] = {
//     {7, 4, 3},
//     {1, 2, 2},
//     {6, 0, 0},
//     {0, 1, 1},
//     {4, 3, 1}};
// // available 是还剩下的总的资源数
// int available[3] = {3, 3, 2};

// bool finish[3];

// int work_all[5][3];

// int work_sum[5][3];

int main()
{
    printf("***********************************************************************************************\n");
    printf("\n");
    printf("*                                    银行家算法的设计与实现                                   *\n");
    printf("\n");
    printf("***********************************************************************************************\n");
    int pno; // i表示输入请求的进程序号，
    char c;  //输入Y/N

    // int request[3];
    int request[m];
    printf("\n\n初始化数据：\n\n");
    input(); // 输入数据
    print(); //输出已知道的数据
    printf("\n**提示:检查初始化系统是否安全中...\n");
    sleep(1); //休眠1秒
    check();  //检测TO时刻已知条件的安全状态

    /*---只有初始进程都处于安全状态时才能请求进程所需的资源--*/
    if (r == 1)
    {
        printf("\n\n\n***************初始化T0时刻系统内的进程是安全状态的,下面模拟进程资源的请求**************************\n");
        do
        {

            printf("\n请输入请求资源的进程序号(0~%d): ", p_sum - 1);
            scanf("%d", &pno); //输入请求进程号

            /*------判断输入是否正确-------------*/
            while (pno >= p_sum)
            {
                printf("\n");
                printf("输入错误,请重新输入: ");
                scanf("%d", &pno); //输入请求进程号
            }

            /*---------输入请求的资源数---------*/
            printf("\n请输入p%d进程所请求的资源数request[]: ", pno);
            for (int j = 0; j < m_sum; j++)
                scanf("%d", &request[j]);

            /*---------调用银行家算法--------------*/
            bank_calculate(pno, request);

            printf("\n是否还需要继续分配？ (Y or N ?)\n");
            scanf("%s", &c);
            printf("\n");
        } while (c == 'Y' || c == 'y');
    }

    system("pause");

    return 0;
}

void input()

{

    int i, j;

    printf("请输入进程总数: "); // P1、P2、P3等

    scanf("%d", &p_sum);

    printf("请输入资源种类数: "); // A、B、C等

    scanf("%d", &m_sum);

    printf("请输入Max矩阵:\n");

    for (i = 0; i < p_sum; i++)

        for (j = 0; j < m_sum; j++)

            scanf("%d", &max[i][j]); //输入已知进程最大资源需求量

    printf("请输入Allocation矩阵:\n");

    for (i = 0; i < p_sum; i++)

        for (j = 0; j < m_sum; j++)

            scanf("%d", &allocation[i][j]); //输入已知的进程已分配的资源数

    // printf("need矩阵为:\n");

    for (i = 0; i < p_sum; i++)

        for (j = 0; j < m_sum; j++)

            need[i][j] = max[i][j] - allocation[i][j]; //根据输入的两个数组计算出need矩阵的值

    printf("请输入可用资源数Available[i]: ");

    for (i = 0; i < m_sum; i++)

        scanf("%d", &available[i]); //输入己知的可用资源数
}

/*--------银行家算法-------*/
void bank_calculate(int pno, int request[3])
{
    //存放资源的原始值保存原已分配的资源数，临时存储信息
    // int allocation_1[5][3];
    // int need_1[5][3];
    // int available_1[3];
    int allocation_1[m][m];
    int need_1[m][m];
    int available_1[m];

    int flag = 1; //哨兵，代表可以预分配系统资源
    int j;        //循环

    /*比较两个*/
    /*-------比较请求量与需求量need--------*/
    for (j = 0; j < m_sum; j++)
    {
        if (request[j] > need[pno][j])
        {
            flag = 0;
            printf("\n**提示：请求资源超过该进程资源需求量,请求失败!\n");
            break;
        }
    }

    /*------ 比较请求量和系统可用资源------*/
    for (j = 0; j < m_sum; j++)
    {
        if (request[j] > available[j])
        {
            flag = 0;
            printf("\n**提示：系统暂时没有足够的资源分配,进程进入阻塞!\n\n");
            break;
        }
    }

    if (flag)
    {
        /*都满足先保存原来已经分配的资源数，需要的资源数，可用的资源数等*/
        for (j = 0; j < m_sum; j++)
        {
            available_1[j] = available[j];
            allocation_1[pno][j] = allocation[pno][j];
            need_1[pno][j] = need[pno][j];

            /*----------系统尝试把资源分配给请求的进程----------*/
            available[j] = available[j] - request[j];
            allocation[pno][j] += request[j];
            need[pno][j] = need[pno][j] - request[j];
        }

        printf("\n-------尝试分配后的有关资源数据--------\n");
        /*-------------打印---------------*/
        print();

        printf("\n**提示：检查分配后系统是否安全中......\n");
        /*-----------检测分配后的安全性-----------*/
        sleep(1);
        check();

        if (r == 0) //如果分配后系统不安全
        {
            //还原已分配的资源数仍需要的资源数和可用的资源数
            for (j = 0; j < m_sum; j++)
            {
                available[j] = available_1[j];
                allocation[pno][j] = allocation_1[pno][j];
                need[pno][j] = need_1[pno][j];
            }
            printf("\n\n提示：即将返回分配前资源数......\n");
            sleep(1);
            print();
        }
        /*------------安全，查看是否需要释放资源-----------*/
        else if (r == 1)
        {
            int flag = 1; //哨兵，为1代表该进程所需要的资源全为零，需要释放该资源
                          /*------判断该进程所需要的资源是否全为零--*/
            for (int j = 0; j < m_sum; j++)
            {
                if (need[pno][j] != 0)
                {
                    flag = 0; //哨兵，为0代表该进程所需要的资源至少有一个不为0，不能释放该资源
                    break;
                }
            }

            /*-------释放资源-------*/
            if (flag == 1)
            {
                for (int j = 0; j < m_sum; j++)
                {
                    available[j] += allocation[pno][j];
                    allocation[pno][j] = 0;
                }
            }
            printf("\n\n提示：此时系统内的资源数如下：\n");
            print();
        }
    }
}

void check()
{
    //先赋初始值，work=available,finish=false
    //然后开始寻找符合条件的进程

    int f;       //哨兵
    int v = 0;   // list数组下标
    int k, i, j; //循环
    // int list[5]; //存储安全序列
    // int work[3];

    int list[m]; //存储安全序列
    int work[m];

    /*赋初值*/
    r = 1; //
    for (i = 0; i < p_sum; i++)
        finish[i] = false; //初始化进程均没得到足够资源数并完成
    // 初始work[i]=available[i]
    for (i = 0; i < m_sum; i++)
        work[i] = available[i];

    //寻找符合条件的进程
    for (k = 0; k < p_sum; k++) //趟数，搜索的趟数，一趟最少可能找到一个
    {
        for (i = 0; i < p_sum; i++) //第i个进程,如果该进程不行就i++找下一个进程
        {
            if (finish[i] == false)
            {
                f = 1;

                /*当前的进程所需要的与工作向量work的每个值比较*/
                for (j = 0; j < m_sum; j++)
                {
                    if (need[i][j] > work[j])
                    {
                        f = 0;
                        break;
                    }
                }

                //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程
                if (f == 1)
                {
                    finish[i] = true;
                    list[v] = i; //记录安全序列号
                    v = v + 1;

                    memcpy(work_all[i], work, sizeof(work)); //将数组work赋给work_all

                    for (j = 0; j < m_sum; j++)
                    {
                        // printf("\n\n----work和allocation[i][j]是：%d和%d\n", work[j], allocation[i][j]);
                        work[j] = work[j] + allocation[i][j];
                    }

                    memcpy(work_sum[i], work, sizeof(work)); //将数组work赋给work_sum
                }
            }
        }
        //提前找到了全部
        if (m == p_sum)
        {
            break;
        }
    }

    //判断是否所有的进程都完成
    f = 1;
    for (i = 0; i < p_sum; i++) //
    {
        if (finish[i] == false)
        {
            f = 0;
            break;
        }
    }

    if (f == 0)
    {
        printf("\n系统处在不安全状态!\n");

        r = 0;
    }

    else
    {
        printf("\n系统当前为安全状态,安全序列为: ");
        for (int i = 0; i < p_sum; i++)
        {
            printf("p%d, ", list[i]);
        }
        printf("\n");
        //打印安全性检查信息
        print1(work, list);
    }
}

void print()
{
    int i, j;
    printf("\n");
    printf("----------------------------------此时刻资源分配情况---------------------------------------------\n");
    printf("|    进程名    |     Max     |   Allocation   |    Need    |    Available    |\n");

    for (i = 0; i < p_sum; i++)
    {
        printf("       p%d         ", i, i);

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", max[i][j]);
        }
        printf("\t ");

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", allocation[i][j]);
        }
        printf("\t ");

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", need[i][j]);
        }
        printf("\t ");

        if (i == 0) //第一个

        {

            for (j = 0; j < m_sum; j++)

                printf("%d   ", available[j]);
        }

        printf("\n");
    }
    printf("-------------------------------------------------------------------------------------------------\n");
}

void print1(int work[m], int list[m])
{

    int i, j, k;
    printf("\n");
    printf("--------------------------------------此时刻安全性检查情况-----------------------------------------\n");
    printf("|    进程名    |     work     |   Allocation   |    Need    |    work+Allocation    |    Finish    |\n");

    for (k = 0; k < 5; k++)
    {
        i = list[k];
        printf("       p%d         ", i);

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", work_all[i][j]);
        }
        printf("\t ");

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", allocation[i][j]);
        }
        printf("\t ");

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", need[i][j]);
        }
        printf("\t ");

        for (j = 0; j < m_sum; j++)
        {
            printf("%d   ", work_sum[i][j]);
        }
        printf("\t\t ");

        if (finish[i])
        {
            printf("true   ");
        }
        else
        {
            printf("false  ");
        }

        printf("\n");
    }
    printf("---------------------------------------------------------------------------------------------------\n");
}

五、运行效果图

（1）初始化输入：

输入后的检查结果：

?

（2）当进程0请求资源，request为1 0 4时，请求失败，结果如下：

（3）当进程0请求资源，request为1 0 2时，无安全序列，请求失败，结果如下：

（4）当进程1请求资源，request为1 0 2时 ，请求资源成功， 结果如下：

（5）当进程1再次请求资源，request为0 2 0时 ，请求资源成功，此时进程p1的need[]都为0，进程p1所需的资源都已分配，当进程p1执行完毕后，需要释放系统为其分配的所有资源，need和allocation都置为0， 结果如下：

?

六、总结

????????通过此次使用银行家算法模拟系统资源的分配和安全性检查，对于银行家算法的基本过程更加清晰，理解也更加透彻。但在实验过程中发现几个需要注意的问题：

????????首先，在系统对请求资源验证通过时，一定要使用临时数组先对原先资源数据保存，防止在安全性检查时因找不到安全序列，导致原先资源数据的丢失；其次，当某个进程的need[]都为0时，表示该进程所需的资源都已分配，当进程执行完毕后应该释放分配给该进程的所有资源。