一、前驱图和程序执行

1.前驱图

前趋图:是一个有向无循环图，用于描述进程之间执行的前后关系。

具有九个结点的前趋图

存在下述前趋关系:
P1→P2，P1→P3，P1→P4，P2→P5， P3→P5， P4→P6，P4→P7，P5→P8， P6→P8，
P7→P9，P8→P9
或表示为: .
P={P1，P2，P3，P4，P5，P6，P7，P8, P9}
→={(P1，P2)， (P1，P3)，(P1，P4)， (P2， P5)，(P3，P5)，(P4，P6)， (P4，P7)，(P5，P8)，(P6， P8)， (P7，P9), (P8，P9)}

具有循环的图

前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。如图所示的前趋关系中就存在着循环。它一方面要求在S3开始执行之前, S2必须完成，另一方面又要求在S2开始执行之前，S3 必须完成。显然，这种关系是不可能实现的。

图中的每个结点可用于描述- 一个程序段或进程，乃至一条语句;
结点间的有向边则用于表示两个结点之间存在的偏序(亦称偏序关系)或前趋关系“→”
如果(Pi，Pj)∈→，可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。
在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。

2.程序顺序执行

2.1 程序的顺序执行

I:输入操作
C:计算操作
P:打印操作

S1:a:=x+y;
S2:b:=a-5;
S3:c:=b+1;

其中，语句S2必须在语句S后(即a被赋值)才能执行,语句S3也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系: S1→S2 →S3,应如图所示的顺序执行。

2.2 程序顺序执行时的特征

(1)顺序性:处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一一个操作结束之后开始。
(2)封闭性:程序是在封闭的环境下执行的，即，资源的状态(除初始状态外)只有本程序才能改变它。程序运行时独占全机资源程序一旦开始执行，其执行结果不受外界因素影响。
(3)可再现性:只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。

3. 程序并发执行

程序顺序执行时，资源利用率低

3.1程序的并发执行

在该例中存在下述前趋关系:
Ii→Ci，I i→I i+1， Ci- >Pi，Ci→Ci+1, Pi→Pi+1

I i+1和Ci及Pi-1是重叠的，即在Pi-1和Ci以及Ii+1之间，不存在前趋关系，可以并发执行。

对于具有下述四条语句的程序段:
S1: a:=x+2
S2: b:=y+4
S3: c:=a+b
S4: d:=c+b

画出的前驱图：

3.2 程序并发执行时的特征

(1) 间断性。程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。
“执行-暂停-执行”间断性的运行。

(2)失去封闭性。当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其它程序的影响。
(3)不可再现性
例:程序A: N:=N+1;
程序B: Print(N); N:=0;
程序A和程序B并发执行，可能出现三种情况(N=n) :
(1) N:=N+1在Print(N)和N:=0之前，此时得到的N值分别为n+1，n+1, 0。
(2) N:=N+1 在Print(N)和N:=0之后，此时得到的N值分别为n，0，1。
(3) N:=N+1 在Print(N)和N:=0之间，此时得到的N值分别为n，n+1， 0。

程序在并发执行时，由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，从而使程序的执行失去了可再现性；程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。