微流程的建模与分析*

徐彬 ，周洋 ，和淑芬 ，洪灿梅 ，周智勋

(1.云南电网有限责任公司 迪庆供电局，云南 迪庆 674400；2.西南林业大学 大数据与智能工程学院，云南 昆明 650224；3.云南云电同方科技有限公司，云南 昆明 650217)

0 引言

起源于本世纪初的业务流程管理(Business Process Management，BPM)已成为组织实施挖掘信息系统的重要使能技术[1]。BPM 是一种以规范化地构造端到端的卓越业务流程为中心、以持续地提高组织业务效绩为目的的系统化方法。一般而言，BPM 能为企业带来如下好处：(1)固化企业的业务流程，以规范化管理；(2)实现业务流程的自动化，以提高业务效率；(3)实现业务流程的优化，以达到流程持续优化的目的。

为了快速响应客户需求、持续演化信息系统，业务流程管理要求业务流程微化[2]。相比传统的业务流程，微流程为特定条件下不可再分解的业务流程。当组织准确实施一个微流程前，要确保微流程能否正常运行，就必须进行流程分析。因此，对微流程进行建模和分析，便成为了业务流程管理领域的关键任务之一[2]。

现有研究工作主要关注传统业务流程的建模与分析。在业务流程的建模方面，文献[3]从控制流的角度提出了在工作流领域大名鼎鼎的工作流网(Workflow Net，WF-net)，以建模组织的业务流程。文献[4]、[5]提出使用事件驱动过程链(Event-driven Process Chains，EPC)作为业务流程建模的符号。文献[6]使用Petri 网，提出了一种多视角的跨组织业务流程建模方法，以建模私有流程、公共流程和协作流程。在业务流程的分析方面，针对组织内的业务流程模型，文献[3]基于Petri 网的分析技术，提出了合理性的形式定义，可以在多项式时间内完成业务流程合理性的检测。针对跨组织业务流程模型，文献[7]也提出了合理性的定义。文献[8]提出了兼容性的概念，用于检测协作流程间的交互正确性。文献[9]使用Pi演算，提出了一种对跨组织业务过程事务进行兼容性分析的方法。与上述工作相比，本文工作的最大不同在于：重点关注微流程在同步通信和异步通信语义下的交互建模和分析。

具体而言，本文提出一种建模与分析微流程的方法，主要贡献：(1)对微流程及组合微流程（同步组合和异步组合）进行了建模；(2)从局部和全局的角度，对组合微流程进行了合理性检测。

1 微流程的建模

由于Petri 网可以直观地表示业务过程的控制流，且具有形式化基础和分析工具[10]，故而，本节采用Petri 网对微流程进行形式化建模。

1.1 微流程的建模

定义1(微流程)微流程是一个六元组MP=(P，T；F，M，i，o)，其中：P∪T≠Ø∧P∩T=Ø，P 为库所集，T 为活动集；T=To∪Tuo∧To∩Tuo=Ø，活动集T 由内部活动集Tuo和交互活动集To组成，且Tuo与To的交集为空集；φ∶T→Σ∪{ε}是标记函数，其中Σ 是有限的事件集；F⊆(P×T)∪(T×P)是流关系；映射M∶P→(0，1)表示微流程的状态；i ∈P 表示微流程的输入库所；o ∈P 表示微流程的输出库所；每一个节点x⊆P∪T 都位于从i 到o 的一条路径上。

更准确地，由定义1 可知，本文建模微流程采用的是工作流网。与Petri 网相比，工作流网要求有唯一的输入库所i 和输出库所o。

此外，还需说明的是，定义1 对工作流网进行了兼容性扩展，将活动集T 划分为两种类型。

为了直观图形地表示微流程，用空心大圆圈表示库所，用实心小圆圈表示库所中托肯，用实心方框表示交互活动，用空心方框表示内部活动，用有向线段表示流关系。

以文献[11]中的建立链接和访问为例，图1 分别定义了4 个微流程，分别表示客户(MP1)、Web 接(MP2)、软件程序(MP3)和数据库(MP4)。首先，客户需要使用软件程序，便向Web 接口发送！connect，Web 接口再向软件程序发送！setup。其次，建立连接后，客户可以访问和使用软件程序(！access)。然后，客户决定退出，便向Web 接口发送！logout。最后，软件程序把客户的相关信息储存到数据库(！log)。其中，活动标记中的“！”表示发送消息，“？”表示接收消息，对于微流程MP1而言，库所p0既是输入库所也是输出库所。

图1 4 个微流程

1.2 同步组合建模

微流程的同步组合是指：在同步通信语义和活动发生规则下，一个微流程中的发送消息动作与另一个微流程中的互补消息动作同时发生交互。所谓互补消息动作是指除首字母外其余字母都相同的标记动作，例如图1 中的“! connect”和“?connect”。

定义2(活动发生规则)微流程是一个六元组MP=(P，T；F，M，i，o)，并具有下述的活动发生规则：

(1)对于活动t∈T，如果∀p∈*t∶M(p)≥1，则说活动t 在状态M 有发生权(enable)，记为M[t>；

(2)若M[t>，则在状态M 下活动t 可以发生(fire)，从状态M 发生活动t 得到一个新状态M'，记为M'[t>M，∀p∈P，满足：

①若p∈*t-t*，M'(p)=M(p)-1；

②若p∈t*-*t，M'(p)=M(p)+1；

③其他，M'(p)=M(p)。

定义3(同步组合)设{MP1，MP2，…，MPn}是一个微流程的集合，且每个微流程为MPk=(Pk，Tk；Fk，Mk，ik，ok)，其中k∈{1，2，…，n}，同步组合MP1||sMP1||s…||sMPn将得到一个新的组合微流程MP=(P，T；F，M，i，o)，其中：P=P1∪P2∪…∪Pn∪{i}∪{o}；T=T1∪T2∪…∪Tn；F=F1∪F2∪…∪Fn；M=M1∪M2∪…∪Mn。

图2 给出了微流程同步组合的示意图。

图2 微流程同步组合的示意图

1.3 异步组合建模

微流程的异步组合是指：在异步通信语义和活动发生规则下，一个微流程中的发送消息动作与另一个微流程中的互补消息动作间通过消息缓冲区进行交互。与同步组合相比，异步组合不要求发送消息动作和互补消息动作同时发生交互。

定义4(异步组合)设{MP1，MP2，…，MPn}是一个微流程的集合，且每个微流程为MPk=(Pk，Tk；Fk，Mk，ik，ok)，其中k∈{1，2，…，n}，异步组合MP1||asMP1||as…||asMPn将得到一个新的组合微流程MP=(P，T；F，M，i，o)，其中：P=P1∪P2∪…∪Pn∪Padd；T=T1∪T2∪…∪Tn；F=F1∪F2∪…∪Fn∪Fadd；M=M1∪M2∪…∪Mn。其 中，Padd和Fadd分别表示新增的库所和弧。图3 给出了微流程异步组合的示意图。其中，虚线圆圈和虚线有向线段分别表示新增的库所和流关系。

图3 微流程异步组合的示意图

2 微流程的分析

2.1 合理性

微流程在执行中因同步交互错误或异步交互错误容易引起死锁，进而导致软件系统出现故障、中断服务。因此，从控制流角度对微流程进行分析对确保微流程模型以及软件系统的正确性至关重要。

首先，为确保构成组合微流程的微流程是无死锁的，本文首先提出了局部合理性的概念。

定义5(局部合理性)给定一个微流程MP=(P，T；F，M，i，o)，该微流程是局部合理的，当且仅当：对于每个从初始状态i 可达的状态M，存在一个活动发生序列，使得M 可达状态o；状态o 是从状态i 可达的唯一状态，且结束时M(o)≥1；∀t∈T，∃M，M'，即不存在死活动。

虽然每个微流程都是局部合理的，但是组合微流程也可能发送因交互引起的死锁。

其次，在局部合理性的基础上，本节提出了全局合理性的概念。

定义6 (全局合理性)给定一个组合微流程MP=MP1||iMP1||i…||iMPn=(P，T；F，M，i，o)，其中||i∈{||s，||as}，MPk=(Pk，Tk；Fk，Mk，ik，ok)为微流程，该组合微流程是全局合理的，当且仅当：MP 是局部合理的。

最后，基于局部合理性和全局合理性，本节提出了合理性的概念，用于确保组合微流程的正确性。

定义7(合理性)给定一个组合微流程MP=MP1||iMP1||i…||iMPn=(P，T；F，M，i，o)，其中||i∈{||s，||as}，MPk=(Pk，Tk；Fk，Mk，ik，ok)为微流程，该组合微流程是合理的，当且仅当：MPk是局部合理的，k∈{1，2，…，n}；MP 是全局合理的。

2.2 合理性检测算法

根据定义5～7，给定一个组合微流程，直接检测该微流程是否满足合理性是困难的。为此，文献[3]证明了可以将合理性规约为活性和有界性，而检测活动和合理性可以使用基于Petri 网的分析技术来完成。

定义8 (活性)给定一个微流程MP=(P，T；F，M，i，o)，该微流程具有活性，当且仅当：对于每个从初始状态i 可达的状态M 和每个活动t，存在一个从M 可达的状态M'，使得M'[t>。

定义9 (有界性)给定一个微流程MP=(P，T；F，M，i，o)，该微流程具有有界性，当且仅当：对于每个库所p，存在一个自然数n，对于每个可达状态M，都有M(p)≤n。

基于定义8 和9，文献[3]提出了定理1。

定理1在一个微流程MP=(P，T；F，M，i，o)，活动t∈T 是死的，当且仅当：可达状态图RG(MP)中不存在以t 为旁标的弧。

定义10 (可达状态图)给定一个微流程MP=(P，T；F，M，i，o)，其中M0是MP 的初始状态图，可达状态图RG(MP)的定义如下：M0∈RG(MP)；若M∈RG(MP)，且存在t∈T 使得M[t>M'，则M'∈RG(MP)。

根据定理1，给出检测组合微流程是否具有合理性的算法如下：

需要说明的是，该算法中使用构建可达状态图的算法可参见文献[12]。

3 工具与实验

3.1 工具

本文采用开源工具WoPeD(Workflow Petri Net Designer，WoPeD)对微流程进行建模与分析。WoPeD[13]是一个用于建模、模拟和分析基于工作流网描述业务流程的工具，被学术界广泛使用。

图1 所示4 个微流程经异步组合得到的组合微流程在WoPED 工具的实现如图4 所示。

图4 组合微流程的建模结果截图

在WoPeD 中，可以使用语义分析功能对组合微流程的合理性进行分析，分析结果如图5 所示。其中，灰色圆圈表示该组合微流程中的库所不满足有界性。因此，该微流程不满足合理性。

图5 组合微流程的分析结果截图

3.2 实验结果

本文在Windows 环境下运行了50 个多例子，其中，部分例子来源于文献，部分例子来源于某电力行业内部的微流程。实验环境的具体配置如下：2.3 GHz Intel Core i7 处理器和16 GB 内存。

表1 给出了部分实验结果。表1 第1 列为编号，编号中“e-*”表示该例子来源于文献，“l-*”表示该例子来源于行业内部；第2 列为组合微流程的描述；第3 列为构成组合微流程的流程个数；第4 列为同步通信语义下得到的组合微流程；第5 列为异步通信语义下得到的组合微流程。在第4 列和第5 列中，“×”表示不满足合理性；“√”表示满足合理性。

表1 部分实验结果

从表1 可知：(1)在来自企业的例子中，e-03 在异步通信语义下，该组合微流程不满足合理性；(2)在来自文献的例子中，l-03 在同步通信和异步通信语义下，该组合微流程都不满足合理性；(3)l-05 在异步通信语义下，该组合微流程不满足合理性。

4 结论

为确保微流程能正常运行，一方面，本文使用工作流网对微流程以及微流程间的同步组合和异步组合进行了建模；另一方面，使用Petri 网的分析技术对组合微流程进行了合理性分析。实验结果表明，该方法能建模微流程，并检测出组合微流程中死锁错误。