银行家算法c++代码实现

银行家算法（Banker's Algorithm）是一种死锁避免算法，用于避免并发系统中的死锁问题。它由艾德加·沃茨·迪科斯基（Edsger W. Dijkstra）于1965年提出。银行家算法的主要思想是在进程请求资源时，先判断该请求是否会导致系统进入不安全状态，如果不会，则分配资源；否则，让进程等待，直到请求满足安全条件。

以下是银行家算法的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义进程状态
enum ProcessState {
    Ready,      // 就绪
    Running,    // 运行
    Blocked,    // 阻塞
    Dead        // 终止
};

// 定义进程结构体
struct Process {
    int id;                 // 进程ID
    ProcessState state;     // 进程状态
    vector<int> max_res;    // 进程最大需求资源量
    vector<int> need_res;   // 进程还需资源量
    vector<int> allocation_res; // 进程已分配资源量
};

// 定义银行家算法类
class Banker {
private:
    int process_num;        // 进程数量
    int res_num;            // 资源种类数量
    vector<int> available_res;  // 系统可用资源量
    vector<Process> processes;  // 进程列表

public:
    Banker(int pnum, int rnum, vector<int> available, vector<Process> p) : 
            process_num(pnum), res_num(rnum), available_res(available), processes(p) {}

    // 银行家算法判断
    bool isSafe() {
        vector<int> work(available_res.begin(), available_res.end()); // 工作向量
        vector<bool> finish(process_num, false);   // 完成进程标记
        vector<int> safe_sequence;  // 安全序列

        int count = 0;  // 已完成进程数
        while (count < process_num) {
            bool found = false;
            for (int i = 0; i < process_num; ++i) {
                if (finish[i] == false) {
                    bool finishable = true;
                    for (int j = 0; j < res_num; ++j) {
                        if (processes[i].need_res[j] > work[j]) {
                            finishable = false;
                            break;
                        }
                    }
                    if (finishable) {
                        for (int j = 0; j < res_num; ++j) {
                            work[j] += processes[i].allocation_res[j];
                        }
                        finish[i] = true;
                        safe_sequence.push_back(i);
                        found = true;
                        count++;
                    }
                }
            }
            if (found == false) {
                return false;
            }
        }

        cout << "Safe sequence: ";
        for (int i = 0; i < process_num; ++i) {
            cout << "P" << safe_sequence[i];
            if (i != process_num - 1) {
                cout << " -> ";
            }
        }
        cout << endl;

        return true;
    }

    // 进程请求资源
    bool requestRes(int pid, vector<int> request) {
        vector<int> work(available_res.begin(), available_res.end()); // 工作向量
        vector<int> finish(process_num, false);   // 完成进程标记

        // 判断请求是否满足需求
        for (int i = 0; i < res_num; ++i) {
            if (request[i] > processes[pid].need_res[i]) {
                return false;
            }
        }

        // 判断请求是否满足可用资源量
        for (int i = 0; i < res_num; ++i) {
            if (request[i] > available_res[i]) {
                return false;
            }
        }

        // 模拟分配资源
        for (int i = 0; i < res_num; ++i) {
            available_res[i] -= request[i];
            processes[pid].allocation_res[i] += request[i];
            processes[pid].need_res[i] -= request[i];
        }

        // 判断是否会导致系统不安全
        int count = 0;
        while (count < process_num) {
            bool found = false;
            for (int i = 0; i < process_num; ++i) {
                if (finish[i] == false) {
                    bool finishable = true;
                    for (int j = 0; j < res_num; ++j) {
                        if (processes[i].need_res[j] > work[j]) {
                            finishable = false;
                            break;
                        }
                    }
                    if (finishable) {
                        for (int j = 0; j < res_num; ++j) {
                            work[j] += processes[i].allocation_res[j];
                        }
                        finish[i] = true;
                        found = true;
                        count++;
                    }
                }
            }
            if (found == false) {
                // 分配资源后会导致系统不安全，回滚分配
                for (int i = 0; i < res_num; ++i) {
                    available_res[i] += request[i];
                    processes[pid].allocation_res[i] -= request[i];
                    processes[pid].need_res[i] += request[i];
                }
                return false;
            }
        }

        return true;
    }
};

int main()
{
    // 测试数据
    int process_num = 5;
    int res_num = 3;
    vector<int> available_res {3, 3, 2};
    vector<Process> processes {
        {0, Ready, {7, 5, 3}, {7, 5, 3}, {0, 0, 0}},
        {1, Ready, {3, 2, 2}, {3, 2, 2}, {0, 0, 0}},
        {2, Blocked, {9, 0, 2}, {9, 0, 2}, {0, 0, 0}},
        {3, Running, {2, 2, 2}, {2, 2, 2}, {0, 0, 0}},
        {4, Ready, {4, 3, 3}, {4, 3, 3}, {0, 0, 0}}
    };

    // 初始化银行家算法
    Banker banker(process_num, res_num, available_res, processes);

    // 测试安全性
    banker.isSafe();

    // 测试进程请求资源
    int pid = 1;
    vector<int> request {1, 0, 2};
    if (banker.requestRes(pid, request)) {
        cout << "Process P" << pid << " request success!" << endl;
    } else {
        cout << "Process P" << pid << " request failed!" << endl;
    }

    return 0;
}

在上面的代码中，我们定义了一个`Process`结构体来表示进程，包含了进程ID、状态、最大需求资源量、还需资源量和已分配资源量等信息。我们还定义了一个`Banker`类来实现银行家算法，构造函数中需要传入进程数量、资源种类数量、系统可用资源量和进程列表等参数。`isSafe()`函数用于判断系统是否安全，而`requestRes()`函数用于模拟进程请求资源的情况。