銀行家算法 C++ 實現：系統資源分配與死鎖避免完整教程

算法原理回顧

Dijkstra 於 1965 年提出的銀行家算法，核心思想是安全性檢查：資源請求到達時，假設分配後若系統仍能找到一個進程完成序列（所有進程最終都能獲得所需資源並釋放），則分配安全，允許請求；否則拒絕並阻塞進程。

數據結構定義

#define M 16  // 最大資源種類
#define N 16  // 最大進程數

class Banker {
    int m, n;                    // 實際資源數、進程數
    int available[M];            // 可用資源向量
    int max[M][N];               // 最大需求矩陣
    int allocation[M][N];        // 已分配矩陣
    int need[M][N];              // 尚需矩陣 = max - allocation
public:
    bool Initialize();           // 輸入參數並計算 need
    bool IsSafe();               // 安全性檢查，輸出安全序列
    bool ResourceAllocate();     // 處理單次資源請求
    bool IsFinish();             // 判斷所有進程是否結束
};

安全性檢查核心邏輯

bool Banker::IsSafe() {
    int work[M], finish[N], result[N];
    memcpy(work, available, sizeof(available));
    memset(finish, 0, sizeof(finish));

    for (int k = 0, i = 0; i < n; ++i) {
        if (finish[i]) continue;
        bool can = true;
        for (int j = 0; j < m; ++j)
            if (need[i][j] > work[j]) { can = false; break; }
        if (!can) continue;

        // 進程 i 可滿足，模擬執行完畢釋放資源
        for (int j = 0; j < m; ++j) work[j] += allocation[i][j];
        finish[i] = 1;
        result[k++] = i;
        i = -1; // 重新掃描
    }

    for (int i = 0; i < n; ++i)
        if (!finish[i]) { cout << "無安全序列\n"; return false; }

    cout << "安全序列: ";
    for (int i = 0; i < n; ++i) {
        bool done = true;
        for (int j = 0; j < m; ++j)
            if (need[result[i]][j] != 0) { done = false; break; }
        if (!done) cout << result[i] << ' ';
    }
    cout << endl;
    return true;
}

資源請求處理流程

1. 讀取進程號、資源號、請求量；
2. 合法性檢查：請求量 ≤ Need 且 ≤ Available；
3. 試分配：更新 Available、Allocation、Need；
4. 調用 IsSafe()：安全則確認分配，不安全則回滾並阻塞；
5. 檢查進程是否完成（Allocation == Max），完成則釋放所有資源。

教材案例驗證

輸入《操作系統原理教程》P62 案例：4 類資源、5 進程，初始 Available=(1,0,2,0)。運行過程中依次嘗試分配，輸出與教材一致：安全序列動態變化，最終所有進程安全完成。

完整可編譯代碼

文末附帶完整 main.cpp，包含 Banker 類實現與交互式主循環，複製即可在 Linux/Windows 下編譯運行（需支持 C++11）。