第4章进程代数讲述.ppt

* 选择算子、并行算子 选择算子-- 描述进程从多个事件中选择执行一个行为 选择算子用符号“+”表示。例如： P = a.(c.NIL + d .NIL) Q1 = a.b.NIL + c.Q2 Q2 = d.Q +e .Q2 并行算子-- 将多个进程组合成一个进程 并行算子用符号“|”表示。例如： P =Q| a.b.Q； P = a.b.NIL | Q | c.d.e.R 。 * 并行算子、屏蔽算子 并行算子不能用于事件 例如： P= a|b 是非法表达式，而P=a.NIL|b.NIL 是合法表达式。 选择算子和并行算子具有如下一些性质： P+P = P P+NIL = P a.P+b.Q = b.Q+a.P P|Q = Q|P a.P+(b.Q+c.R) = (a.P+b.Q)+c.R P|(Q|R) = (P|Q)|R 屏蔽算子-- 屏蔽算子用来限制一些指定事件的执行 屏蔽算子用符号“\ ”表示，“\ ”之后的字符表示列入屏蔽范围的事件。 屏蔽a也将屏蔽a，反之亦然。 例如，设a和a，b和b为两对协同事件，下面的例子表示出限制算子的作用。 (a.P| a.Q)\ a = a.(P|Q) \ a (a.P|b.Q) \ {a, b} = NIL * 4.2.2 AB协议的规格 见教材p96-98（略） * 混合进程 进程P和Q的混合进程是，进程中所执行的每个事件为P或Q中的一个事件，记为P|||Q。 符号“|||”称为进程的混合复合算子 混合进程是各自进程中事件的交替执行，无论事件是否相同。 并发进程则是各自进程中不同事件的交替执行，但相同事件需要同步执行。 * 混合进程 STOP进程是不执行任何事件的进程,可能由于死锁或者其它设计误错所引起,并不是设计人员所期望的系统行为。 进程并不一定要无休止地执行下去，在进程完成所需执行任务之后，就可以停止执行，将这种停止执行称为成功停止。 为了和STOP加以区分，引入一成功终止事件，记为 “?”，并定义一成功终止进程SKIPA: ?SKIPA= A?{?} 如: 仅执行choc 或toffe后, 就成功终止的进程表示为 VEN = (coin→ (choc→SKIP| toffe→SKIP)) * 顺序进程 进程P和Q的顺序进程是，成功执行P后再继续执行Q的进程，记为P;Q 。 符号“;”称为进程的顺序复合算子。 进程的顺序复合算子具有如下性质： SKIP ; P = P ; SKIP = P （SKIP是其单位元） P; (Q; R) = (P ; Q) ; R (x：B→P(x)) ; Q = (x：B→(P(x) ; Q)) (a →P) ;Q = a →(P;Q) STOP ; Q = STOP * 4.1.4 进程的模型 (1) 确定性进程 确定性进程P的行为具有两个属性： ?P --- P执行中所包含的事件集合 traces(P) --- P执行的所有可能事件序列（迹）集合 上述两个属性满足如下条件： ?traces(P) （非空性） s^t?traces(P) ? s?traces(P) （前缀封闭性） traces(P) ? (?P)* * (1) 确定性进程 满足上述条件的事件集合A和迹集合S组成的序偶(A,S)，由下述步骤可构造出与之相应的进程P： ① P={x?S} ② 对x?P，P(x):= {t| x^t?S} 也可从进程P构造序偶(A, S)： A = ?P S = traces(x：P→P(x)) * 确定性进程定义 确定性进程是满足下列条件的一个序偶(A, S)，其中A是一个事件符号集合，S?A* ?S s^t?S ? s?S 下面给出满足上述定义的一些确定性进程模型： STOPA=(A, {}) RUNA= (A, A*) (x：B→(A, S(x)))=(A,{} ? {x^s| x?B ? s?S(x)}) (B?A) (A, S)\s = (A, {t | (s^t ? S)}) * (2) 非确定性进程 非确定性进程的行为较之于确定性进程更为复杂 对于或进程和选择进程，由于进程的迹是相同，如果仅从进程迹的角度是难以对二者进行区分。 如果将它们放在环境（进程）交互中，就会发现或进程在起始执行时会产生死锁，而选择进程不会有此现象。 但是，或进程只是可能发生死锁，至于是否会发生，无从所知，这也带来进程行为的不确定性。 * 进程的拒绝事件集 给定进程P，设X为与P交互的其它环境进程的初始执行