2.1　前趋图和程序执行

早期没有操作系统以及单道批处理时期，内存中一次只装入一道程序。它独占全部资源，完成后才切换下一道。机器常常空闲，效率低，由此推动了后续并发执行技术的发展。

为明确「谁必须等待谁完成」，引入前趋图：结点为程序段或语句，有向边表示偏序。下面先给出定义，再结合图2-1，然后对照顺序执行（图2-2）与并发执行（图2-3、图2-4）。

前趋图是一个有向无环图，英文记作 DAG。每个结点可以表示一个进程、一段程序，甚至一条语句；结点之间的箭头表示偏序，即前趋关系。

写成 Pi→Pj，表示 Pj 开始之前 Pi 必须已完成。此时 Pi 是 Pj 的直接前趋，Pj 是 Pi 的直接后继。没有前趋的结点称为初始结点，没有后继的称为终止结点。结点还可带一个重量，表示该段程序的规模或执行时长。

具体的一组关系画在图2-1 里。

图2-1 用九个结点画出下面这组前趋关系。P1 是初始结点，分别走到 P2、P3、P4；P2 与 P3 都进入 P5，P4 分出 P6 和 P7；P5 与 P6 汇合到 P8，P7 与 P8 再汇合到终止结点 P9。

前趋图里不能有环。一旦出现环，就会有结点永远等不到前趋结束，这种关系实现不了。

一个应用程序常拆分为若干段，每段执行一项确定的任务，且必须按次序进行：只有前一段完成，后一段才能开始。

用圆圈表示操作：I 是输入，C 是计算，P 是打印，箭头表示先后。一道作业就是 Ii→Ci→Pi。语句也一样，只能写成 S1→S2→S3。图2-2 就是这种一条链——没有分叉，也就没有可以同时推进的结点。

程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。

四条语句的前趋关系

再看四条赋值语句：S1 写 a := x+2，S2 写 b := y+4，S3 写 c := a+b，S4 写 d := c+b。

S1 与 S2 互不依赖，可以并发；S3 使用 a 和 b，必须等待 S1 和 S2 均结束；S4 使用 c 和 b，必须等待 S3 和 S2。图2-4 给出了这组前趋边。该图与图2-3 不同：一张描述一批作业的 I/C/P 流水，一张描述一个程序段中四条语句的依赖关系。

系统中同时存在多道作业时，输入、计算、打印可错开进行，不再是一道作业完成后再切换下一道。

图2-3 里，同一作业仍然是 I→C→P；相邻作业的 I、C、P 各自排成队，所以有 Ii→Ii+1、Ci→Ci+1、Pi→Pi+1。但 Ii+1 与 Ci、以及与 Pi−1 之间没有前趋边，可以重叠执行。这就是程序并发执行时的前趋图。