标识无冲突可重复网极小活标识的配置

Vol 15增刊 系 统 仿 真 学 报

Aug 2003 JOURNAL OF SYSTEM SIMULATION · 35 ·

无冲突可重复网极小活标识的配置

许安国,赵义军

山东科技大学基础部, 泰安271019

The Assignment of MinimalLiveMarkingfor Choice-Free RepetitivePetri Net

XUAn-guo,ZHAO Yi-jun

(Dept of Basic Courses,Shandong University of Science and Technology,Taian 271019,China)

Abstra ct:The first, the choice-free rep etitive Petri net is defined,and it is proven that this kind of nets is all structural live

The second, the assignment of minimal live marking for choice-free rep etitive Petri net is transformed into the assignmentof minimal live marking for the strong connective T graph The m-n+1 linear indep endence the group of direct circles isobtained by solving m-n+1 linear indep endence minimal S invariants’ supp ort sets ofthe strong connective T graph Hence,the direct spanning root-tree of the strong connective T graph is constructed The effective algorithm of the assignment ofminimal live marking is given based on the direct sp anning root-tree

Keywords:choice-free rep etitive Petri net; liveness;minimal live marking;T graph

引 言

近些年对于P et ri网的活性判定问题开辟了一条新的 理[1]设(N,M0)是一个无冲突网系统 (N,M0)是活途径先从网的结构入手研究活的P etri网应满足的条件 的充分必要条件是存在一个可达标识然后讨论在这种网中怎样配置初始标识才能使得到的标识 MR(N,M0) :M0[ 其中 #(ti /)X(i)  则网为活的。文[2]提出了网的结构活性定义使这种研究策 X(X(1),X(2),X(n))T为正整数向量且使得。但文[1]并未略明朗化。 [2]还给出了S图、 T图、 自由选择网和扩充的 讨论无冲突网的结构活性判定与极小活标自由选择网结构活的充分必要条件。文[2]中提到标识图 识的配置问题 因此本文研究了无冲突网的结构活性的判(G,M0) M0是G的活标识并且有最小的标点数称M0 定并把结构活的无冲突网的极小活标识的配置作为本文研是G的活的安全标识 即M0是(G,M0)的极小活标识。文 究的重点问题之二。一个自动控制系统常常可以用一个活的

[2]给出了下述定理 P et ri网来描述结构活的P etri网的极小活标识的配置就它的

标识只能用凑的方法无规律可循但是对于较多回路组成 1 无冲突可重复网的结构活性判定及的强连通T图的极小活标识配置根本无法实现这也是本 极小活标识配置问题的转化

收稿日期 2003-05-28 基金项 定义1 1[1]设N是一个S/T网 N叫做无冲突网当且

Vol 15增刊· 36 · 系 统 仿 真 学 报 Aug 2003

A组成一个互为上故 必 存在 M0 :M0[  设 M0 [M  即 游回路的集合。

由于结构活网一定是可重复网再考虑定理12可得 为N的一个陷井。

定理1 3设N是无冲突网则N是结构活网的充要条 定义17[2]网N(S,T;F)称为自由选择网当且仅当件是N是可重复网。 t1 ,t2T(t1 t2)

证明对sS若不存在有向回路C使sC则 显然图1图2中各自的S元组成的集合构成一个死锁从s向后追踪路可能不止一条不能退到某个回路上这 也各自构成一个陷井。

种情况下必退到某个变迁节 tb tb可能不止一个。 定理1 5 N(S,T;F)为一个无冲突可重复网 S1S



达t且tC1 ,tC则称C1为C的一个上游回路同时称C 由上可得

定义 14 若 N 中有向回路 C1和 满足 配上M(C1 )1 其他位置空着 另一个包含s4位置的分支

C2

C1SC(C2)C2SC(C1) 称C1和C2互为上游回路,如图 让s4空着删去的s 3也让其空着则图1就成为活的。2 对图2可以这样配置极小活标识首先保留C1的位置所示。

Vol 15增刊

Aug 2003 许安国, 等无冲突可重复网极小活标识的配置 · 37 ·

是如何配置上极小活标识。在一个无冲突可重复网 N中 连通T-图分支中的无界位置保持空着剩下的问题就归结首先利用已知的代数算法求出N的所有死锁与陷井然 为强连通 T- 图极小活标识的配置其中包括

对每一个Li 保留Ci1 然后删去通向Ci1的任一位置 按前面叙述的删去方法得到图 4a  b  c几个连的输入弧(tp,sj),sj Ci1 ,tp Ci1(i1,2 ,q) 其次删去N中 通的T图分支。

为一条弧其结构活性不变因此为方便起见只对没有并 个标点 C1 ,C2 , ,Ck内其余位置让其空着如 kmn1 行弧的T图加以讨论。 则极小活标识配置完毕如果kmn1 则转2 。

(1)解方程组Ay0 求出N的mn1个线性无关 (2)除e1 ,e2, ,ek外在Ck1 ,Ck2, ,Cmn1中找出以立于极小支集上的极小S不变量它对应的mn1 ek1为公共连枝的所有有向回路 不妨设为个

变迁tj为根的有向生成树J的算法在此不再重述。 在sjk1中放上一个标点 Ck1 ,Ck2 , ,C kp中其他位置3

N的极小活标识 (3)在Ckp1 ,Ckp2, ,Cmn1中找出以ekp1为公共

设J是按照上述方法构造的有向生成树性无关有向回路组为C1 ,C2 , ,Cmn1 对应的线性无关极 有向量设为ykp1 ,ykp2, ,y kpq 则在s jkp1内放上小S不变量为y1 ,y2 , ,ymn1  对应删去的连枝为 一个标点在Ckp1 ,Ckp2 , ,Ckpq 内其余位置就让其空e1 ,e2, ,emn1 它们对应的位置为sj1 ,sj2 , ,sjmn1 。 着如果k pqmn1 则极小活标识配置完毕

Vol 15增刊· 38 · 系 统 仿 真 学 报 Aug 2003

M(Ci)1(i1,2 ,mn1)  当删去sj 1 ,sj2 ,sjr 对应的连枝 C1 ,C2 ,C3 ,C4 ,C5 ,C6 选t1为有向生成树的根可得有向生e 1,e2, er后线性无关有向回路组C1 ,C2 , ,Cmn1中每一个有向 成树(如图5(a)所示 。

回路均被破坏也即N中的任一个有向回路都不存在 (3)配置极小活标识

因此N中的任一个有向回路至少包含e1,e2, er中的一条连 其中只有y1 ,y2,y3 ,y4中对应s3的分量为1在s3内放枝 即对于C(imn1):M(c)1,(mn1i2mn1)。 由文献[2] 上一个标点只有在y5 ,y6中对应s 10的分量为1在s10内

28页定理67 即定理[2]知按上法配置的标识是强连通T- 放上一个标点其余位置让其空着见图5 a 。图的极小活标识。 同理根据上述 6 个线性无关有向回路4 举例

例2对图4所示的T图的强连通部分配置极小活标识。 其中只有y1对对应s2的分量为1则在s2内放上一

解写出图4(a)所示的T图的强连通部分的关联矩阵A 个标点只有y2对应s4的分量为1则在s4内放上一个标

 无界位置让其空着  图

a b c

a a′  b

图5

Vol 15增刊

Aug 2003 许安国, 等无冲突可重复网极小活标识的配置 · 39 ·

4(c)的无界位置让其空着在图3中被删去的无界位置让其 参考文献:

空着 即可将图3所示的无冲突可重复网配置好极小活标识

[1] Enrique Teruel, Jose’Manuel Colom Member IEEE,Manuel Silvas1,s2,s3,s4,s5,s6,s7,s8,s9,s10,s11,s12,s13,s14, Member IEEE Choice-Free Petri Nets:A Model for Deterministic

M0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0)T Humans, 1997:27(1): 73-83

突网网的结构满足可重复性的条件就可判断无冲突网的结构活 Specia l Volume in the series Advances in Petri Nets[M] New York:性。另外本文解决了无冲突可重复网极小活标识的配置问 Springer-Verlag, 1987

题

小S_不变量的方法结合强连通T_图的有向生成树给 [7]许安国,王培良 加权T_图活性的进一步研究[J] 计算机学报,出了强连通T_图极小活标识配置的有效算法解决了文[2] 1998,21(1): 92-96

中由多个回路组成的T

上接第28页为这两个函数的增 4 结论

广P et ri网模型。

在这两个图中假设进程组中有m个进程而其中的 在点到点通信的增广P etri网模型中用库所s b体现了

图10 数据收集函数的增广Petri网模型 [5] 罗省贤, 何大可 基于MPI 的网络并行计算环境及应用[M] 成

都:西南交通大学出版社, 2001

[6] J L Peterson著,吴哲辉译 Petri网理论与系统模拟[M]徐州:中

国矿业大学出版社, 1989