第二章进程管理 例:程序A、B,共享变量N。代码如下: 程房A 程房B BEGIN BEGIN REPEAT REPEAT N:=N+1 PRINTON N:=0 UNTIL FALSE UNTIL FALSE END END
第二章 进 程 管 理 例：程序A、B，共享变量N。代码如下： 程序A BEGIN REPEAT … … N：=N+1 … … UNTIL FALSE END 程序B BEGIN REPEAT … … PRINT(N) N:=0 … UNTIL FALSE END
第二章进程管理 两个程序以不同速度运行,可能出现三种情况: aN:=N+1在Prn(N和N:=0之前 N值分别为N+1,N+1,0 aN:=N+1在Prin(N)和N:=0之后 N值分别为N,0,1 aN:=N1在PrnN和N:=0之间 N值分别为N,N+1,0 思考:任何并发执行都是不可再现的吗?
第二章 进 程 管 理 两个程序以不同速度运行，可能出现三种情况： ▪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 思考：任何并发执行都是不可再现的吗？
第二章进程管理 并发执行的条件 并发执行的条件:达到封闭性和可再现性。 并发执行失去封闭性的的原因是共享资源的影响, 去掉这种影响就行了。1966年,由 Bernstein给出并 发执行的条件 将程序中任一语句或程序段Pi划分为两个变量的 集合,R(pi)和W(pji)。其中, R(pi)={a1,a2,an},程序pi在执行期间引用的 (读的)变量集,称为“读集”。 W(pi)={b1,b2,…bm},程序pi在执行期间改变的 (写的)变量集,称为“写集
第二章 进 程 管 理 并发执行的条件： 并发执行的条件：达到封闭性和可再现性。 并发执行失去封闭性的的原因是共享资源的影响， 去掉这种影响就行了。1966年，由Bernstein给出并 发执行的条件。 将程序中任一语句或程序段Pi划分为两个变量的 集合， R(pi)和 W(pi)。其中， R(pi)={a1,a2,…an}，程序pi在执行期间引用的 （读的）变量集，称为“读集” 。 W(pi)={b1,b2,…bm}，程序pi在执行期间改变的 （写的）变量集，称为“写集”
第二章进程管理 Bernstein条件: 如果对于语句p1、p2,如果同时满足以下 个条件 R(p1)∩W(p2)={ R(p2)∩W(p1)={} W(p1)∩W(p2)={} 则语句p1、p2可以并发执行
第二章 进 程 管 理 Bernstein条件: 如果对于语句p1、p2 ，如果同时满足以下 三个条件： R(p1)∩W(p2) ={ } R(p2)∩W(p1) ={ } W(p1)∩W(p2) ={ } 则语句p1、p2可以并发执行
第二章进程管理 例如,有如下四条语句: S1:a:=x+ S2:b:=z+1 S3: C:=a S4:W:=c+1 其中:R(S1)={x,y}W(S1)={a} R(S2)={z}W(S2)={b} R(S3)={a,b}W(S3)={c} R(S4)={c}W(S4)={w} 对于S1和S2,有: R(S1)∩W(S2)={},R(S2)∩W(S1)={}, W(S1)∩W(S2)={ 结论:语句S1和S2满足 Bernstein条件,可以并发执行。 其他语句之间自己分析
第二章 进 程 管 理 例如，有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a – b S4: w := c + 1 其中：R(S1)={x,y} W(S1)={a} R(S2)={z} W(S2)={b} R(S3)={a,b} W(S3)={c} R(S4)={c} W(S4)={w} 对于S1和S2 ，有： R(S1)∩W(S2) ={ }，R(S2)∩W(S1) ={ }， W(S1)∩W(S2) ={ } 结论：语句S1和S2满足Bernstein条件，可以并发执行。 其他语句之间自己分析