【系统架构设计（30）】操作系统中：前驱图、死锁与银行家算法

一、本文知识覆盖范围

1、知识意义

前趋图与银行家算法是操作系统中的核心同步与死锁处理技术，它们解决了多进程并发执行中的关键问题：

• 前趋图：解决进程间执行顺序控制问题，确保依赖关系的进程按正确顺序执行，避免数据竞争和逻辑错误
• 银行家算法：解决资源分配中的死锁预防问题，通过动态资源分配策略避免系统陷入死锁状态

具体应用场景：

• 数据库事务处理中的依赖关系管理
• 分布式系统中的任务调度
• 云计算平台的资源分配
• 实时系统中的任务优先级控制

2、知识体系概览

二、前趋图：进程依赖关系的图形化表示

本章节将详细讲解前趋图的基本概念、结构特征和实际应用，帮助读者掌握进程间依赖关系的表示和管理方法。

1、前趋图基本概念

概念定义：前趋图（Precedence Graph）是一种有向无环图（DAG），用于表示进程、程序段或语句之间的执行先后顺序关系。

核心特征：

实际例子：

• 编译系统：词法分析→语法分析→语义分析→代码生成→优化
• Web应用：用户登录→权限验证→业务处理→结果返回
• 数据处理：数据采集→数据清洗→数据转换→数据分析→结果输出

适用场景：

• 多进程系统的任务调度
• 工作流引擎的设计
• 并行计算中的任务依赖管理
• 数据库事务的依赖控制

2、前趋图结构分析

概念定义：前趋图由节点和有向边组成，节点代表进程或任务，有向边代表前趋关系。

核心特征：

实际例子：

电商订单处理流程：
订单创建(A) → 库存检查(B) → 支付处理(C) → 订单确认(D) → 发货通知(E)

适用场景：

• 业务流程建模
• 系统架构设计
• 任务调度算法设计
• 并行计算优化

3、PV操作实现前趋图

概念定义：PV操作是操作系统提供的进程同步原语，P操作用于检查资源，V操作用于释放资源并通知等待进程。

• pv：
  • p代表：资源等待方检查资源使用方是否使用完；
  • v代表：资源使用方释放资源。
• 信号量初值：实现并发时信号量初值常为0 ，前趋图中有几个前趋关系（箭头），一般就设置几个信号量。

核心特征：

• P 操作：也叫 “等待操作”（wait），作用是申请资源。执行 P 操作时，信号量的值减 1：
  若结果 ≥ 0，说明能获取资源，进程可继续执行；
  若结果 ＜ 0，说明资源不足，进程会被阻塞，进入等待队列。

• V 操作：也叫 “释放操作”（signal），作用是释放资源。执行 V 操作时，信号量的值加 1：
  若结果 ≤ 0，说明有进程在等待该资源，会唤醒等待队列中的一个进程；
  若结果 ＞ 0，说明无进程等待，仅更新信号量值。

• S代表信号量（Semaphore），是操作系统中的一种同步原语，用于进程间的同步和互斥控制。
  初值为0：表示初始状态下没有资源可用，需要等待前趋进程完成

适用场景：

• 进程间同步控制
• 资源访问控制
• 临界区保护
• 条件等待机制

### 1、依赖关系识别

从前趋图可以看出，存在以下**4个直接依赖关系**：

| 依赖关系 | 含义 | 信号量 |
|:-------|:-------|:-------|
| P1 → P2 | P1完成后P2才能开始 | S1 |
| P1 → P3 | P1完成后P3才能开始 | S2 |
| P2 → P4 | P2完成后P4才能开始 | S4 |
| P3 → P4 | P3完成后P4才能开始 | S5 |

### 2、进程特征分析

- **起始进程**：P1（没有前趋）
- **终结进程**：P4（没有后继）
- **并行进程**：P2和P3（都依赖P1，可以并行执行）

## 三、信号量设计原理

### 1、为什么需要5个信号量？

**标准情况**：4个依赖关系需要4个信号量
**实际情况**：题目要求5个信号量，原因如下：

| 信号量 | 管理依赖 | 使用位置 | 作用 |
|:-------|:-------|:-------|:-------|
| S1 | P1→P2 | P1完成，P2开始 | 确保P1完成后P2才能开始 |
| S2 | P1→P3 | P1完成，P3开始 | 确保P1完成后P3才能开始 |
| S3 | P3→P2 | P3完成，P2开始 | 确保P2等待P3完成（隐式依赖） |
| S4 | P2→P4 | P2完成，P4开始 | 确保P2完成后P4才能开始 |
| S5 | P3→P4 | P3完成，P4开始 | 确保P3完成后P4才能开始 |

### 2、S3的特殊作用

**关键理解**：S3实现了P3→P2的隐式依赖，这意味着：
- P2必须等待P3完成后才能继续执行
- 实际执行顺序变为：P1 → P3 → P2 → P4
- 这超出了前趋图显示的显式依赖关系

## 四、PV操作实现

### 1、正确答案分析

**点a, b, c的操作**：
- **点a**：V(S1)V(S2) - P1完成后通知P2和P3
- **点b**：P(S1)P(S3) - P2等待P1和P3完成
- **点c**：V(S4) - P2完成后通知P4

**点d, e, f的操作**：
- **点d**：P(S2) - P3等待P1完成
- **点e**：V(S3)V(S5) - P3完成后通知P2和P4
- **点f**：P(S4)P(S5) - P4等待P2和P3完成

### 2、执行流程


1. P1执行 → V(S1)V(S2)通知P2和P3
2. P3执行 → V(S3)V(S5)通知P2和P4
3. P2执行 → V(S4)通知P4
4. P4执行 → 完成所有任务

三、死锁理论：系统资源竞争的核心问题

本章节将深入讲解死锁的产生机制、必要条件以及预防和避免策略，帮助读者理解并解决系统资源竞争问题。

1、死锁的四大必要条件

概念定义：死锁是指多个进程因竞争资源而造成的一种僵局，当进程都在等待对方释放资源时，系统无法继续执行。

核心特征：

实际例子：

死锁场景：两个进程竞争两个资源
进程A：请求资源1 → 获得资源1 → 请求资源2 → 等待
进程B：请求资源2 → 获得资源2 → 请求资源1 → 等待
结果：A等待B释放资源2，B等待A释放资源1，形成死锁

适用场景：

• 多线程程序调试
• 数据库事务管理
• 分布式系统设计
• 资源池管理

2、死锁预防策略

概念定义：死锁预防是通过打破死锁的四大必要条件来防止死锁发生的方法。

核心特征：

3、死锁避免：银行家算法

概念定义：死锁避免是在资源分配时动态检查系统是否处于安全状态，避免进入可能导致死锁的状态。

核心特征：

实际例子：

银行家算法示例：
系统资源：总共有10个资源
进程A：最大需求7个，已分配2个，还需5个
进程B：最大需求5个，已分配3个，还需2个
进程C：最大需求8个，已分配2个，还需6个

当前可用资源：10-2-3-2=3个
安全序列检查：B(需2个) → A(需5个) → C(需6个)
分配给B两个，运行完（3+5），分配给A后，满足a的需求
A完成后(释放给c)可用：6+2=8个，满足C的6个需求

4、 死锁最小资源数计算

题目核心要点：

1. 死锁条件公式：系统资源数 >= 进程数 × (进程所需资源数 - 1) + 1

2. 计算结果：3个进程，每个需要5个资源，系统至少需要13个资源才能避免死锁

3. 系统状态分类：

   • [0,4]：必定死锁
   • [5,12]：可能死锁
   • [13,∞)：不可能死锁

4. 银行家算法作用：通过动态检查确保系统处于安全状态，避免死锁发生

四、银行家算法：动态资源分配的核心技术

本章节将详细讲解银行家算法的原理、实现方法和实际应用，帮助读者掌握动态资源分配和死锁避免技术。

1、银行家算法基本原理

概念定义：银行家算法是一种经典的死锁避免算法，通过模拟资源分配过程，确保系统始终处于安全状态。

资源分配原则：

2、安全状态检查机制

概念定义：安全状态是指系统存在一个安全序列，能够使所有进程按此序列执行并最终完成。

核心特征：

3、资源分配决策过程

概念定义：资源分配决策是在进程请求资源时，通过银行家算法检查分配后系统是否仍处于安全状态。

核心特征：

4、 习题

五、总结

核心知识点回顾：

• 前趋图：通过DAG表示进程依赖关系，使用PV操作实现进程同步，确保任务按正确顺序执行
• 死锁理论：理解死锁的四大必要条件，掌握预防和避免策略，保证系统稳定运行
• 银行家算法：通过安全状态检查实现动态资源分配，有效避免死锁发生

不同场景的技术选择建议：