前趋图

前趋图：用于描述进程之间的执行顺序的一种有向无循环图。

结点表示： 一个进程、一个程序段或 一条语句。
有向边表示： 前驱关系。箭头所指的是后继。

例题

(2009年下半年软件设计师上午试卷25、26题)

进程P1、P2、P3和P4的前趋图如下：

若用PV操作控制这几个进程并发执行的过程，则需要设置4个信号量S1、S2、S3 和S4，且信号量初值都等于零。下图中a和b应分别填写（25)，c和d应分别填写(26)。

(25)A.P(S1) P(S2) 和 P(S3)    B.P(S1) P(S2) 和 V(S1)

​     C.V(S1) V(S2) 和 P(S1)     D.V(S1) V(S2) 和 V(S3)

(26)A.P(S1) P(S2) 和 P(S4)    B.P(S2) P(S3) 和 P(S4)

​      C.V(S1) V(S2) 和 V(S4)    D.V(S2) V(S3) 和 V(S4)

解析：

将4个信号量，按顺序写到图一上。

执行操作之前为P操作，执行操作之后为V操作。

a：为P1执行之后，故为V操作，操作的信号量由图一可知为S1和S2，故a为V（S1）V（S2）。
b：为P2执行之前，故为P操作，操作的信号量由图一可知为S1，故b为P（S1）。
c：为P3执行之前，故为P操作，操作的信号量由图一可知为S2和S3，故c为P（S2）P（S3）。
d：为P4执行之前，故为P操作，操作的信号量由图一可知为S4，故d为P（S4）。


(2010年下半年软件设计师上午试卷23、24、25题)
进程P1、P2、P3、P4和P5的前趋图如下：

若用PV操作控制进程P1〜P5并发执行的过程，则需要设置6个信号量S1、S2、S3.S4.S5和S6,且信号量S1〜S6的初值都等于零。下图中a和b处应分别填写 (23)， c和d处应分别填写（24) , e和f处应分别填写（25)。

(23)A.P(S1) P(S2) 和 P(S3)P(S4)     B.P(S1) V(S2) 和 P(S2) V(S1)

      C.V(S1) V(S2) 和 V(S3) V(S4)     D.P(S1) P(S2) 和 V(S1) V(S2)

(24)A.P(S1) P(S2) 和 V(S3) V(S4)     B.P(S1) P(S3) 和 V(S5) V(S6)

​       C.V(S1) V(S2) 和 P(S3) P(S4)   D.P(S1) V(S3) 和 P(S2) V(S4)

(25)A.P(S3) P(S4) 和 V(S5)V(S6)     B.V(S5) V(S6) 和 P(S5) P(S6)

​      C.P(S2) P(S5) 和 P(S4) P(S6)    D.P(S4) V(S5) 和 P(S5) V(S6)

解析：如上题。

(2015年上半年软件设计师上午试卷23、24、25题)

若用PV操作控制进程P1、P2、P3、P4 、P5并发执行的过程，则需要设置5个信号

量S1、S2、S3、S4和S5，且信号量S1～S5的初值都等于零。下图中a、b 和c处应分别填写（23），d和e处应分别填写（24），f和g处应分别填写（25）。

(23)A.V(S1)、P(S1)和V(S2)V(S3)     B.P(S1)、V (S1)和V(S2)V(S3)

​     C.V(S1)、V(S2)和P(S1)V(S3)       D.P(S1)、V(S2)和V(S1)V(S3)

(24)A.V(S2)和P(S4)     B.P(S2)和V(S4)

​       C.P(S2)和P(S4)     D.V(S2)和V(S4)

(25)A.P(S3)和V(S4)V(S5)     B.V(S3)和P(S4)P(S5)

​       C.P(S3)和P(S4)P(S5)     D.V(S3)和V(S4)V(S5)

解析：如上题。

(2016年上半年软件设计师上午试卷26、27、28题)

进程P1、P2、P3、P4和P5的前趋图如下图所示：

若用PV操作控制进程P1、P2、P3、P4和P5并发执行的过程，则需要设置5个信号S1、S2、S3、S4和S5，且信号量S1～S5的初值都等于零。下图中a和b处应分别填（26），c和d处应分别填写（27），e和f处应分别填写（28）。

(26)A.V(S1)P(S2)和V(S3)     B.P(S1)V(S2)和V(S3)
      C.V(S1)V(S2)和V(S3)     D.P(S1)P(S2)和V(S3)
(27)A.P(S2)和P(S4)     B.P(S2)和V(S4)
      C.V(S2)和P(S4)     D.V(S2)和V(S4)
(28)A.P(S4)和V(S4)V(S5)     B.V(S5)和P(S4)P(S5)
      C.V(S3)和V(S4)V(S5)     D.P(S3)和P(S4)V(P5)

解析：如上题。

(2017年上半年软件设计师上午试卷26、27、28题)

进程 P1、P2 、P3、P4 和 P5 的前趋图如下所示:

若用 PV 操作控制进程 P1、P2、P3、P4 和 P5 并发执行的过程，需要设置 5 个信号量 S1、S2、S3、S4 和 S5，且信号量 S1~S5 的初值都等于零。如下的进程执行图中 a 和 b 处应分别填写(26)，c 和 d 处应分别填写(27) ，e 和 f 处应分别填写(28)。

(26)A.V (S1)和 P(S2)V(S3)     B.P(S1)和 V(S2)V(S3)

​       C.V(S1)和 V(S2)V(S3)     D.P(S1)和 P(S2)V(S3)

(27)A.P(S2)和 P(S4)     B.V(S2)和 P(S4)

​      C.P(S2)和 V(S4)     D.V(S2)和 V(S4)

(28)A.P(S4)和 V(S5)    B.V(S5)和 P(S4)

​       C.V(S4)和 P(S5)   D.V(S4)和 V(S5)

解析：如上题。

(2018年下半年软件设计师上午试卷24、25、26题)

进程P1、P2、P3、P4和P5的前趋图如下所示：

若用PV操作控制这5个进程的同步与互斥的程序如下，那么程序中的空①和空②处应分别为(24)，空③和空④处应分别为(25)，空⑤和空⑥处应分别为(26)。

(24)A. V(S1)和P(S2)     B. P(S1)和V(S2)

    　C. V(S1)和V(S2)     D. V(S2)和P(S1)

(25)A. V(S3)和V(S5)     B. P(S3)和V(S5)

  　C. V(S3)和P(S5)     D. P(S3)和P(S5)

(26)A. P(S6)和P(S5)V(S6)     B. V(S5)和V(S5)V(S6)

  　C. V(S6)和P(S5)P(S6       D. P(S6)和P(S5)P(S6)

解析：原理一样。

(2019年下半年软件设计师上午试卷23、24、25题)

19、进程p1、p2、p3、p4和p5的前趋图如下所示：

若用PV操作控制这5个进程的同步与互斥的程序如下，那么程序中的空①和空②处应分别为（23）；空③和空④处应分别为（24）；空⑤和空⑥处应分别为（25）

(23)A.V(S1)和P(S2)P(S3)     B.P(S1)和V(S1)V(S2)

​       C.V(S1)和V(S2)V(S3)     D.P(S1)和V(S1)P(S2)

(24)A.V(S4)V(S5)和P(S3)     B.V(S3)V(S4)和V(S5)

​      C.P(S4)P(S5)和V(S5)     D.P(S4)P(S5)和V(S4)

(25)A.P(S6)和P(S5)V(S6)     B.V(S5)和V(S5)V(S6)

​       C.P(S6)和P(S5)P(S6)     D.V(S6)和P(S5)P(S6)

解析：如上题。

练习题1

问：进程A、B、C、D该执行什么PV操作？
答：
进程A——剁肉；V(Sa)   进程B——切葱花；V(Sb)    进程C——切姜粒；V(Sc)
进程D——搅拌肉馅；P(Sa)、P(Sb)、P(Sc)、V(Sd)
进程E——包饺子；P(Sd)

前趋图：是为了描述一个程序的各部分间的依赖关系，或者是一个大的计算的各个子任务间的因果关系的图示。

---

练习题2

进程P1、P2、P3、P4、P5的前趋图如下：

  若用PV操作控制进程并发执行的过程，则需要设置4个信号量S1、S2、S3和S4且信号量初值都等于零。下图中a和b应分别填写（1） ，c和d应分别填写（2）， e和f应分别填写（3）。

第一空：
A. P（S1）和P（S2）
B. P（S1）和V（S2）
C. V（S1）和V（S2）
D. V（S1）和P（S2）

第二空：
A. P（S1）、P（S2）和V（S3）、V（S4）
B. P（S1）、P（S2）和P（S3）、P（S4）
C. V（S1）、V（S2）和P（S3）、P（S4）
D. V（S1）、V（S2）和V（S3）、V（S4）

第三空：
A. P（S3）和P（S4）
B. P（S3）和V（S4）
C. V（S3）和V（S4）
D. V（S3）和P（S4）

注意：此题我们可以将信号量S1…S4依次标注在图1的4个箭头上，在用PV操作去思考解题思路。

---

练习题3

  假设某系统采用非抢占式优先级调度算法，若该系统有两个优先级相同的进程P1和P2,各进程的程序段如下所示，若信号量S1和S2的初值都为0。进程P1和P2并发执行后a、b和c的结果分别为：a=_ (1) _、b= _ (2) _、c= _ (3) _。

P1程序段begin{                                			P2程序段begin{
a:=1;													 b:=2;							
a:=a+1;													 b:=b+1;
V(S1);													 P(S1);
c:=a+5;													 b:=a+b;
P(S2);													 V(S2);
a:=a+c;										 			 c:=b+c;
}														 }
end											 			 end

(1) A. 9   B. 12   C. 13   D. 14
(1) A. 5   B. 6     C. 9     D. 10
(1) A. 4   B. 6     C. 12   D. 13

注意：此题着重说明了不考虑优先级，所以我们不能按照常规的PV操作去思考本题。在进程P1阻塞的情况下，当P2去唤醒P1时不生效，P2还是依次执行完毕后再次执行P2。得到的结果如下图所示：

---

在早期未配置OS的系统和单批道处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并行执行。可见，这种方式浪费资源、系统运行效率低。

2.1.1 前趋图

为了更好地描述程序的顺序和并发执行情况，我们先介绍用于描述程序执行先后顺序的前趋图。所谓前趋图，是指一个有向无循环图，可记为DAG，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表示两个结点之间存在的偏序或前趋关系。

进程（或程序）之间的前趋关系可用“→”来表示，如果进程P_i和P_j存在着前趋关系，可表示为(P_i,P_j)∈→，也可以写成P_i→P_j，表示在P_j开始执行之前P_i必须完成。此时P_i是P_j的直接前趋，而称P_j是P_i的直接后继。

在前趋图中，把没有前趋的结点称为初始结点，把没有后继的结点称为终止结点。此外，每个结点还具有一个重量，用于表示该结点所含有的程序量或程序的执行时间。

如上如所示的前趋图中，存在着如下前趋关系：

注意：

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

2.1.2 程序顺序执行

1. 程序的顺序执行

通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。

例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后才是运行打印程序，打印计算结果。我们用结点代表各程序段的操作，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的前后次序。上述的三个程序段间就存在着这样的前趋关系：I_i→C_i→P_i，其执行的顺序可以用如下前趋图描述：

即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含三条语句的程序段：

S₁：a:=x+y;

S₂：b=a-5;

S₃：c=b+1;

其中，语句S₂必须在语句S₁后（即a被赋值）才能执行，语句S₃也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系：S₁→S₂→S₃，应按如下前趋图顺序执行：

2. 程序顺序执行时的特征

1. 顺序性

   指处理机严格地按照程序所规定地顺序执行，即每一操作必须在下一操作开始之前结束。

2. 封闭性

   指程序在封闭地环境下运行，即程序运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响。

3. 可再现性

   指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“走走停停”地执行，都可获得相同的结果。程序顺序执行时的这种特性，为程序员检测和矫正程序的错误带来了很大的方便。

2.1.3 程序并发执行

1. 程序的并发执行

例1：

在上文所述的输入程序、计算程序和打印程序三者之间，存在着I_i→C_i→P_i这样的前趋关系，以至于对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况如下图所示：

由上图可以看出，存在着前趋关系I_i→C_i，I_i→I_i+1，C_i→P_i，C_i→C_i+1，P_i→P_i+1，而I_i+1和C_i及P_i-1是重叠的，即在P_i-1和C_i以及I_i+1之间，不存在前趋关系，可以并发执行。

例2：

对于具有下述四条语句的程序段：

S₁：a:=x+2

S₂：b:=y+4

S₃：c:=a+b

S₄：d:=c+b

可画出如下图所示的前趋关系。可以看出：S₃必须在a和b被赋值后方能执行；S₄必须在S₃之后执行；但S₁和S₂则可以并发执行，因为它们彼此互不依赖。

2. 程序并发执行时的特征

在引入了程序间的并发执行功能后，虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成同一项任务而相互合作，致使在这些并发执行的程序之间必将形成相互制约的关系，由此会给程序并发执行带来新的特征。

1. 间断性

   程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。如下图中的I、C和P是三个相互合作的程序，当计算程序完成C_i-1的计算后，如果输入程序I_i尚未完成数据的输入，则计算程序C_i就无法进行数据处理，必须暂停运行。只有当程序暂停的因素消失后（如I_i已完成数据输入），计算程序C_i便可恢复执行。由此可见，相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。

   

2. 失去封闭性

   当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其他程序的影响。例如，当处理机已被分配给某个程序运行时，其它程序必须等待。显然程序的运行已失去了封闭性。

3. 不可再现性

   程序在并发执行时，由于失去了封闭性，也将导致其又失去了可再现性。例如，由两个循环程序A和B，它们都共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后将N置成“0”。程序A和B以不同的速度运行。这样，可能出现下述三种情况（假定某时刻变量N的值为n）：①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。

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

---

参考资料：《计算机操作系统(第四版)》—— 汤小丹等。