计算机系统性能评价

《计算机系统性能评价》由会员分享，可在线阅读，更多相关《计算机系统性能评价（13页珍藏版）》请在装配图网上搜索。

1、第12讲 第八章 随机Petri网模型与分析（下）Petri理论根据实际的需要在不断完善和发展,本节介绍另外三种常见的随机petri网: 广义随机Petri网、 随机回报网(Stochastic Reward Net，SRN) 、确定与随机Petri网（DSPN）. 8.3广义随机Petri网(GSPN)概述：l 广义随机Petri网(Generalized Stochastic Petri Nets，GSPN)的提出为缓解状态爆炸提供一种途径。l GSPN是SPN的一种扩充。表现在将变迁分成两类： 一种为瞬时变迁，它的实施延时为零，实施与随机开关相关联; 另一种为时间变迁，它的实施延时服从指

2、数分布。 8.3.1 GSPN的定义定义一个GSPN(S, T; F, W, M0, l), 其中 (a)S, W, M0, l与SPN定义相同(定义); (b)F中允许有禁止弧, 禁止弧仅存在于从位置到变迁的弧。禁止弧所连接的位置的原可实施条件变为不可实施(disenable)条件, 原不可实施条件变为可实施条件, 且在相连变迁实施时, 没有标记从相连的位置中移出。 (c)变迁集T划分为两个子集: T = TtTi, TtTi =, 时间(timed)变迁集Tt = t1, t2, , tk, 瞬时(immediate)变迁集Ti = tk+1, , tn, 与时间变迁集相关联的平均变迁实施

3、速率集合l = l1, l2, , lk。 (d)为在一个标识M下多个可实施瞬时变迁定义一个随机开关, 确定它们之间实施可能性选择。 如果在一个标识M下, 有若干个变迁构成一个可实施变迁集合H, 则有下列两种情形: (1)如果H全部由时间变迁组成, 则H中任一时间tiH实施的概率为: 与SPN的情形相同。 (2)如果H包含若干个瞬时变迁和若干个时间变迁或不包含时间变迁时, 只有瞬时变迁能实施, 时间变迁不能实施。瞬时变迁的实施要根据一个概率分布函数。H的全部瞬时变迁构成的子集连同相关的概率分布一起称为一个随机开关(random switching)。相应的概率分布称为一个开关分布。 若与一个可

4、实施的瞬时变迁相关的概率为零, 则该变迁不能实施, 其结果就好象它不可实施一样。 例子8.3.1 图显示了一个GSPN, 包含三个时间变迁: t1, t4, t5, 且t1的平均实施速率a依赖于位置P1的标识M(P1), 实际平均实施速率为M(P1) a。t4和t5的平均实施速率分别为实常数b和c。t2, t3, t6, t7为瞬时变迁。 两个随机开关：l t6和t7相冲突因而总是同时可实施的, 故必须定义一个开关分布, 在满足M(P7)0的标识下使用。l 当P2, P3, P4同时包含标记时, t2和t3可是同时可实施的, 故必须定义一个开关分布, 以便在满足M(P2)0, M(P3)0和M

5、(P4)0的标识下使用。 一般情况下, 一个GSPN的可达集是相关P/T网可达集的一个子集，因为GSPN中瞬时变迁优先于时间变迁的实施, 造成一些标识不可达。 8.4 随机回报网(SRN) l G.Ciardo等人的随机回报网(Stochastic Reward Net，SRN)是1993年提出来的。l SRN是GSPN的一种扩充, 表现在允许系统性能测量可以用回报定义形式表达。l 基于GSPN，在SRN中, 还有三种模型功能的扩充:(1)弧权变量(variable cardinality arc) 在标准Petri网， 弧权都是常数。如果从位置p到变迁t输入弧的弧权是k，t要可实施必需至少有

6、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中，允许有输入、输出和禁止弧的弧权变量。当弧权变量为零时，就认为此弧不存在。也可利用弧权变量

7、构造弧权函数，例如，max1, 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)变迁实施优先级(tran

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

9、N的一种扩充，主要表现在允许时间变迁的实施延时即可以时常数，也可以是指数分布的随机变量。 在图形上，确定时间变迁用黑体长方形表示，指数时间变迁用空白长方形表示。 位置P1包含的标记表示正在“思考”的顾客，亦即，顾客既没有提出服务请求，也没有接受服务。变迁t1模拟由顾客发出的服务请求，它是指数时间的变迁并且实施的速率与负载相关，等于m1；m1是位置p1所含标记的数量，是每一个思考顾客发出服务请求的速率。位置p2包含的标记表示顾客已经发出的服务请求，但还没有开始服务。位置p4包含的标记表示空服务状态。瞬时变迁t2模拟服务的开始。位置p3可以包含一个正在接受服务的顾客标记。t3是一个确定时间变迁，时

10、间间隔为，它模拟服务时间。8.6随机Petri网与排队论 随机Petri网与排队论的比较：(1) 从求解的观点来看，随机Petri网与排队论模型等价，它们对应着相同的马尔可夫链。(2) 排队模型的描述能力还有不足，特别在如下一些现象的描述上：l 同步l 阻塞(blocking)l 顾客的分裂(splitting)(3) 随机Petri网比排队模型有更强的描述能力，尤其在分布系统、并行系统和同步系统的性能分析应用中更是如此。几个模型描述的对照1. M/M/1队列 M/M/1队列模型显示在图。 顾客达到 服务 顾客离开 等待队列图8.6.1 M/M/1队列模型 M/M/1队列的SPN模型表示在图。

11、 l m图8.6.3 M/M/1队列的SPN模型它们有相同的CTMC状态转换速率图，见图 在图中，表示了GSPN的M/M/1队列模型。使用瞬时变迁，可以明显地表示等待队列、服务站和空闲服务器。 l 等待队列 服务 m 空闲服务器图8.6.3 M/M/1队列的GSPN模型2. M/M/2/5/10 在图中，表示了一个M/M/2/5/10队列的GSPN模型。在这个模型中，等待队列的空间限定为5，顾客数量为10。等待队列由位置p1表示，忙服务器由在位置p2中的标记表示, 空闲服务器由在位置p3中的标记表示。位置p4中包含着顾客标记，如果它们能得到允许，它们能到达等待队列。位置p5包含着标记表示等待队

12、列空闲位置数量。位置p4的标识决定着模拟顾客到达变迁的实施速率，位置p2的标识决定着模拟顾客服务并离开变迁的实施速率。 在排队论模型中，要描述有限顾客，正常使用具有指数分布间隔时间的到达过程来描述，它的速率是队列外顾客数量的比例项。补充: 时序Petri网时序Petri网(Temporal Petri net)是在原型Petri网的基础上加入一组时序逻辑公式构成的Petri网变型模型。在这种网系统模型中，常常依靠时序逻辑公式的语义来限制某些 (在原型Petri网语义下可以发生的)变迁的发生，从而控制网系统的运行，使网系统具有某些 (系统设计者所希望的) 优良性质。由于时序逻辑可以清晰地描述系统

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

14、上是一种逻辑顺序。定义1: 时序Petri网是一个二元组 TPN = (,j)基中=(S,T;F,M0)是一个原型Petri网，j是一组时序逻辑公式。TPN的运行既要符合原型Petri网的语义，又要满足时序逻辑公式组j的语义约束。或者说，TPN是在j中各个时序逻辑公式的语义控制下，根据原型Petri网的运行规律运行。定义2: 设TPN = (, j)是一个时序Petri网，TPN的(时序逻辑)公式集j由满足下列条件的公式组成：1) 原子命题s, tfire, t是公式，其中a) s表示(在当前标识下)，库所s中至少有一个标志；b) tfire表示在当前标识下，变迁t可以发生；c) t表示变迁t

15、发生。2) 若f和g是公式，则, f,也是公式，其中a) 是通常的逻辑联结符；b) 表示在当前标识下的下一个可达标识，为真；c) 表示当前标识(包括当前标识)以后的所有标识，至少存在一个标识,使得为真；d) f表示当前标识(包括当前标识)以后的所有标识，均为真；e) 表示从当前标识开始，直至g为真为止，对每个可达标识都为真。例: 下图给出的是一个时序Petri网TPN = (, j)，其中是一个原型Petri网(它与图10.1b的原型Petri网完全相同，是一个时序逻辑公式：(当时序逻辑公式组j蜕化为一个时序逻辑公式时，我们用(,)代替(, j)来表示一个时序Petri网。) s1 ：a)原型

16、Petri网 b)时序逻辑公式图:一个时序Petri网(, j)时序逻辑公式的含义是：当库所s3中至少有一个标识时，变迁t2不能发生，而且当库所s4中至少有一个标识时，变迁t3不能发生。我们知道，在原型Petri网中，是从可达的一个标识， =也是的一个可达标识。在原型Petri网的语义下，且，同样且。记，就有和= 。显然，和都是死标识(没有任何变迁可以发生)。而且，容易验证，在原型Petri网中，只有和这两个可达 标识是死标识。这样，在时序Petri网(,)中，时序逻辑公式的作用实质上就是规定了和，防止标识和的出现，从而保证了(,)是一个活的网系统，换句话说，时序逻辑公式起到了对进行活性控制的作用。写一篇200字以上论文,内容从下面方面选择其一:（在课件20讲）1. 排队论理论是否可以在你熟悉领域中的应用.2. petri理论是否可以在你熟悉领域中的应用.3. 自相似理论是否可以在你熟悉领域中的应用4. 学习petri理论及其发展过程后,你对理论与实践的关系有什么认识.5. 对某篇文章或书中某部分内容的体会或感想 6对已经读过的某篇文章的改进或完善