进程网的细化研究*

郭峰

(北方工业大学信息学院,北京 100144)

0 引言

进程网[1]是一种很好的描述并发系统、建模、进行系统分析的工具。Petri网对于简单模型来说很容易表示,而实际应用中的系统模型往往是很复杂,详细的规范说明使建模者不太容易理解和分析,因此,一个抽象机制是必要的,它用来简化模型和方便进行性质分析,提供系统的更高层次的视图。这时,就需要提供细化机制以增强其描述能力,通过细化低层次子网来表示更高层次系统模型[2]。进程网也可以采用这种机制。为了方便进行系统仿真和性能分析,进程网也需要进行抽象和细化。

建模方法遵循三个步骤:第1步是建立系统的功能级模型;第2 步将功能级模型变换的成高层次可靠性模型,对于每个预先选择的候选系统生成一个模型;第3步将选择的系统中的高级模型细化成详细可靠性模型[3]。

复杂系统的设计模型通常由简单的设计模型经过逐步求精获得[4]。在系统建模中,细化[5]操作是一个必要和基本的问题,比如在工作流建模方面可以用细化规则保证工作流[6]的合理性。

在建模中使用细化和以一个更加抽象的模型开始建模有很多优点:细化给出了一个好的、结构化的视图。系统内的部件可以清楚地识别,建模者不必理会内部细节。细化节省了时间和空间的分析,解决了状态空间爆炸问题[7]。进程网的细化可以用于模型的层次化设计,它被用来表示系统在不同抽象层次的模型[8]。

采用基于层次细化这种设计方法,人们可以得到满足最初的抽象模型指定的所有属性的系统。此外,细化后模型的属性也可以得到保护,可以进行更详细的分析。

进程网的细化就是对粗略进程网系统中的基本组件具体化。细化技术根据他们保持得性质的不同分为两类:一类是保持行为性质,另一类是保持语义等价[9]。

进程网的细化通过替换部分简单的成分形成较为具体的子网结构,使得进程网能够用于复杂系统的建模[10]。提出了使用网模型的细化设计一个在不同抽象层次上的上的复杂动态系统的方法。某些变迁进行细化,在细化过程中保持原系统的某些性质不变。在一个给定的抽象层次上的变迁被一个复杂的进程在较低层次上进行替代。

系统模型细节的描述在底层中,中间层反映了抽象的变迁的细节。基本性质分析都在较高的层次上考虑,建模开始时省略分支或细节,这些细节会在较低层次一步一步的考虑,直到完成一个完全描述模型[11]。

我们详细的说明细化技术主要是为了规范结构化建模,也是为了便于进行技术验证,它可以保持系统的行为属性。

使用给定的细化规则来进一步的细化。细化规则可以保证进程网的工作流可以有期望的稳定性。

进程网建模工具可以进行建模、存储,但仍有一些缺陷。进程网的层次建模过程是自顶向下的,先建立的模型还比较粗糙,最开始从一个单一的进程网的基本组件出发,建立抽象模型。细化技术可以用于一个自上而下的方法合成并发系统的进程网模型。目前进程网的建模及细化工具很少,在本论文中我们给出了一个进程网细化的方法和工具。

本文提出了进程网细化的规则和实现方法。可以反映进程网的详细构建的过程,表现了系统在不同抽象层次上的视图。论文的结构如下:在第1 节描述基本概念。第2节介绍进程网的细化规则和细化模型分析,第3节介绍进程网的细化的实现以及存储,第4节结论。

1 进程网及其细化规则

进程网:(Process Net)是一个七元组(P,T,F,A,β,I,O),其中(P,T,F)是一个Petri网;A是动作集合,I∈T,表示接受消息的变迁集合,O∈T表示输出消息的变迁集合[1]。

细化指从较为抽象的高层模型到更具体的底层模型的转换过程[12]。在Petri网的研究中,细化通常是指用一个子网结构替换一个变迁或者库所[13]。进程网的细化是用一个子网结构替换一些基本组件形成较为具体的子网模型。

进程网的基本组件是进程网用来建模的最小单位,也是进程网进行细化的基本单位,进程网的基本组件有3种,分别表示三种不同的基本动作:内部动作,发送消息动作,接收消息动作。进程网细化模型允许设计者通过预定义的模型进行细化(主要是变迁的细化)使模型的设计更加合理[14],进程网的细化规则如下:

规则1:一个变迁扩展为一个子网的细化规则,如图4、图5所示。

在图1中,可以看到将一个变迁替换成进程网的基本组件后,可以完成进程网的细化。在图2中,将一个变迁分解成有两个分支的进程网模型,实现细化。

规则2:并发细化的细化规则:如图3所示。

图3 细化规则2:进程网的并发细化规则Fig.3 Refinement rule 2: concurrent refinement rule of process network

在图3中,将一个新的进程网附加在原来存在的进程网的一侧,完成进程网的细化。虽然图3和图2进行细化后的效果看着一样,但本质不同。它们分别是在遵循两种不同的细化规则后所实现的。图2 是一种分解操作,是一个变迁扩展为子网的细化规则。图3 是一种附加操作,是并发细化规则。

规则3:选择细化的细化规则:如图4所示。

图4 细化规则3:进程网的选择细化规则Fig.4 Refinement rule 3: selection refinement rule of process network

图5 细化规则4:进程网的循环细化规则Fig.5 Refinement Rule 4:cycle refinement rule of process network

在图4中一个进程网组件或进程网基本组件中的变迁经过细化后变成具有两个分支的进程网,它属于选择细化规则。

规则4：循环细化的细化规则:如图5所示。

图5中一个进程网中的变迁或基本组件经过细化后变成具有循环结构的进程网,它属于循环细化。

规则5：通信细化的细化规则:如图6所示。

图6 细化规则5:进程网的通信细化规则Fig.6 Refinement Rule 5: Communication refinement rule of process network

图6中两个进程网经过细化后变成具有通信功能的进程网,它属于通信细化。细化后的进程网不仅保持了进程网的一些特性,使模型更加准确,而且细化规则可以帮助设计者进行系统的分析。细化后模型可以提供多层次视图来反映进程网的层次关系。这种模型可以支持模块化验证和设计分析。

2 进程网细化的实现

目前在进程网建模工具中实现了上述的细化规则[15],建模工具的类图如图7 所示。

进程网建模工具的基本组件由最基本的图形,如圆、直线、矩形等进行组合表示的。定义了基本组件和复杂组合组件,分别用BaseSingle、BaseComplex这两个接口来实现进程网基本组件的绘制。

进程网细化规则类之间的关系如图8 所示。

进程网的细化研究中定义了5个细化规则,在工程中定义了5个细化类:TransitionExtendsToSubNetRule,SimulationRefinementeRule,SelectionRefinementRule,LoopRefinement,CommunicationRefinementRule。这5个类分别来实现子网,同步,选择,循环,通信这5种不同的细化。

建模时首先建立进程网的粗略抽象模型。当需要进行细化时,首先按层次选中想要细化的最基本组件。在构建模型的过程中,已经保存了模型的层次关系,选择进程网的顶层模型,一层一层自顶向下选中,直到选中需要细化的那一层。进行细化时,会显示一个细化选择的选项框,用来供建模者进行细化规则的选择,细化结果将会在新的层次上进行显示。

选择5种不同的细化规则之后,将弹出一个新的面板,在新的面板上显示进程网基本组件被细化后的效果。进程网每一个组件的属性及标记与细化前的保持一致。

在文献[16]中,建立了petri网的细化树。在进程网细化中也可以构建进程网的细化树。由于进程网的细化是自顶向下的,逐步求精的,进程网建模工具在建模时使用二叉树的结构,如图9所示。

图7 进程网建模工具整体类图Fig.7 Overall class diagram of process network modeling tool

图8 进程网细化规则类图Fig.8 Process network refinement rule class diagram

图9 层次进程网细化树Fig.9 Hierarchical process network refinement tree

进程网按照细化规则转换后,我们得到一个细化树。进程网的基本组件我们用树的叶子表示,树根表示最初的进程网模型。

在建模工具中支持分层视图。在工具中我们可以分层浏览系统模型,可以使用细化树浏览分层结构,或者双击细化的基本组建,就可以进入到下一层次中。

进程网的逻辑结构和细化后的结果保存在x m l 文件里。进程网的建模过程中的逻辑关系用二叉树的结构进行存储。他们之间的层次关系,每个组件的属性和标记用xml文件进行存储。当进行建模和性能分析时,将xml文件导入到进程网建模工具中,即可还原出建模时的系统模型。

3 结语

本文提出了一种进程网分层模型的细化规则和细化方法,并实现了进程网的细化,给出了进程网的细化树,提供了一个进程网细化的工具。到目前为止,实验室已经完成了进程网建模工具的画图,仿真,可完成图的生成,分层选中,进程网的细化。进程网的语义等价性等方面的研究还有待完善。