Berstein条件

首先看一道习题

1.程序的顺序执行和并发执行有什么异同之处？
2.什么是Bernstein条件？
(1)对于下面的语句：
$S1：a=5−x$S1：a=5−x
$S2：b=a∗x$S2：b=a∗x
$S3：c=4∗x$S3：c=4∗x
$S4：d=b+c$S4：d=b+c
$S5：e=d+3$S5：e=d+3

(2)说明S2和S3是可以并发执行的，而S3和S4是不能并发执行的。

1.顺序执行与并发执行的异同之处：
(1)顺序执行要求一个程序开始执行必须要等到前一个程序已执行完成，具有顺序性；而并发执行若干个程序可以同时在系统中执行，时间上具有重叠性，因此不具有顺序性。
(2)顺序执行的程序一旦开始执行，它的计算结果不受外界因素影响，具有封闭性；而并发执行程序之间资源共享，因此不具有封闭性。
(3)顺序执行其程序的运行的结果与与时间无关，即给定相同的输入，一定会得到相同的输出，具有可再现性；而并发执行由于存在资源共享，失去结果可再现性。
(4)顺序执行与并发执行在单CPU环境下每个时刻都只能有一个程序被执行
2.Berstein条件的解释：
若两个程序p1、p2满足如下条件：
$R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)=Ø$R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)=Ø
（$R(read)$R(read)读的集合、$W(write)$W(write)写的集合）
那么他们便能并发执行，且具有可再现性。
(1)首先解释一下前驱图的定义，如下几点：

• Precedence graph (前趋图) is a Directed Acyclic Graph(有向无环图, DAG).
• Node(结点)：代表一个执行单元（如一条语句、一个程序段或进程）
• Edge(边, directed edge(有向边))：The precedence relation (前趋关系)“→”
  →={(Pi,Pj)| Pi必须在Pj开始执行前执行完}
  接下来是根据此题画出的前驱图：