《操作系统》银行家算法（C语言版）

银行家算法简述

银行家算法是最有名的避免死锁的策略（区别于死锁的检测）。

该策略以银行的借贷策略为基础建立模型。系统掌握有限个数的资源，用于提供给不同的进程。如果所有进程都能得到他们需要得最大资源数，并运行完成、归还资源，则该系统是安全的。

算法流程描述

1、·首先对进行当前的系统状态进行初始化：先输入系统所拥有的每种资源的数量（Resource）、当前运行的进程对每种资源的最大需求量（MaxNeed）和每个进程已分配到的每种资源的数量（Allocation），就可以计算出每个进程还需要的资源量（Need）及系统还未分配的资源量(Available)。至此，对系统状态的初始化完成。

2、系统进行安全判定。这里用Work保存系统运行中Available的动态过程。

先将每个进程的状态（Finish）初始化为0。依次对比Need与Work中资源数目，当Work里的资源能够满足Need中某一进程对资源的需求量时，将Finish里该进程赋值为1，该进程转化为完成时。将该进程释放的资源给Work（Work[j] += Allocation[i][j];），保存进程下标。

若全部进程均运行完成，则系统处于安全状态，输出安全序列。

完整代码：

#include <stdio.h> 
#include <windows.h>

#define R 3  //资源数
#define P 4  //进程数

int Resource[R];//资源总量
int Available[R];//还剩下
int MaxNeed[P][R];//每个进程最大需要
int Allocation[P][R];//已分配
int Need[P][R];//还需要
int Work[R];//保存工作时剩余资源数量
int Finish[P];//保存工作过程中进程的状态
int SafeList[P];    //存放安全序列的下标序列 


//创建初始状态：先输入 Resource、MaxNeed和 Allocation，再计算出 Need、Available。   
void Initial(){

    int i, j;
    printf("请分别输入%d种资源的数量:\n",R);
    for (i = 0; i < R; i++) {

        scanf_s("%d", &Resource[i]);
        Available[i] = Resource[i];//目前还未分配，将资源总量与未分配数同步
    }
    printf("当前运行了%d个进程，请输入每个进程对应的%d种资源的最大需求量:\n",P,R);
    for (j = 0; j < P; j++)
        for (i = 0; i < R; i++)
            scanf_s("%d", &MaxNeed[j][i]);
    printf("请输入这%d个进程目前已分配的每种资源的数量:\n",P);
    for (j = 0; j < P; j++)
        for (i = 0; i < R; i++)
            scanf_s("%d", &Allocation[j][i]);

    //计算每个进程还需要的每种资源数量
    for (j = 0; j < P; j++)
        for (i = 0; i < R; i++)
            Need[j][i] = MaxNeed[j][i] - Allocation[j][i];

    //计算每种资源还剩下的资源总量 
    for (j = 0; j < R; j++)
        for (i = 0; i < P; i++)
            Available[j] = Available[j] - Allocation[i][j];

}


void Printf(int num[R]) {
    int j;

    for (j = 0; j < R; j++) {
        printf("%-4d",num[j]);
        }
    printf("|");
    }
//输出当前状态
void PrintState(){
 
    int i,j;
    printf("当前状态:\n|进程|最大需求    |已分配      |还需要      |还剩下      | \n");
    for (i = 0; i < P; i++){

        printf("|P%-3d|",i);
        Printf(MaxNeed[i]);
        Printf(Allocation[i]);
        Printf(Need[i]);
        if (i == 0) {
            Printf(Available);
            printf("\n");
            }
        else
            printf("            |\n");
      }
}


//返回同时满足1、Finish[i]=false;  2、Need[i][j]≤Work[j]的进程号 i，修改i的完成状态。
int Judge(){

    int i, j, num;//记资源满足数
    for (i = 0; i < P; i++){
        for (j = 0, num = 0; j < R; j++) {
            if (Finish[i] == 0 && Need[i][j] <= Work[j])
                num++;
                
            if (num == R){
                for (j = 0; j < R; j++)
                    Work[j] += Allocation[i][j];//获取已完成的进程释放的资源
                Finish[i] = 1;//修改状态
                return i;
                }
            }
    }
    return -1;
}


//检测当前状态是否为安全状态，如果是，保存安全序列
int Y_NSafe(){

    int i, SerialNum;
    int NUM = 0;//记进程满足数

    for (i = 0; i < R; i++)
        Work[i] = Available[i];//还剩下
    for (i = 0; i < P; i++)
        Finish[i] = 0;

    for (i = 0; i < P; i++){

        for (int j = 0; j < R; j++){
            if (MaxNeed[i][j] > Resource[j]) {
                printf("%d进程对%d资源的最大需求数量大于系统所拥有的%d资源总数!\n",i,j,j);
                }
            }
        for (int j = 0; j < R; j++) {
            if (Need[i][j] > MaxNeed[i][j]) {
                printf("您请求的%d资源大于%d进程对%d资源的最大需求\n",j,i,j);
                }
            }
        SerialNum = Judge();
        if (SerialNum != -1){
            SafeList[i] = SerialNum;
            NUM++;
        }
    }
    if (NUM == P)
        return 1;
    else
        return 0;
}


//输出安全序列
void printList(){

    int i0, i, j;
    printf("\n安全序列表如下:\n|进程|已分配      |还需要      |还剩下      |\n");
    for (j = 0; j < R; j++){
        Work[j] = Available[j];
    }
    for (i0 = 0; i0 < P; i0++) {
        for (j = 0; j < R; j++) {
            Work[j] += Allocation[SafeList[i0]][j];
            Allocation[SafeList[i0]][j] = 0;
            Need[SafeList[i0]][j] = 0;
            }
        for (i = 0; i < P; i++) {
            printf("|P%-3d|",i);
            Printf(Allocation[i]);
            Printf(Need[i]);
            if (i == 0) 
                Printf(Work);
            printf("\n");
            }
        printf("\n");
        }
}



int main(){

    int i;
    Initial();
    PrintState();// Resource[R];资源总量int MaxNeed[P][R];每个进程最大需要
   
    for (int j = 0; j < R; j++)
        if (Available[j] < 0)
            printf("已分配的 %d资源数量大于系统所拥有的该资源总量\n",j);

    if (Y_NSafe() == 0){

        printf("当前系统状态不安全\n");
    }else {

        printf("\n当前系统状态安全\n");
        printList();
    }
}