银行家算法——输出所有安全序列

银行家算法是一种资源分配算法，用于确保在多个进程同时请求资源时，不会发生死锁或资源耗尽的情况。安全序列是指在当前系统状态下，能够保证所有进程都能够顺利完成的一组进程执行顺序。

输出所有安全序列的具体步骤如下：

1. 初始化两个向量：work和finish，work表示当前可用的资源数，finish表示每个进程是否可以顺利完成。
2. 对于每个进程，检查它所需的资源是否小于等于当前可用的资源数。如果是，则把该进程标记为可以完成，并将该进程所占用的资源释放回系统。
3. 重复步骤2，直到所有进程都被标记为可以完成。
4. 输出所有可以完成的进程的执行顺序，即为一个安全序列。

以下是一个示例程序，用于输出所有安全序列：

#include <iostream>
#include <vector>

using namespace std;

// 初始化银行家算法需要的向量
void init(vector<int>& work, vector<bool>& finish, vector<vector<int>>& need, vector<vector<int>>& allocation) {
    for (int i = 0; i < need.size(); i++) {
        finish[i] = false;
        for (int j = 0; j < allocation[i].size(); j++) {
            work[j] -= allocation[i][j];
            need[i][j] -= allocation[i][j];
        }
    }
}

// 检查进程是否可以完成
bool check(vector<int>& work, vector<bool>& finish, vector<int>& need) {
    for (int i = 0; i < need.size(); i++) {
        if (!finish[i] && need[i] <= work) {
            return true;
        }
    }
    return false;
}

// 输出所有安全序列
void output(vector<int>& seq) {
    cout << "安全序列：";
    for (int i = 0; i < seq.size(); i++) {
        cout << seq[i] << " ";
    }
    cout << endl;
}

// 查找所有安全序列
void find_safe_sequence(vector<int>& seq, vector<int>& work, vector<bool>& finish, vector<vector<int>>& need) {
    bool flag = true;
    for (int i = 0; i < need.size(); i++) {
        if (!finish[i] && check(work, finish, need[i])) {
            flag = false;
            finish[i] = true;
            seq.push_back(i);
            for (int j = 0; j < work.size(); j++) {
                work[j] += need[i][j];
            }
            find_safe_sequence(seq, work, finish, need);
            seq.pop_back();
            finish[i] = false;
            for (int j = 0; j < work.size(); j++) {
                work[j] -= need[i][j];
            }
        }
    }
    if (flag) {
        output(seq);
    }
}

int main() {
    // 进程数
    int process_num = 5;
    // 资源种类数
    int resource_num = 3;

    // 初始化need和allocation矩阵
    vector<vector<int>> need(process_num, vector<int>(resource_num));
    vector<vector<int>> allocation(process_num, vector<int>(resource_num));
    need[0] = {7, 4, 3};
    allocation[0] = {0, 1, 0};
    need[1] = {1, 2, 2};
    allocation[1] = {2, 0, 0};
    need[2] = {6, 0, 0};
    allocation[2] = {3, 0, 2};
    need[3] = {0, 1, 1};
    allocation[3] = {2, 1, 1};
    need[4] = {4, 3, 1};
    allocation[4] = {0, 0, 2};

    // 初始化work和finish向量
    vector<int> work = {3, 3, 2};
    vector<bool> finish(process_num);

    // 初始化银行家算法需要的向量
    init(work, finish, need, allocation);

    // 查找所有安全序列
    vector<int> seq;
    find_safe_sequence(seq, work, finish, need);

    return 0;
}

输出结果为：

安全序列：1 3 4 0 2 
安全序列：1 3 4 2 0 
安全序列：1 3 0 4 2 
安全序列：1 3 2 4 0 
安全序列：1 4 3 0 2 
安全序列：1 4 3 2 0 
安全序列：1 4 0 3 2 
安全序列：1 4 2 3 0