|
||||
|
||||||||
随机Ｐｅｔｒｉ网与系统性能评价 |
|
国家信息中心 林闯 副研究员 一、引言 系统性能评价的传统方法是采用排队论来解决系统的描述问题，数学求解的基础是马 尔可夫随机过程。８０年代初，Ｍｏｌｌｏｙ提出的随机Ｐｅｔｒｉ网（Ｓｔｏｃｈａｓ ｔｉｃ Ｐｅｔｒｉ Ｎｅｔｓ，ＳＰＮ）、１９８４年Ｍａｒｓａｎ等人提出的广义随 机Ｐｅｔｒｉ网（Ｇｅｎｅｒａｌｉｚｅｄ Ｓｔｏｃｈａｓｔｉｃ Ｐｅｔｒｉ ＮＥ ＴＳ，ＧＳＰＮ）和１９８６年林闯等人提出的随机高级Ｐｅｔｒｉ网（Ｓｔｏｃｈａｓ ｔｉｃ ＨｉｇｈＬｅｖｅｌ Ｐｅｔｒｉ Ｎｅｔｓ，ＳＨＬＰＮ），为系统的性能 评价结供了新的数学描述工具。随机网的研究和应用已成为Ｐｅｔｒｉ网实际应用成功的 领域。从１９８５年起，每两年召开一次专门讨论Ｐｅｔｒｉ网性能模型理论和应用的国 际学术会议。 时间参数的引入并不破坏原Ｐｅｔｒｉ网结构的描述和特性的分析，但在进行性能评 价时，其模型动态行为将受时间参数的影响，原系统并发不确定次序的行为将变成有不同 级别的优先选择。 时间引入Ｐｅｔｒｉ网有两种方式：一是每个库所相关联一个时间参数；二是每个变 迁相关联一个时间参数。目前，大多数文献采用后者，将每个变迁同一个固定延时时间相 关联的Ｐｅｔｒｉ网叫做时间Ｐｅｔｒｉ网（Ｔｉｍｅｄ Ｐｅｔｒｉ Ｎｅｔｓ）。在 时间Ｐｅｔｒｉ网中，系统性能分析依赖于系统动态行为的调度排列，即变迁的实施序列 ，变迁延迟时间的累加即为实施序列的总延迟。 另外一种在Ｐｅｔｒｉ网中引入时间参数的方法是：在每个变迁的可发生与实施之间 联系一个随机的延迟时间，这类Ｐｅｔｒｉ网叫做随机Ｐｅｔｒｉ网。大多数随机网模型 的性能分析是建立在其状态空间与马尔可夫链（Ｍａｒｋｏｖ Ｃｈａｉｎ ＭＣ）同构 基础上的。ＳＰＮ为系统的性能模型提供了良好的描述手段，随机马尔可夫过程为模型的 性能评价提供了坚实的数学工具。 在随机Ｐｅｔｒｉ网中，变迁实施延时随机变量又分为离散和连续两种情形。对这两 种随机变量可定度多种分布函数。通常要求机关离散时间的随机变量是几何分布，而相关 连续时间随机变量是指数分布。 由于篇幅所限，主要对Ｍｏｌｌｏｙ的ＳＰＮ做一些介绍，其它类型的随机网详见有 关文献。 二、随机Ｐｅｔｒｉ网与性能评价的方法 在连续时间的ＳＰＮ中，一个变迁从可发生到实施需要延时，即在一变迁变成可发生 到它实施时刻之间被看成是一个连续随机变量，且服从于指数分布。已经证明，一个ＳＰ Ｎ同构于一个连续时间的ＭＣ。ＳＰＮ的每个标识映射成ＭＣ的状态，ＳＰＮ的可达图同 构于ＭＣ的状态空间，ＭＣ状态之间的转移速率与相应变迁的实施速率相关联。换包话说 ，只要将ＳＰＮ可达图中标识之间的转换变迁换成相应的实施速率就可得到相应的ＭＣ。 ＳＰＮ是一般Ｐｅｔｒｉ网的扩充。每个变迁相关联一个实施速率，表示在可发生条 件下单位时间平均实施的次数，单位是：次数／单位时间。特别是注意，实施速率可能依 赖于标识，是标识的函数。例如，在一个变迁表示多个任务或进程并发执行时，变迁的平 均实施速率任务个数（或进程个数）成正比。平均实施速率的倒数称为变迁实施延时或平 均服务时间。Ｐｅｔｒｉ网（指Ｐ／Ｔ网）可看成是ＳＰＮ的特例，其所有变迁实施延时 都为零。 ＳＰＮ可达图的获得同相应Ｐ／Ｔ网的可达图的获得完全相同。如果对一个网设置不 同的初始标识，就会得到不同的可达图，也就会得到不同的ＭＣ。给系统模型初始标识中 的托肯设置得越多，ＭＣ就越大。 ＳＰＮ与Ｐ／Ｔ网也有不同的特性。在一个标识下，如果有几个可以发生的变迁，发 生的可能小。但在Ｐ／Ｔ网中所有可以发生的变迁，发生的可能性都相同。 在一般情况下，ＳＰＮ模型要求其库所都是有界的，即在任何标识中所有库所的托肯 数量都小于个正整数。另外，要求模型的标识都是可往返回该标识。这样要求的目的，是 为了便于ＳＰＮ所同构ＭＣ的稳定状态概率的计算和系统的系统的性能评价。 ＳＰＮ在系统性能评价中的应用主要分为三步： （１）给出系统的一个ＳＰＮ模型； （２）构造出该ＳＰＮ所同构的ＭＣ； （３）基于ＭＣ稳定状态概率进行系统所要求的性能评价。 ＳＰＮ是一个动态系统，，当时间趋于无穷时，它会达到一种动态平衡。昆时，该Ｓ ＰＮ居于每个状态稳定概率可由相应ＭＣ牟转移速率矩阵■描述。Ｒ的非对角线上的元素 ■为：当从动态ｉ到动态ｊ有一条弧连接时，则弧上的速率值即是■的值。如果从动态ｉ 到状态ｊ没有弧连接，则■＝０。Ｒ的对角线上的元素■等于从状态ｉ输出各条弧上速率 之和的负数。设ＭＣ中有Ｓ个标识的稳定概率是一个行向量Ｘ＝（ｘ［１］ｘ［２］…， ｘ［ｓ］），则有下列线性方程组： 解此线性方程组，就可获得每个标识（或称状态）的稳定概率。有了每个状态稳定概 率，应打开了系统性能评价的大门。 在求得稳定概率的基础上，可以进一步分析以下性能指标： （１）在每个状态中逗留的时间； （２）托肯概率密度函数； （３）库所中平均托肯数； （４）变迁的利用率； （５）变迁的托肯流速。 有了这些性能指标，配合使用Ｌｉｔｔｌｅ规则和流平衡原理等，就可计算“系统的 平均延时时间”、“系统吞吐量”和“资源利用率”等系统性能。 三、多处理系统性能评价的例子 现以一个多处理机系统为例，说明ＳＰＮ的应用。假定该系统有２个相同的处理机， ２个共用存储器和一条传输总线。每个处理机交替地在私有存储器和共用存储中进行存取 操作。当它要进入共用存储器时，它必须得到传输总线的控制权；当它完成在共用存储器 的操作时，它要释放共用存储器和总线。个处理机对每个共用存储器要求存取的可能性假 定是相同的。在图１中，显示了一个多处理机系统的ＳＰＮ模型。 @@499116T1.PCX;图一@@ 库所和变迁的含义如下： Ｆ：是“私有存储器”库所。当Ｆ包含着托肯时，就表示相应的处理机是在它们自己 的私有存储器中操作。 Ｑ［１］（Ｑ［２］）是“第一队列（第二队列）”库所。当Ｑ［１］（Ｑ［２］） 包含着托肯时，就表示相应的处理机是在第一（第二）公用存储器的等待队列中。 Ｍ［１］（Ｍ［２］）：是“第一（第二）公用存储器空闲”库所。当Ｍ［１］（Ｍ ［２］）包含着托肯时，就表示第一（第二）公用存储器牌空闲状态。 Ｂ：是“传输总线空闲”库所。当Ｂ包含着托肯时，就表示相应的总线牌空闲着状态 。 Ａ［１］（Ａ［２］）：是“第一（第二）公用存储器存取”库所。当Ａ［１］（Ａ ［２］）包含着托肯时，就表示相应的处理机正在第一（第二）公用存储器中操作。 Ｅ［１］（Ｅ［２］）：是“结束私有活动，进入第一（第二）队列”变迁可以发生 。变迁实施时间为１／ 。 Ｇ［１］（Ｇ［２］）：是“进入第一（第二）公用存储器”变迁。当处理机要求公 用存储器和总本都有效时，这个变迁可以发生。变迁实施时间为 Ｒ［１］（Ｒ［２］）：是“存取并释放第一（第二）公用存储器”变迁。在公用存 储器的操作后，处理机释放公用存储器总线，并返回私有存储器执行。变迁的实施时间为 这个系统的可达集和对应的ＭＣ如图２所示。注意到变迁Ｅ［１］（Ｅ［２］）的实 施率与库所Ｆ中的托肯数成正比。变迁Ｇ［１］（Ｇ［２］）的实施速率与库所Ｑ［１］ （Ｑ［２］）的托肯数成正比。 @@499116T2.PCX;图二@@ 现在我们可求不同系统资源的平均利用率。仅以处理机为例，其平均利用率公式为： 其中，ｍ［ｉ］（Ｑ）表示系统处于状态ｉ时，库所Ｑ中所含托肯的个数。Ｐｒ［ｉ ］表示系统处于状态ｉ的稳定概率。 表示处理机平均利用率，Ｓ表示年有状态的集合。 如图２的ＭＣ，假如取值 四、随机 网的问题与发展 随机 网与排队论相比较没有非乘积解的困扰，而且具有并行、不确定性、异步描 述能力和分析能力等优点。求解随机网与求解相同构的马尔可夫随机过程的复杂性是相同 的。但是随机网提供了可视描述功能和系统动态活动描述功能，便于人们理解和交流，为 系统的性能评价提供了友好的界面。 随机网面临的主要问题是其状态空间会随着问题的增大而呈指数性地增长，甚至使其 同构的ＭＣ求解变为不可能。 目前，解决随机网的状态爆炸问题可有如下三种方法：寻找抽象力更强的新型随机网 ；提供随机网模型结构分解、化简和性能等效替代的方法；计算机辅助随机网软件和计算 工具。 ＧＳＰＮ和ＳＨＬＰＮ等的提出和发展就是为缓解状态爆炸而提供的新型随机网。Ｇ ＳＰＮ是ＳＰＮ的一种扩充。它将变迁分为两类：一类为瞬时变迁实施延时为零／另一类 为时间变迁与指数随机分布的实施延时相关联。瞬时变迁描述系统操作之间的逻辑关系， 时间变迁描述系统操作处理。另外，在可发生的变迁中，瞬时变迁具有实施优先权。这种 优先权可造成可达集状态的减少。瞬时变迁的存在可将系统状态空间分为消失状态集和实 存状态集。进一步可将消失状态移出，只剩下实存状态，就可定义一个压缩的可嵌入ＭＣ 。通过这种手段，可以进一步简化状态空间。ＧＳＰＮ简化了状态空间，但是瞬时变迁随 机开关的确定、消失状态的移出和压缩的可嵌ＭＣ的计算也要给状态稳定概率的求解带来 一些额外的计算，而且有进使ＧＳＰＮ模型的可读性也受到了某种伤害。 既要简化系统的状态空间，又要保持良好的模型特性和模型的可读性，正是提出ＳＨ ＬＰＮ的基本思路。ＳＨＬＰＮ出发点是把指数分布的变迁实施时间变量引入到高级Ｐｅ ｔｒｉ网的变迁集，使之既继承高级Ｐｅｔｒｉ网在描述和分析方面原有的特点和性质， 又具有ＳＰＮ的状态空间与提供强有力的数学基础。更重要的是在ＳＨＬＰＮ中，不但保 持了高级Ｐｅｔｒｉ网将多个同结构子系统压缩成一个子系统的特点，而且进一步引入了 托肯类型和托肯变量的概念，将同类托具形成的具有等价意义的多个标识用一个标识变量 表示，显著地减小了系统的状态空间。具有标训变量的ＳＨＬＰＮ达到了形式描述紧凑和 状态简化的和谐统一。 从ＳＰＮ到ＳＨＬＰＮ，主要是从标识语义的表达上寻找更有抽象能力的性能模能模 型描述工具。如何从图形语法上或网的结构上寻找分解和简化网复杂性的方法，是网分析 方法的重要内容。在随机网中的分解和合并，主要着眼于系统模型性能一致性的保持。系 统模型的性能影响主要体现在系统的操作及操作与资源环境的关系上。模型中的操作又分 为串行操作和并行操作，操作之间的关系又可分为异步操作和同步操作。如果能对这些操 作之间的关系进行分解和使性能影响近似等效，就可能将系统模型分解为多个独立的子模 型，分别进行性能评价，达到缓解系统模型状态指数性增长的问题。目前，作者可以提供 帮种模型结构的分解和性近似等效的计算方法：层次模型和分层性能评价；互斥结构的分 解和性能近似等效计算；多路选择结构的分解和托肯流路的性能评价。 随机网辅助分析计算机软件是随机网研究和实际应用必不可少的工具。目前，已有Ｓ ＰＮ和ＧＳＰＮ等机网软件商品在市场上销售，还有十几种随机网软件包可由科研单位和 大学提供。随着计算机存储和计算能力的不断扩大，随机网软件能计算的问题的机械也会 不断地扩大。尤其是随机网并行分析算法的提出和求解，更加扩充了辅助分析软件的能力 。 目前，随机网的研究热点仍然是解决状态空间爆炸问题。基中重点是寻找随机网结构 分解和性能近似等计算的方法、性能模型瓶颈和性能近似等效计算的方法、性能网和排队 论模型有机结合及理论方法的衔接等。 （计算机世界报 1994年 第27期） |
周报全文频道联系方式：010-68130909 |
||||||
| 【关于我们】 【广告服务】 【周报发行】 【投稿指南】 【投稿声明】 【联系方式】 【法律声明】 【媒体手册】 【编读往来】 |
||||||
| Copyright© ccw.com.cn,All rights reserved | ||||||
| 中国计算机世界出版服务公司版权所有 | ||||||