开放网—交互式并行系统的模型

《开放网—交互式并行系统的模型》由会员分享，可在线阅读，更多相关《开放网—交互式并行系统的模型（6页珍藏版）》请在金锄头文库上搜索。

1、西北大学计算机科学系软件工程研究所 西北大学学报（自然科学版），1997, 5。 开放网交互式并行系统的模型开放网交互式并行系统的模型* 郝 克 刚 （西北大学 计算机科学系，西安，710069） 摘摘 要要 本文提出的开放网概念是 Petri 网的一种推广。由于引入了系统与外部的交互机制及层次结构，它可以作为开放的交互式并行系统，特别是规模较大的复杂系统的描述与分析的工具。本文定义了开放网的静态结构、动态行为、系统的进程，讨论了开放网及其进程的分解与合成、抽象对象、开放网的外部特性黑盒理论及开放网的层次结构等基本问题。 关键词关键词 Petri 网，开放网，交互式并行系统，复杂系统，层次化结

2、构。 OPEN NET -A MODEL FOR INTERACTIVE AND CONCURRENT SYSTEMS Hao Kegang （Department of Computer Science, Northwest University, Xian 710069） Abstract This paper introduces a new concept called Open Net which is an extension of Petri Net by adding interactive mechanism between systems. The Open Net can

3、 be considered as an ideal model for interactive and concurrent, especially for large scare complex systems. The interactive mechanism is discussed and the definitions for static structure and dynamic behavior of Open Net are introduced. This paper also discusses some relative problems such as compo

4、sition and decomposition , black box theory and hierarchy structure of Open Nets. Keywords Petri Net, Open Net, interactive system, concurrence, complex system, hierarchy structure. 1 引 言 1 引 言 Petri 网是公认的描述和分析并行系统的比较好的模型。但是，由于它固有的一些特性， 使得它在实际的应用中受到很大的限制，主要表现在如下几个方面。 第一，传统的Petri网，没有反映系统与外部交互的机制，它基本上

5、是一种封闭系统的模 型。Petri网的行为是由初始标识开始的，在执行过程中外部无法干预，它也不对外部产生任何 影响。从外部功能来看它只适合于描述那种初值结果型系统即所谓转换型系统（Transition Systems8,9。 ）然而客观实际是相当复杂的，严格讲任何系统都不可能是完全封闭的。大量的 系统是开放型的，与外部不断进行信息交换的交互式系统或称为反应型系统（Reactive Systems8,9。 ） 第二，由于缺少与外界交互的机制，从而无法对 Petri 网进行外部功能的抽象。所以从本 质上讲 Petri 网理论是个白盒理论，无法研究黑盒理论有关的问题，如外部功能的等价，以及 外部功能

6、等价意义下的变换和化简等。 第三，由于上述的特点，Petri 网很难层次化。因为层次化的基本思路是系统由层次结构图 描述， 上层图中的一个结点是下层图的外部功能的描述， 而下层图是上层图相应结点功能的具 体实现。由于缺少外部功能的抽象，从而很难把 Petri 网描述成为层次的结构。这些就为 Petri* 本文得到国家科委 863 高科技基金的资助。 * 郝克刚，教授，博士生指导教师，主要从事软件工程和软件理论的研究工作。 1西北大学计算机科学系软件工程研究所 西北大学学报（自然科学版），1997, 5。 网在规模较大的复杂系统的应用中带来难以克服的困难。 近年来，围绕上述问题，有不少学者开展了

7、研究工作，并有许多进展，高级Petri网的引入 2在某种意义上也可以说是在Petri网中引入了层次。 正如我们在1 文中所指出， 它是对系统位子集和转移集的一种划分。也就是说，高级网中的一个位子（转移）代表P/T网中的若干个位 子（转移） 。高级网的引入在实际应用中确实增加了表达能力，但这毕竟不是通常意义下的分 层结构。Huber等人的“层次着色网”可以说是在Petri网中引入层次结构的关键性的一步3。 也有一些学者用这种模型来描述交互式系统和作为面向对象方法的模型456。但这种层次结 构仍有很大的限制。 本文提出了开放网概念，它是 Petri 网的一种扩充，比较完整地解决上述问题。Petri

8、 网和 层次着色网都可以看作是它的特例。 开放网可以作为理想的描述与分析开放型交互式并行复杂 系统的模型。 本文的结构如下，在第二节讨论输入输出机制，定义开放网的静态结构。第三节讨论开 放网的动态行为，引入开放网进程的概念。第四节引入描述外部特性的抽象对象概念，讨论开 放网的外部特性，即开放网的黑盒理论。第五节讨论开放网的层次结构，并以五个哲学家就餐 为例，说明对复杂系统的层次描写。 2 开放网的静态结构 2 开放网的静态结构 开放网是传统的 Petri 网（P/T 网）的一种扩充。 ，我们在 Petri 网的基础上增加两类结点， 一类称为外部位子，一类称为外部转移。在图形中用虚线图形表示，或

9、将其画在系统边界的外 边。另外增加四种类型的联接（弧函数） ，以反映四种与外界交互的手段：主动的输入、输出 和被动的输入、输出。相应地，将原 Petri 网中的结点称为内部结点。 定义 2.1（开放网） 。我们称六元组()= P T PTI M, , ,00 0为开放网，其中 1，为互不相交的有限集。分别称为内部位子集，内部转移集，外部位子集 和外部转移集。 P T PT, ,0002，映射 其中： IIIIIIIPTTPPTTPPTTP=UUUUU000 ()IPTPTMS ()ITPTPMS ()IPTPTMS00 ()ITPTPMS00()IPTPTMS00()ITPTPMS00 3，：

10、，但对任何，. M0PPNU0pP00Mp000() =P F01tTt T0PF02PTPEPFtE t E0图 1 一个开放网的例子（哲学家就餐） 我们用 表示 S 上所有多重集的集合。对于开放网也可以有相应的图形表示。图 1 就是一个开放网的例子（哲学家就餐） 。网中，是外部结点。为了下面叙述方便，SMS tE0tT0pF01pF022西北大学计算机科学系软件工程研究所 西北大学学报（自然科学版），1997, 5。 我们将凡与外部结点相连的内部结点称为接口结点，即： 定义 2.2（接口结点） 我们将： ()()PpPtTI p tI tpI=000000:, ()()TtTpPI ptI

11、 t pI=000000:, 分别称为接口位子集和接口转移集。如图 1 中PpTttI FT TE=, 3 开放网系统的动态行为 3 开放网系统的动态行为 开放网系统的动态行为既要考虑其内部 Petri 网的标识的变化还要考虑它同外部结点的关 系，即受外部条件的制约和对外部的影响。然而我们在讨论开放网时，是把它放在一个尚未确 定的外部环境下，进行一般性的讨论，从而我们不可能涉及外部位子的确切的托肯数，也不涉 及外部转移是否可激发以及何时激发。 于是直观地讲， 我们总是设想外部位子中有取之不尽的 托肯可使用。对外部转移，只要其相应的内部位子中的托肯数满足条件，即可激发。我们用 表示 S 上所有广

12、义多重集的集合。所谓 S 上的广义多重集，是指 S 到整数集上的映射：SGMS SInt.它与普通多重集的区别在于它允许负系数。 定 义3.1 （ 标 识 ） 我 们 称是 开 放 网的标识。 MMMMPMPII MSGMS=U00,0. ()= P T PTI M, , ,00 0对于开放网，在标识下转移 称为是可激发的，它的条件是： tTTU0( )()pP M pI p t , 也就是说它与外部位子中的托肯数无关。在 t 激发后的后继标识状态 M 定义为： 对所有 ：pPPU0( )( )()()MpM pI p tI t p,=.+ 显然，对所有 pP . 但是对于 就有可能. 这正是

13、引入广义多重集概念的原因。 ( )Mp 0pP0( )Mp 0为了确切地描述开放网的动态行为，我们需要把 Petri 网进程的概念加以扩充，定义开放 网进程。我们先从定义出现网开始： 定义 3.2（出现网） 将满足下述条件的三元组 N =( B, E, F ) 称为出现网： 1，B, E 是两个互不相交的有限集，BEI= ，分别称为条件结点集和事件结点集。 2，在 B 和 E 的有些元素之间有有向弧相连，即() ()FBEEBU，称为弧集。 3，B 中元素的入向弧和出向弧的个数（入度和出度）均不超过 1，即 bBbb:11 其中b的前集和后集b的定义如下： b()=bee bF, ()beb

14、eF=, 4，网中无循环，即不存在满足下述条件的结点序列，x1xBEnU， 对任何 i=1，n-1，()x xFii,+1且xxn1=。 由此定义可知，两结点间方向相同的有向弧至多只能有一条，不允许多重弧。和b也 是普通意义下的集合而不是多重集。 b显然，可以把 F 看作是结点集XBE=U中的一种二元关系，而且由条件 4 可证 F 的自 反传递闭包 F* 形成 X 上的偏序，记作. 定义 3.3（出现网偏序）设 N=（B，E，F）是出现网，令XBE=U， =，称F()X,是与出现网 N 关联的偏序集。 对于偏序集，我们可以定义链、线（即最大链） 、反链、切（即最大链） 、极大（Max） 、3西

15、北大学计算机科学系软件工程研究所 西北大学学报（自然科学版），1997, 5。 极小（Min）等概念。 定义 3.4（开放网的进程）设()= P T PTI M, , ,00 0是一开放网，N=(B，E，F)是一出现网，g 是一映射 g：BE，如果 N，g 满足下述条件，则称PTPTUUUU00=（N，g） 是的一个进程。 1， 对任何；对任何( )bB g bPP,U0( )eE g eTT,U0 2， 对任何，而且( )( )eE geg e=,( )( )g eg e= 3， 对任何bBbb=01,U 定义中，e 是 e 的前集：()=ebb eF,是普通意义下的集合，但这个集合在 g 下的象 g()一般是个多重集，一般也是个多重集，所以，条件 2 中的等号是多重集意义下的相等。 对于也类似。条件 3 中的b( )g e( )( )g eg e=( )BbB g bP00=是外部条件结点集。 定义 3.5（头进程） ，若