（计算机软件与理论专业论文）异构的分布式实时系统的建模及性能分析.pdf

摘要摘要随着分布式计算和计算机网络技术的发展，分布式系统的应用及其设计技术成为计算机科学研究领域的热点。分布式实时系统的应用也日益进入人们的日常生活，这些应用包括虚拟现实，远程教育，远程医疗，网络电话等。分布式实时系统对时问和o o s 的有非常严格要求，因此对设计、实现和测试的技术和工具都有很高的要求。模糊时间p e 啊网是将模糊集合理论用于不确定的或主观的时间信息的表示，在每个变迁上添加时间间隔约束对模糊时间p e 缸网进行扩展得到扩展的模糊时间p 附i 网，它是一种对网络实时系统进行建模和分析的形式化模型，p e 晡网数学理论基础能保证并发系统的可靠性和正确性。本文详细地介绍了模糊时问p e t r i 网及扩展的模糊时间p 曲j 网，扩展的时间p 出i 网的网精简方法，使用c p n t 0 0 i s 仿真扩展的模糊时间p c t r i 网。分布式多媒体系统支持数据库中或网络中的声音、视频、文本和数字数据的整合与协同。分布式多媒体同步包含异构的源和媒体之间的异步通信。不是所有的媒体分段都有事先知道的播放时间间隔，几个分布的、独立的源之间的多媒体同步可能包含不确定的时间需求，所以需要一个时间模型来处理这些不确定性。本文使用扩展的模糊时间p e t r i 网对分布式多媒体同步进行建模和分析。在分布式多媒体系统中，资源预留协议是保证服务质量的一个重要协议。但是资源预留协议的一些说明文档模棱两可，晦涩难懂；而且修改协议中的错误可能付出高昂的代价。对r s v p 进行形式化方法建模，可以使问题更清晰；同时对r s v p 进行验证，可以及时发现错误而不必付出高昂代价。本文介绍了资源预留协议，使用c p nt o o l s 建立网络模型，分析了时间参数，并且对网络模型的性能进行分析。接着介绍了一个分布式多媒体系统的实例一远程教育系统，并且对会话控制模块进行了建模和简要分析。最后探讨了进一步研究的方向。关键词：分布式；实时；异构；扩展的模糊时间p e 岫网；多媒体：资源预留协议；远程教育系统三重三些奎兰三兰堡圭兰堡尘圣a b s t r a c tw i t ht h ea d v a n c eo fd i s t r i b u t e dc o m p u t i n ga n dd e v e l o p m e n to fc o r n p u t e rn e t w o r k ，t h ea p p li c a ti o na n dd e si g nt e c h n o g o l yo fd is t r i b u t e ds y s t e i i lb e c o m et h ef o c u sp o i n ti nc o m p u t e rs c i e n c er e s e a r c hf i e l d a l s ot h ea p p l i c a t i o no fd i s t r i b u t e dr e a l 一t i m es y s t e me n t e r sp e o p l e sd a i l y1 i f e ，i n c l u d i n gv i r t u a lr e a l i t y ，t e l e t e a c h i n g ，t e l e - m e d i c i n e ，v o i pa n ds oo n d i s t r i b u t e dr e a l t i m es y s t e md e m a n d ss t r i c tr e q u i r e m e n to ft i m ea n dq o s ，t h e r e f o r ec a l l sf o rh i g hq u a l i t yt o o l sa n dt e c h n o l o g i e st od e s i g 兀，i m p l e m e n ta n dt e s t f u z z y t i m i n gp e t r in e t ( f t n ) e m p l o yf u z z ys e tt h e o r yt oe x p r e s su n c e r t a i no rs u b j e c t i v et i m i n gi n f o r l a t i o n ，b ye a c ht r a n s i t i o nb e i n ga s s o c i a t e dw i t haf i r i n gi n t e r v a l ，w eg e te x t e n d e df u z z y t i m i n gp e t r in e t ( e f t n ) e x t e n d e df u z z y t i m i n gp e t r in e t ( e f t n )i saf o r m a l 0 d e lf o rm o d e li n ga n da n a l y s i so fn e t w o r k b a s e dr e a l t i m es y s t e m s ，p e t r in e t sm a t h e m a t i c a lt h e o r yb a s i sw i l le n s u r et h er e l i a b i l i t ya n dc o r r e c t n e s so fc o n c u r r e n ts y s t e m s t h et h e s i sd e t a i l e d l yi n t r o d u c e st h ed e f i n i t i o no ff t na n de f t n ，m o d e lc h e c km e t h o d ，n e t r e d u c t i o nt e c h n o l o g y ，u s i n gc p nt o o l st os i l u l a t ee f t n d i s t r i b u t e dm u l t i m e d i as y s t e m ss u p p o r tt h ei n t e g r a t i o na n dc o o r d i n a t i o no fa u d i o ，v i d e o ，t e x ta n dn u m e r i cd a t ao r i g i n a t i n gf r o md a t a b a s e so rh i g h s p e e dn e t w o r k s i nd i s t r i b u t e dm u l t i m e d i as y n c h r o n i z a t i o ni n v 0 1 v i n g ，a s y n c h r o n o u sc o 砌u n i c a t i n aw i t hh e t e r o g e n e o u ss o u r c e sa n dm e d i a ，n o ta l lm e d i as e g m e n t sh a v eap r i o rk n o w np r e s e n t a t i o nt i m e d u r a t i o n s ，m u l t i m e d i as y n c h r o n i z a t i o na l o n gs e v e r a ld i s t r i b u t e da n di n d e p e n d e n ts o u r c e sm a yi n c l u d eu n c e r t a i nt e m p o r a lr e q u i r e m e n t s s ow en e e dat e m p o r a lm o d e lw h i c hc a nd e a lw i t ht h i st e m p o r a lu n c e r t a i n t i e s t h i st h e s i sm o d e l sa n da n a l y s e sd i s t r i b u t e dm u l t i m e d i as y n c h r o n i z a t i o nb ye f t n i nd i s t r i b u t e d 叫l t i m e d i as y s t e m ，r e s o u r c er e s e r v a t i o np r o t o c o li sa ni m p o r t a n tp r o t o c o lt oe n s u r eq u a l i t yo fs e r v i c e s o m ep a r t so ft h ed o c u m e n tm a yb ea m b i g u o u s ，d i f f i c u l tt ou n d e r s t a n d a n di m p r e c i s e ：a l s ot h ec o s tf o rf i x i n ge r r o r si nt h ep r o t o c o li if o u n di nt h ei m p l e m e n t a t i o nc a nb eh i g h t h ef o r m a ls p e c i f i c a t i o na n dv e r if i c a t i o no fr s v pc l a r i f i e st h ep r o b l e m ：a l s of i n d i n ge r r o r si nt i m ew h i t h o u tc o s t t h et h e s i si n t r o d u c e st h er e s o u r c er e s e r v a t i o np r o t o c 0 1 m o d e l st h en e t w o r ku s i n gc p nt o o l s ，a n a l y s e st i m ep a r a m e t e ra n dt h ep e r f o r m a n c e i ns u c c e s s i o ni n t r o d u c e sa ne x a m p l eo fd i s t r i b u t e d u l t i m e d i as y s t e m r e m o t ee d u c a t i o ns y s t e m ，a n dm o d e l st h es e s s i o nc o n t r 0 1m o d u la n ds i m p l ya n a l y s e st h em o d e l f i n a l l yg i v e ss o m ed i r e c t i o n so ff u t u r ew o r k k e yw o r d s ：d i s t r i b u t e d ：r e a 卜t ir r l e ：h e t e r o g e n e o u s ：e f t n ：m u l t i 巾e d i ar s v p ；r e m o t ee d u c a t i o ns y s t e mi i i第一章绪论第一章绪论1 1 论文的选题背景及意义随着分布式计算和计算机网络技术的发展，分布式系统的应用及其设计技术成为计算机科学研究领域的热点。本章首先介绍本文的研究背景，包括分布式系统的一般概念，讨论了开发软件系统形式化方法的必要性，然后介绍了本文主要研究内容和主要贡献，最后一节是全文的内容安排。1 1 1 分布式实时系统随着通信技术和计算技术的发展，分布式实时系统发展很快。分布式实时系统的应用包括虚拟现实网络沉浸( v i r t u a lr e a l i t yt e l e i m m e r s i o n ) ，实时服务器客户机系统，多媒体，远程教学，远程医疗等等。这些应用依赖于高性能高可靠性的o o s 和端到端高带宽的数据传输。分布式系统定义为：“一个分布式系统是一些独立的计算机的集合，但是对于这个系统的用户来说，系统就像一台计算机一样。w m w ”这里有两个方面的含义：从硬件角度来讲，每台计算机都是自主的，即每台计算机都能够脱离系统而独立运行；从软件角度来讲，用户将整个系统看作是一台计算机，用户在使用非本地资源时不需要特殊的物理信息，资源库所对用户透明。这二者都是必须的，缺一不可。在分布式系统中，异构是无法避免的“。造成异构的原因很多，一个原因是计算机技术的快速发展，不同时期最优的技术可能存在于同一个分布式系统内；另一个原因为了能使分布式系统中某一部分的性能达到最优，可能采用不同的计算机、操作系统、网络平台的组合。分布式系统的异构性主要集中在两大方面：硬件异构性表现为指令系统、数掘表示、系统配置不同。软件异构性表现为操作系统、网络协议的不同。由于异构的分布式实时系统对时间和服务质量( o o s ) w 一，的有严格要求，因此对设计、实现和测试的技术和工具都有很高的要求。对异构的分布式实时系统建模的两条原则：寻求独立于平台的模型和抽象，这样有助于解决大部分问题；广东工业大学工学硕士学位论文在不牺牲太多性能的情况下，尽可能的隐藏低层的复杂细节。1 1 2 形式化方法形式化方法。”“o 是指有完备的数学基础，并且这种数学基础不仅提供了精确定义的方法，具有一致性、完整性等特征，而且也提供了不需运行系统就可证明其性质的方法。形式化的过程始于描述而终于分析。一个形式化方法最初的目标就是完整的、准确的、无二义的描述：而最终的目标则是对己经用形式化语言描述好的系统进行分析，从而对系统的正确性、安全性等问题做出准确的判断。在通信服务的工业领域有许多用于形式化建模和分析的方法1 。但是他们存在着种种不足，1 ) 这些方法大多数意在规格说明和证明一个特定通信服务的正确性m “- ”。2 ) 现存的方法很少考虑网络服务质量的需求分析，和如何评价这些分布式实时系统的应用程序。3 ) 在分布式实时系统中存在着时间不确定性。比如说网络延迟可能分布在很大一个区域内，实时系统中一些动作的持续时间不能确定。为了准确分析网络性能和实时系统的行为，当我们为这些系统建模的时候就需要捕获时间的不确定性。4 ) 尽管形式化证明领域做了很多工作，但迄今为止最大的瓶颈是“状态爆炸问题”m m w m m 。当软件系统的大小成线性增长时，系统的分析复杂度成指数增长。对于一个大型的网络，现行技术的容量和性能远远不够。所以，有必要开发形式化建模技术来获取分布式实时系统中的时间不确定性，为这些系统开发有效的分析工具。1 1 3 通信协议的形式化描述技术通信协议( c 0 l r n u n 硫i o np r o t o c 0 1 ) 是一组实体在执行某项任务中相互通信行为的规则和格式( 语法和语义) ，它是数据通讯、计算机网络、多机系统等分布式系统的灵魂。过去，人们习惯采用自然语言进行协议描述。自然语言的优点是方便、易懂，但其致命缺点是不严格、不精确和有多义性( 或二义性) 。不同的人对协议描述的理解不同，因此这样设计出的协议不但不能保证o s i ( 开放系统互连) 环境下互连，甚至还会得出错误协议。历史上这类教训很多，例如1 9 7 8 年版的x2 5 中，对端到端序号的含义以及释放和重置分组的意义规定得不清楚，有多义性。为此必须第一章绪论用形式化方法( f o 彻a lm e t h o d s ) 规范协议1 。随着网络与分布式系统的迅速发展，通信协议的形式化技术，其中包括一系列形式化理论、模型及实现方法已获得了长足的进步。所谓协议的形式化技术是指协议及服务规范的形式描述、设计验证、实现验证和一致性测试。在这些形式化技术中，形式描述与验证技术是整个协议设计与实现的基础，对协议实现的正确性、完全性和复杂度有至关重要的影响。在众多的形式化描述技术中，p e t r i 网受到了更多的青睐，因为它具有一套成熟的数学理论工具，并且建立了许多分析技术，包括可达性分析、不变量分析( 使用线性代数方法) 、保持特性的变换( 包括网精简) 、构造理论、语言理论、同步距离以及网的分解和合成等。而网的形式基础使网与其它并发模型建立了连接，这对于分布式系统的描述和分析是很有益的。近几年来，人们的注意力集中在如何将代数的抽象数据类型融合在高级网结构中，极大地方便了表示描述协议和服务所用的高级p e 缸网系统。1 2 国内外研究动态p e t r i 网、时序逻辑和有限自动机都是并发系统建模的著名的形式化方法。在所有这些形式化方法中，p d r i 网有严格的数学分析能力并且能保证并发系统的可靠性和正确性。现在已经有许多p e 缸网在时间方面的扩展，比如随机p e 缸网( s t o c h a s t i cp e t r in c t s ) ，m e f l i i l 时间p e t r i 网( m 甜l i i l sp e 砸n c t s ) ”，对象组成p e t r i 网( o b i e c t c o r n p o s i t i o n p 曲矗n e t ) 陋1 ，时间流p e 缸网( t j m es 仃e 咖p e 晡d d )m 。随机p e t r i 网中每个变迁与一个指数分布的随机变量相关联，表示从点燃使能变迁点燃的延迟。如果几个变迁同时使能，则具有最短延迟的变迁最先点燃。m c r l i i l 时间p e t r i 网中每个变迁t 与时间间隔 t m i i l ，t m a ) 【】有关。假设在时问t o 使能，则变迁t 的点燃时间在t o + t m i n 和t o + t m a x 之间。为了处理实时系统中的时间不确定性问题，m u r a t a 提出了模糊时问高级p e t r i网( f u z z y - t i i l l i i l gh i 曲一l e v e lp e mn e t s ) m ，将模糊集合理论用于不确定的或主观的时问信息的表示。1 3 论文的组织广东工业大学工学硕士学位论文本文的内容安排如下：第一章本章作者查阅了大量中外文献，介绍了分布式实时系统的概念，形式化方法，模糊时间p e t r i 网以及扩展的模糊时间p e t r i 网，分析了分布式实时系统建模的困难，最后是本课题研究的思路，主要内容和本文的组织。第二章本章主要介绍了模糊时间p e t r i 网的定义，以及变迁点燃之后四个模糊时间函数的点燃规则。第三章本章主要介绍了扩展的模糊时间p e t r i 网的定义，模糊时间戳的更新规则，性能分析技术和如何使用仿真工具c p nt o o l s 对扩展的模糊时间p e t “网进行仿真。第四章本章使用扩展的模糊时间p e t r i 网，采用从上到下逐步求精的方法，对分布式多媒体的同步进行建模和分析。第五章本章介绍了资源预留协议，采用从上到下逐步求精的方法，对使用资源预留协议的网络进行建模，网络模型进行性能分析。第六章本章介绍了分布式多媒体应用的框架，c o r b a a vs t r e a m 规范，对远程教育系统中的会话控制进行了p e t r i 网建模并且进行了分析。最后是本文的结论和进一步的研究工作。4第二章模糊时间p e t r i 嘲第二章模糊时间p e t r i 网2 1 模糊时间p e tr - 网的定义为了处理实时系统中的时间不确定性问题，m u m t a 提出了模糊时间高级p e 晡网( f 1 1 z z y - t i m i n g h i 曲- l e v e l p e 缸n e t s ) ，将模糊集合理论用于不确定的或主观的时问信息的表示。f t h n 的主要特性是如下四个模糊集合理论的时间函数：模糊时间戳( f h z z yt i m e s t a n l p ) ，模糊使能时间( m z z ye n a b l i n gt i r n e ) ，模糊发生时问( 矗l z z yo c c u r r e n c et 曲e ) 和模糊延迟( f i j z z yd e l a y ) 。模糊时间戳万( r ) 是个模糊时间函数或者概率分布，表示一个特定的令牌在时间f 到达特定库所的概率。如果z ( f ) = o 5 ，说明它在时间r 到达的概率为o 5 。从变迁t 到库所p 的每一个弧( t ，p )和模糊延迟d 。t ) 相关。如图2 1 所示，用四元组( 石。，石：，乃，万。) 定义的梯形或三角形的概率分布来表示模式时间函数，其中高度h ，的默认值是1 ，三角彤是梯形中万，= 刀，的特殊形式。其中图2 1 梯形和三角形概率分布f 吨2 1t r a p e z o i d a la n dt r i a n g u l a rp o s s i b i l i t yd i s t r i b u t i o n s模糊时间高级p 出i 网的静态结构是一个九元组，n = ( ，p ，t a ，c ，d ，c 工f t f )( i ) 是有限的类型集合，称为颜色集合( i i ) p 是有限的库所的集合( i i i ) t 是有限的变迁的集合( i v ) a ( p f ) u 仃xp ) 是弧的集合( v ) c 尸斗是个颜色函数处一鬣滁一)_咎一牛广东工业大学工学硕士学位论文( v i ) d 是所有模糊延迟d 。( f ) 的集合，每个延迟与口r p p ) 相关( 诃) c t = ( p ，v ) ip n n 西p ) ) 是所有可能的颜色令牌的集合( v j j i ) f t 是所有模糊时间戳的集合。时间戳是一个从时间范围t s 到实数间隔【0 ，1 】的映射函数( i x ) f 是变迁函数，表示变迁点燃时令牌的移动情况。2 2 模糊时间p e t r i 网的时间戳更新r 1 1 计算每个变迁t 模糊使能时间。假设变迁t 需要n 个令牌才能点燃，它们的模糊时间戳是万，( f ) ，i _ 1 ，2 ，n ，那么变迁t 模糊使能时间e ，( f ) = l a t e s t 乃( r ) ，i 1 ，2 ，n ) ，h t e s t 运算符表示“最晚到达最低概率的分布”，每个变迁需等待最晚到达的令牌。( 2 ) 计算下一个变迁发生的概率分布。变迁t 的模糊发生事件d ，( r ) 是变迁t 开始点燃时间的概率分布。当有m 个变迁发生冲突时，他们的模糊使能时间幺( r l ，i _ l ，2 ，t ，m 变迁t 的模糊使能时间为q ( f ) ，q p ) = i i l i n e 盯l i e s t q ( f ) ，i _ 1 ，2 ，t ，m ) ，e a l l i e s t 运算符是从m 个分布中求“最早到达最大概率分布”。( 3 ) 根据模糊发生时间和模糊延迟求模糊时间戳。模糊延迟d 。( f ) 是变迁t 的点燃时间到令牌到达库所p 的事件长度的概率分布。模糊时间戳( f ) 表示每个令牌到达库所口的时间的概率分布，石。( f )=q ( )od ，( f )=( 0 。，o ：，码，o 。) o p ，d ：，毛，d 。)=( 0 t + d i ，d 2 + d 2 ，d 3 + d 3 ，d 4 + d 4j第三章扩展的模糊时间p e ”i 网第三章扩展的模糊时间p e t r i 网3 1 扩展的模糊时间p e tr 网定义通过把f 1 n 和m e r l i n 时间p e t r i 网相结合得到扩展的模糊时间p c t r i 网m 。当扩展的模糊时间p e 啊网模型的d 。( f ) 默认值是( o ，o ，o ，o ) 的时候就变成了f t n 模型，另外还有一个附加的函数c t ：r 斗q + q + ( q + u 。o ) ，即从变迁集合t 到点燃瞬间的映射是个概率分布：就是说每个变迁与点燃瞬间p l 口，i 相对应，默认值是1 【o ，0 ( 一个变迁使能之后马上点燃) 。如果一个变迁t 在时刻r 使能，那么t 在r + 口之前不能点燃，t 必须在r + 时刻或之前点燃。概率p l o ，1 l 。如果变迁t与其它变迁没有冲突，那么p = l 。当为冲突的变迁赋予不同概率时，p 1 。比如说变迁t 1 和t 2 有冲突，t 1 以9 9 的概率点燃，t 2 以1 的概率点燃，那么让“= 0 9 9 ，p ，= o o l 。变迁点燃本身是一个原子过程，不占用时间。为变迁赋予点燃瞬间概率的目的在于当发生冲突时给与点燃的可能性和优先级。3 2 扩展的模糊时间p e t r i 网的模糊时间戳更新计算每个变迁t 模糊使能时间。假设变迁t 需要n 个令牌才能点燃，他们的模糊时间戳是乃( ) ，i = 1 ，2 ，n ，那么变迁t 模糊使能时间q ( r ) = l a t e s t 曩( r ) ，i - 1 ，2 ，n ，h t e s t 运算符表示“最晚到达最低概率的分布”，每个变迁需等待最晚到达的令牌。计算下一个变迁发生的概率分布。变迁t 的模糊发生时间o ，f ) 是变迁t 开始点燃时间的概率分布。当有m 个变迁发生冲突时，他们的模糊使能时间q ( r ) ，i 1 ，2 ，t ，m 变迁t 的模糊使能时间为e ，( f ) ，变迁t 的模糊发生时间为o ，0 ) = 扛，( f ) o p 。0 ，a ，肛，层l e n r f f 韶f 诂，g ) o p 如，瑾；，屈，屈) ，f _ l ，2 ，f ，m ) ) ，e 盯l i e s t 运算符是从m 个分布中求“最早到达最大概率分布”。当变迁t 与其它变迁没有冲突的时候，其中c r o ，) = p 。k ，屈】，那么模糊发生时间为d f ( r ) = q ( r ) o q 。，屈，肛) 。=：童三些奎兰三兰竺圭兰堡竺兰3 3 扩展的模糊时间p e t r i 网的性能分析技术3 3 1 扩展的模糊时间p e t r i 网的例子给定一个f m t l 规则，它说明了实时系统中的时间需求，通过使用模型检测技术，可以计算出在e f l l n 中从初始标识到目标标识的满足时序要求的变迁点燃序列的概率。图3 1 的例子说明了e f t n 模型中模糊时问戳的更新。图3 1e 兀n 模型的一个例子f i 9 3 - 1a ne x a n l p l eo f e f t n进程a 和进程b 共享资源p r 并且互斥访问。只( 或b ) ：进程a ( 或b ) 在等待；墨。( 或圪) ：进程a ( 或b ) 正在使用资源e ；只。( 或只。) ：进程a ( 或b ) 已经使用完资源只；f 。( 或。) ：进程a ( 或b ) 获取资源；f ：。( 或f ：。) ：进程a ( 或b ) 释放资源。最后的状态是进程a 和b 各使用资源一次并且库所只，。和乞。各有一个令牌。下面是两个达到最后状态的可能的点燃序列：盯l ：m o f 1 。 m 1 f 2 。 m 2 6 m 3 f 2 6 m 4 ，盯2 ：m o f 1 6 m 5 【f 2 6 m 6 r l 。 m 7 【f 2 。 m 8 ，其中每个标识由含有一个令牌的库所组成：m 。= 化只只) ，m = 她。只) ，m ：= ( p 。一。e 圪) ，m ，= 慨。一。圪) ，m 。= c 。只。) ，m ，= 亿。只) ，第三章扩展的模糊时间p e t r i 网m 。= 忆。，。# 只) ，m ，= 幢。只。) ，m 。= 眈。) 。假设初始标识m 。中的只，r ，e 中的三个令牌有如下的模糊时问戳：石。p ) = ( 1 ，3 ，3 ，5 ) ，z 。( r ) = ( 3 ，5 ，5 ，7 ) ，( ) = ( o ，o ，o ，o ) 。当只和p 得到一个令牌时，变迁f ，。在时间问隔 1 ，3 】使能，当咒和p 得到一个令牌时，变迁f 。在时间间隔【2 ，4 使能。当变迁。和f 。都使能时就会发生冲突。在这种情况下，变迁f 。的点燃概率是0 8 ，f 。的点燃概率是o 2 。首先，计算出变迁。和f 。的模糊使能时间：e 。( ) = 肠f “f 丌。( ) ，p ) = 肠融蚶 ( 1 ，3 ，3 ，5 l ( o ，o ，o ，o ) ) = ( 1 ，3 ，3 ，5 )q 。( r ) = 肠把蚶k 。( f l 氏0 ) = 肠把对 ( 3 ，5 ，5 ，7 ) ( 0 ，o ，o ，o ) = ( 3 ，5 ，5 ，7 )然后计算p 口，f 部f 叠。( ) o o 8 ( 1 ，l ，3 ，3 l p 。( r ) o o 2 ( 2 ，2 ，4 ，4 ) = e d r “f o 8 ( 2 ，4 ，6 ，8 l o 2 ( 5 ，7 ，9 1 1 ) = o 8 ( ，变迁f ，。和f ，。点燃的模期发生时问如下：0 1 。e ) = m i n 叠。0 ) o o 8 ( 1 ，l ，3 ，3 i 即，f 把，f 叠。( ) o o 8 ( 1 ，l ，3 ，3 ) ，p 。( f ) o o 2 ( 2 ，2 ，4 ，4 ) = o 8 ( 2 ，4 ，6 ，8 )o b ( f ) = m i n 叠。g ) o o 2 ( 2 ，2 ，4 ，4 l g n r f 记，f 叠。( ) o o 8 ( 1 ，1 ，3 ，3 ) ，p 。g ) o o 2 ( 2 ，2 ，4 ，4 ) = o 2 ( 5 ，7 ，7 5 ，8 )点燃序列q 中令牌到达，。和只。的模糊时间戳石。( r ) ，z 。p ) ：，z 。g ) = 0 l 。( ) o 矾。( f ) = o f 8 ( 2 ，4 ，6 ，8 ) o ( o o ，o ，o ) = o 8 ( 2 ，4 ，6 ，8 )。：。( f ) = e ：。0 ) = 万，。p ) = o 8 ( 2 ，4 ，6 ，8 )石：。( ) = d ：。( ) o d ：。( ) = o 8 ( 2 ，4 ，6 ，8 ) o ( 4 ，5 ，7 ，9 ) = o 8 ( 6 ，9 ，1 3 ，1 7 ) = 万。( r )e 0 ( f ) = 胁蜘f 协：。( l 万。o ) = 肠f 即f o 8 ( 6 ，9 ，1 3 ，1 7 ) ，( 3 ，5 ，5 ，7 ) = o 8 ( 6 ，9 ，1 3 ，1 7 )吒( f ) = p 0 ( f ) o ( 2 ，2 ，4 ，4 ) = o 8 ( 8 ，1 l ，1 7 ，2 1 )z 。( f ) = d ：。( r ) o d ：。( ) = o 8 ( 8 ，1 1 ，1 7 ，2 1 ) o ( 4 ，5 ，7 ，9 ) = o 8 ( 1 2 ，1 6 ，2 4 ，3 0 )同样，对于点燃序列盯：计算令牌到达只。和巴。的模糊时涮戳万，丌8 6 【) ：。：。( f ) = e ：。( ) = o 。( ) o d 。( ) = o 2 ( 5 ，7 ，7 5 ，8 ) o ( o ，啦o ，o ) = o 2 ( 5 ，7 ，7 5 ，8 )z 。( ) = z 。0 ) = o ：。( f ) = o 2 ( 9 ，1 2 ，1 4 5 ，1 7 ) o ( 1 ，l ，3 ，3 ) o d 。( f ) o d ：。( f ) = o 2 ( 1 4 ，1 8 ，2 4 5 ，2 9 )3 3 2 网精简( n e tr e d u c t i o n )当软件系统的大小成线性增长时，分析这个系统所用的时间和空间可能成指数增长。实时系统的验证比非实时系统更复杂，因为实时系统的正确性不仅依赖广东1 业大学工学硕士学位论文于它们的功能而且取决于它们的时间限制。在所有说明和验证实时系统的形式化语言中都存在状态爆炸问题。和其他形式化语言相比，时间扩展的p e t r i 网比非时间扩展的p d 啊网分析的复杂度要高。在大规模实时分布式系统中使用性能分析技术是解决“状态爆炸”问题的切实可行的途径。网精简技术是p e m 网中解决状态爆炸问题的一个重要技术，它致力于减小p c t r i 网模型的规模，同时保证并发的特性比如活性，安全性和有界性。普通p e t r i 网的精简方法有l e e - k w a n g w ，b e r t h e l o t w 等方法，着色p e 缸网精简方法m ，m 刚协时间p e 晡网精简方法m ，延迟p e 缸网精简方法。“1 。精简规则1 ( 变迁的向后融合) 如果存在一个库所p 满足如下条件变迁集合t a 就能向后融合为变迁集合t b 。1 ) p = 删和p = 四( t a t b 是库所p 的输入变迁和输出变迁) 2 ) 库所p 开始没有令牌3 ) 对于每个变迁舾佃，西= p 并且p 硭舾( p 是t b 的唯一的输入库所但不是输出库所) 4 ) 删n 佃= ( 对于每个f 黝和每个出馏，t a 和t b 没有共同的输出库所) 5 ) 对于每个变迁f 6 册，陆n 0 巩，8 拥l m i n 1 ，z h ) 】n k 6 ，6 】庐( 每个变迁t b 都有机会点燃) 6 )对于每个变迁曲船，如果旧l 1 ，那么t b = l b 。精简规则2 ( 变迁的并行融合) 如果存在库所p a 和p b 满足下面条件那么两个变迁t 1 和t 2 也是可融合的。1 ) f l = f 2 = 切口 ，并且小一f 2 = 扫6 2 )p 6 1 ，6 1 】n 如r 并且【幽2 ，6 2 】n 彤4 妒，其中倒。= 【m i n g 6 1 ，e 6 2 l m i n ( f 6 l ，胁2 ) 】( t 1 和t 2 都有机会点燃) 3 ) 时间间隔 6 1 ，舾1 】n 矿) o 如1 ( r ) 和 6 2 ，舾2 】n 形) o 曲2 ( f ) 是重叠的， 6 1 ，舾1 】n 形) o 如1 ( f ) 是相对于令牌到达库所p a 的时间，点燃变迁t 1 令牌到达库所p b 的最早时间， 6 2 ，胁2 】n 彬) o 如2 ( )是相对于令牌到达库所p a 的时间，点燃变迁t 2 令牌到达库所p b 的最早时间。( 点燃t 1 和t 2 令牌到达p b 的时间间隔) 4 ) 如果胛 f 1 ，f 2 ( p a 的输出变迁不是t 1 和t 2 ) ，就假设变迁t 是在t 1 和t 2 之间具有最早点燃时间的变迁( p 加= m i n k 6 1 ，e 6 2 1 ) ，令牌到达p b 的最早时间和最晚时间都需要通过t 的点燃来获取。精简规则3 ( 变迁的向前融合) ：如果满足以下条件变迁集合t b 可以向前融合为一个变迁t 。1 ) 对于f 中的每个库所2 ) f 并且瑚= ( 变迁t 至少有一个输入库所并且是每个库所的唯一的输出变迁) 3 ) f = p ( 变迁t 有唯一1 0第三章扩展的模糊时问p e t r i 网的输出库所p ) 4 ) 库所p 开始时没有令牌5 ) p = f 并且矿= 四( 库所p 有唯一的输入变迁t 并且库所p 的所有输出变迁的集合等同于t b ) 6 ) f 壁四( 变迁t不属于t b )精简规则4 ( 冗余变迁的移除) 如果存在一个库所p 和变迁t b l 满足以下条件变迁t b l 可以被移除并且被标注为死的变迁1 ) f 6 2 = 扫 ：2 ) 曲1 _ 扫 ；3 )8 6 2 舾l ( 变迁t b 2 没机会点燃) 。精简规则5 ( 变迁的侧向融合) 如果存在变迁t 满足以下条件，那么变迁集合t b 可以侧向融合。1 ) 对于每个变迁曲f 四：l 曲i = l ( t b i 有唯一的输入库所) 2 ) 对于每个库所p f 邸，p f - t 并且b i = l ( t 是库所p 唯一的输入变迁，p 有一个输出变迁) 3 ) 对于t b 中的每对变迁t b l 和t b 2 ，它们没有共同的输出变迁4 ) 对于每个库所四，p i 有相同数目的变迁，如果p i 没有变迁，那么每个讲( f 有相同的值。5 ) 对于每个变迁f 6 f 纺和t b i 唯一的输入库所p i ，5 一1 ) 如果i 加4 1 并且库所p i 没有令牌，那么扰仞) 的值为( r ) = b ，x ，工，x ) ) ，并且e 6 f - 腩f ，5 2 ) 如果l 曲刊 1 并且库所p i 有令牌，那么p 臃= 仿f精简规则6 ( 库所的并行融合) 如果满足下面的条件则库所p 1 和p 2 是可融合的1 ) p 1 和p 2 有相同的初始标识2 ) p 1 = p 2 并且脚= p 2 。精简规则7 ( 冗余库所的删除) 如果库所p 开始时没有令牌而且没有输入变迁，那么p 和所有的输出变迁都可以被移除。是由e f t n 冗余库所的删除规则得到的，那么。和在时间和死锁方面等价。证明：在e f t nn 中，库所p 开始时没有令牌并且没有输入变迁，所以库所p永远不可能含有一个令牌而且库所p 的所有输出变迁都不可能被使能和点燃。在e f t n 。中移除它们，时间和死锁特性并不会改变。3 4 使用c p nt o o i s 仿真c p nt o o l s m ，是丹麦的奥尔胡斯大学计算机系的c p n 小组开发的用来编辑，模拟和分析着色p e t r i 网的工具。g u i 是基于高级的交互技术，比如工具眼镜，状态菜单和双手交互技术；反馈工具提供上下文相关的错误信息，指明网中各元件之间的依赖关系，在提供建网工具的同时提供语法检查工具和代码产生工具；模拟器可以快速模拟各种p e 缸网：分析工具可以产生和分析全局或局部的状态空间图，标准的状态空间报告包广东工业大学t 学硕士学位论文含了诸如活性，有界性的重要信息。c p nt 0 0 1 s 的最新版本是c p nt 0 0 l sv c r s i o n2 o o 。工具箱中有辅助工具( a u x i l i a r y ) ，建网工具( c r e a t e ) ，层次工具( h i e r 盯c h y ) ，追踪工具( m o n i t o d n g ) ，编辑工具( n c t ) ，模拟工具( s i n l u l a t i o n ) ，状态空间工具( s t a t e 印a c e ) ，风格工具( s t v l e ) 和查看工具( v i e w ) 。c p nt o o l s 可以和j a v a 联合使用，更加直观的显示模拟结果。c p n t 0 0 1 s 使用c p nm l 来定义变量和函数。3 4 1 仿真模糊时间功能可使用类似于模糊变量的单值仿真对e f l n 模型的模糊延迟进行仿真。通过定义一个函数来产生c p nt 0 0 l s 中四边形概率分布标准值：给定一个模糊延迟d ( f ) = 0 ，6 ，c ，d ) ，再定义一个函数，2 y 0 ，6 ，c ，d ) 来产生四边形概率分布的单个延迟g ，6 ，c ，d ) 来代表模糊延迟。c p n t 0 0 1 s 中兀尼z y 0 ，6 ，c ，d ) 的代码如下所示，重复以下的过程直到得到一个延迟值：( 1 )产生一个时间间隔k ，d 】中的随机时间值“砌t e( 2 )如果醐恸8 在时问间隔 6 ，c 】，n 砌m 就将作为延迟值，因为时间间隔陆，c 】内的概率是l 。( 3 )如果n f f m e 在时间间隔k ，6 ) 或( c ，d 】，四边形分布0 ，6 ，c ，d ) 中的概率d g 砌z e ) 。为延迟值。如nf u z z y ( a ：r e a l ，b ：r e a l ，c ：r c a l ，d ：r e a l ) =v a la t i m e = c p n r a n d r c a i ( a ，d ) ；m( i f a t i m e = _ ba r l da l s oa ：t j 加宁一- _ c )产生一个( o ，1 ) 的随机值v 并且计算只有当d 0 锄p ) 矿时，劬锄e 才作第三章扩展的模糊时间p e t r i 刚1 e na t i m ee l s ei f ( a t i m e b )t l l e l li 坟a = c p n r a l l d r e a l ( o ，0 ，1 ，o ) ) t h e na t i m ee l s ef u z z y ( a ，b ，c ，d ) ；e l s e i f ( a t i m e = a ) t h e l l ae l s ef u z z y ( a b ，c ，d ) ；e ki h d c )t h c ni f ( ( a t i n l e - c ) ( c - d ) + 1 0 -c p n r a n d r e a l ( 0 ，o ，1 ，0 ) )t h e na t i m ee l s ef u z z y ( a ，b ，c ，d ) ；e l s ei f ( a t i i i l e = c ) t h e nce l s e 兀j z z y ( a ，b ，c ，d ) ；3 4 2 将扩展的模糊时间p e t r i 网进行仿真在e f t n 模型中，一个变迁可能与点燃间隔和点燃概率相关联。c p nt o o l s默认不支持这些特性。在四nt o o l s 中，时间延迟可能和变迁的输出弧和变迁自己相关联。但是，c p nt o o l s 中与变迁相关联的延迟实际上时变迁点燃的延迟。e f t n 中变迁点燃问隔是指从变迁使能开始到变迁点燃的时间间隔。e f t n 模型中变迁点燃的时间为o 。为了使用c p nt 0 0 1 s 进行仿真，通过添加一些多余的变迁，库所和代码段把e 兀n 模型转化为c p nt o o l s 模型。图3 2 显示了有冲突的广东t 业大学工学硕士学位论文变迁的转化。在转化的模型中，产生一个i o ，1 i 内的随机数，如果这个随机数小于0 8 则变迁t n 点燃，否则就是变迁t 也点燃。这个转化的模型模拟了e 兀n 模型中有点燃概率的变迁t l 或t 2 。图3 3 展示了变迁点燃间隔的转化。在转化的模型中，库所p 1 和p 2 中的每个令牌都有一个唯一的标识号，比如f 0 砌f 和幻艇”，。当库所p 1 被向愚n f 使能，库所p 2 被抽恕h ，使能，在时间间隔k l ，d 2 l 一个令牌将放到库所订旭日咖。当令牌到达