前趋图和程序执行

一、前趋图（Precedence Graph）

1. 定义与本质

前趋图是一种有向无循环图（DAG, Directed Acyclic Graph），核心作用是描述进程、程序段或语句之间的执行先后顺序，清晰呈现“谁必须在谁之前执行”的偏序（Partial Order）或前趋关系。

2. 组成要素

• 结点：可代表一个进程、一个程序段或一条语句，是执行的基本单元。
• 有向边：表示两个结点间的前趋关系，例如若存在边 A→B，则意味着A执行完成后，B才能开始执行。

3. 关键特性

• 必须无循环：若存在循环（如 A→B→A），会导致执行顺序矛盾，无法正常调度，因此含循环的图（如文档中“具有循环的前趋图”）不具备实际执行意义。
• 可直观展示顺序与并发边界：通过边的连接，能快速判断哪些单元必须顺序执行（有直接或间接边连接），哪些可并发执行（无任何边连接）。

二、程序的顺序执行

1. 定义

程序执行时遵循“严格先后次序”，即一个应用程序的若干程序段（或一条语句的若干操作）中，仅当前一个程序段（或操作）完全执行完毕，后一个才允许开始。例如文档中：

• 程序段的顺序关系：Ii（输入）→ Ci（计算）→ Pi（输出），输入完成后才能计算，计算完成后才能输出。
• 语句的顺序关系：S1: a := x+y → S2: b := a-5 → S3: c := b+1，S1的结果是S2的输入，S2的结果是S3的输入，必须依次执行。

2. 典型执行场景

早期未配置OS的系统和单道批处理系统中，内存仅装入一道用户程序，该程序独占CPU、内存等所有系统资源，直到执行完成才释放资源，装入下一个程序。

3. 核心特征

特征	具体说明
顺序性	程序执行路径唯一，每个操作的开始和结束时间完全确定，无“暂停-恢复”的间断。
封闭性	程序运行在“独占资源”的封闭环境中，资源状态仅由当前程序修改，不受外界（其他程序）影响。
可再现性	只要执行环境（如硬件配置）和初始条件（如输入数据）相同，无论执行多少次，最终结果完全一致。

三、程序的并发执行

1. 定义

多个程序段（或语句）在时间上重叠执行，即一个程序段尚未执行完成，另一个程序段便可开始执行，但前提是二者不存在前趋关系（无直接或间接依赖）。例如文档中：

• 语句组 S1: a=x+2、S2: b=y+4、S3: c=a+b、S4: d=c+b 中，S1和S2无依赖（分别依赖x、y，互不影响），可并发执行；但S3必须等待S1、S2都完成，S4必须等待S3完成。

2. 典型执行场景

多道批处理系统和分时系统中，内存可装入多道程序，OS通过调度让多道程序交替使用CPU，实现并发执行，以提高资源利用率（如CPU不再空闲等待I/O）和系统吞吐量。

3. 核心特征（与顺序执行完全相反）

特征	具体说明	示例（文档中N值问题）
间断性	程序执行过程中会因“等待资源”（如等待CPU、等待I/O完成）而频繁“执行-暂停-执行”，执行路径不连续。	-
失去封闭性	多程序共享系统资源（如共享变量、打印机），一个程序对资源状态的修改会影响其他程序的执行，环境不再封闭。	程序A（N:=N+1）与另两个程序（Print(N)、N:=0）共享变量N，A的执行顺序会改变N的最终值。
不可再现性	即使初始条件相同，因并发执行时资源竞争的顺序不同，最终结果可能不一致。	1. A在Print(N)和N:=0前执行：N值为n+1、n+1、0； 2. A在Print(N)和N:=0后执行：N值为n、0、1； 3. A在Print(N)和N:=0间执行：N值为n、n+1、0。

四、核心对比与关键结论

维度	程序顺序执行	程序并发执行
执行方式	单道程序独占资源，严格先后	多道程序共享资源，时间重叠
资源利用率	低（CPU、I/O设备易空闲）	高（CPU与I/O可并行工作）
执行稳定性	稳定（封闭、可再现）	不稳定（需同步机制协调）
适用场景	早期简单系统（无OS、单道批处理）	现代OS（多道批处理、分时、实时）

关键结论

程序并发执行虽能提升系统效率，但会因“失去封闭性和可再现性”导致执行结果不可控，因此必须配置进程同步机制（如后续章节的信号量、管程），协调多程序对共享资源的访问，确保执行结果可预期。