4程序并发执行时的特征(续) ◆不可再现性 程序在并发执行时,由于失去了封闭性,也导致失去了可再现 性 例如:有两个循环程序A和B,它们共享一个变量N。程序A 每执行一次时都要做N=N+1操作;程序B每执行一次时,都 要做prnt(N)操作,然后再将N置成“0”,程序A和B以不同 的速度运行。(假定某时刻变量N的值为k) (1)N=N+1在 print(N)和N=0之前,此时得到的N值分别为 (2)N=N4在prmt(N)和N=0之后,此时得到的N值分别为 (3)N=N+1在 print(N)和N=0之间,此时得到的N值分别 为 k,k+1,0
4.程序并发执行时的特征(续) 不可再现性 – 程序在并发执行时，由于失去了封闭性，也导致失去了可再现 性。 – 例如：有两个循环程序A和B，它们共享一个变量N。程序A 每执行一次时都要做N＝N＋1操作；程序B每执行一次时，都 要做print（N）操作，然后再将N置成“0”，程序A和B以不同 的速度运行。（假定某时刻变量N的值为k） （1）N＝N＋1在print（N）和N＝0之前，此时得到的N值分别为 （2）N＝N＋1在print（N）和N＝0之后，此时得到的N值分别为 （3）N＝N＋1在 print（N）和N＝0之间，此时得到的N值分别 为 k＋1，k＋1，0 k， 0， 1 k， k＋1， 0
5程序并发执行的条件 ◆1966年, Bernstein(伯恩斯坦)提出了相邻语句 P1,P2可以并发执行的条件。 ◆如果并发执行的各程序段中语句或指令满足 Bernstein的条件,则认为并发执行不会对执 结果的封闭性和可再现性产生影响
5.程序并发执行的条件 1966年，Bernstein(伯恩斯坦)提出了相邻语句 P1，P2可以并发执行的条件。 如果并发执行的各程序段中语句或指令满足 Bernstein的条件，则认为并发执行不会对执行 结果的封闭性和可再现性产生影响
定义程序读集与写集符号 R(P)={a1a2,…am} 表示程序P在执行期间需引用的变量的集合称P的读集; W(P)={b1,b2,…bm} A必表示程序P在执行期间需改变的变量的集合称P的写集 若有两条语名P1:c=a+b;P2:X=x+1;则它们的读集与写为: R(P1)={a,b}W(P1)={c R(P2)={x}W(P2)={x} P1的读集与写集的交集为空;P2的读集与写集的交集非空; R(P1)NW(P1= R(P2)NW(P1=(]
定义程序读集与写集符号 R(Pi )={a1 ,a2 ,···,am} 表示程序Pi在执行期间需引用的变量的集合,称Pi的读集; W(Pi )={b1 ,b2 ,···,bm} 表示程序Pi在执行期间需改变的变量的集合,称Pi的写集; 若有两条语名P1: c=a+b; P2:x=x+1; 则它们的读集与写为: R(P1)={ a, b } W(P1)={ c } R(P2)={ x } W(P2)={ x } P1的读集与写集的交集为空;P2的读集与写集的交集非空; R(P1)∩W(P1)={ } R(P2) ∩W(P1)={ x }
Bernstein条件 ◆若两个程序P1和P2能满足下述条件,它们 便能并发执行,否则不能 62 R(P)nW(P2U R(P2)nW(P,)U W(P1)nW(P2)=) 即 人①R(PWP2) ②2WP)∩RP2)={} 8W(P)W(P2)={} 同时成立
Bernstein条件 若两个程序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 (P1 )∩W(P2 )={ } ② W(P1 )∩R (P2 )={ } ③ W(P1 )∩W(P2 )={ } 同时成立