银行家算法

设计目的

1. 银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
2. 在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
3. 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

数据结构

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

1. 可利用资源向量 Available[m]。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
2. 最大需求矩阵Max[n][m]。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
3. 分配矩阵Allocation[n][m]。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。
4. 需求矩阵Need[n][m].这也是一个n × m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
   通过各矩阵的描述，我们可以得到下述关系:
   　　　　　　　　　　　　　　Need[i,j] = Max[i,j] - allocation[i, j]

算法详述

设Request[m]是进程Pi的请求向量，如果 Requesti[j] = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査:

1. 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
2. 如果 Requesti[j] ≤ Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
3. 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值
   　　　　Available[j] = Available[j] - Requesti[j];
   　　　　Allocation[i,j] = Allocation[i,j] + Requesti[j];
   　　　　Need[i,j] = Need[i,j] - Requesti[j];
4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法

系统所执行的安全性算法可描述如下:

1. 设置两个向量:
   1. 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work[m] = Available[m]；
   2. Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] = -1；当有足够资源分配给进程时，再令Finish[i] = 分配的顺序。最后所得到的Finish[m]就是安全序列
2. 从进程集合中找到一个能满足下述条件的进程
   1. Finish[i] = -1;
   2. Need[i,j] ≤ Work[j];
   3. 若找到，执行步骤(3)，否则，执行步骤(4)。
3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
   1. Work[j] = Work[j] + Allocation[i,j];
   2. Finish[i] = true;
   3. go to step 2;(goto语句不推荐使用，可以通过while循环)
4. 如果所有进程的 Finish[i] =true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

设计流程

设计说明

废弃方案

1. 网上诸多算法均是将Finsh数组当做Bool型进行信息记录，此处算法进行了修改（好像是负向优化，分配的空间增加了）。我们可以试着思考一下，在寻找安全序列的过程中，肯定需要遍历n次，如果是安全序列，每次遍历肯定能修改一个Finish值。如果在某次遍历中，未对Finish修改，可以直接得知该请求不安全，则返回结果，未能找到安全序列。
2. 前提假设：进程一旦达到Max需求量，那么在下次请求之前将会释放占用的资源，换言之，Available[m]数组值会发生修改。
3. 设置一个Unfinished[n + 1]的vector，用来记录未完成的进程信息。Unfinished[0]记录未完成进程数。相当于进程的索引数组（或者理解为阻塞队列）。个人感觉更正确的方法是直接从MAXSIZE等矩阵动手，这样才能真正意义上的释放空间，但这难度较高，可能算法复杂度也比较高，这里不做这种操作。

方案实现

1. 新增flag[n]数组，用来记录某进程是否已经完成，一旦完成的进程会释放占有的资源并不会在之后的信息打印栏中出现。
2. 新增safeSeries一维数组用来存放安全序列，数组长度虽程序运行而变化。
3. 新增num，用来记录进程完成的数量。
4. 在寻找安全序列的过程中，肯定需要遍历n次，如果是安全序列，每次遍历肯定能修改一个Finish值。如果在某次遍历中，未对Finish修改，可以直接得知该请求不安全，则返回结果，未能找到安全序列。

代码展示

源码

#include <iostream>
using namespace  std;

const int MAX_PROCESS = 100;
const int MAX_RESOURCE = 100;
int n; //记录进程数
int m; //记录资源数
int Max[MAX_PROCESS][MAX_RESOURCE]; //记录进程所需最大资源数
int Allocation[MAX_PROCESS][MAX_RESOURCE]; //记录进程已分配的资源数
int Need[MAX_PROCESS][MAX_RESOURCE]; //记录进程还需分配的资源数
int Available[MAX_RESOURCE]; //记录可用资源数
int Request[MAX_RESOURCE]; //记录请求的资源数
bool Finish[MAX_PROCESS]; //安全判断辅助数组
bool flag[MAX_PROCESS]; //记录进程是否完成
int safeSeries[MAX_PROCESS]; // 记录进程
int sum = 0; //记录已完成的进程数


void printfInfo(){ // 打印系统信息
    cout << "系统当前可用的资源：" << endl;
    for (int i = 0; i < m; ++i)
        cout << Available[i] << " ";
    cout << endl;
    cout << "系统当前未完成的进程资源分配情况如下：" << endl;
    cout << "   PID    " << "  Max   " << "   Allocation   " << "  Need   " << endl;
    for (int i = 0; i < n; ++i)
    {
        if (flag[i])
        {
            cout << "   P" << i << "     ";
            for (int j = 0; j < m; ++j)
                cout << Max[i][j] << "  ";
            cout << '\t';
            for (int j = 0; j < m; ++j)
                cout << Allocation[i][j] << "  ";
            cout << '\t';
            for (int j = 0; j < m; ++j)
                if (flag[i])
                    cout << Need[i][j] << "  ";
            cout << endl;
        }
    }
}

bool  cmp(int a[], int b[]){ // 比较函数，如果a < b, 返回true
    for (int i = 0; i < m; ++i)
        if (a[i] > b[i])
            return false;
    return true;
}

bool safe(){ // 安全性算法
    for (int i = 0; i < n; ++i)
        Finish[i] = false;  // 初始化Finish辅助数组
    int work[MAX_RESOURCE];
    for (int i = 0; i < m; ++i) // 将Available数组复制到work
        work[i] = Available[i];
    for (int i = 0; i < sum; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (flag[j])
            {
                if ( !Finish[j] && cmp(Need[j], work))
                {
                    Finish[j] = true;
                    for (int k = 0; k < m; ++k)
                        work[k] += Allocation[j][k];
                    safeSeries[i] = j;
                    break; //这次遍历结束，直接break
                }
                else if (j == n - 1 && (Finish[j] || !cmp(Need[j], work))) //如果某一次遍历并未对Finish进行修改，则说明目前进程不安全，直接返回结果
                    return false;
            }
        }
    }
    return true;
}

bool bank(int index){
    if (!flag[index])
    {
        printfInfo();
        cout << "该进程已经结束，无需分配资源，请求已被系统拒绝！" << endl;
        return false;
    }
    if (!cmp(Request, Need[index]))
    {
        printfInfo();
        cout << "本次请求大于所需资源数，请求已被系统拒绝！" << endl;
        return false;
    }
    if (!cmp(Request, Available))
    {
        printfInfo();
        cout << "本次请求大于系统所剩资源数，请求已被系统拒绝！" << endl;
        return false;
    }
    // 尝试分配资源
    for (int i = 0; i < m; ++i)
    {
        Available[i] -= Request[i];
        Allocation[index][i] += Request[i];
        Need[index][i] -= Request[i];
    }
    if (safe())
    {
        printfInfo();
        cout << "当前系统安全！" << endl;
        cout << "安全序列为：";
        for (int i = 0; i < sum; i++)
            cout << safeSeries[i] << "  ";
        cout << endl;
        return true;
    }
    else
    {
        // 撤销之前的尝试
        for (int i = 0; i < m; ++i)
        {
            Available[i] += Request[i];
            Allocation[index][i] -= Request[i];
            Need[index][i] += Request[i];
        }
        printfInfo();
        cout << "当前请求不安全，无法进行操作！" << endl;
        return false;
    }

}

void init(){ //读入系统进程的初始状态
    while (true)
    {
        cout << "请输入进程的数量：";
        cin >> n;
        cout << "请输入系统资源种类数：";
        cin >> m;
        sum = n; //初始状态，所有进程均未完成
        // 初始化flag数组，表示这些进程均未完成
        for (int i = 0; i < n; ++i)
            flag[i] = true;
        cout << "请输入各进程的最大需求矩阵：" << endl;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> Max[i][j];
        cout << "请输入各进程的已分配的资源数：" << endl;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> Allocation[i][j];
        cout << "请输入系统各资源的个数：" << endl;
        for (int i = 0; i < m; ++i)
            cin  >> Available[i];
        //计算获得Need矩阵
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                Need[i][j] = Max[i][j] - Allocation[i][j];

        for (int i = 0; i < n; ++i) //获取Available矩阵
            for (int j = 0; j < m; ++j)
                Available[j] = Available[j] - Allocation[i][j];
        printfInfo();
        if (safe())
        {
            cout << "当前系统安全！" << endl;
            cout << "安全序列为：";
            for (int i = 0; i < n; i++)
                cout << safeSeries[i] << "  ";
            cout << endl;
            return;
        }
        else
            cout << "当前系统不安全，无法进行操作，请重试！" << endl;
    }
}

void isFinished() //判断是否有进程已经结束
{
    for (int i = 0; i < n; ++i)
    {
        bool isFinished = true;
        for (int j = 0; j < m; ++j)
        {
            if (Need[i][j] != 0)
            {
                isFinished = false;
                break;
            }
        }
        if (isFinished && flag[i])
        {
            flag[i] = false;
            sum --;
            for (int j = 0; j < m; ++j)
                Available[j] += Max[i][j];
            return; //从整个系统来看，我们得知一次请求最多只可能使一个进程结束
        }
    }
}
int main()
{
    init();
    cout << "============数据录入完毕=============" << endl;
    int choice;
    while (true)
    {
        int index;
        //判断是否有进程已经结束，并进行处理
        isFinished();
        if (sum == 0)
        {
            cout << "进程已全部结束！" << endl;
            return 0;
        }
        cout << "请输入发布请求的进程ID(0~" << n - 1 << ")：";
        cin >> index;
        cout << "请依次输入请求的资源数：";
        for (int i = 0; i < m; ++i)
            cin >> Request[i];
        bank(index);
    }
}

测试数据

测试数据

1. 测试数据1

5 3

8 5 3
3 2 2
9 5 2
2 2 2
4 3 6

0 1 0
2 0 0
3 0 2
2 1 1
0 0 2

10 5 7

2. 测试数据2

5 3

7 5 3
3 2 2
9 0 2
2 2 2
4 3 3

0 1 0
2 0 0
3 0 2
2 1 1
0 0 2

10 5 7

1
1 0 2

4
3 3 0

1
0 1 0

3
0 1 2

1
0 1 0

1
0 1 1

4
4 3 1

3
0 1 1

2
6 0 0

0
7 4 3

运行截图

运行截图

后序

注意，这只是模拟，可以观察到当某个进程在第一次need == 0时，在后续的安全序列中仍能见到该进程的Id，其实这并不是Bug。前提假设：在进程一旦达到Max时，在下次请求到达之前便会释放资源并结束进程。如是看来，在安全序列中出现其Id不无道理，因为在那时它仍占用这资源。但是下个请求到来之际，他便会自动释放资源（该步是我们自己假设的，并不是本次重点，实际操作并没有这么简单），也可以观察到，下次请求发生后，未完成的进程信息栏中并没有该进程的信息。