银行家算法学习笔记

银行家算法是经典的死锁避免算法，由两个部分构成。

所需要的数据结构：（n是系统中的进程数量，m是资源类型的数量）

Available：长度为m的向量，表示当前系统各资源的可用数量。Available[j]==k，表示类型为j的资源 ，可用数量为k。

Max：nxm的矩阵，表示所有进程对资源的最大需求量。Max[i][j]==k，表示进程Pi对类型为j的资源的最大需求量为k。

Allocation：nxm的矩阵，表示当前时刻，进程所占有的资源情况。Allocation[i][j]==k，表示进程Pi当前占有k个j类型的资源。

Need：nxm的矩阵，表示进程对资源的申请情况。Need[i][j]==k，表示进程Pi还需要k的j类型的资源才能完成它的工作。注意，

Need[i][j]=Max[i][j]-Allocation[i][j]。

我们可以将Need，Max，Allocation这些二维数组的每一行看作是一个向量，Need[i]表示进程Pi还需要申请的资源数量，Max[i]表示Pi对资源的最大需求数量。

一、安全算法

1. 创建向量Work和Finish，长度分别为m和n。初始化Work=Available，Finish[i]=false, for i = 0,1,...,n-1

2. 在进程集合P中寻找一个满足以下两个条件的i：

　　1) Finish[i] == false

　　2) Need[i] <= Work（Need[i]的每一个分量都小于等于Work的每一个分量）

    如果没有这样的i存在或者集合P为空，跳到步骤4

3. Work = Work + Allocation[i];

    Finish[i] = true;

    P - {Pi};

4. 如果对于所有i，Finish[i] == true，则系统是安全的，否则是不安全的。

C++代码：

#include <stdio.h>
#define M 3
#define N 5
int Available[M] = {3,3,2};
int Max[N][M] = {
    {7,5,3},
    {3,2,2},
    {9,0,2},
    {2,2,2},
    {4,3,3}
};
int Allocation[N][M] = {
    {0,1,0},
    {2,0,0},
    {3,0,2},
    {2,1,1},
    {0,0,2}
};

int Need[N][M];

void initNeed() {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            Need[i][j] = Max[i][j] - Allocation[i][j];
        }
    }
}

bool isLessAndEqual(int Need[], int Work[]) {
    int result = 0;
    for (int j = 0; j < M; j++) {
        if (Need[j] > Work[j])
            return false;
    }
    return true;
}

void addTo(int to[], int from[]) {
    for (int i = 0; i < M; i++) {
        to[i] += from[i];
    }
}

// 判断当前系统是否处于安全状态，看能否找出一个安全序列
bool isSafe() {
    int Work[M];
    bool Finish[N] = {false};
    for (int i = 0; i < M; i++) {
        Work[i] = Available[i];
    }
    printf("正在判断系统是否安全：\n");
    int counter = N;
    bool found;    // 标记遍历一次是否有找到可以分配的进程，如果没有则退出循环，不需再继续遍历
    while (counter > 0) {
        found = false;
        for (int i = 0; i < N; i++) {
            if (!Finish[i] && isLessAndEqual(Need[i], Work)) {
                addTo(Work, Allocation[i]);
                Finish[i] = true;
                counter--;
                printf("%d ", i);
                found = true;
            }
        }
        if (found == false)
            break;
    }
    printf("\n");
    for (int i = 0; i < N; i++)     {
        if (!Finish[i])
            return false;
    }

    return true;
}

int main()
{
    initNeed();
    if (isSafe()) {
        printf("安全！\n");
    } else {
        printf("不安全！\n");
    }

}

 二、资源分配算法

令Request[i]表示进程Pi的请求向量，Request[i][j] == k表示Pi请求k个类型为j的资源，当进程申请资源时执行以下步骤：

1. 如果Request[i] <= Need[i]，跳到步骤2，否则抛出错误，因为Pi的请求数量已经超过了它的最大资源需求数。

2. 如果Request[i] <= Available，跳到步骤3，否则Pi进入等待状态，因为没有足够多的资源。

3. 假定系统可以分配给进程Pi所请求的资源，并按以下方式修改状态：

　　Available = Available - Request[i];

　　Allocation[i] = Allocation[i] + Request[i];

　　Need[i] = Need[i] - Request[i];

   此时判断系统是否处于安全状态，如果是则事务结束，进程Pi可以分配到所需要的资源。否则Pi必须等待，且各数据结构恢复到之前的状态。