计算机系统性能评价12.doc

第12讲第八章随机Petri网模型与分析(下)
Petri理论根据实际的需要在不断完善和发展,本节介绍另外三种常见的随机petri网: 广义随机Petri网、随机回报网(Stochastic ,SRN) 、确定与随机Petri网(DSPN).
§ (GSPN)
概述:
广义随机Petri网(Generalized Stochastic s,GSPN)的提出为缓解状态爆炸提供一种途径。
GSPN是SPN的一种扩充。表现在将变迁分成两类: 一种为瞬时变迁,它的实施延时为零,实施与随机开关相关联; 另一种为时间变迁,它的实施延时服从指数分布。
§ GSPN的定义
=(S, T; F, W, M0, l), 其中
(a)S, W, M0, l与SPN定义相同();
(b)F中允许有禁止弧, 禁止弧仅存在于从位置到变迁的弧。禁止弧所连接的位置的原可实施条件变为不可实施(disenable)条件, 原不可实施条件变为可实施条件, 且在相连变迁实施时, 没有标记从相连的位置中移出。
(c)变迁集T划分为两个子集: T = TtÈTi, TtÇTi =φ, 时间(timed)变迁集Tt = {t1, t2, …, tk}, 瞬时(immediate)变迁集Ti = { tk+1, …, tn}, 与时间变迁集相关联的平均变迁实施速率集合l = {l1, l2, …, lk}。
(d)为在一个标识M下多个可实施瞬时变迁定义一个随机开关, 确定它们之间实施可能性选择。
如果在一个标识M下, 有若干个变迁构成一个可实施变迁集合H, 则有下列两种情形:
(1)如果H全部由时间变迁组成, 则H中任一时间tiÎH实施的概率为:

与SPN的情形相同。

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

, 包含三个时间变迁: t1, t4, t5, 且t1的平均实施速率a依赖于位置P1的标识M(P1), 实际平均实施速率为M(P1) ´ a。t4和t5的平均实施速率分别为实常数b和c。t2, t3, t6, t7为瞬时变迁。
两个随机开关:
t6和t7相冲突因而总是同时可实施的, 故必须定义一个开关分布, 在满足M(P7)>0的标识下使用。
当P2, P3, P4同时包含标记时, t2和t3可是同时可实施的, 故必须定义一个开关分布, 以便在满足M(P2)>0, M(P3)>0和M(P4)>0的标识下使用。
一般情况下, 一个GSPN的可达集是相关P/T网可达集的一个子集,因为GSPN中瞬时变迁优先于时间变迁的实施, 造成一些标识不可达。
§ 随机回报网(SRN)
(Stochastic ,SRN)是1993年提出来的。
SRN是GSPN的一种扩充, 表现在允许系统性能测量可以用回报定义形式表达。
基于GSPN,在SRN中, 还有三种模型功能的扩充:
(1)弧权变量(variable cardinality arc)
在标准Petri网, 弧权都是常数。如果从位置p到变迁t输入弧的弧权是k,t要可实施必需至少有k个标记在p中。当t实施时,k个标记从p中清除。在模型中,经常有要求将位置p中的所有标记移到位置q中。常数弧权不方便完成这个描述。在GSPN中,。变迁t实施仅移动第一个标记从p到q且把一个控制标记放入位置pflush中,然后瞬时变迁tflush能移动所有p中剩余标记,直到p为空。最后,瞬时变迁tstop从pflush中清除这个控制标记。
同样的系统行为可简单地由规定弧权变量解决,在从位置p到变迁t输入弧和从变迁t到位置q输出弧的弧权上标注M(p),表示p中的标记数量。在SRN中,允许有输入、输出和禁止弧的弧权变量。
当弧权变量为零时,就认为此弧不存在。也可利用弧权变量构造弧权函数,例如,max{1, M(p)}表示至小为“1”。
(2)变迁实施函数(transition enabling function)
在SRN 中,每一个变迁t都可以联系一个布尔实施函数e。在每一个标识M中, 当变迁t存在实施可能性时,实施函数e将要被评价