顺序执行与并发执行

一、前趋图

前趋图是一个有向无环图，可记为DAG（Directed Acyclic Graph），它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，节点间的有向边则表示两个节点之间存在的偏序关系或前趋关系。

进程（或程序）之间的前趋关系可用“$\to$→”来表示，如果进程$P_i$Pi​和$P_j$Pj​存在前趋关系，可以写成$P_i\to P_j$Pi​→Pj​，表示$P_j$Pj​开始执行前$P_i$Pi​必须完成。此时称$P_i$Pi​是$P_j$Pj​的直接前趋，而称$P_j$Pj​是$P_i$Pi​的直接后趋。在前趋图中，把没有前趋的结点称为初始节点，把没有后继的节点称为终止节点。

在下图中，存在如下的前趋关系：
$P_1\to P_2,P_1\to P_3,P_1\to P_4,P_2\to P_5,P_3\to P_5,P_4\to P_6,P_4\to P_7,P_5\to P_8,P_6\to P_8,P_7\to P_9,P_8\to P_9$P1​→P2​,P1​→P3​,P1​→P4​,P2​→P5​,P3​→P5​,P4​→P6​,P4​→P7​,P5​→P8​,P6​→P8​,P7​→P9​,P8​→P9​

注意前趋图中不允许有循环，否则必然会产生不可能实现的前趋关系。如下所示：

二、顺序执行

2.1 程序的顺序执行

通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后才是运行打印程序，打印计算结果。用节点表示上述过程，I代表输入操作，C代表计算操作，P代表打印操作，用箭头表示前趋关系。这样，上述的三个程序段就可以用前趋图来表示：

2.2 程序顺序执行时的特征

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

三、程序的并发执行

程序顺序执行时，虽然可以给程序员带来方便，但系统资源的利用率却很低。为此，在系统中引入了多道程序技术，使程序或程序段间能并发执行。然而，并非所有的程序都能并发执行。事实上，只有不存在前趋关系的程序间才可能并发执行，否则无法并发执行。

3.1 程序的并发执行

通过一个常见的例子来说明程序的顺序执行和程序的并发执行，还是以上面的计算程序为例。存在着$I_i\to C_i\to P_i$Ii​→Ci​→Pi​这样的前趋关系，对每一个作业的输入、计算和打印程序，都必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况则如下所示：

输入程序$(I_1)$(I1​)在输入第一次数据后，由计算程序$(C_1)$(C1​)对该数据计算的同时，输入程序$(I_2)$(I2​)可以再输入第二次数据，从而使第一个计算程序$(C_1)$(C1​)可以与第二个输入程序$(I_2)$(I2​)并发执行。事实上，正是由于$C_1$C1​和$(I_2)$(I2​)之间并不存在前趋关系，因此它们之间可以并发执行。一般来说，输入程序$(I_{i+1})$(Ii+1​)再输入第i+1次数据时，计算程序$(C_i)$(Ci​)可能正在对程序$(I_i)$(Ii​)的第i次输入的数据进行计算，而打印程序$(P_{i-1})$(Pi−1​)正在打印程序$(C_{i-1})$(Ci−1​) 的计算结果。

从上图可以看出，存在前趋关系：
$I_i\to C_i, I_i\to I_{i+1},C_i\to P_i,C_i\to C_{i+1},P_i\to P_{i+1}$Ii​→Ci​,Ii​→Ii+1​,Ci​→Pi​,Ci​→Ci+1​,Pi​→Pi+1​
而$I_{i+1}$Ii+1​和$(C_i)$(Ci​)以及$(P_{i-1})$(Pi−1​)使重叠的，即在$P_{i-1}$Pi−1​和$C_i$Ci​以及$I_{i+1}$Ii+1​之间，不存在前趋关系，可以并发执行。

3.2 程序并发执行时的特征

1. 间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。例如在上图中，I、C和P就是三个相互合作的程序当计算程序完成了$C_{i-1}$Ci−1​的计算后，如果输入程序$I_i$Ii​尚未完成数据的输入，则计算程序$C_i$Ci​就无法进行数据处理，必须暂停运行。只有当程序暂停的因素消失后（如$I_i$Ii​已完成数据输入），计算程序$C_i$Ci​便可恢复执行。由此可见，相互制约将导致并发程序具有“执行-暂停-执行”这种间断性的活动规律
2. 失去封闭性：当系统中存在着多个可以并发执行的程序时，系统中的各资源将为它们所共享，而这些资源的状态也有这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其他程序的影响。例如，当处理机已被分配给某个进程运行时，其他程序必须等待。显然，程序的运行已经失去了封闭性
3. 不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其又市区可在现性。例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作，程序B每次执行时，都要执行print（N）操作，然后执行N=0操作。程序A和B以不同的速度运行，这样就会出现以下的情况：如果N=N+1在print（N）和N=0前，那么N值分别为n+1，n+1，0；如果N=N+1在print（n）和n=0后，那么得到的n值分别为n，0，1；如果N=N+1在print（N）和N=0之间，此时得到的N值分别为n，n+1，0