操作系统中的银行家算法
字数 2417 2025-11-03 12:22:58
操作系统中的银行家算法
银行家算法是一种用于避免死锁的资源分配算法，由艾兹格·迪杰斯特拉提出。它通过模拟资源分配来检查系统是否处于安全状态，从而决定是否分配资源。下面我将详细讲解其核心概念、算法步骤和一个具体例子。
1. 核心概念
- 可用资源（Available）：系统中当前可用的各类资源数量。
- 最大需求（Max）：每个进程对各类资源的最大需求量。
- 已分配（Allocation）：当前已分配给每个进程的各类资源数量。
- 需求（Need）：每个进程还需要的各类资源数量（Need = Max - Allocation）。
- 安全状态：存在一个进程执行序列（安全序列），使得系统能按此序列分配资源并完成所有进程，不会发生死锁。
2. 银行家算法的步骤
步骤1：初始化
定义资源向量和进程矩阵。例如：
- 资源类型：A、B、C（如打印机、内存块等）。
- 进程数量：P0、P1、P2、P3、P4。
- 可用资源向量 Available = [3, 3, 2]（表示A、B、C类资源分别剩余3、3、2单位）。
步骤2：检查资源请求
当进程请求资源时，算法按以下顺序判断：
- 请求是否合法：请求量不能超过进程声明的最大需求（Need）。
- 资源是否充足：请求量不能超过当前可用资源（Available）。
- 试探分配：假设分配资源，更新状态：
- Available = Available - Request（减少可用资源）。
- Allocation = Allocation + Request（增加已分配资源）。
- Need = Need - Request（减少需求资源）。
- 执行安全性检查：判断试探分配后系统是否仍处于安全状态。
步骤3：安全性检查算法
- 初始化两个向量：
- Work = Available（当前可用资源副本）。
- Finish = [false, false, ...]（标记进程是否完成）。
- 循环查找满足以下条件的进程：
- Finish[i] = false（进程未完成）。
- Need[i] ≤ Work（进程所需资源≤当前可用资源）。
- 若找到这样的进程：
- Work = Work + Allocation[i]（释放该进程占用的资源）。
- Finish[i] = true（标记进程完成）。
- 重复步骤2，直到所有进程完成（安全）或找不到符合条件的进程（不安全）。
步骤4：决策
- 若安全性检查通过（存在安全序列），则实际分配资源。
- 若未通过，则拒绝请求，进程等待。
3. 具体示例
假设系统有3类资源（A、B、C），5个进程（P0-P4），初始状态如下：
| 进程 |
Allocation (A,B,C) |
Max (A,B,C) |
Available (A,B,C) |
| P0 |
0,1,0 |
7,5,3 |
3,3,2 |
| P1 |
2,0,0 |
3,2,2 |
|
| P2 |
3,0,2 |
9,0,2 |
|
| P3 |
2,1,1 |
2,2,2 |
|
| P4 |
0,0,2 |
4,3,3 |
|
计算Need矩阵（Max - Allocation）：
- P0: (7,5,3) - (0,1,0) = (7,4,3)
- P1: (3,2,2) - (2,0,0) = (1,2,2)
- P2: (9,0,2) - (3,0,2) = (6,0,0)
- P3: (2,2,2) - (2,1,1) = (0,1,1)
- P4: (4,3,3) - (0,0,2) = (4,3,1)
安全性检查过程：
- Work = Available = (3,3,2), Finish = [false, false, false, false, false]。
- 查找 Need ≤ Work 的进程：
- P1: Need=(1,2,2) ≤ Work=(3,3,2) → 满足。更新 Work=(3,3,2)+(2,0,0)=(5,3,2), Finish[1]=true。
- P3: Need=(0,1,1) ≤ Work=(5,3,2) → 满足。更新 Work=(5,3,2)+(2,1,1)=(7,4,3), Finish[3]=true。
- P4: Need=(4,3,1) ≤ Work=(7,4,3) → 满足。更新 Work=(7,4,3)+(0,0,2)=(7,4,5), Finish[4]=true。
- P0: Need=(7,4,3) ≤ Work=(7,4,5) → 满足。更新 Work=(7,4,5)+(0,1,0)=(7,5,5), Finish[0]=true。
- P2: Need=(6,0,0) ≤ Work=(7,5,5) → 满足。更新 Work=(7,5,5)+(3,0,2)=(10,5,7), Finish[2]=true。
- 所有 Finish=true，安全序列为 [P1, P3, P4, P0, P2]（不唯一）。
4. 关键点总结
- 优点：避免死锁，保证系统安全。
- 缺点：需要提前知道最大资源需求，且计算开销较大（适合资源类型少的场景）。
- 实际应用：多用于教学或理论分析，现实系统中更常用死锁检测与恢复策略。
操作系统中的银行家算法 银行家算法是一种用于避免死锁的资源分配算法，由艾兹格·迪杰斯特拉提出。它通过模拟资源分配来检查系统是否处于安全状态，从而决定是否分配资源。下面我将详细讲解其核心概念、算法步骤和一个具体例子。 1. 核心概念 可用资源（Available） ：系统中当前可用的各类资源数量。 最大需求（Max） ：每个进程对各类资源的最大需求量。 已分配（Allocation） ：当前已分配给每个进程的各类资源数量。 需求（Need） ：每个进程还需要的各类资源数量（Need = Max - Allocation）。 安全状态 ：存在一个进程执行序列（安全序列），使得系统能按此序列分配资源并完成所有进程，不会发生死锁。 2. 银行家算法的步骤 步骤1：初始化 定义资源向量和进程矩阵。例如： 资源类型：A、B、C（如打印机、内存块等）。 进程数量：P0、P1、P2、P3、P4。 可用资源向量 Available = [ 3, 3, 2 ]（表示A、B、C类资源分别剩余3、3、2单位）。 步骤2：检查资源请求 当进程请求资源时，算法按以下顺序判断： 请求是否合法 ：请求量不能超过进程声明的最大需求（Need）。 资源是否充足 ：请求量不能超过当前可用资源（Available）。 试探分配 ：假设分配资源，更新状态： Available = Available - Request（减少可用资源）。 Allocation = Allocation + Request（增加已分配资源）。 Need = Need - Request（减少需求资源）。 执行安全性检查 ：判断试探分配后系统是否仍处于安全状态。 步骤3：安全性检查算法 初始化两个向量： Work = Available（当前可用资源副本）。 Finish = [ false, false, ... ]（标记进程是否完成）。 循环查找满足以下条件的进程： Finish[ i ] = false（进程未完成）。 Need[ i ] ≤ Work（进程所需资源≤当前可用资源）。 若找到这样的进程： Work = Work + Allocation[ i ]（释放该进程占用的资源）。 Finish[ i ] = true（标记进程完成）。 重复步骤2，直到所有进程完成（安全）或找不到符合条件的进程（不安全）。 步骤4：决策 若安全性检查通过（存在安全序列），则实际分配资源。 若未通过，则拒绝请求，进程等待。 3. 具体示例 假设系统有3类资源（A、B、C），5个进程（P0-P4），初始状态如下： | 进程 | Allocation (A,B,C) | Max (A,B,C) | Available (A,B,C) | |------|-------------------|-------------|-------------------| | P0 | 0,1,0 | 7,5,3 | 3,3,2 | | P1 | 2,0,0 | 3,2,2 | | | P2 | 3,0,2 | 9,0,2 | | | P3 | 2,1,1 | 2,2,2 | | | P4 | 0,0,2 | 4,3,3 | | 计算Need矩阵（Max - Allocation） ： P0: (7,5,3) - (0,1,0) = (7,4,3) P1: (3,2,2) - (2,0,0) = (1,2,2) P2: (9,0,2) - (3,0,2) = (6,0,0) P3: (2,2,2) - (2,1,1) = (0,1,1) P4: (4,3,3) - (0,0,2) = (4,3,1) 安全性检查过程 ： Work = Available = (3,3,2), Finish = [ false, false, false, false, false ]。 查找 Need ≤ Work 的进程： P1: Need=(1,2,2) ≤ Work=(3,3,2) → 满足。更新 Work=(3,3,2)+(2,0,0)=(5,3,2), Finish[ 1 ]=true。 P3: Need=(0,1,1) ≤ Work=(5,3,2) → 满足。更新 Work=(5,3,2)+(2,1,1)=(7,4,3), Finish[ 3 ]=true。 P4: Need=(4,3,1) ≤ Work=(7,4,3) → 满足。更新 Work=(7,4,3)+(0,0,2)=(7,4,5), Finish[ 4 ]=true。 P0: Need=(7,4,3) ≤ Work=(7,4,5) → 满足。更新 Work=(7,4,5)+(0,1,0)=(7,5,5), Finish[ 0 ]=true。 P2: Need=(6,0,0) ≤ Work=(7,5,5) → 满足。更新 Work=(7,5,5)+(3,0,2)=(10,5,7), Finish[ 2 ]=true。 所有 Finish=true，安全序列为 [ P1, P3, P4, P0, P2 ]（不唯一）。 4. 关键点总结 优点 ：避免死锁，保证系统安全。 缺点 ：需要提前知道最大资源需求，且计算开销较大（适合资源类型少的场景）。 实际应用 ：多用于教学或理论分析，现实系统中更常用死锁检测与恢复策略。
