并发执行判定条件.pptVIP

程序并发执行的条件 1、读、写集的概念 2、Bernstein条件 3、程序并发执行的判定 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} 2、Bernstein条件 1966年Bernstein首先提出了p1、p2并发执行的条件，又称为Bernstein条件。 若两个程序p1、p2能满足下述条件，他们便能并发执行，且具有可再现性。 R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ 3、程序并发执行的判定 例如，有四条语句： S1：a:=x+y S2：b:=z+1 S3：c:=a-b S4：w:=c+1 利用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} 容易判定S1与S2可并发执行，而S1与S3、S2与S3、S3与S4不能并发执行。 考虑S1与S4能不能并发执行？ 利用前趋图判定 无前趋后继关系的两个节点可并发执行，如上图所示。 * S1 S2 S3 S4 *