基于FTPN的实时系统资源冲突分析

王梅

摘要：定义了一类模糊时间Petri网（FTPN）演示在不确定的时间范围内的事实系统的变化，通过对模糊时间情况下的知识的推理和模糊时序情况下的逻辑分析，解决了在实时系统中的资源冲突的问题，以及在实时系统中如何解决时间-空间的冲撞问题，通过一个简单的生产加工系统来模拟演示如何解决系统资源冲突原因，更好的描述了基于FTPN的系统资源冲突的分析。

关键词：模糊时间；实时系统；不确定性；资源冲突

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2014）21-5112-03

1 概述

Petri网自1962年由德国的C. A. Petri提出以来，经历四十多年的发展，已经形成了较为坚实的理论基础，并形成多种类型的应用体系。Petri网直观的图形表示和坚实的数学基础使其特别适合描述系统的并发、竞争、同步等特征。在实时系统进行建模和分析时，时间是一个非常重要的因素[1]。传统的Petri网模型没有时间的概念，也就约束了Petri网在实时系统中的应用，因对实时系统时间行为分析和性能评估的需求，各种与时间相关的Petri网模型也相继提出。目前，常见的时间Petri网有Timed Petri Net[2]，Stochastic Petri Net[3]和Time Petri Net[4]，这些时间Petri网模型都是在基本网的变迁上添加时间因素形成的。但是时间知识具有一定的不确定性，所以在对实时系统进行建模和分析时时间的合理表示和处理成为十分关键的问题。随着可能性理论和模糊集理论的引入，Murata提出了一种模糊时间高级Petri网[5]，这种网能够合理分析系统中的时间不确定性，同时能够进行时间知识的推理。

2 模糊时间Petri网

3 冲突的检测

4 冲突的消解

在模糊时间Petri网模型中，若检测到冲突的存在，应该采用相关的策略来消解冲突。通常情况下，采用先来先服务的原则解决冲突问题。该文除了解决资源有限的冲突问题，还分析了因库所容量形成的冲撞问题。冲撞为特殊的冲突，并且在结构上冲撞问题可以转化为冲突问题。

如果实时系统中存在冲撞的情况时，不能简单的将其转化为冲突的结构来解决问题，因为系统存在了时间因素。如图4所示，[T1]和[T2]不存在资源的冲突，但是[T1]和[T2]不能同时触发，因为库所[P4]的容量为4，而[T1]和[T2]同时触发一共要产生5个托肯。这种特殊的冲突也可采用先来先服务的策略来消解。

由模糊时间知识推理可以计算得到变迁[T1]产生的托肯到达[P4]的模糊时间为[πP4（τ）=[4，6，9，11]]，变迁[T2]产生的托肯到达[P4]的模糊时间为[πP4（τ）=[6，8，11，13]]，[T1]和[T2]产生的托肯在模糊时间[6，8，9，11]内在库所[P4]可能发生冲撞。同理，采用模糊时序逻辑求的[T1]产生托肯先于[T2]产生的托肯到达[P4]的可能性为1，[T2]产生托肯先于[T1]产生的托肯到达[P4]的可能性为0.6，计算得到，[T1]先于[T2]触发的概率应为0.625， [T2]先于[T1]触发的概率应为0.375。

5 实例分析

一个简单的生产加工系统如图5所示。系统的模糊时间Petri网模型如图6所示，[P1][P2][P3]和[P4]的模糊时间分别表示预备原料1-原料4所需的时间，弧上的模糊时间表示设备加工所需要的时间。依据对FTPN模型的分析，通过模糊时间知识推理可以计算得到原料2使得设备1和设备2在模糊时间[3，4，4，5]内发生冲突，通过模糊时序逻辑的分析，可以计算得到设备1占用原料2进行加工的概率为2/3，设备2占用原料2进行加工的概率为1/3。另外，从模型中可以看到设备1产生的中间产品1和设备3产生的中间产品1在储罐1中可能因容量限制产生冲撞，通过模糊时间知识推理可得到设备1产生的中间产品1和设备3产生的中间产品1可能在模糊时间[4，6，7，9]内产生冲撞，使得储罐1内的中间产品1溢出。通过模糊时序逻辑分析，选择设备1的概率为5/9，选择设备2的概率为4/9。

6 结论

本文主要分析了基于时间不确定性的实时系统资源冲突问题，采用模糊时间Petri网进行建模，通过模糊时间知识推理，研究了实时系统冲突的检测方法，通过模糊时序逻辑分析，研究了实时系统冲突的消解方法。最后，通过一个简单的生产加工系统的分析，验证了方法的有效性。

参考文献：

[1] Tasi JJP， Yang SJ. Timing Constraint Petri Nets and Their Application to Schedulability Analysis of Real-time System Specifications [J]. IEEE Trans. Software Engineering， 1995， 21（1）：32-49

[2] 洪国彬.基于随机Petri网的企业业务流程重组的理论与优化方法研究[D].天津：天津大学， 2003.

[3] Ciardo G，German R，Lindemann C.A characterization of the stochastic process underlying a stochastic Petri net [J]. IEEE Trans on Software Engineering， 1994， 20 （7）：506-515

[4] Merlin P M，Farber D J.Recoverability of communication protocols： Implications of a theoretical study [J]. IEEE Trans on Communications， 1976， 24（9）：1036-1043

[5] 袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005：35-36.