Petri网展开图法的分析和应用

Petri网的展开图是一种特殊的并发系统状态空间搜索方法，它不需要重复考虑并发事件的所有可能的交集，从而大大缩减状态空间爆炸给验证分析带来的空间复杂度和时间复杂度。使用展开图分析Petri网的行为属性与传统的Petri网分析方法相比，具有自己的特点。该文首先介绍了Petri网展开图的构造算法，在此基础上使用展开图分析方法对一个典型Petri网的活性，有界性和可逆性等行为属性进行了分析，并与传统的Petri网分析方法作比较。     

Reverse Unfolding of Petri Nets and its Application in Program Data Race Detection

The unfolding technique can partially alleviate the state explosion in Petri nets through branching processes. However, all states of a system are still contained in its unfolding net. To deal with some practical problems, only the coverability determination of a specific state is needed. In view of this, reducing the scale of the unfolding net is feasible. This study proposes a target-oriented reverse unfolding algorithm for the coverability determination of 1-safe Petri nets, which combines a heuristic technique to reduce the scale of unfolding nets, thereby improving the efficiency of coverability determination. Furthermore, the reverse unfolding is applied to the formal verification of concurrent programs, and their data race detection is converted into the coverability determination of a specific state in 1-safe Petri nets. The experiment compares the efficiency between forward nfolding and reverse unfolding in the coverability determination of a Petri net. The results show that when the Petri net has more forward branches than backward branches, reverse unfolding is more efficient than forward unfolding. Finally, the key factors influencing the efficiency of reverse unfolding are analyzed.     

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

As a powerful analysis tool of Petri nets, reachability trees are fundamental for systematically investigating many characteristics such as boundedness, liveness and reversibility. This work proposes a method to generate a reachability tree, called ωRT for short, for a class of unbounded generalized nets called ω-independent nets based on new modified reachability trees (NMRTs). ωRT can effectively decrease the number of nodes by removing duplicate and ω-duplicate nodes in the tree, and verify properties such as reachability, liveness and deadlocks. Two examples are provided to show its superiority over NMRTs in terms of tree size.      

Modeling Multithreaded Applications Using Petri Nets

Since most modern computing systems contain multiple processing elements, applications are relying on multithreaded programming techniques that allow a program to execute multiple tasks concurrently to take advantage of the processing capabilities. Multithreaded programs are more difficult to design and test because of the nondeterministic execution orders and synchronization among the threads. Different approaches can be used to test Multithreaded Applications. In our approach we use Petri nets to represent the key elements of interactions among threads to identify potential problems such as race conditions, lost signals, and deadlocks. A tool called C2Petri has been developed which converts C-Pthreads programs to the equivalent Petri net model. This tool helps verification of Pthread-based programs. At present the tool has limited capabilities and we hope to expand the capabilities of our tool in the near future.     

Design of Regulatory Traffic Light Control Systems with Synchronized Timed Petri Nets

Fixing the phases is one of the common methods to control an urban traffic network. Once a road is filled with a high traffic flow approaching its capacity, the conventional traffic light controller is not able to handle this traffic congestion phenomenon well. In this paper, we propose a novel regulatory traffic light control system to handle such traffic congestion by using synchronized timed Petri nets (STPNs). Three kinds of intersections in an urban traffic network are defined and employed to demonstrate our new regulatory traffic light control system models. Finally, the liveness and reversibility of the proposed STPN models are proven through the reachability graph analysis method. To our knowledge, this is the first work that solves a traffic congestion problem with a regulatory traffic light control technique that is effective in preventing vehicles from entering traffic congestion zones.     

基于Petri网的非相似余度飞控计算机可靠性分析

应用混合Petri网建立故障诊断模型,应用广义随机Petri网建立Boe ing 777非相似余度飞控计算机故障行为模型.描述了非相似余度系统的结构以及故障的产生和传播的动态过程,分析了该系统的可靠度和容错度,并有效地消除了瞬态故障对分析系统可靠性的影响.     

Control Synthesis of Petri Nets Based on S-Decreases

A method for constructing a controller for a discrete event system modeled by a Petri net is presented in this paper. The control specification of the system is given by a set of linear inequality constraints defined on the marking of the net. The controller that forces the net to obey the constraints is an extended Petri net, which is synthesized based on minimal support S-decreases. The method can deal with general Petri nets with uncontrollable transitions, and then provides a systematic way for synthesizing net-based controllers for discrete event systems.     

有色Petri网的一种面向对象扩展形式

Ｐｅｔｒｉ网与面向对象的结合一直是一个令人感兴趣的研究课题。本文把有色Ｐｅｔｒｉ网引入到面向对象方法中,提出了一种面向对象的扩展有色Ｐｅｔｒｉ网,简称为ＯＥＣＰＮ,     

Off-Line Computation of Real-Time Schedules Using Petri Nets

We present a methodology of off-line analysis of real-time systems, composed of periodic, synchronous or asynchronous precedence and resource constrained real-time tasks. As there is no polynomial optimal scheduling technique for such tasks sets, we present an enumerative method based on the construction of the state graph of a Petri net. The time is modeled by the Petri net through the earliest firing rule.     

An Improvement of McMillan's Unfolding Algorithm

McMillan has recently proposed a new technique to avoid the state explosion problem in the verification of systems modelled with finite-state Petri nets. The technique requires to construct a finite initial part of the unfolding of the net. McMillan's algorithm for this task may yield initial parts that are larger than necessary (exponentially larger in the worst case). We present a refinement of the algorithm which overcomes this problem.     

基于Petri网工作流的动态访问控制

访问控制是信息系统的一项重要安全保护机制,它是通过限制主体对资源的访问权限,从而保证资源的可用性、完整性和可信性的机制。此种机制通过访问控制矩阵实现,但现在的访问控制矩阵是静态的,它们不随时间的变化而改变。文中通过访问控制矩阵和基于Petri网的工作流结合提出了动态访问控制。访问权限是根据工作流的状态来赋予的,这样减少了对资源和数据的误操作,提高了系统访问的安全性和适时性。文中的工作流模型采用Petri网来描述,Petri网具有坚实的数学分析基础,很适合于表述工作流这样的离散模型。     

对象化模糊Petri网的任务协同分配建模与推理

为解决FPNN/FCPN建模与推理过程中存在模型规模急剧增大、模糊变量颜色化的作用有限、无法表示知识分类等问题,提出了一种改进的对象化模糊Petri网（FPN）建模及模糊推理算法.该算法采用面向对象技术化简规模庞大的模糊赋色Petri网（FCPN）,经简化的FCPN退化为普通的FPN,但是库所中托肯的语义也发生了变化,它不仅表示模糊语言变量的集合,更重要的是它可作为其他FCPN的引用.最后将该算法应用于协同设计环境中任务分配的模糊推理过程,可有效地降低Petri网模型的复杂程度,且对象化FPN模型直观,易于理解.     

Petri网的反向展开及其在程序数据竞争检测的应用

展开技术借助分支进程可在一定程度上缓解Petri网性质分析中的状态爆炸问题.但展开网中仍然包含了系统的所有状态信息.某些应用问题仅需对系统特定状态的可覆盖性进行判定,以此为目标,有望缩减网系统展开的规模.为此,针对安全Petri网的可覆盖性判定问题提出了一种目标导向的反向展开算法,结合启发式技术缩减展开的规模,以此提高...     

基于平行Petri网的制造系统调度与控制一体化方法

为了消除制造系统调度层与控制层之间的隔阂, 实现对生产事件快速灵活响应, 本文提出了一种调度与控制一体化的方法. 首先, 定义了一种新型Petri网模型, 即平行Petri网, 从而集成地描述了传感器、执行器、任务和资源信息, 构建制造系统的信息物理系统模型; 其次, 提出了一种从平行Petri网到赋时Petri网的抽象简化方法, 大规模压缩优化调度所需搜索的状态空间; 再次, 定义了策略Petri网以描述最优调度策略. 最后, 给出了平行Petri网与策略Petri网同步执行算法, 使得平行Petri网与物理系统同步执行.     

基于随机对象Petri网的柔性制造系统性能分析

为了增强传统对象Petri网的定量分析能力,提出随机对象Petri网模型。该模型具备随机性和层次特性,获得与随机Petri网的等价关系,从宏观和微观2个层面对系统进行性能分析,并将该模型应用到柔性制造系统中。实验结果表明,该系统保留了面向对象的建模能力,具有较强的定量分析能力。     

Tutorial and Survey Articles: An introduction to Petri Nets

This paper describes the fundamental concepts and characteristics of Petri nets (PNs) that make them a significant tool for modeling and analyzing asynchronous systems with concurrent and parallel activities and follows the extensions that improved the implementation capabilities of the original PNs.

Their first and most relevant extension was time modeling, a vital aspect of system performances not considered in the original version. There are several possibilities for introducing time in PNs. Among them, a technique that associates time with places is presented in some detail. As PNs tend to become cumbersome and time consuming when large and complex systems are involved, a method for decomposing timed PNs of open queuing networks is reviewed here.

Though initially developed as an information/computer-based technique, PNs were immediately adopted in a variety of application areas, such as manufacturing, design, planning and control. Viewed through a more recently developed programming perspective, the ordinary PNs became “high level” PNs suitable for defining different data types and for applying hierarchical approaches.

It is expected that the robust theoretical basis of this tool coupled with its visual and flexibility features will continue to appeal to researchers and practitioners alike in a variety of domains and as a result will continue to evolve and expand.     

不可否认协议的Petri网建模与分析

Petri网是一种描述及分析并发行为的工具,在安全协议的形式化分析中得到了广泛的应用．作为一种特殊的安全协议,不可否认协议虽然已得到了多种形式化方法的分析,但还没有人使用Petri网来分析它们．以一般安全协议的Petri网分析方法为基础,提出了使用Petri网分析不可否认协议的建模及分析方法,该方法可以描述并分析一些其他形式化方法无法描述的协议性质．使用该方法分析Zhou和Gollmann于1996年提出的一个公平不可否认协议,可以发现该协议的一个许多其他形式化方法不能发现的已知缺陷．     

DEDS对象化高级Petri网模型研究--对象化高级Petri网上的一致性网络

针对对象化高级Petri网缺乏标识的状态空间度量,采用谓词集对各位置上的可达标识进行完全划分,形成与加色网等价的一致性网络.原网络的语言是其任何一个一致性网络语言的子集,因而可以用加色网来定义及分析对象化高级Petri网的各种不变量.     

Petri网的一类禁止状态问题的混合型监控器算法设计

针对广义互斥约束下Petri网的不可控影响子网为状态机的一类禁止状态问题,给出了观测器的设计方法,并基于观测器得到了求解最大允许控制策略的算法.利用观测器将广义互斥约束简化为单禁止库所约束,并将存在不可控变迁的问题简化为相当于变迁全部可控的问题,这有效地解决了不可控变迁带来的计算复杂性问题.最后,利用一个地铁交通调度示例验证和说明该监控器设计方法.