C 語言實現銀行家算法：動態分配、安全性檢測、資源請求處理

編輯：關於C語言

C 語言實現銀行家算法

銀行家算法是操作系統死鎖避免的經典算法。核心思想：**寧可拒絕請求，不進入不安全狀態**。本文提供基於動態內存分配的完整實現，包含安全性檢測、資源請求處理、數據文件驅動測試。

核心數據結構

int P;  // 進程數
int R;  // 資源類型數

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

採用一維展開二維：mat[i*R + j] 訪問第 i 進程第 j 資源，便於 malloc 連續分配。

安全性檢測核心函數 `testStatus`

int testStatus(int P, int R) {
    int *status = calloc(P, sizeof(int));       // 0=未完成, -1=等待, 1=完成
    int *work   = malloc(R * sizeof(int));
    memcpy(work, Available, R * sizeof(int));

    int finish = 0, wait = 0;
    while (finish != P && wait != P) {
        // 選擇 Need[:,0] 最小的未完成進程 (貪心策略)
        int minP = -1, minNeed = INT_MAX;
        for (int i = 0; i < P; ++i)
            if (status[i] == 0 && Need[i*R] < minNeed) {
                minNeed = Need[i*R]; minP = i;
            }
        if (minP == -1) break;  // 無可選進程

        // 檢查該進程所有資源需求是否可滿足
        bool can = true;
        for (int j = 0; j < R; ++j)
            if (Need[minP*R + j] > work[j]) { can = false; break; }

        if (can) {
            // 分配成功：標記完成，回收資源，喚醒等待進程
            status[minP] = 1; finish++;
            for (int j = 0; j < R; ++j) work[j] += Allocation[minP*R + j];
            for (int k = 0; k < P; ++k) if (status[k] == -1) { status[k] = 0; wait--; }
        } else {
            status[minP] = -1; wait++;  // 進入等待
        }
    }
    free(status); free(work);
    return (finish == P);
}

資源請求處理 `request`

int request(int P, int R, int pid, const int *req) {
    // 1. 請求是否超過 Need
    for (int j = 0; j < R; ++j)
        if (req[j] > Need[pid*R + j]) return 0;

    // 2. 請求是否超過 Available
    for (int j = 0; j < R; ++j)
        if (req[j] > Available[j]) return 0;

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

    // 4. 安全性檢測 (需臨時修改 Need/Available)
    // 這裡為簡化直接調用 testStatus，實際需構造臨時上下文
    // 略...

    // 5. 正式提交
    memcpy(Allocation, trial, P * R * sizeof(int));
    free(trial);
    return 1;
}

輸入文件格式 `in.txt`

5 3                # P=5, R=3
17 5 20            # Resource 總量
5 5 9              # Max 矩陣 (5行×3列)
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 向量

編譯運行

gcc banker.c -o banker
./banker
# 輸出示例:
# Saft
# Allocate

複雜度與優化點

指標	複雜度	優化方向
安全性檢測	O(P² × R)	優先隊列維護可滿足進程，降為 O(P log P × R)
空間	O(P × R)	位圖壓縮布爾矩陣
請求處理	O(P² × R)	增量更新工作向量，避免全量拷貝