C語言實現操作系統銀行家算法：死鎖避免經典案例

銀行家算法核心思想

「捨大取小，先滿足小需求進程，最後滿足大需求」。通過安全性檢查，只分配能導致系統進入安全狀態的資源請求。

數據結構設計（動態分配版）

int *Resource;      // 各類資源總量 [R]
int *Max;           // 最大需求矩陣 [P][R]
int *Need;          // 需求矩陣 [P][R]
int *Allocation;    // 已分配矩陣 [P][R]
int *Available;     // 可用資源 [R]

// 一維數組模擬二維：進程 i 的資源 j 存放在 [i*R + j]

核心：安全性檢查算法

int testStatus(const int P, const int R) {
    int *status = malloc(P * sizeof(int));       // 進程狀態：FALSE/WAIT/TRUE
    int *Available_tmp = malloc(R * sizeof(int)); // 可用資源副本
    memcpy(Available_tmp, Available, R * sizeof(int));
    memset(status, FALSE, P * sizeof(int));

    int finish = 0, wait = 0;
    while (finish != P && wait != P) {
        // 策略：選第一類資源需求最小的未完成進程
        int minP = -1, minR = Resource[0];
        for (int i = 0; i < P; ++i)
            if (status[i] == FALSE && Need[i*R] < minR)
                minR = Need[i*R], minP = i;

        // 檢查該進程所有資源需求能否滿足
        int j;
        for (j = 0; j < R; ++j)
            if (Need[minP*R + j] > Available_tmp[j]) break;

        if (j == R) {  // 能滿足
            status[minP] = TRUE; finish++;
            // 回收資源
            for (int l = 0; l < R; ++l)
                Available_tmp[l] += Allocation[minP*R + l];
            // 喚醒等待進程
            for (int k = 0; k < P; ++k)
                if (status[k] == WAIT) status[k] = FALSE, wait--;
        } else {  // 不能滿足
            status[minP] = WAIT; wait++;
        }
    }
    free(status); free(Available_tmp);
    return finish == P;  // 全部完成則安全
}

資源請求處理

int request(const int P, const int R, const int pid, const int *req) {
    // 1. 請求超過可用？拒絕
    for (int i = 0; i < R; ++i)
        if (req[i] > Available[i]) return FALSE;

    // 2. 試分配
    int *testAlloc = malloc(P * R * sizeof(int));
    memcpy(testAlloc, Allocation, P * R * sizeof(int));
    for (int i = 0; i < R; ++i)
        testAlloc[pid*R + i] += req[i];

    // 3. 安全性檢查
    int safe = testStatus(P, R);
    if (safe) memcpy(Allocation, testAlloc, P * R * sizeof(int));
    free(testAlloc);
    return safe;
}

輸入文件格式 (in.txt)

5 3          // 5進程 3資源類
17 5 20      // 總資源量
5 5 9        // Max 矩陣 (5x3)
5 3 6
4 0 11
4 2 5
4 2 4
2 1 2        // Allocation 矩陣
4 0 2
4 0 5
2 0 4
3 1 4
2 3 3        // Available

關鍵實現細節

• 動態內存： 適應任意進程/資源數，避免固定大小限制
• 一維模擬二維： [i*R + j] 訪問，簡化 malloc/free
• 貪心選擇： 每次挑選第一類資源需求最小的進程，符合「先滿足小需求」
• 狀態機： FALSE(可嘗試) → WAIT(暫不可滿足) → TRUE(完成釋放)
• 資源回收： 進程完成時歸還所有佔用資源，可能喚醒其他等待進程

測試輸出解讀

Saft         // 初始狀態安全
Allocate     // 進程1請求(0,3,4)可滿足，分配成功

若請求導致不安全狀態，將輸出 Non-Allocate 並拒絕分配。

現代系統中的應用

雖然現代 OS 多採用死鎖檢測/恢復或忽略策略（如 Linux），但銀行家算法思想廣泛應用於：

• 資源池管理（數據庫連接池、線程池）
• 雲資源調度（配額管理、預留實例）
• 實時系統確定性資源分配