Correctness verification and performance analysis of real-time systems using stochastic preemptive time Petri nets

Time Petri nets describe the state of a timed system through a marking and a set of clocks. If clocks take values in a dense domain, state space analysis must rely on equivalence classes. These support verification of logical sequencing and quantitative timing of events, but they are hard to be enriched with a stochastic characterization of nondeterminism necessary for performance and dependability evaluation. Casting clocks into a discrete domain overcomes the limitation, but raises a number of problems deriving from the intertwined effects of concurrency and timing. We present a discrete-time variant of time Petri nets, called stochastic preemptive time Petri nets, which provides a unified solution for the above problems through the adoption of a maximal step semantics in which the logical location evolves through the concurrent firing of transition sets. We propose an analysis technique, which integrates the enumeration of a succession relation among sets of timed states with the calculus of their probability distribution. This enables a joint approach to the evaluation of performance and dependability indexes as well as to the verification of sequencing and timeliness correctness. Expressive and analysis capabilities of the model are demonstrated with reference to a real-time digital control system.     

基于DTPN的时间Petri网的组件级化简规则

时间Petrl网(TPNs)是实时系统时间特性常用的描述和验证的Petri网模型.组件级化简方法是TPN模型常用的分析方法,在保持外部可观察时间特性的前提下,将组件TPN模型化简成一个很简单的TPN模型.然而它却失去了组件内部的性质,如冲突和并发等性质.文中引人延迟时间Petri网(DTPN),通过组件TPN模型向DTPN模型转化,使化简后模型既保持外部可观察时间特性,又保持组件内部的冲突和并发等性质.为了分析化简后的DTPN模型,文中还提出了一种新的DT-PN调度分析方法.最后通过对一个C2系统的组件TPN模型的分析实例,验证该方法的有效性.     

延迟时间Petri网的验证分析

延迟时间Petri网（Delay Time Petri Nets，DTPN）是一类重要的时间扩展Petri网系统，解决了其他时间扩展Petri网（如时间Petri网）在保存时间约束时所面临的困难。可调度验证的目的是验证工作流模型时间约束的合理性，对流程实例的时间可达性进行仿真。提出一种基于DTPN的时间约束工作流验证分析方法。给出了DTPN的相关定义，并结合工作流控制结构描述了变迁可触发的时间条件；提出了DTPN触发点的概念以及基于此的验证分析算法；简要分析了DTPN的特性。DTPN的研究丰富完善了现有时间Petri网体系，具有积极的意义。     

Computer aided verification of Lamport's fast mutual exclusionalgorithm using colored Petri nets and occurrence graphs with symmetries

In this paper, we present a computer tool for verification of distributed systems. As an example, we establish the correctness of Lamport's Fast Mutual Exclusion Algorithm. The tool implements the method of occurrence graphs with symmetries (OS-graphs) for Colored Petri Nets (CP-nets). The basic idea in the approach is to exploit the symmetries inherent in many distributed systems to construct a condensed state space. We demonstrate a significant increase in the number of states which can be analyzed. The paper is to a large extent self-contained and does not assume any prior knowledge of CP-nets (or any other kinds of Petri Nets) or OS-graphs. CP-nets and OS-graphs are not our invention. Our contribution is the development of the tool and verification of the example, demonstrating how the method of occurrence graphs with symmetries can be put into practice     

时间Petri网分析工具的实现

时间Petri网是非常适合描述实时系统的模型工具,由于时间的复杂性因素使得它的可达性分析变得非常困难。该文在分析了基于全局时间变量的时间Petri网的可达性算法的基础上,采用OOP技术,实现了一个时间petri网的分析工具。     

Reduction methods for real-time systems using Delay Time Petri Nets

We present a new net-reduction methodology to facilitate the analysis of real-time systems using Delay Time Petri Nets (DTPNs). Net reduction is one of the most important techniques for reducing the state-explosion problem of Petri nets. However, the application of net reduction to current timed-extensions of Petri nets (such as Merlin's Time PNs) is very limited due to the difficulty faced in the preservation of timing constraints. To overcome this problem, we introduce DTPNs which are inspired by Merlin's (1976) Time PNs, Senac's (1994) Hierarchical Time Stream PNs, and Little's (1991) Timed PNs. We show that DTPNs are much more suitable for net reduction. Then, we present a new set of DTPN reduction rules for the analysis of schedule and deadlock analysis. Our work is distinct from the others since our goal is to analyze real-time systems and the reduction methods we propose preserve both timing properties (schedule) and deadlock. To evaluate our framework, we have implemented an automated analysis tool whose main functions include net reduction and class-graph generation. The experimental results show that our net-reduction methodology leads to a significant contribution to the efficient analysis of real-time systems     

一种利用UML的Petri网软件实现方法

Petri网既是一种图形化建模工具，又是一种形式化数学工具。Petri网具有对并发、并行、分布、异步系统进行验证仿真的能力。但是，Petri网是用来描述和分析要开发的系统模型的工具。不是计算机的实现工具，必须要通过一定的方法才能将Petri网用软件来实现。由于UML(统一建模语言)具有友善的用户界面，易于编程实现，故提出一种利用UML作为过渡的Petri网软件实现方法。     

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

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

基于Petri网的网上股票交易系统模拟与验证

给出了基于时序Petri网下的网上证券交易系统,其模型过于复杂。由于Petri网本身很强的模拟能力,本文用P/T_系统,模拟了证券交易所的网上证券交易系统,进而用S-不变等方法对其进行了验证。     

Monotonic Extensions of Petri Nets: Forward and Backward Search Revisited

In this paper, we revisit the forward and backward approaches to the verification of extensions of infinite state Petri Nets. As contributions, we propose an efficient data structure to represent infinite downward closed sets of markings and to compute symbolically the minimal coverability set of Petri Nets, we identify a subclass of Transfer Nets for which the forward approach generalizes and we propose a general strategy to use both the forward and the backward approach for the efficient verification of general Transfer Nets.     

Implementing Coloured Petri Nets Using a Functional Programming Language

Coloured Petri Nets (CPNs) are a graphically oriented modelling language for concurrent systems based on Petri Nets and the functional programming language Standard ML. Petri Nets provide the primitives for modelling concurrency and synchronisation. Standard ML provides the primitives for modelling data manipulation and for creating compact and parameterisable CPN models.Functional programming and Standard ML have played a major role in the development of CPNs and the CPN computer tools supporting modelling, simulation, verification, and performance analysis of concurrent systems. At the modelling language level, Standard ML has extended Petri Nets with the practical expressiveness required for modelling systems of the size and complexity found in typical industrial projects. At the implementation level, Standard ML has been used to implement the formal semantics of CPNs that provide the theoretical foundation of the CPN computer tools.This paper provides an overview of how functional programming and Standard ML are applied in the CPN modelling language and the supporting computer tools. We give a detailed presentation of the key algorithms and techniques used for implementing the formal semantics of CPNs, and we survey a number of case studies where CPNs have been used for the design and analysis of systems. We also demonstrate how the use of a Standard ML programming environment has allowed Petri Nets to be used for the implementation of systems.     

Verification of real‐time systems design

The main objective of this paper is to present an approach to accomplish verification in the early design phases of a system, which allows us to make the system verification easier, specifically for those systems with timing restrictions. For this purpose we use RT‐UML sequence diagrams in the design phase and we translate these diagrams into timed automata for performing the verification by using model checking techniques. Specifically, we use the Object Management Group's UML Profile for Schedulability, Performance, and Time and from the specifications written using this profile we obtain the corresponding timed automata. The ‘RT‐UML Profile’ is used in conjunction with a very well‐known tool to perform validation and verification of the timing needs, namely, the UPPAAL tool, which is used to simulate and analyze the behaviour of real‐time dynamic systems described by timed automata. Copyright © 2009 John Wiley & Sons, Ltd.     

基于面向对象时间Petri网的密码协议分析

利用面向对象技术和时间Petri网的优点,提出一种基于面向对象时间Petri网的密码协议分析方法。该方法可以降低建模复杂性和计算复杂性,提高建模效率,实现时间Petri网的高度模块化,能更好地适应密码协议分析过程中的重组和扩充。实例分析结果证明了该方法的有效性。     

基于受控时间Petri网的车辆检测过程模型

针对汽车检测线运行效率评估及确保给定数量车辆检测时间最短的问题,通过分析检测过程中的驱动事件和状态演变,给出了车辆调度的约束条件,在此基础上把模型中的时间约束与受控Petri网相结合,提出了受控时间Petri网（Controlled Time Petri Nets）模型,采用该模型对检测线调度过程中的节拍控制与车辆调度进行可视化的建模与分析。实践表明对于多批次车辆检测任务采用该过程模型可明显缩短检测时间。     

Petri网在C3I系统仿真建模中的应用

建模仿真技术是C^3I系统性能评估、C^3I系统仿真分析与设计的一个重要方法。该文介绍了Petri网的基本概念,说明了Petri网建模的特征;给出了一种应用于C^3I系统仿真研究的建模方法：应用Petri网对C^3I系统进行分析与设计,实现从C^3I系统的组织框图到Petri网数学模型的转换;指出了Petrl网在C^3I系统仿真建模方面的不足和改进方向。最后,该文给出了用Petri网建模的一个简单应用实例。     

Revisiting state space exploration of timed coloured petri net models to optimize manufacturing system’s performance

Due to constant fluctuations in market demands, nowadays scheduling of flexible manufacturing systems is taking great importance to improve competitiveness. Coloured Petri Nets (CPN) is a high level modelling formalism which have been widely used to model and verify systems, allowing representing not only the system’s dynamic behaviour but also the information flow. One approach that focuses in performance optimization of industrial systems is the one that uses the CPN formalism extended with time features (Timed Coloured Petri Nets) and explores all the possible states of the model (state space) looking for states of particular interest under industrial scope. Unfortunately, using the time extension, the state space becomes awkward for most industrial problems, reason why there is a recognized need of approaches that could tackle optimization problems such as the scheduling of manufacturing activities without simplifying any important aspect of the real system. In this paper a timed state space approach for properties verification and systems optimization is presented together with new algorithms in order to get better results when time is used as a cost function for optimizing the makespan of manufacturing systems. A benchmarking example of a job-shop is modelled in CPN formalism to illustrate the improvements that can be achieved with the proposed implementations.     

Petri网及其扩展研究

Petri网是一种应用非常广泛的建模工具。首先给出了基本Petri网的概念,在此基础上对多种Petri网进行了广泛的研究,包括时间因素Petri网、有色Petri网、面向对象Petri网、模糊Petri网及受控Petri网,并针对每种Petri网的特点和应用范围进行了讨论,提出了Petri网当前发展的方向和急需解决的热点问题。     

Performance analysis of stochastic timed Petri nets using linearprogramming approach

Stochastic timed Petri nets are a useful tool in the performance analysis of concurrent systems such as parallel computers, communication networks and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to efficiently compute upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming     

基于加权FPN的聚驱综合调整系统决策分析

模糊Petri网(Fuzzy Petri Nets, FPN)是一种适合于描述异步并发事件的计算机系统模型,可以有效地对并行和并发系统进行形式化验证和决策分析.针对聚驱综合调整系统知识具有不确定性和模糊性的特点,给出了基于加权模糊产生式规则的加权FPN决策模型.在此模型的基础上,给出了决策推理过程的形式化推理算法.算法考虑了推理过程中的众多约束条件,将复杂的推理过程采用矩阵运算来实现,充分利用了FPN的并行处理能力,使决策推理过程更加简单和快速.并以压裂方式调整为例,说明了该模型具有直观、表达能力强和易于推理等优点,具有较强的实用价值.