计算机系统性能评价12

第12讲 第八章 随机Petri 网模型与分析（下）

Petri 理论根据实际的需要在不断完善和发展, 本节介绍另外三种常见的随机petri 网: 广义随机Petri 网、 随机回报网(Stochastic Reward Net，SRN) 、确定与随机Petri 网（DSPN ）.

§ 8.3广义随机Petri 网(GSPN)

概述：

● 广义随机Petri 网(Generalized Stochastic Petri Nets，GSPN) 的提出为缓解

状态爆炸提供一种途径。

● GSPN 是SPN 的一种扩充。表现在将变迁分成两类： 一种为瞬时变迁，

它的实施延时为零，实施与随机开关相关联; 另一种为时间变迁，它的实施延时服从指数分布。

§ 8.3. 1 GSPN的定义

定义8.3.1一个GSPN ＝(S, T; F, W, M0, λ) , 其中 (a)S, W, M0, λ与SPN 定义相同(定义8.2.1);

(b)F中允许有禁止弧, 禁止弧仅存在于从位置到变迁的弧。禁止弧所连接的位置的原可实施条件变为不可实施(disenable)条件, 原不可实施条件变为可实施条件, 且在相连变迁实施时, 没有标记从相连的位置中移出。

(c)变迁集T 划分为两个子集: T = Tt ⋃T i , Tt ⋂T i =φ, 时间(timed)变迁集T t = {t1, t2, „, tk }, 瞬时(immediate)变迁集T i = { tk+1, „, tn }, 与时间变迁集相关联的平均变迁实施速率集合λ = {λ1, λ2, „, λk }。

(d)为在一个标识M 下多个可实施瞬时变迁定义一个随机开关, 确定它们之间实施可能性选择。

如果在一个标识M 下, 有若干个变迁构成一个可实施变迁集合H, 则有下列两种情形:

(1)如果H 全部由时间变迁组成, 则H 中任一时间t i ∈H 实施的概率为: λi ∑λk

t k ∈H

与SPN 的情形相同。

(2)如果H 包含若干个瞬时变迁和若干个时间变迁或不包含时间变迁时, 只有瞬时变迁能实施, 时间变迁不能实施。瞬时变迁的实施要根据一个概率分布函数。H 的全部瞬时变迁构成的子集连同相关的概率分布一起称为一个随机开关(random switching)。相应的概率分布称为一个开关分布。

若与一个可实施的瞬时变迁相关的概率为零, 则该变迁不能实施, 其结果就好象它不可实施一样。

例子8.3.1

图8.3.1显示了一个GSPN, 包含三个时间变迁: t 1, t 4, t 5, 且t 1的平均实施速率a 依赖于位置P 1的标识M(P1), 实际平均实施速率为M(P1) a。t 4和t 5的平均实施速率分别为实常数b 和c 。t 2, t3, t6, t7为瞬时变迁。

两个随机开关：

● t 6和t 7相冲突因而总是同时可实施的, 故必须定义一个开关分布, 在满足

M(P7) ＞0的标识下使用。

● 当P 2, P3, P4同时包含标记时, t2和t 3可是同时可实施的, 故必须定义一个

开关分布, 以便在满足M(P2) ＞0, M(P3) ＞0和M(P4) ＞0的标识下使用。

一般情况下, 一个GSPN 的可达集是相关P/T网可达集的一个子集，因为GSPN 中瞬时变迁优先于时间变迁的实施, 造成一些标识不可达。

§ 8.4 随机回报网(SRN)

● G.Ciardo 等人的随机回报网(Stochastic Reward Net，SRN) 是1993年提出

来的。

● SRN 是GSPN 的一种扩充, 表现在允许系统性能测量可以用回报定义形

式表达。

● 基于GSPN ，在SRN 中, 还有三种模型功能的扩充:

(1)弧权变量(variable cardinality arc)

在标准Petri 网， 弧权都是常数。如果从位置p 到变迁t 输入弧的弧权是k ，t 要可实施必需至少有k 个标记在p 中。当t 实施时，k 个标记从p 中清除。在模型中，经常有要求将位置p 中的所有标记移到位置q 中。常数弧权不方便完成这个描述。在GSPN 中，使用图8.4.1中的模型能完成上述描述。变迁t 实施仅移动第一个标记从p 到q 且把一个控制标记放入位置p flush 中，然后瞬时变迁t flush 能移动所有p 中剩余标记，直到p 为空。最后，瞬时变迁t stop 从p flush 中清除这个控制标记。

同样的系统行为可简单地由规定弧权变量解决，在从位置p 到变迁t 输入弧和从变迁t 到位置q 输出弧的弧权上标注M(p)，表示p 中的标记数量。在SRN 中，允许有输入、输出和禁止弧的弧权变量。

当弧权变量为零时，就认为此弧不存在。也可利用弧权变量构造弧权函数，例如，max{1, M(p)}表示至小为“1”。

(2)变迁实施函数(transition enabling function)

在SRN 中，每一个变迁t 都可以联系一个布尔实施函数e 。在每一个标识M 中, 当变迁t 存在实施可能性时，实施函数e 将要被评价。实施可能性表现在：1. 没有具有比t 更高优先级的变迁在M 下可实施； 2. 变迁t 要满足可实施条件，即，每一个输入位置中都含有大于或等于输入弧权的标记；

3. 每一个输入禁止位置中都含有小于禁止输入弧权的标记。

当上述条件满足时，e(M)被评价，变迁t 可实施iff e(M) = TRUE。缺省e 表示它

为永TRUE 。

(3)变迁实施优先级(transition enabling priority)

在SRN 中，一个实施优先级同每一个变迁相联系。如果S 是在一个标识下可实施的变迁集合，且变迁k 在S 中具有最高优先级h ，那么任何在S 中具有优先级小于h 的变迁都不可能实施。为了避免理论上的混淆，时间变迁和瞬时变迁不能有相同的优先级，瞬时变迁具有比时间变迁更高的实施优先级。一般对时间变迁优先级不加以说明时，可以认为所有时间变迁优先级为“0”，而瞬时变迁的优先级大于等于“1”。变迁实施优先级可以简化模型的设计，特别对于一些系统的控制和管理方案的模拟，将带来极大的效益。

§8.5 确定与随机Petri 网（DSPN ）

确定与随机Petri 网（DSPN ）是GSPN 的一种扩充，主要表现在允许时间变迁的实施延时即可以时常数，也可以是指数分布的随机变量。

在图形上，确定时间变迁用黑体长方形表示，指数时间变迁用空白长方形表示。

位置P1包含的标记表示正在“思考”的顾客，亦即，顾客既没有提出服务请求，也没有接受服务。变迁t1模拟由顾客发出的服务请求，它是指数时间的变迁并且实施的速率与负载相关，等于m1λ；m1是位置p1所含标记的数量，λ是每一个思考顾客发出服务请求的速率。位置p2包含的标记表示顾客已经发出的服务请求，但还没有开始服务。位置p4包含的标记表示空服务状态。瞬时变迁t2模拟服务的开始。位置p3可以包含一个正在接受服务的顾客标记。t3是一个确定时间变迁，时间间隔为τ，它模拟服务时间。

§8.6随机Petri 网与排队论

随机Petri 网与排队论的比较：

(1) 从求解的观点来看，随机Petri 网与排队论模型等价，它们对应着相同的马尔可夫链。

(2) 排队模型的描述能力还有不足，特别在如下一些现象的描述上： ● 同步

● 阻塞(blocking)

● 顾客的分裂(splitting)

(3) 随机Petri 网比排队模型有更强的描述能力，尤其在分布系统、并行系统

和同步系统的性能分析应用中更是如此。

几个模型描述的对照 1. M/M/1队列

M/M/1队列模型显示在图8.6.1。

顾客达到

顾客离开

图8.6.1 M/M/1队列模型

M/M/1队列的SPN 模型表示在图8.6.3。

λ μ

图8.6.3 M/M/1队列的SPN 模型

它们有相同的CTMC 状态转换速率图，见图8.6.2

在图8.6.4中，表示了GSPN 的M/M/1队列模型。使用瞬时变迁，可以明显地表示等待队列、服务站和空闲服务器。

图8.6.3 M/M/1队列的GSPN 模型

2. M/M/2/5/10

在图8.6.4中，表示了一个M/M/2/5/10队列的GSPN 模型。在这个模型中，等待队列的空间限定为5，顾客数量为10。等待队列由位置p 1表示，忙服务器由在位置p 2中的标记表示, 空闲服务器由在位置p 3中的标记表示。位置p 4中包含着顾客标记，如果它们能得到允许，它们能到达等待队列。位置p 5包含着标记表示等待队列空闲位置数量。位置p 4的标识决定着模拟顾客到达变迁的实施速率，位置p 2的标识决定着模拟顾客服务并离开变迁的实施速率。

在排队论模型中，要描述有限顾客，正常使用具有指数分布间隔时间的到达过程来描述，它的速率是队列外顾客数量的比例项。

补充: 时序Petri 网

时序Petri 网(Temporal Petri net)是在原型Petri 网的基础上加入一组时序逻辑公式构成的Petri 网变型模型。在这种网系统模型中，常常依靠时序逻辑公式的语义来限制某些 (在原型Petri 网语义下可以发生的) 变迁的发生，从而控制网系统的运行，使网系统具有某些 (系统设计者所希望的) 优良性质。 由于时序逻辑可以清晰地描述系统的需求规范和约束条件，用原型Petri 网对实际系统建立起基本的物理模型后，再加入一组时序逻辑公式来表示某些特殊需求或人为规定，以实现对系统运行的控制，也是一种常见的思维方式。因此，时序Petri 网 这种变型模型被提出，而且也受到了部分研究人员的关注。 时序逻辑是在经典逻辑的基础上加入了时序算子形成的，从而使命题的真值同时间 (或者说时序) 关联，是一种适于描述同时间相关的命题的表示方法。在时序Petri 网中，“时序”的含义并不真正同物理时间相联系，由于时序Petri 网是在原型Petri 网中加入一组时序逻辑公式形成的，而原型Petri 网中并没有全局时钟，因此在时序Petri 网中的“时序”的含义，实质上是一种逻辑顺序。

定义1: 时序Petri 网是一个二元组 TPN = (∑, ϕ)

基中∑=(S,T;F,M0) 是一个原型Petri 网，ϕ是一组时序逻辑公式。TPN 的运行既要符合原型Petri 网∑的语义，又要满足时序逻辑公式组ϕ的语义约束。或者说，TPN 是在ϕ中各个时序逻辑公式的语义控制下，根据原型Petri 网∑的运行规律运行。

定义2: 设TPN = (∑, ϕ) 是一个时序Petri 网，TPN 的(时序逻辑) 公式集ϕ由满足下列条件的公式组成： 1) 原子命题s, tfire , t是公式，其中

a) s 表示(在当前标识下) ，库所s 中至少有一个标志； b) t fire 表示在当前标识下，变迁t 可以发生； c) t 表示变迁t 发生。

2) 若f 和g 是公式，则

⌝f , f ∧g , f ∨g , f →g , f g , f , ◊f , □f, f until g

也是公式，其中 a) ⌝, ∧, ∨, →, 是通常的逻辑联结符； b) f 表示在当前标识下的下一个可达标识，f 为真；

c) ◊f 表示当前标识(包括当前标识) 以后的所有标识，至少存在一个标识, 使得f 为真；

d) □f 表示当前标识(包括当前标识) 以后的所有标识，f 均为真；

e) f until g表示从当前标识开始，直至g 为真为止，对每个可达标识f 都为真。 例: 下图给出的是一个时序Petri 网TPN = (∑, ϕ) ，其中∑是一个原型Petri

'

网(它与图10.1b 的原型Petri 网∑1完全相同，f 是一个时序逻辑公式

f ：(s 3→⌝t 2) ∧(s 4→⌝t 3)

(当时序逻辑公式组ϕ蜕化为一个时序逻辑公式f 时，我们用(∑, f ) 代替(∑, ϕ) 来表示一个时序Petri 网。)

s1

t 2 t 3

t 4

t 1 s 2

s 3

t 5

s 4 s 5

f ：(s 3→⌝t 2) ∧(s 4→⌝t 3)

a) 原型Petri 网∑ b)时序逻辑公式

图:一个时序Petri 网(∑, ϕ)

时序逻辑公式f 的含义是：当库所s 3中至少有一个标识时，变迁t 2不能发生，而且当库所s 4中至少有一个标识时，变迁t 3不能发生。 我们知道，在原型Petri 网∑中，M 1 = [1,0,1,0,0]T M 3是从M 0可达的一个标识，在原型Petri 网的语义下，M 2 =[1,0,0,1,0]T 也是M 0的一个可达标识。M 1[t2>且M 1[t3>，同样M 2[t2>且M 2[t3>。记M 1[t ，M 2[t3>M4，就有2>M 3

T

。显然，M 3和M 4都是死标识(没有任何变M 3 = [0, 0T , 和2, M 04, = 0[0,0,0,2,0]]

迁可以发生) 。而且，容易验证，在原型Petri 网中，只有M 3和M 4这两个可达 标识是死标识。这样，在时序Petri 网(∑, f ) 中，时序逻辑公式f 的作用实质上就是规定了⌝M 1[t2>和⌝M 2[t3>，防止标识M 3和M 4的出现，从而保证了(∑, f ) 是一个活的网系统，换句话说，时序逻辑公式f 起到了对∑进行活性控制的作用。

11

12

写一篇200字以上论文, 内容从下面方面选择其一:（在课件20讲）

1. 排队论理论是否可以在你熟悉领域中的应用.

2. petri 理论是否可以在你熟悉领域中的应用.

3. 自相似理论是否可以在你熟悉领域中的应用

4. 学习petri 理论及其发展过程后, 你对理论与实践的

关系有什么认识.

5. 对某篇文章或书中某部分内容的体会或感想

6．对已经读过的某篇文章的改进或完善

13