基于Petri网的异步并发系统建模方法及应用研究

从Petri网的角度,异步并发是指两个或多个事件没有因果关系及由因果关系产生的顺序,与是否同时或是否有统一的时间控制没有关系,异步并发系统具有对称性、自返性而不具备传递性。其建模过程涉及到变迁发生的条件、结果以及是否存在冲突、冲撞等问题。用异步并发系统的建模方法改进Linux系统的队列数据结构,用Visobjnet++软件进行模拟,并编程测试,得到了比原结构更高的效率

维普资讯 http://doc.guandang.net

第 2卷第 6期 7VO . 7 12 NO 6 .

计算机工程与设计Co ue gn ei ga dDe in mp trEn ie rn n sg

20年 3 06月M a .2 0 r 0 6

基于 Pt网的异步并发系统建模方法及应用研究 ei r黄敏，张鹏丽 (长沙理工大学计算机与通信工程学院，湖南长沙 4 07) 106摘要：k e网的角度， b Pt i f异步并发是指两个或多个事件没有因果关系及由因果关系产生的顺序，是否同时或是否有统一与的时间控制没有关系异步并发系统具有对称性、 自返性而不具备传递性。其建模过程涉及到变迁发生的条件、结果以及是否存在冲突、冲撞等问题异步并发系统的建模方法改进 Ln x系统的队列数据结构， V sbnt+件进行模拟，用 iu用 i je+软 o并编程测试，到了比原结构更高的效率。得

关键词： e i Pt网；异步并发系统；Lnx改进队列：建模 r i; u

中图法分类号：P0. T 31 6

文献标识码： A

文章编号：00 0420) 6 93 3 10. 2 ( 60— 7。 7 0 0 0

Re e rh a p iai n o d l gmeh df r s n h o o ssmu tn o sy s se s a c p l t f c o mo ei t o o y c r n u i l e u l y tm n a a

b sdo er n t a e np ti e HUAN G i, ZHAN G e g l M n P n—i

( ol e f o ue adC mmu i t n C agh nvri f cec n eh o g, h n sa 1 0 6 C ia C l g mptr n o e oC n a o, hn sa i syo i e d cn l y C a gh 7, hn) ci U e t S n a T o 40Ab t a t F o p ti e’ a ge a y c r n u i l n o sy s se i a rmo e e e t h v nt h ea i n h p o a s n sr c: r m e r n t n l, s n h o o s mu t e u l y t m s h t wo o r v n s a e t e r lt s i f u ea d S s a t t o c

e e t a dtesq e c r d c db e . I ant o tigt owi i l et

dtesmet ec nr 1 I h step o et f c, n e u n ep o u e yt m h h t s’s mehn d t smut i a a m o to. t a h rp r h o h n a yn h i y o mmer, rtr igi ef b t o a s tig Is eh do d l giv le o nytec n io s n eut ft n lt n fy s t y e nn s l u t, u tr mi n . t to f n tn t m mo ei ov s t l o dt n drs l o a sai, n n n o h i a s r o

b t l n i i n olin t.I p l a o fmpo e u u i l e yVsbn t+ rga u s c fc o adcls,e ao ol tn io c t api t no rv dq e e s mua db i je,po rmme n s di s ci i is t o+ dadi t t se e nLiu p rt n a di f ce c ih r h ep i r tu tr . n xo eai . n s i in yi hg e a t r o te S tn h maysr cueKe r s p ti e; a y c r n u i l e u l se y wo d: e r n t s n h o o ss mu t o sy s t m; Li u; i r v dq e e mo e i g n a y nx mp o e u u; dl n

0引言 Pt网是 16年由德国的 C rA a e i ei r 90 al dmPt博士首先提出 r 的，不仅有充分的模拟能力、富的分析方法、丰形象直观的图形表示，而且有严格的数学理论作基础，特别适合于描述异步并发系统…。

两个或多个事件同时发生。但从 Pt网的角度看， ei r两个或多

个事件只要没有因果关系及由因果关系产生的先后顺序就是并发的，于是否同时发生、没有统一的时间控制是没有关至有

系的，甚至不保证有了发生权的事件就一定会发生，由此可见异步和并发在本质上是一致的。】 定义 1设 x为网系统中包含的所有元素的集合，元素之问的因果关系及由因果关系产生的顺序用“”<表示，< x y表示有信号从 X出发而后到达 Y若满足条件，x∈X八1 (< ), y x y八1 (< ) y x

在现实

生活和计算机领域内，异步并发现象随处可见。火车在铁路上飞驰，汽车在公路上奔跑，飞机在蓝天翱翔等都

是异步并发的。汁算机内进程 A在进行文字处理、进程 B在发送电子邮件等也是异步并发的。人们天天都看到异步并发现象，却没有异步并发的准确定义。 本文从 Pt网的角度， ei r给异步并发下了一个准确的定义， 并分析了异步并发系统的特征，讨论了其建模方法，后用此最方法分析了一个实例。本文涉及的网和网系统的基本概念见参考文献[】 1记为 x O Y C

其中： 1”“——表示非或不存在，则该系统为异步并发系统，定义 2 N=(,; )是一个网， o{,,, )N= 12 ST F N= 0 l2…, {,, 3…)表示无穷，:,, 则

() S 1 K:—N。∞ U{ )称为 N上的容量函数；()给定的容量函数 K,:—N称为 N上的 标识 2对 M S。个的条件是：∈S M() x; Vx: x≤K()

l异步并发系统的概念按照字典里的解释，步是没有统一的时间控制，发是异并收稿日：2 0.3 6期 05 .。 02

() F 3w:—N.为N的权函数， xY∈F W(,= (,称 对(, ), xy w( ) x

y称为(,上的权。 ) ) x) y

基金项目：湖南省教育厅科学研究基金项日 ( C 8) 0 08。 2 作者简介：黄敏 (98 ) 16,女，重庆人，硕士，副教授，研究方向为 Pt网及其应用、Lnx作系统；张鹏丽 ( 7-) ei r i操 u 1 8,女，湖北武汉人 9硕士生。研究方向为P t网及其应用 er i-——

9 3 - 7——