实验四 避免死锁实验（实验报告）

班级：123030201
学号：1230904XXXX
姓名：段 X X

课程目标	目标3得分（功能实现情况）	目标4得分（自主学习和解决问题能力情况）
自评分	95	95
批阅分

一、实验目的

1. 理解死锁的概念和产生条件

2. 掌握银行家算法的基本原理

3. 学会应用银行家算法进行资源分配的安全性检查

4. 培养自主学习解决实际资源分配问题的能力

二、实验原理

（一）死锁产生的四个必要条件

1. 互斥条件：资源不能被共享

2. 请求并保持条件：进程持有资源并等待其他资源

3. 不可剥夺条件：资源不能被强制剥夺

4. 循环等待条件：存在进程资源的循环等待链

（二）银行家算法核心概念

• 可用资源向量：Available

• 最大需求矩阵：Max

• 分配矩阵：Allocation

• 需求矩阵：Need = Max - Allocation

三、实验内容

实验场景：计算机系统资源分配模拟，用银行家算法分析避免死锁

（一）初始系统状态

系统资源：A(3)、B(7)、C(11)

T0时刻进程资源情况：

进程	最大需求(Max)	已分配(Allocation)	需求(Need)	完成状态
P0	(0, 0, 4)	(0, 0, 3)	(0, 0, 1)	□
P1	(1, 7, 5)	(1, 0, 0)	(0, 7, 5)	□
P2	(2, 3, 5)	(1, 3, 5)	(1, 0, 0)	□
P3	(0, 6, 4)	(0, 0, 2)	(0, 6, 2)	□
P4	(0, 6, 5)	(0, 0, 1)	(0, 6, 4)	□
当前可用资源：Available = (1, 4, 0)

（二）实验步骤

第一步：计算初始Need矩阵和Available向量

计算过程：

Need[i] = Max[i] - Allocation[i]

• P0: Need = (0-0, 0-0, 4-3) = (0, 0, 1)

• P1: Need = (1-1, 7-0, 5-0) = (0, 7, 5)

• P2: Need = (2-1, 3-3, 5-5) = (1, 0, 0)

• P3: Need = (0-0, 6-0, 4-2) = (0, 6, 2)

• P4: Need = (0-0, 6-0, 5-1) = (0, 6, 4)

Available = 总资源 - ∑Allocation[i]

• 总资源：(3, 7, 11)

• ∑Allocation[i]：(0+1+1+0+0, 0+0+3+0+0, 3+0+5+2+1) = (2, 3, 11)

• Available = (3-2, 7-3, 11-11) = (1, 4, 0)

第二步：执行安全性算法

安全性检查表：

步骤	进程	Work	Need(≤ Work?)	Work + Allocation	完成状态
1	P2	(1, 4, 0)	是(1, 0, 0 ≤ 1, 4, 0)	(1+1, 4+3, 0+5) = (2, 7, 5)	完成
2	P0	(2, 7, 5)	是(0, 0, 1 ≤ 2, 7, 5)	(2+0, 7+0, 5+3) = (2, 7, 8)	完成
3	P1	(2, 7, 8)	是(0, 7, 5 ≤ 2, 7, 8)	(2+1, 7+0, 8+0) = (3, 7, 8)	完成
4	P3	(3, 7, 8)	是(0, 6, 2 ≤ 3, 7, 8)	(3+0, 7+0, 8+2) = (3, 7, 10)	完成
5	P4	(3, 7, 10)	是(0, 6, 4 ≤ 3, 7, 10)	(3+0, 7+0, 10+1) = (3, 7, 11)	完成
安全序列：⟨P2, P0, P1, P3, P4⟩

第三步：资源请求处理

场景1：T0时刻后进程P1请求资源 Request = (0, 2, 0)

1. 检查 Request ≤ Need? ☑是 □否（0≤0，2≤7，0≤5）

2. 检查 Request ≤ Available? ☑是 □否（0≤1，2≤4，0≤0）

模拟分配后的状态：

• Available = (1, 4, 0) - (0, 2, 0) = (1, 2, 0)

• Allocation[1] = (1, 0, 0) + (0, 2, 0) = (1, 2, 0)

• Need[1] = (0, 7, 5) - (0, 2, 0) = (0, 5, 5)

执行安全性检查：

☑ 系统处于安全状态 □ 系统处于不安全状态

安全序列：⟨P2, P0, P1, P3, P4⟩

决策：☑ 同意分配 □ 拒绝分配

场景2：T0时刻后进程P3请求资源 Request = (0, 4, 0)

1. 检查 Request ≤ Need? ☑是 □否（0≤0，4≤6，0≤2）

2. 检查 Request ≤ Available? ☑是 □否（0≤1，4≤4，0≤0）

模拟分配并检查安全性：

决策：□ 同意分配 ☑ 拒绝分配

理由：模拟分配后系统仍存在安全序列，资源分配不会导致死锁。

思考：T0时刻系统处于安全状态的系统资源最小值是：(3, 6, 11)

第四步：伪代码填空

函数 安全性检查():
    工作向量 = 可用资源
    完成标记 = [假, 假, 假, ...]
    
    循环 直到没有进程可执行为止:
        找到这样一个进程i：
           完成标记[i] = 假
           需求[i] <= 工作向量   # 填空
        
        如果找到:
            工作向量 = 工作向量 + 分配[i]   # 填空
            完成标记[i] = 真   # 填空
            加入安全序列
        否则:
            跳出循环
    
    如果所有进程都完成:
        返回 真   # 填空
    否则:
        返回 假   # 填空

第五步：编程验证

#include <stdio.h>

#define N 5   // 进程数
#define M 3  // 资源类型数

// 安全性检查函数，返回1表示安全，0表示不安全，seq存储安全序列
int safetyCheck(int Max[N][M], int Allocation[N][M], int Need[N][M], int Available[M], int seq[N]) {
    int Work[M];
    int finish[N] = {0};
    int count = 0;
    // 初始化工作向量
    for (int i = 0; i < M; i++) {
        Work[i] = Available[i];
    }
    while (count < N) {
        int found = 0;
        for (int i = 0; i < N; i++) {
            if (!finish[i]) {
                // 检查Need[i] ≤ Work
                int ok = 1;
                for (int j = 0; j < M; j++) {
                    if (Need[i][j] > Work[j]) {
                        ok = 0;
                        break;
                    }
                }
                if (ok) {
                    // 分配资源，更新Work
                    for (int j = 0; j < M; j++) {
                        Work[j] += Allocation[i][j];
                    }
                    finish[i] = 1;
                    seq[count++] = i;
                    found = 1;
                }
            }
        }
        if (!found) break; // 无可用进程，跳出循环
    }

    return count == N ? 1 : 0;
}

// 资源请求处理函数
int requestResource(int pid, int Request[M], int Max[N][M], int Allocation[N][M], int Need[N][M], int Available[M]) {
    // 检查Request ≤ Need
    for (int i = 0; i < M; i++) {
        if (Request[i] > Need[pid][i]) {
            return 0;
        }
    }

    // 检查Request ≤ Available
    for (int i = 0; i < M; i++) {
        if (Request[i] > Available[i]) {
            return 0;
        }
    }

    // 模拟分配
    for (int i = 0; i < M; i++) {
        Available[i] -= Request[i];
        Allocation[pid][i] += Request[i];
        Need[pid][i] -= Request[i];
    }

    // 安全性检查
    int seq[N];
    if (safetyCheck(Max, Allocation, Need, Available, seq)) {
        return 1; // 安全，同意分配
    } else {
        // 不安全，回滚分配
        for (int i = 0; i < M; i++) {
            Available[i] += Request[i];
            Allocation[pid][i] -= Request[i];
            Need[pid][i] += Request[i];
        }
        return 0; // 拒绝分配
    }
}

int main() {
    // 初始数据定义
    int Max[N][M] = {
        {0, 0, 4},
        {1, 7, 5},
        {2, 3, 5},
        {0, 6, 4},
        {0, 6, 5}
    };
    int Allocation[N][M] = {
        {0, 0, 3},
        {1, 0, 0},
        {1, 3, 5},
        {0, 0, 2},
        {0, 0, 1}
    };
    int Need[N][M];
    int Available[M];

    // 计算需求矩阵
    printf("计算Need矩阵:\n");
    for (int i = 0; i < N; i++) {
        printf("P%d: ", i);
        for (int j = 0; j < M; j++) {
            Need[i][j] = Max[i][j] - Allocation[i][j];
            printf("%d ", Need[i][j]);
        }
        printf("\n");
    }

    // 计算初始Available向量
    int totalResource[M] = {3, 7, 11};
    int allocSum[M] = {0};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            allocSum[j] += Allocation[i][j];
        }
    }
    for (int j = 0; j < M; j++) {
        Available[j] = totalResource[j] - allocSum[j];
    }
    printf("\n初始Available向量: (%d, %d, %d)\n", Available[0], Available[1], Available[2]);

    // 初始安全性检查
    int seq[N];
    if (safetyCheck(Max, Allocation, Need, Available, seq)) {
        printf("初始系统安全，安全序列: ");
        for (int i = 0; i < N; i++) {
            printf("P%d ", seq[i]);
        }
        printf("\n");
    } else {
        printf("初始系统不安全\n");
    }

    // 处理P1的资源请求(0,2,0)
    int pid1 = 1;
    int req1[M] = {0, 2, 0};
    printf("\n处理P%d的请求(%d, %d, %d):\n", pid1, req1[0], req1[1], req1[2]);
    if (requestResource(pid1, req1, Max, Allocation, Need, Available)) {
        printf("同意分配\n");
    } else {
        printf("拒绝分配\n");
    }

    // 处理P3的资源请求(0,4,0)
    int pid2 = 3;
    int req2[M] = {0, 4, 0};
    printf("\n处理P%d的请求(%d, %d, %d):\n", pid2, req2[0], req2[1], req2[2]);
    if (requestResource(pid2, req2, Max, Allocation, Need, Available)) {
        printf("同意分配\n");
        // 输出分配后的安全序列
        safetyCheck(Max, Allocation, Need, Available, seq);
        printf("分配后安全序列: ");
        for (int i = 0; i < N; i++) {
            printf("P%d ", seq[i]);
        }
        printf("\n");
    } else {
        printf("拒绝分配\n");
    }

    return 0;
}

四、实验结果分析

（一）实验运行验证情况

实验运行后，输出结果包含 Need 矩阵、初始 Available 向量、安全序列及对 P1 和 P3 资源请求的处理决策，与预期结果一致，验证了算法的正确性。

（二）初始状态安全性

• 安全序列：⟨P2, P3, P4, P0, P1⟩

• 系统是否安全：☑是 □否

（三）资源请求分析

请求场景	是否安全	安全序列	分配决策
P1(0, 2, 0)	☑是 □否	⟨P2, P0, P1, P3, P4⟩	☑同意 □拒绝
P3(0, 4, 0)	☑是 □否	⟨P2, P0, P3, P1, P4⟩	□同意 ☑拒绝

五、讨论

（一）除了银行家算法，还有哪些死锁处理策略？

1. 死锁预防：破坏死锁的四个必要条件之一，如资源预分配（破坏持有并等待）、资源有序分配（破坏循环等待）、允许资源剥夺（破坏不可剥夺）。

2. 死锁检测：定期执行死锁检测算法，识别死锁进程与资源，通过终止进程或剥夺资源解除死锁。

3. 死锁忽略：不主动处理死锁，依赖用户或管理员手动干预（适用于死锁概率极低的场景，如个人计算机）。

（二）请讨论在实际系统中死锁处理的工程权衡

1. 资源利用率与安全性：预防死锁会降低资源利用率（如预分配导致资源闲置），银行家算法需提前知晓最大需求，实际中难以完全满足。

2. 开销与复杂度：检测死锁需额外计算资源依赖关系，解除死锁可能导致数据丢失；忽略死锁虽无额外开销，但可能因死锁导致系统不稳定。

3. 场景适配：嵌入式系统优先选择简单的预防策略（低复杂度），服务器系统倾向于检测+解除（平衡利用率与稳定性），个人PC多采用忽略策略（低成本）。

六、实验报告（电子版Word文档）

1.操作系统实验报告【实验四 死锁解决实验】

操作系统实验报告【实验四 死锁解决实验】