前驱图（Precedence Graph），在操作系统和软件工程文献中也常被称为"偏序图"或"依赖图"，是一种用有向无环图（DAG，Directed Acyclic Graph）来描述一组程序或程序段之间执行顺序的形式化工具。在软考系统架构设计师的考试体系中，前驱图属于操作系统基础知识板块的核心内容，它与进程管理、并发控制和PV操作等知识点紧密关联，是理解多道程序并发执行的理论基础。
前驱图的图形表示非常直观：用节点（圆圈或方框）表示一个程序段、一个语句或一个进程，用有向边（箭头）表示节点之间的前驱关系。如果存在一条从节点A指向节点B的有向边，则意味着A必须在B开始执行之前完成，A称为B的直接前驱，B称为A的直接后继。不允许出现环路——因为环路意味着循环依赖，表示A必须在B之前完成，B又必须在A之前完成，这在逻辑上不可能。
在软考教材中，前驱图的引入是为了回答一个根本性问题：给定一组有依赖关系的程序段，哪些可以并发执行、哪些必须顺序执行？这个问题的答案直接决定了多道程序系统的并发度和资源利用率。前驱图的价值在于，它将程序之间复杂的依赖关系抽象为一种可视化的图结构，使得并发性分析变得可计算、可验证。2023年下半年系统架构设计师真题的第1至2题就是一道典型的前驱图分析题——给出一个包含输入、计算、输出程序段的作业并发执行前驱图，要求考生根据图中标号判断各节点对应的程序段名称。这道题的解题关键不在于记忆，而在于理解前驱图中边的方向所表示的依赖语义。
从知识层级的角度看，前驱图位于"程序执行理论"和"并发编程实践"的交叉点。向下看，它建立在图论的基本概念之上（有向图、无环性、拓扑排序）；向上看，它是理解信号量机制、管程模型、事务并发控制等高级并发概念的先修知识。系统架构设计师作为软考高级科目，对前驱图的考查往往超出"会看图"的层面，要求考生具备"会分析图背后的并发性"的能力——这与架构师在实际工作中需要评估系统并发性能的职责是高度吻合的。
要理解前驱图的深层意义，必须先理解程序的两种执行方式——顺序执行和并发执行——以及两者之间的本质差异。
在早期的单道程序系统中，程序的执行是严格顺序的：内存中只有一道程序，CPU按指令序列逐条执行，前一条指令执行完毕后才开始执行下一条指令。顺序执行有三个显著特征：封闭性（程序在运行过程中独占全部资源，执行结果仅取决于程序本身，不受外界因素影响）、可再现性（只要初始条件相同，程序每次运行的结果都完全相同）和顺序性（程序内部指令的执行顺序与程序的静态书写顺序一致）。这三个特征使得顺序程序的调试和验证相对简单——只要代码逻辑正确，结果就是确定的。
多道程序系统的出现打破了顺序执行的假设。为了提升CPU利用率，操作系统允许多道程序同时驻留内存，当一个程序因输入/输出操作而等待时，CPU可以切换到另一道程序继续执行。这种宏观上"同时运行"、微观上"交替执行"的方式，就是并发执行。并发执行带来了三个根本性的变化：首先是失去了封闭性——多道程序共享CPU、内存和输入/输出设备等资源，一个程序的执行状态会受到其他程序的影响；其次是失去了可再现性——程序在并发环境下的执行结果不仅取决于程序本身的逻辑，还取决于程序之间相对推进速度的不可预测性（即"竞态条件"）；最后是程序内部指令的执行顺序不再严格遵循静态书写顺序——编译器优化、CPU乱序执行和操作系统的调度都可能改变指令的实际执行次序。
正是在这个背景下，前驱图的理论价值凸显出来。前驱图提供了一种形式化方法来描述程序段之间的依赖约束，从而在并发环境中划定出"可以并发"和"必须顺序"的边界。这个边界不是由程序员的主观感觉决定的，而是由程序段之间的数据依赖关系客观决定的。
1966年，计算机科学家伯恩斯坦（A. J. Bernstein）提出了判断两个程序段能否并发执行的精确条件，即著名的Bernstein条件。给定两个程序段S1和S2，定义R(S1)为S1的读集（S1在执行过程中读取的所有变量的集合），W(S1)为S1的写集（S1在执行过程中修改的所有变量的集合）。则S1和S2可以并发执行的充要条件是以下三个交集全部为空：
R(S1) ∩ W(S2) = ∅ — S1读取的变量不会被S2修改；
R(S2) ∩ W(S1) = ∅ — S2读取的变量不会被S1修改；
W(S1) ∩ W(S2) = ∅ — S1和S2不会修改同一个变量。
这三个条件的直觉解释是：两个程序段可以并发执行，当且仅当它们之间不存在"读-写冲突"和"写-写冲突"。如果存在"读-读"关系（两个程序段读取同一个变量但不修改它），不影响并发——因为读操作不会改变程序状态。Bernstein条件将并发判断从一个"感觉"问题转化为一个"集合运算"问题，在理论上奠定了并发控制的形式化基础。
把前驱图和Bernstein条件结合起来，就形成了一个完整的并发性分析框架：首先用前驱图表示程序段之间的已知依赖关系（来自业务逻辑本身的要求），然后在剩余的程序段对之间应用Bernstein条件判断是否可以并发执行。前驱图中的每条有向边对应一个Bernstein条件不满足（即存在数据依赖），而没有边连接的两个节点，如果同时满足Bernstein条件，就可以并发。
构建前驱图的过程，本质上是对程序内部数据流和控制流的建模。以2023年架构师真题中的场景为例：系统中有四个作业T1到T4（优先级递减），每个作业包含三个程序段——输入Ii、计算Ci和输出Pi，执行顺序为Ii→Ci→Pi。各种程序段之间存在资源共享和依赖关系，需要画出完整的前驱图来判断并发执行的可能性。
构建前驱图的第一步是识别每个节点——本场景中共有12个节点（4个作业×3个程序段）。第二步是确定每个作业内部的强制顺序：对任意i，Ii必须在Ci之前执行，Ci必须在Pi之前执行，这是由程序语义决定的不可违反的依赖关系。第三步是确定跨作业的依赖关系——这里涉及资源共享：输入设备只能被一个作业的输入程序段使用，CPU只能被一个作业的计算程序段使用，输出设备只能被一个作业的输出程序段使用。这意味着Ii之间不能并发（共享输入设备）、Ci之间不能并发（共享CPU）、Pi之间不能并发（共享输出设备）。但在不同资源类型的程序段之间——如一个作业的Ci和另一个作业的Pi——则可以并发执行，因为它们使用不同的资源。
真题中要求根据前驱图中的标号判断各节点对应的程序段。解题思路是：先定位图中"最靠前"的节点（入度为零，没有前驱），确定为最先执行的那个作业的输入程序段；然后沿着有向边追踪，利用已知的执行次序约束（Ii→Ci→Pi）和资源共享约束（同类程序段不能并发）来逐节点推断。图中①、②、③三个节点位于同一层级且没有直接依赖，说明它们可以并发执行——而且一定属于不同类型的程序段（因为同类程序段之间会因为资源冲突而不能并发）。按照这个逻辑，①、②、③对应的恰好是三个不同作业中不同类型的程序段：I2、C2和C4，答案为选项A。
前驱图的应用不限于操作系统领域。在数据库系统中，事务的并发控制本质上就是对事务操作序列构建前驱图（称为"可串行化图"或"冲突图"），如果图中有环则说明调度不可串行化。在编译器中，指令调度优化的核心就是构建指令之间的依赖图（类似前驱图），然后在满足依赖约束的前提下重排指令以最大化流水线效率。在分布式系统中，事件的"发生在之前"关系由Lamport逻辑时钟来推断，而这个关系的数学表示正是一个偏序图。理解前驱图的通用性，对于架构师来说尤其重要——架构师需要在系统设计的多个层面（硬件指令级、操作系统进程级、数据库事务级、分布式消息级）反复遇到并发性和依赖性的权衡问题，而前驱图提供了一个统一的思维模型。
在实际的系统设计中，前驱图的使用有两种模式。第一种是分析模式：给定一个已有的程序或系统，画出其前驱图，分析其中的并发瓶颈和依赖冗余。如果一个前驱图中存在大量不必要的顺序依赖（即图中有很多边并非数据依赖所必需，而是由于设计不当
本篇完！