基于Time Petri Nets的实时系统资源冲突检测

Time Petri Nets在实时系统的建模和性能分析中得到广泛应用,而冲突是Petri网及其扩展模型的重要行为,解决冲突是正确分析模型动态行为的关键.目前随机Petri网、混合Petri网和区间速率连续Petri网的冲突检测方法由于没有考虑到时间约束因此无法在TPN网中使用.时间约束的引入使得Time Petri Nets模型的使能和触发语义比Petri网模型的语义复杂,冲突检测变得更加困难.为了计算冲突发生的时间和概率,首先根据时间约束,给出了变迁持续使能时延迟区间的计算方法,并证明了该方法的合理性和完备性;然后在此基础上定义并证明了Time Petri Nets模型中不冲突的检测方法;并提出了Time Petri Nets模型的冲突检测方法,给出了冲突时间区间和变迁实施概率的计算方法;最后通过实例验证说明了该方法的正确性和有效性.     

具有多品种晶圆混合加工的单臂组合设备调度

为了提高晶圆制造中组合设备的生产效率,在考虑晶圆驻留时间约束条件下,研究没有共享加工模块的多品种晶圆混合加工的单臂组合设备调度问题.首先,采用面向资源的Petri网模型描述多种晶圆产品的混合加工过程,引入控制变迁避免模型的死锁,采用赋时库所和赋时变迁模拟系统资源的活动时间.其次,通过虚拟加工的方法平衡工序的负载,基于系统Petri网模型和拉式调度策略,推导出单臂组合设备在多品种晶圆混合加工情形下的可调度性判定条件,并以解析形式描述.最后,提出了系统稳态调度求解算法并以实例验证了算法的有效性和可行性.     

面向对象双变迁Petri网及应用研究

针对Petri网数据流描述能力的不足,引入了数据变迁的概念,给出了双变迁Petri网的定义和图形表示,详细分析了双变迁Petri网的行为规则;定义了面向对象双变迁Petri网,使复杂系统的网模型易于分析理解;实例建模表明,该方法对控制流和数据流共存的复杂系统建模十分有效.     

基于逻辑时延Petri网的停车预订系统建模与分析

为解决逻辑Petri网不能详尽地描述模型在规定时间点变迁引发和引发完成的时间问题,提出逻辑时延Petri网.首先在普通变迁的基础上引入变迁的引发时间和变迁完成时间形成决策变迁,为每个token定义到达时间和自身时间属性等;其次重新定义引发规则和可达图算法,并针对决策变迁和可达图生成进行算法描述;最后使用逻辑时延Petri网对停车预订系统进行建模,构建可达图分析系统中重分配问题以及车位的利用率等问题.在此基础上设计实验验证了逻辑时延Petri网的可行性和智能停车预订系统的优势.     

基于Time Petri Net的实时系统冲撞检测与消解

time Petri net(TPN)在实时控制系统的建模中得到广泛应用,而冲撞是Petri网及其扩展模型的重要行为,解决冲撞是正确分析模型动态行为的关键.由于引入时间约束,使得TPN模型的使能和触发语义比Petri网模型的语义复杂,冲撞的检测及消解变得更加困难.首先根据时间约束,给出了变迁持续使能时延迟区间的计算方法,并证明了该方法的正确性;然后在此基础上定义并证明了TPN模型中冲撞的检测方法;给出了冲撞时间区间及修改时间约束的冲撞消解方法;最后通过实例验证说明了该方法的有效性和正确性.     

移动网可达树

随着计算机技术和网络通信技术的高速发展,对于并发分布式系统,已经提出了进程代数以及Petri网等形式化分析方法。近年来由于移动互联网的出现和快速发展,通过在进程代数中增加移动性得到了pi演算,与此同时,Petri网领域也采用谓词/变迁网、颜色网等构建移动系统模型。但它们仍存在一些不足之处。在此基础上,A.Asperti和N.Busi提出了移动网这一系统模型。移动网是在Petri网的基础上增加了移动性并结合了进程代数的优势得到的,适用于描述和刻画移动计算系统。然而,目前并没有对于移动网相应分析方法的研究。为此开展了移动网模型分析方法的研究,给出了移动网可达树的构造算法,提供了移动网模型可达性分析方法,并对移动车辆电话通信系统实例进行了分析。     

可重写Petri网:位置可重写及性质分析

针对Petri网对动态系统重构形式化描述和建模能力的不足,提出了可重写Petri网和位置可重写Petri网的基本概念.分析了位置可重写Petri网保持有界性、保守性、可重复性及活性等性质.给出了位置可重写Petri网保持活性的一个充要条件.证明了共享合成Petri网是位置可重写Petri网的一个实例,建立了退化的位置可重写Petri网模拟共享合成Petri网的算法.所得结果能够为动态重构系统的Petri网形式化建模提供理论方法,为大规模动态分布式系统的形式化验证提供有效途径.     

专家寄语

正Petri网是20世纪60年代由C.A.Petri发明的分布式系统的建模和分析工具。Petri网既有直观的图形表达方式,也有严格的数学表述方式。作为一种系统模型,Petri网不仅可以刻画系统的结构,而且可以描述系统的动态行为。Petri网自身具备的可运行性方便了系统形式化描述级的模拟,可以用于表达不同抽象级上的系统概念并清楚地描述整个系统的运作过程。Petri网可以对复杂的系统进行分层描述,逐步求精,使其便于同面向对象的思想方法相沟通。Petri网没有人为的控制流,直观地表示了非确定性。     

基于一致分布的时间Petri网模型

时间Petri网的现有分析理论主要关注基于区间端点的计算和推理,缺乏对实施区间内不确定性的定量描述,不利于时间Petri网进行系统性能评价和动态模拟实现.为了解决这一问题,提出基于一致分布的时间Petri网模型.首先给出变迁实施概率和变迁序列实施概率的计算方法;然后引入概率条件到状态类,用于构造时间Petri网的概率可达类树;最后给出动态模拟实验,检验理论方法的正确性.     

基于Petri网的分布式系统并发进程的死锁检测

分布式系统中的并发进程具有明显的并发、异步及分布性,而Petri网是模拟与分析并发、异步、分布式系统的有效工具.为此通过引入Petri网,给出了分布式系统局部并发进程等待的Petri网模型及死锁检测方法,提出了全链路合成的概念,利用全链路合成技术组装了全局并发进程等待的Petri网模型,给出了判断整个系统是否出现死锁的充分必要条件.