➢ 或表示为：Ｐ={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)}
➢ 应当注意，前趋图中必须不存在循环，但在上图(b)中却有着下述的前趋 关系：S2→S3, S3→S2
二、程序的顺序执行
➢1、程序的顺序执行 ➢2、程序顺序执行时的特征
1、程序的顺序执行
➢仅当前一操作(程序段)执行完后，才能执行 后继操作。例如，在进行计算时，总须先输 入用户的程序和数据，然后进行计算，最后 才能打印计算结果。
➢ 每个结点还具有一个重量(Weight)，用于表示该结点所含有 的程序量或结点的执行时间。
➢ 如：Ii→Ci→Pi和S1→S2→S3
DAG定义续
P2
P5
S1
P1
P3
P8
P9
P6
S2
P4
P7
(a) 具有九个结点的前趋图
S3
(b) 具有循环的有向图
➢ 对于上图(a)所示的前趋图， 存在下述前趋关系：P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
2、Bernstein条件
➢1966年Bernstein首先提出了p1、p2并发执行 的条件，又称为Bernstein条件。
➢若两个程序p1、p2能满足下述条件，他们便 能并发执行，且具有可再现性。
R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ
3、程序并发执行的判定
➢ 例如，有四条语句：
I1
I2
I3
I4
S1
C1

P2
P3
(a) 并发执行时的前趋图
P4
(b) 四条语句的前躯关系
➢ 在上图(a) ▪ Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 ▪ 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。
1、读、写集的概念
➢读集R(pi)={a1,a2,…,am}表示程序pi在执行期 间所要参考的所需参考的所有变量的集合。
➢写集W(pi)={b1,b2,…,bn}表示程序pi在执行期 间要改变的所有变量的集合。
➢如c:=a-b和w:=c+1两条语句，其读、写集分 别为：
▪ R(c:=a-b)={a,b} W(c:=a-b)={c} ▪ R(w:=c-1)={c} W(w:=c-1)={w}
• 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。
四、程序并发执行的条件
➢1、读、写集的概念 ➢2、Bernstein条件 ➢3、程序并发执行的判定
▪ S1：a:=x+y
S1
▪ S2：b:=z+1
S3
S4
▪ S3：c:=a-b ▪ S4：w:=c+1
S2
➢ 利用Bernstein条件判定
▪ R(S1)={x,y} R(S2)={z} R(S3)={a,b} R(S4)={c} ▪ W(S1)={a} W(S2)={b} W(S3)={c} W(S4)={w} ▪ 容S4易不判能定并S发1执与行S2。可并发执行，而S1与S3、S2与S3、S3与 ▪ 考虑S1与S4能不能并发执行？
第二章 进程的描述与控制
➢2.1 前趋图和程序执行 ➢2.2 进程的描述 ➢2.3 进程控制 ➢2.4 线程的基本概念
2.1 前趋图和程序执行
➢一、前趋图的定义 ➢二、程序的顺序执行 ➢三、程序的并发执行 ➢四、程序并发执行的条件
一、前趋图的定义
➢ 前趋图(Precedence Graph)是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前 后关系。图中的每个结点可用于描述一个程序段或进程，乃 至一条语句；结点间的有向边则用于表示两个结点之间存在 的偏序(Partial Order)或前趋关系(Precedence Relation)“→”。
➢ 利用前趋图判定
▪ 无前趋后继关系的两个节点可并发执行，如上图所示。
2.2 进程的描述
➢一、进程的定义与特征 ➢二、进程的基本状态 ➢三、进程的挂起状态 ➢四、进程控制块PCB
一、进程的定义与特征
➢1、进程的定义 ➢2、进程的特征
1、进程的定义
➢ 较典型的进程定义有：
▪ 进程是程序的一次执行。 ▪ 进程是可以和别的计算并发执行的计算。 ▪ 进程可定义为一个数据结构及能在其上进行操作的一个程序。 ▪ 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ▪ 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配
➢ 对于具有下述四条语句的程序段，可用上图(b)表示。 ▪ S1：a:=x+2 ▪ S2：b:=y+4 ▪ S3：c:=a+b ▪ S4：d:=c+b
2、程序并发执行时的特征
➢1) 间断性 ➢2) 失去封闭性 ➢3) 不可再现性
▪ 例如，有两个循环程序A和B，它们共享一个变 量N。程序A每执行一次时，都要做N∶=N+1操 作；程序B每执行一次时， 都要执行Print(N)操 作，然后再将N置成“0”。程序A和B以不同的速 度运行。
➢ →={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的 直接后继。在前趋图中，把没有前趋的结点称为初始结点 (Initial Node)，把没有后继的结点称为终止结点(Final Node)。
➢再如：
I1
C1
P1
I2
C2
P2
▪ S1：a:=x+y;
(a)程序的顺序执行
▪ S2：b:=a-5;
▪ S3：c:=b+1;
S1
S2
S3
(b)三条语句的顺序执行
2、程序顺序执行时的特征
➢⑴顺序性； ➢⑵封闭性； ➢⑶可再现性。
三、程序的并发执行
➢1、程序的并发执行 ➢2、程序并发执行时的特征
1、程序的并发执行