ѧ
Journal of Software
2000 Vol.11 No.1 P.104-109



Petriģ͵ľ
ִ
ժҪPetriģͼжֲͬķ.򵥵ʹģͼȥģ⸴ӵϵͳ,Ʊ״̬ռıը,޷ϵͳ.ģ;Կյģ,¶ԭģģ͵ĶԺ໥ϵ,Ϊģ͵ķֽ춨.Զϵͳģ͵ľΪ,չʾñǨʵʩνʺؽģ;ķ.»˶ϵͳĵȡѡƷ,ṩЩPetriģ.
ؼʡģ;,Petri,ģ,ϵͳ,ܷ.
ͼšTP301
On Refinement of Model Structure for Stochastic Petri Nets
LIN Chuang
(State Information CenterBeijing100045)
AbstractThe stochastic Petri net modeling technique can be used in many different ways. It allows the simple design for complex system models, that typically are very costly to solve due to their state space explosion problem. However, refinement of models can be used to develop compact models, which reveal the independence and interdependent relations of submodels in the original models and can be solved by decomposition technique. In this paper, the author uses a multiserver multiqueue system model as an example to show how the refinement of a stochastic Petri net model can be developed by applying the description of enabling predicates and random switches of transitions. In addition, the routing and selecting schemes for multiserver multiqueue systems are discussed and the stochastic Petri net models for those schemes are provided.
Key wordsRefinement of model, stochastic Petri net, model design, multiserver multiqueue system, performance analysis.
Դ1981Petri(stochastic Petri net,SPN)1,SPNۡӦѾõܴչ.SPNģ͵ܵǵϲ,״̬ռ䱬ըٵҪ.Ŀǰ,дڷֽѹֽ̽״̬ռָЧ2,ǺйSPNģ͵صоSPNģ͵.ṹѷֽܵЧѹ.ĿǰΪֹ,ûһּ˵ּṩ͵SPNģ͵ķֽѹ.,SPNģ͵⼼ģΪǰ,ҪģƼΪ⼼춨.
еSPNģо,˲ģƣ3ݡģ֯4ݡܵȼۣ5ݵȼͷ.ģ͵ľȻף6,ûչо.ģ;Ҫص£
(1) ģͽṹ,ʹģ,⣻
(2) ر¶ģ͵Ĳ,Ϊģ͵ķֽͷṩ˻
(3) ϵͳ״̬ռ,Ҫɾ˲Ҫ˲ʱ״̬
(4) ģ͵,ģƺͱĹ.
SPNģ;Ƶŵ,(2)ΪҪ.ģƵĿҪṩϵͳܷ.,ģ;ӦΪSPNģƵıҪ.ģ;ƷѳӦڸ͹ԴϵͳģͺܷУ79,ʾּЧ.
Զϵͳģ͵ľΪ,չʾñǨʵʩνʺؽģ;ķ.ϵͳǵǰһоȵ,϶ǻŶ۽о,кܶҪ.ĵһĿ,SPNģͼΪϵͳģͺṩһµġЧ;.ƪ,ڶϵͳģ͸ֵȺѡ񷽰ܱȽԼܷ.
ĶԽҪǵĶϵͳģԼ(1jm,1in)
(1) ϵͳ,ʹñʶqi(qij)ʾ,±;
(2) еĿռ޵,qi(qij)Ϊbi(bij);
(3) n,i񵽴Ϊ(Poisson),Ϊi.еʱ,ж;
(4) m,ʹñʶsj(sij)ʾ,Ϊj(ijǷjΪiķ),Ƕ,ֲָ.
Ǽ߶SPNۺӦһЩ˽,йϸSPNɲף1,10.ǵSPNģ,ĲͷʱǨʾ,ʿϵͳ״̬;뻺к͹˲ʱǨʾ,ǲռôʱ,ϵ(ʵʩ);ûص˲ʱǨ,Ϊ1.пλʾ,ǵռг̶ȿλõıʶ(marking)ʾ.,ģǨʵʩȼ,Ǩͬʱʵʩʱ,ʵʩȼߵ,ȼ͵ʵʩ,ͬȼıǨʵʩ.˲ʱǨʱǨиߵʵʩȼ.ģ,ǨʵʩñǨĿʵʩνʹ涨,Ǩνʱ,Ǩʵʩ.ûпʵʩνʵıǨ,ʵʩνΪ.ģеı(token)ԱʾԴ. 
1Ȼģ͵ľ
SPNȻģ,һPetriĳͻṹֱǵķ,SPNǨĿʵʩνʺֵȻ߷ѧʽʷ,SPNǨʵʩȼָȷ.ȻߵĻģ1򼸸жλún(n>1)˲ʱǨ,ͼ1ʾ.Ϊ˼˵,ͼ1н1жλü˲ʱǨ.

Fig.1A SPN model of  the routing scheme
ͼ1һȻߵSPNģ
ͼ1,ʱǨcʾ(˿)ĵ,ʵʩʦ,ĿʵʩνM(q1)+M(q2)<b1+b2,༴ʱжĵ.λfʾж,˲ʱ,di(i=1,2)ϵĿʵʩνʻһ.˲ʱǨdi(i=1,2)ԱʾȻߵִ,Ȼ߿ϵĿʵʩνʺ,ĵȻ.λqi(i=1,2)յ,޶Ϊbi(i=1,2).ʱǨsi(i=1,2)ʾ,ʵʩʦi(i=1,2),Ҳпʵʩν,Աʾѡ,һ,ڲĿʵʩν.
Ǩdi(i=1,2)ϵָĿʵʩνʺ,ͬĵȺ;߷,ǽڶϵͳģӾ˵,ٶǨdi(i=1,2)ĿʵʩνΪyi(i=1,2),ұǨdi(i=1,2)Ϊgi(i=1,2).
SPNģ͵ľ,༴ͼ1ʾģ͵ľ,Եõͼ2ʾĵȼģ.

Fig.2A refined SPN model of the routing scheme
ͼ2ȻߵSPNģ
ͼ2,ɾλfǨdi(i=1,2)Ļ,ʹñǨci(i=1,2)Ǩc.ԭǨdi(i=1,2)ĿʵʩνʺطֱǨci(i=1,2)Ŀʵʩνʺʵʩϵ,ıֲ.Ǩci(i=1,2)Ŀʵʩνyi,ʵʩΪˡgi.
ͨͼ2ʾģͿԿģ͵Ļ֡ģ͵໥ϵ(ڱǨci(i=1,2)Ŀʵʩνyiʵʩ),ȷһĵģ֮6.
2ѡģ͵ľ
SPNѡģͽƵĹ,һPetriͬͻṹֱǵ޶,SPNǨĿʵʩνʺֹѡѧʽʷ.ѡĻģһλ(ŹԴ)n(n>1)˲ʱͬǨ,ͼ3ʾ.Ϊ˼˵,ͼ3н1λr(1Դ)˲ʱͬǨd1d2.

Fig.3A SPN model of the selecting scheme
ͼ3һѡSPNģ
ͼ3,ʱǨci(i=1,2)ʾ(˿)ĵ,ʵʩʦi,ʵʩνM(qi)<bi,༴ʱжĵ.λrʾз,Ź,di(i=1,2)ϵĿʵʩνʺΪһе.˲ʱǨdi(i=1,2)Աʾͬѡִ,ѡķϵĿʵʩνʺر,ѡ񷽰.λqi(i=1,2)յ,޶Ϊbi(i=1,2).ʱǨsi(i=1,2)ʾеķ,ʵʩʦi(i=1,2).λwi(i=1,2)ڱʾĽ.
Ǩdi(i=1,2)ϵָĿʵʩνʺ,ͬĹѡ񷽰,ǽڶϵͳģо˵,ٶǨdi(i=1,2)ĿʵʩνΪyi(i=1,2),ұǨdi(i=1,2)Ϊgi(i=1,2).ҲñǨdi(i=1,2)ʵʩȼѡ񷽰.
SPNģ͵ľ,༴ͼ3ʾģ͵ľ,Եõͼ2ṹͬĵȼģ.
ͼ3ģ͵ľ,ɾλrλwi(i=1,2)Ǩdi(i=1,2)Ļ,ԷĹϵsi(i=1,2)Ŀʵʩνʺʶʵʩʵı.ԭǨdi(i=1,2)ĿʵʩνʺطֱǨsi(i=1,2)Ŀʵʩνʺʵʩϵ,ıֲ.Ǩsi(i=1,2)Ŀʵʩνyi,ʵʩΪigi.
ͨģ;,ػģ͡ģ͵ľϵ(ڱǨsi(i=1,2)Ŀʵʩνyiʵʩ).
3ϵͳģ͵ľ
һ,ǽۺڵľģƷ,Ӧõϵͳģ͵ľ.ǿǵĶϵͳһ,nm,ͼ4һϵͳSPNģ.
ͼ4,Ǩλõĺ(1in,1jm).
ci ʾ(˿)ʱǨ,ʵʩʦi.
fi ʾжϵλ,˲ʱĵi,dijϵĿʵʩνʻһ.
dij ʾȻߵִ,Ȼ߿ϵĿʵʩνʺر.
qij ʾĶ,޶Ϊbij.
sij ʾǨ,ʵʩʦij.skj(1kn)j,ѡɿʵʩνʱ.Ϊ˼رģ,ͼ4ûиṹ.

Fig.4A SPN model of the multiserver multiqueue system
ͼ4һϵͳSPNģ
ͼ4ʾģ,ǨciϵĿʵʩνʿԱΪ

ǨdijϵָĿʵʩνʺ,sijҲϵָĿʵʩνԼʶصʵʩ,ȡڵȺѡ񷽰ѡȡ.ǿ4ֵȷģ.
(1) (random routing,RR)
ǨdijĿʵʩνyijд

Ǩdijgijд

RR(M)={k|M(qik)<bik}.
(2) ̶е(shortest queue routing,SQR)
ǨdijĿʵʩνyijд

Ǩdijgijд

SQR(M)={k|M(qik)=min(M(qi1),M(qi2),...,M(qim))and M(qik)<bik}.
(3) Сȴʱ(shortest expected delay routing,SEDR)
ǨdijĿʵʩνyijд

Ǩdijgijд


(4) Сȴʱ(overall shortest expected delay routing,OSEDR)
ǨdijĿʵʩνyijд

Ǩdijgijд


Ŀǿÿжȴʱܺ,Сȴʱķ,ڵõõЧ.
xijʾjѡqijеʵִе,xijֵĲͬȷ˲ͬѡ񷽰.ǽһѡ񷽰ѡ(random selecting,RS).
Ǩsijûпʵʩν.
Ǩsijʶصʵʩxijд

RS(M)={k|M(qkj)>0,1kn}.
ȷѡ񷽰ϲһϵͳǵȷѡ񷽰ϵͳͬ,ҪǷ֮.оѡ񷽰,OSEDRҪ޸ĲRSѡ񷽰,ȡøõЧ.OSEDRRSϲϵͳ,µҪ빲ͬһеһͬ,õ.µȴʱʱ,Ҫܵ,,yijOSEDR(M)޸ģ



ЩSPNģ͵ľ,༴ͼ4ʾģ͵ľ,ǿԵõͼ5ʾĵȼ۵ģ.ͼ5,ǽһģ,ģͬ.ͼ4ʾģȽ,ɾλfiǨdijĻ,ʹñǨcijǨci.ԭǨdijĿʵʩνʺطֱǨcijĿʵʩνʺʵʩϵ,ıֲ.ǨcijĿʵʩνyij,ʵʩΪˡgij(M).Ǩsijʶصʵʩxij.

Fig.5A refined SPN model of the multiserver multiqueue system
ͼ5ϵͳľSPNģ
,õĿʵʩνʡءʵʩȼʵʩʵֱSPN11ݵıʵ.
4ᡡ
Զϵͳģ͵ľΪ,չʾñǨʵʩνʺؽģ;Ƶķ.˶ϵͳĵȡѡƷ,ṩЩPetriģ,ΪϵͳģͺṩһµġЧ;.SPNģ͵صоģͺ͵ȼģһµġҪо,ۺͷֵо.߽һо.
оõȻѧ(No.69873012).
ִϢġ100045
E-mail: clin@mx.cei.gov.cn
ο
1Molly M K. Performance analysis using stochastic Petri nets. IEEE Transactions on Computers, 1982,C-31(9):913917
2Lin Chuang. On the decomposition and aggregation for stochastic Petri nets. Journal of Software, 1997,8(7):514548
(ִ.Petriķֽѹ.ѧ,1997,8(7):514548)
3Lin Chuang, Wu Jian-ping, Wang Ding-xing. Hierarchical modeling and performance evaluation of stochastic high-level Petri nets. Journal of Software, 1995,6(supplement):5967
(ִ,⽨ƽ,.߼PetriĲģͺͷֲ.ѧ,1995,6():5967)
4Marsan M A, Donatelli S, Neri F et al. On the construction of abstract GSPNs: an exercise in modeling. In: Proceedings of the 4th International Workshop on Petri Nets and Performance Models. Los Alamitos, CA: IEEE Computer Society Press, 1991. 217
5Buchholz P. A notion of equivalence for stochastic Petri nets. Lecture Notes in Computer Sicence, 1995,(935):161179
6Ciardo G, Trivedi K S. A decomposition approach for stochastic reward net models. Performance Evaluation, 1993,(18):3759
7Li Bo, Lin Chuang, Chanson S T. Analysis of a hybrid cutoff priority scheme for multiple classes of traffic in multimedia wireless networks. ACM Journal of Wireless Networks, 1988,4(4):279290
8Lin Chuang, Li Bo, Wu Jian-ping. Modeling ATM traffic using stochastic Petri nets. In: Proceedings of the 6th International Conference on Computer Communications and Networks (ICCCN'97). Los Alamitos, CA: IEEE Computer Society Press, 1997. 538541
9Lin Chuang. A model of systems with shared resources and analysis of approximate performance. Chinese Journal of Computers, 1997,20(10):865871
(ִ.һԴϵͳģͺͽܷ.ѧ,1997,20(10):865871)
10Marsan M A, Conte G, Balbo G. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computing Systems, 1984,2(2):93122
11Ciaodo G, Muppala J, Trivedi K S. SPNP: stochastic Petri net package. In: Proceedings of the Petri Nets and Performance Models. Los Alamitos, CA: IEEE Computer Society Press, 1989. 142151
1998-08-27ո
1999-01-28޸
