D 的个人博客

全职做开源,自由职业者

  menu

基于 Petri 网的软件过程支撑环境设计

基于 Petri 网的软件过程支撑环境设计


摘要

在软件的生存周期中,软件过程是整个软件开发实施的核心。成功实施的软件项目必须基于一个良好的软件过程元模型与相应的软件过程支撑环境。本论文为提出了 一个基于 XML Schema 定义的以活动为中心的软件过程定义语言 SPDL,设计并初步实现了其基于 Petri 网理论进行软件过程执行控制的支撑环境。


关键词:Petri 网,软件过程,过程模型,SPDL

Abstract

Software process is the core of development in software life cycle. Successful software project must base on a good software process meta model and a corresponding support environment. The thesis presents a XML Schema-based and activity-centric software process definition language SPDL, then designs and implements a execution controlling support environment based on the Petri net theory.

Keywords: Petri net, software process, process model, SPDL

第 1 章 绪论

1.1 软件过程与过程建模

软件过程是软件生存周期中所涉及的一系列相关过程。过程是活动的集合,活动是任务的集合,任务是把输入转换为输出的操作[3]。软件过程模型是软件过程的静态描述,是软件过程执行的依据。软件过程是软件过程模型的执行实例,它是软件过程模型的动态表现。
在进行具体软模块时,都需要对其进行建模,根据 L. Osterweil 提出的“软件过程也是软件”[3]的观点出发,软件过程需要建模是自然的。目前,对软件模块进行建模时最为常用的建模工具是 UML[1],它提供了对面向对象软件模块进行建模的统一标准。

1.3 软件过程支撑环境现状

对于软件过程建模来说,目前尚未形成类似 UML 影响力的建模工具。OMG 提出了 SPEM(Software Process
Engineering Meta-Model )[16] 用于描述软件过程模型,文献[17]提出了基于 SPEM 的 CMM
软件过程元模型,但都却缺乏一个软件过程执行、过程演化的执行支撑环境。
在文献[3]中提出了一个的软件并行开发模型及其控制模型,并基于 Petri 网理论对这些模型进行了精确定义,表明了 Petri 网理论是解决软件过程建模与执行控制的有效途径。

1.3 本课题的研究内容及意义

1.3.1 研究内容

  1. 软件过程与软件过程模型
    软件过程是指软件生存周期中所涉及的一系列相关过程,软件过程模型是软件过程的静态描述。如何准确地描述软件过程模型是重中之重。
  2. 软件过程控制
    为了精确地进行软件过程执行控制,基于 Petri 网的软件过程模型描述与软件过程控制是解决这一问题的有效途径之一。
  3. 软件过程支撑环境
    软件过程建模、软件过程模型修改(模型演化)、软件过程执行管理最终的目的是为了提高软件生产率,所以提供一个高质量的支撑环境是必然的。

1.3.2 意义

近年来,随着社会对软件需求的与日俱增,如何控制软件生产过程以及如何持续地改进、演化软件过程就成为了软件工程研究的核心问题之一。我认为提出一个精确 的软件过程定义语言,并实现针对此语言可用的软件过程支撑环境是非常有必要的。在该支撑环境下,软件开发者:
  1. 能够准确地定义软件生存周期涉及的各类软件过程模型
  2. 能够根据定义的软件过程模型精确地完成相应的软件过程
  3. 在发现已定义的软件过程模型有缺陷时能够将其及时修正
综上,通过软件过程的精确控制及其模型的不断演化,达到软件开发者认为最优的软件过程,从而提高其软件生产率。

1.4 Petri 网简介

Petri 网是一种用于描述离散的、分布式系统的数学建模工具。1962 年,Carl Adam Petri 以其著名的论文“Kommunikation mit Automaten”获得博士学位。在该论文中,他正式提出了 Petri 网论,这一年被视作 Petri 网的诞生之年。1970 年以后,Petri 又将他的网论发展为通用网论。现在,世界各地有许多科研人员专注于 Petri 网的研究,每年都举行 Petri 网国际会议。

Petri 网含有五个基本元素:
  • place(库所)
    一般用圆圈表示,可以形容为容纳标码的场所。它可以有容量限制也可以假设为容量无穷大。
  • transition(变迁)
    一般用矩形或者一条短线表示,描述了从一个状态到另一状态的变化。变迁的发生是发生一般是原子性的,即不可中断。
  • arc(有向弧)
    一般用一段有向弧表示,从库所指向变迁或者由变迁指向库所,表征了两者之前一种偏序关系。弧上可以设定权值大小,即一次性消耗的资源数目。
  • token(标码)
    即网系统中的资源,标码的数目即资源数。在活的网系统中,资源可以在库所变迁中不断流动。
  • marking(标记)
    记录了 Petri 网中 token 的分布情况,描述了 Petri 网的状态。



第 2 章 软件过程定义语言

2.1 SPDL 概述

软件过程定义语言 —— SPDL 是一种面向软件过程建模者、以活动为中心的模型定义语言。它具有如下特征:
  • 涵盖了软件过程所涉及的基本元素,对这些元素的关联、功能、信息进行了描述
  • 能够对软件过程中的活动进行并行描述
  • 能够对软件过程中涉及的角色进行统一的职责描述,定义各角色的权限
  • 使用 XML 作为过程模型描述载体,具有良好的可读性与互操作性

2.2 SPDL 元模型

元模型(meta-model)是用来定义语义模型的构造(construct)和规则(rule)的,通常称为定义表达模型的语言的模型[1]。软件过 程定义语言 —— SPDL 的元模型是用于描述软件过程模型中的各个元素、元素之间的关系以及元素属性的。
对象管理组织(OMG)使用元对象设施(Meta-Object Facility, MOF)对 UML 进行元模型建模[4]。MOF 是一个 4 层体系结构的模型驱动工程[5], 如下图:

图 2.1 MOF 模型

在 M3 层中,MOF 定义了最基本的元元模型;在 M2 层中,使用了 MOF 定义的元元模型定义了 UML 元模型;在 M1 层中,使用了 UML 元模型进行软件模型建模;在 M0 层中,将建模好的软件模型进行实例化,该实例描述了真实世界中的对象。

效仿 UML 的元模型建模方法,得出 SPDL 元模型建模体系结构如下图:

图 2.2 SPDL 模型

在 M3 层中,XML Schema[15] 定义了最基本的元元模型;在 M2 层中,使用了 XML Schema 定义的元元模型定义了 SPDL 元模型;在 M1 层中,使用了 SPDL 元模型进行软件过程模型建模;在 M0 层中,将建模好的软件过程模型进行实例化,该实例描述了真实世界中的软件过程实例。
下图是 SPDL 的类设计(为简洁起见,所有类图都隐去了属性以及操作)


图 2.3 SPDL 类图

2.2.1 XML Schema

附录1

2.3 模型变换

2001 年,对象管理组织(OMG)提出了 MDA[2] 开发的概念,其中提到下面两种类型的模型:
  • PIM(平台独立的模型,Platform Independent Model)
    此类模型不与任何具体特定的平台技术相关。例如,当我们在讨论 SPDL 概念时,我们只关心什么是过程定义、什么是活动定义、什么是任务定义,而不会去关心 SPDL 的支撑环境是如何实现这些概念。
  • PSM(平台特定的模型,Platform Specific Model)
    此类模型非常重视给定平台的特殊性与平台的能力,让模型变换以及代码生成成为可能。例如,一个银行应用的 PIM 可以使用 UML 来建模,然后变换这个 PIM UML 模型到 PSM Java EJB 模型以及生成绝大部分的 Java 代码。
下图给出了从一种模型变换成另一种模型的原理概要:


图 2.4 模型变换原理概要

2.3.1 SPDL 域到 Java 域的变换

一个 SPDL 的实例是一个 XML 文档,它描述了一个软件过程模型。当 SPDL 实例部署到支撑环境中时,必须解析并生成相应的一些 Java 对象,以方便操作,例如进行 Petri 网图的生成,过程模型与过程的关联等。
在实现从 XML 领域到 Java 领域的模型变换时,JAXB 2.0(JSR 222)[7] 提供了规范的方法,下图给出这个变换处理的原理概要:
图 2.5 JAXB 2.0 原理概要

2.3.2 SPDL 实例的 Petri 网图生成

Petri 网可以从两个层次去描述,一是静态层次,即 Petri 网图;二是动态层次,即标记网。本节主要阐述 Petri 网图及其生成。
下面给出 Petri 网图的形式定义及其基本术语。
定义 1.1[3] 如果三元组 (S, T, W) 称为一个 Petri 网图,那么
  • S 是库所的有限集合
  • T 是变迁的有限集合
  • S ∪ T ≠ Φ,且 S ∩ T = Φ
  • W: (S × T) ∪ (T × S) → N 为弧的多重集

流关系是弧的集合:F = {(x, y) | W(x, y) > 0}。在一些介绍 Petri 网相关文献中,弧的重度只定义为 1,并在定义 Petri 网图时使用 F 代替了 W。

定义 1.2[3] 设 N = (S, T, F) 为一个 Petri 网图,x ∈ S ∪ T,则

  • .x = {y ∈ S ∪ T | (y, x) ∈ F}
  • x. = {y ∈ S ∪ T | (x, y) ∈ F}
  • .x. .x ∪ x.
其中,.x 称为 x 的前提,x. 称为 x 的后提,.x. 称为 x 的前后提。

根据定义 1.1, Petri 网图的 UML 建模如下:




图 2.6 Petri 网图类图

根据 SPDL 的元素结构,可以将其定义的软件过程模型分为如下三种基本结构:
  1. 顺序结构
  2. 选择结构
  3. 并行结构

在实际的软件过程建模中,一般需要组合这三种基本结构从而定义出实用的软件过程模型。
2.3.2.1 基元块
基元块使用 Petri 网刻画了 SPDL 过程模型中的基本结构。基元块有以下几类:
  1. 顺序块
    刻画了活动 ei 与 ej 是依次串行进行的,如图所示。

    图 2.7 顺序块

  2. 选择块
    刻画了活动 ei 与 ej 是有选择地进行,如图所示。

    图 2.8 选择块

  3. 并行块
    刻画了活动 ei 与 ej 是并行进行的,如图所示。

    图 2.9 并行块

2.3.2.2 Petri 网图生成
根据 SPDL 实例生成的 Petri 网图中,库所用于存放标码,一个标码描述了一个过程实例;变迁描述了 SPDL 活动,活动的完成将导致变迁的点火,从而引起标码的移动。
下面各图分别展示了顺序、选择与并行结构的 Petri 网图生成实例。
  • 顺序结构
    图 2.10 顺序结构的 Petri 网图生成

  • 选择结构
    图 2.11 选择结构的 Petri 网图生成

  • 并行结构
    在进行并行结构的 Petri 网图生成时,将生成 Join 库所队列结构。这个结构是一个顺序块,其中库所的个数与变迁的个数都等于并行活动个数 - 1。
图 2.12 并行结构的 Petri 网图生成



2.4 基于 SPDL 的软件过程建模方法

基于 SPDL 进行软件过程建模时有两种基本策略:
  1. 自顶向下
    从过程开始建模,发现过程模型中所需要的活动不存在时进行活动建模、任务建模等。
  2. 自底向上
    从参与者、属性等开始建模,最后将这些实体组合成过程。

这两种策略在建模时是交替使用的,自顶向下的策略可以看作是对过程建模的逐步精化;自底向上的策略可以看作是对过程元素的复用。
下面是基于 SPDL 的软件过程建模方法的 UML 用例图。

图 2.13 建模方法 UML 用例图

下图是基于 SPDL 的软件过程建模方法的 UML 活动图。

图 2.14 建模方法 UML 活动图

第 3 章 软件过程执行控制

3.1 过程生存周期

过程是从无到有的,首先经过过程建模,得到一个原始的过程模型。该过程模型部署后执行时将得到过程实例,在过程实例的执行期对其进行监控,并针对过程执行中的数据、问题进行分析,可以得到一个改进的过程模型,最终将原始的过程模型进行重建模,并反复这个过程。
综上,软件过程是动态的,根据过程执行的反馈,按需修改过程模型,达到进一步提高软件生产率的目标。软件过程的生存周期如下图所示。

图 3.1 软件过程生存周期

3.2 过程执行控制

SPDL 为建模者提供了一种软件过程模型的定义语言。在软件过程模型实例化出一个软件过程后必须精确地控制其执行,而基于 Petri 网的过程控制正是解决这一问题的有效途径之一。
在执行的过程中,活动的完成将导致过程的完成或者导致下一个活动的创建,该执行控制是基于 Petri 网进行控制的。在一次点火后,将改变过程状态,生成新的活动,如下图所示。
图 3.2 过程执行控制概览

3.2.1 标记网初始化

标记网用于描述 Petri 网图的状态的,在软件过程支撑环境中用于描述过程的状态。
下面给出标记网的形式定义及其基本术语。

定义 1.3[3] 设 N = (S, T, F) 为一个 Petri 网图,∑ = (S, T, F, M) 称为一个标记网,其中

  • M ⊆ S,称为 N 的一个标记或一个瞬态
  • 若 S ∈ T,且 .x ⊆ M,x. ∩ M = Φ,称事件 x 为可触发的
  • 若事件 x 被触发(称为点火),则标记网 ∑ 转化为 ∑' = (S, T, F, M'),其中 M' = (M - .x) ∪ x.,M' 也是 N 的一个标记,∑' 也是一个标记网

使用一个给定的过程模型实例化一个过程时就是在与给定的过程模型对应的 Petri 网图中初始化一个标记网的过程。
过程实例化的 UML 时序图如下:

图 3.3 过程实例化 UML 时序图

3.2.2 点火控制

当一个过程执行时,其中某一个活动满足了其完成条件时将触发一次对应此活动的变迁的点火。如果点火顺利完成,则相关标码也会被成功移动,并生成对应的活动或结束整个过程。
根据基元块类别,可以将点火控制分为如下三类:
  1. 顺序块点火
  2. 选择块点火
  3. 并行块点火

在控制这三种基本结构中的变迁点火时都基于如下步骤概要:
  1. 检查变迁的点火条件是否满足,如果满足进行步骤 2;如果不满足则退出点火
  2. 在输入库所中根据需要完成活动所在的过程选出对应标码将标码
  3. 从输入库所移到输出库所,即进行点火
下面各图分别展示了顺序块、选择块与并行块的点火控制实例。
  • 顺序块点火

    图 3.4 顺序块点火

  • 选择块点火
    图 3.5 选择块点火(1)
    点火 Activity 1[Choice],说明在过程执行时选择了 Activity 1。
    图 3.6 选择块点火(2)

  • 并行块点火
    在完成 Start Activity 活动时将引起其相关联的 Petri 网的执行:与这个完成活动的过程相关联的标码将与 Start Activity[Start] 库所移动到 Fork 库所。

    图 3.7 并行块点火(1)

    当标码移动到 Fork 库所时,自动进行一次 Fork 变迁点火。
    图 3.8 并行块点火(2)

    当 各并行的活动之一完成时,其对应的变迁的输入库所中的标码将被移动到 Join 输出库所。此时,变迁 Activity 2 是不能被点火的,如果活动 Activity 2 在这个时刻完成,其对应的变迁 Activity 2 的点火将在变迁 Join 自动点火后进行。
    图 3.9 并行块点火(3)

    当标码移动到 Join 库所时,自动进行一次 Join 变迁点火,使得这一标码进入 Join 库所队列中。如果并行活动个数为 n,则在这个库所队列中进行(n - 2)次点火,使得标码移动到队列的尾部库所(Join Queue n-1)。
    图 3.10 并行块点火(4)

    当各并行的活动之一完成时,其对应的变迁的输入库所中的标码将被移动到 Join 输出库所。此时,若不能进行变迁 Join 点火,说明所有的并行活动已经完成,因为 Join 库所队列已经放置满了标码。

    图 3.11 并行块点火(5)

    并行活动已完成后,点火 Join 库所队列队尾变迁,结束整个并行块。

    图 3.12 并行块点火(6)

3.3 历史追踪

过程是动态的,其状态随着过程执行而变化,所以必须记录每次过程状态的变化。通过对历史的追踪,可以得到很多重要的数据,对这些数据进行挖掘整理,有助于对过程模型的演化提供信息,并可以提供项目管理所需的必要数据。
根据软件过程的结构[6],将历史记录分为如下三个部分:
  1. 过程历史
    记录了过程在某一操作发生时的关键数据。例如过程创建 / 完成,过程的活动执行路径,优先级变更等。
  2. 活动历史
    记录了过程中的活动在某一操作发生时的关键数据。例如活动创建 / 完成,活动所有者变更等。
  3. 任务历史
    记录了活动中的任务在某一操作发生时的关键数据。例如任务创建 / 完成,参与者、优先级变更等。

第 4 章 软件过程支撑环境设计

4.1 BeyondTrack 项目简介

ByondTrack 是一个基于
JavaEE 平台的 B/S
结构的软件过程支撑环境。在该环境下,使用者可以进行:

  • 可视化的软件过程建模
  • 自定制过程变量
  • 过程变量粒度的权限管理
  • 过程任务、参与者管理
  • 基于 Wiki 的文档管理
  • 追踪过程事件历史

4.2 体系结构设计

BeyondTrack 项目涉及到的主要技术以及相应的使用情况如下:
  • 在 SPDL 处理上使用 JAXB 2.0(JSR 222)
  • 在应用框架上使用 JBoss Seam 框架[8](2.1.1.GA),该框架为 Java Context and Dependency Injection(JSR 299)[9]的超集实现
  • 数据库持久化方面使用 JPA 1.0 (a part of JSR 220)[10]的 Hibernate[14] 实现,使用 Seam 托管的实体管理与事务管理
  • 表现层选择了 JSF 1.2(JSR 252)[11]的 RichFaces[12] 实现,以 Facelets[13] 作为 JSF 视图定义框架

这里简述一下选择 JBoss Seam 框架的原因:
  • 优秀的组件作用域与组件生存周期管理
  • Annotation-based 组件配置,框架配置非常简洁
  • 整合了很多应用功能,例如规则引擎、工作流引擎、PDF 生成等
  • 是一个 full-stack 的应用框架,提供了表现层、业务逻辑层与数据持久化层的整体解决方案
  • 是 Java 企业级应用框架的"准规范"

高层组件设计如下:

图 4.1 BeyondTrack 组件设计

高层包设计如下:

图 4.2 BeyondTrack 包设计

结论

软 件过程模型是软件项目进行可控实施的基本保证,一个优良的、项目规模适用的软件过程元模型是软件过程模型建模的必要条件。使用 SPDL 能够描述简单的(顺序 / 选择 / 并行)软件过程模型,并在 BeyondTrack 系统中得到过程建模、部署、执行、优化全生存周期的全支撑,在一定程度上提高了软件开发效率。 在进一步的工作中,将继续完善 SPDL 元模型,使之能够描述更复杂的软件过程(例如子过程),并加入对活动变迁条件的定义,使之在基于 Petri 网的过程执行控制时能够自动或半自动地进行。

致谢

在此衷心感谢我的导师李彤博士,正是有了他辛勤的工作,细心的指导和严格的要求,才有了本篇论文的顺利完成。
感谢金峰软件公司,在那里我学习到了很多学校里学不到的软件工程实践与经验。
感谢 BeyondTrack 项目组的成员,大家一起齐心协力,成功地完成了这个项目。这里特别感谢赵禹同学,他给出了很多细心的建议,在项目实现上也尽心尽责。
最后感谢我的家人,是你们深情的教诲和无微不至的关怀,才有了我今天的成绩,对你们的感激之情无论用多少语言都无法表达!

参考文献

[1] Rumbaugh J, Jacobson I, Booch G. The Unified Modeling Language Reference Manual. Addison
Wesley Longman, Inc., 1999
[2] OMG. MDA Guide Version 1.0.1, document no: omg/2003-06-01, 2003
[3] 李彤, 孔兵, 王黎霞等. 软件并行开发过程. 北京:科学出版社, 2003
[4] http://en.wikipedia.org/wiki/Metamodeling
[5] http://en.wikipedia.org/wiki/Model-driven_engineering
[6] ISO/IEC 12207, SOFTWARE LIFE CYCLE PROCESSES
[7] JSR 222, JavaTM Architecture for XML Binding (JAXB) 2.0
[8] http://www.seamframework.org
[9] JSR 299, Web Beans
[10] JSR 220, Enterprise JavaBeansTM 3.0
[11] JSR 252, JavaServer Faces 1.2
[12] http://www.jboss.org/jbossrichfaces
[13] http://facelets.dev.java.net
[14] http://www.hibernate.org
[15] http://www.w3.org/XML/Schema
[16] http://www.omg.org/technology/documents/formal/spem.htm
[17] 基于SPEM的CMM软件过程元模型, 2005 Journal of Software, Vol.16, No.8

附录

1 SPDL XML Schema