性能评价技术的研究与应用

性能评价技术的研究与应用

性能评估（pe）是计算机网络和计算机科学研究和应用的重要理论和技术支持。它是通信和计算机科学领域的研究方向。这也是一个理论和实践紧密相连、内容丰富、体系完整的学科。它主要对系统的动态行为进行分析和评价,包括对实际系统的行为进行测量和建模、按照一定的性能要求对方案进行选择、对现有系统的性能缺陷和瓶颈进行改进、对未来系统的性能进行预测,以及在保证一定服务质量的前提下进行设计。现在PE技术已经被广泛用于计算机和通信领域中。随机Petri网(stochasticPetrinet,SPN)方法为系统的性能评价提供了新的、有效的途径。SPN是图形的、数学的模型,可以作为分析的工具,已广泛应用于计算机科学、通信网络和管理与控制等领域。SPN的随机、异步、并行、并发、优先化、资源共享等描述特性和模型分解、压缩技术更适合于系统资源管理、任务调度方案和模型的研究。本文主要基于随机Petri网模型对系统的性能进行讨论,总结了作者近年来在这个领域的研究成果,并指出进一步的研究方向。1理论创新1.1elpn模型技术随互联网应用的发展,Web服务器集群系统在互联网上得到了广泛的应用。作者在多年研究多服务器多队列系统模型和性能分析的基础上,提出了一类多服务器多队列网络(multiservermultiqueuenetwork,MSMQN)模型,利用随机高级Petri网(stochastichigh-levelPetrinets,SHLPNs)模型技术为一类多服务器多队列网络问题的模型和性能求解提供新的、有效的途径。SHLPN是林闯在国际上首先提出的一种高级Petri网(HLPN),已经得到了国际上的认可,并广泛地应用于计算机科学、通信网络和管理与控制等领域的系统模型和性能分析。在MSMQN模型中,网络的每一个站点由一个多服务器多队列系统构成,来自外部的用户(请求)可能被传送到任何一个站点、进入一个队列得到服务。在服务后,服务结果的响应文件返回用户。在这个网络性能模型中,可以包括动态站点选择算法、动态请求分配算法和加权优先请求调度算法,这些算法可以一致地综合在SHLPN模型中,并且能够获得请求花费在网络中延时和用户所经历的响应时间等性能分析和评价指标。多服务器多队列网络模型的应用是当前研究热点,有很多问题需要解决,模型的性能分析仍是一个开放问题。我们将继续研究和比较多服务器多队列网络用户要求的控制方案、算法及其性能评价,特别是模型综合方案的性能评价和满足服务质量(QoS)的策略等问题。1.2局部平衡的方法一些研究者在SPN中引入乘积形式解(product-formsolution,PFS,简称乘积解)的概念,将SPN的求解表达为每一个位置项的乘积形式,并且提出了几种判别和研究具有PFS的SPN的方法。例如,Lazar等提出了基于SPN可达图特殊结构存在的检测方法;Henderson等提出了基于SPN网结构的分析给出某些判定条件的方法;Donatelli等对这两种方法进行了比较,并把它们统一到同一结构上。我们在SPN中引入站平衡(stationbalance)的概念,利用站平衡来判断SPN模型是否具有PFS,即对于一个由站(一个或多个)组成的服务系统,其SPN模型具有PFS当且仅当模型中所有的站在所有可能状态下都是平衡的。这种方法的特点是基于对模型的结构和语义的分析来判断模型是否具有PFS。应用这种方法,发现了3类有可能导致站不平衡的模型结构:有限容量位置结构、冲突结构以及同步冲突结构,从语义上分别对这些结构进行了分析,得出了产生非PFS的模型原因,即有限的被动资源、基于系统队列状态的调度策略以及基于系统队列状态的共享资源分配策略。在此基础上,讨论了PFS与非PFS的关系,即乘积解是非乘积解的界限,为快速获取非乘积解系统的性能界限提供了一种方法。对于不具有PFS的SPN模型,可利用PFS方法来求解其性能界限。这种利用PFS求解非PFS系统模型性能界限的方法在QN中有人采用过,我们将其引入SPN中。这种界限方法的特点是从分析系统模型的局部平衡入手,分析非PFS系统不满足局部平衡的原因,进而从结构和语义上对模型进行修改,使修改后的模型具有PFS,通过求解修改后的模型来快速获取原模型的性能界限。这种方法的优点是充分利用了SPN的变迁实施条件谓词来刻划模型的修改,使得应用更加简便而且有效。1.3基于随机petri网的多阵列系统模型分解方法已有的SPN的分解和压缩技术包括:时间数量级分解、接近无关分解、响应时间保留压缩、流等价压缩、层次模型以及分层分析和乘积形式解。虽然这些技术可以在一些类型的SPN模型中解决状态空间爆炸问题,但是到目前为止,还没有一种技术或者多种技术结合起来可以提供所有类型的SPN模型的分解和压缩方法。任意网络结构是难分解和性能等效压缩的,也不可能存在着单一的技术可用于任何类型SPN的分解和压缩。针对多队列系统模型,我们提出一种适合这类模型结构特点的分解和近似求解方法。这里讨论的多队列系统模型的结构特点是:组成模型的基本结构单位是队列,各队列之间是速率相关的。这类模型由于各队列之间存有相互影响,因而会产生非乘积解,当模型规模较大时很难精确求解。这时,可以考虑先对模型进行分解,将多队列模型分解成由单个队列组成的子模型,而单个队列的模型具有乘积形式解,也就是说,将多队列模型分解成具有乘积解的子模型,然后迭代求解各子模型得到原模型的近似解。我们基于随机Petri网研究了非乘积解多队列系统模型的近似求解问题。为解决模型的状态空间爆炸问题,提出了一种适用于这类模型的近似性能分析方法。为简化模型结构,给出了一种新的模型设计技术。应用这种近似求解方法可以显著地简化模型求解的复杂性,并且近似结果具有足够的精确性。今后,将进一步对更多、更复杂系统的近似求解开展研究。1.4基于模型的随机petri网模型求解技术网络系统业务的自相似模型及其性能评价是目前计算机网络研究面临的重要挑战。自相似的概念与分形和混沌理论有关,问题相对比较复杂。对于网络的自相似研究,大量的问题有待解决。主要的困难在于传统的排队模型基本上是在短相关的假定下研究队列性能,但是,排队理论对分析自相似性这种具有复杂长范围相关(long-rangedependence,LRD)的排队问题则无能为力,目前,还没有一套完整的技术能够解决长范围相关队列的性能分析与评价。因此,网络的自相似问题是当今网络研究公认的热点和难点。基于Andersen和Nielsen提出的使用Markov方法对具有LRD特性的分组传输进行建模和分析的方法,利用SPN模型技术为网络自相似业务到达过程的模型和求解提供一个新的、有效的途径,即通过多个两状态的MMPP模型的叠加从而实现在多个时间尺度上近似逼近具有LRD特性的自相似分组传输,提出自相似业务到达过程的随机Petri网模型。为了解决模型求解中的状态空间爆炸问题,采用了一种基于模型分解和迭代的近似性能分析技术以简化模型求解的复杂性。我们的模型方法和近似分析技术可以有效地应用于自相似到达条件下的Web服务器集群系统的性能分析,并可以显著地简化模型求解的复杂性。这种方法的一个不足在于服务器服务时间假定服从指数分布,更合理的假设应为重尾分布,还需要进一步研究。2模型改进2.1模型精化技术SPN的模型技术有多种不同的方法,简单地使用模型技术去模拟复杂的系统,势必造成状态空间爆炸,而无法分析系统性能。模型精化技术可以开发出紧凑的模型,暴露出原模型中子模型的独立性和相互依存关系,为模型的分解求解奠定基础。我们在精化设计中充分利用了SPN的模型特性,即变迁的实施条件谓词和实施概率等来描述各子模型之间的相互关系。一般地,对一个给定的多队列系统的SPN模型A进行精化设计需分如下2步进行:1模型a的简化主要是删除A中的瞬时变迁以时间变迁来代替,同时删除A中的消失位置,得到一个与之标记流等价的SPN模型。2spn模型精化设计的优点瞬时变迁的实施条件谓词和实施概率分别与原时间变迁的实施条件谓词和实施速率相结合,使得两模型对应的Markov链相同。删除瞬时变迁和消失位置的目的是从结构上切断各队列之间的相互联系,暴露出原模型中各队列的独立性,使模型结构简化便于分解。确定新添时间变迁的实施条件谓词和实施速率,把各队列之间的相互关系描述在变迁的实施条件谓词和实施速率中,保证分解后的模型与原模型对应的Markov链相同,同时也确定了迭代求解中各子模型之间的输入、输出关系。我们提出的SPN模型精化设计主要优点如下:1)简化了模型结构的描述,使模型易设计,好理解;2)清楚地暴露子模型的不相关性,为模型的分解和分析提供了基础;3)减少了系统的状态空间,主要删除了不必要的消失状态;4)由于子模型的相似性,可以显著简化模型设计和编程求解的工作量。利用SPN模型的特点来研究随机网紧凑模型和等价模型设计是一个新的和重要的研究领域,但是目前仍有许多理论和方法问题值得研究。2.2模型的基本思想MatthiasBecker和HelenaSzczerbicka曾经将排队网和随机Petri网结合起来,提出了一种称作PniQ(Petrinetsincludingqueuingnetworks)的模型。在此基础上,我们提出了NM-QPN(含有非Markov过程的排队Petri网,queuingPetrinetincludingnon-Markovianprocesses)模型,对排队网、随机Petri网和非Markov过程三者进行了有机结合,并提供了一套完整的自底向上的近似求解方法。因为SPN模型的分析求解和模拟求解各有优缺点,再加上排队网络对某些系统建模的方便性,我们考虑将这三者结合到一起,取长补短发挥各自的优点。首先,对于要建模的系统中那些便于用排队网进行建模的部分,特别是有乘积形式解的部分,可以利用排队网络来建模。这样做的好处是:建模和求解相对简单,在有乘积形式解的情况下更是有利于解决状态空间爆炸的问题。然后,把系统中那些服从(或近似服从)指数分布的部分用广义随机Petri网GSPN进行建模。最后,剩下的那些非Markov过程的部分用含有一般分布的Petri网来建模。NM-QPN继承并发展了Petri网和排队网图形化模型的优点,能够方便地对复杂模型建模;我们提出的化简以及求解技术可以使得模型的状态空间大大减少,而且这些化简方法在GSPN以及排队网模型中也是适用的。对模型的等效化简以及对非Markov过程的研究都是尚待探讨的问题。3应用扩展3.1工作流模型的建立近几年,工作流技术的研究和应用已引起了研究人员、开发人员和用户的普遍关注。我们最近提出了一种新的方法研究工作流系统,即根据基于随机Petri网的工作流模型的顺序、并行、选择、循环这4种基本结构,推导出由任意多个变迁组成的串联、并联、选择和循环结构的性能等价公式,用所得公式可以对复杂的系统进行等价化简,最终求出工作流的性能参数。这种性能等价分析技术不仅能够极大地简化模型的分析求解过程和复杂性,而且还可以得到性能参数的精确解,此技术除了可以应用到工作流系统中,而且还可以广泛应用于诸如多媒体系统、计算机网络等模型的性能分析中。3.2petri网模型目前已有一些方法分析给定的一个网络系统或调度策略是否稳定。我们使用Petri网模型来模拟具有缓冲优先调度的系统。Petri网是描述优先调度、不确定性、并行和异步操作的有效模型工具。另外,Petri网模型可以直观显示系统的正反馈结构,它是造成不稳定的主要因素。我们推导了基本随机Petri网结构的稳定特性,即当一个系统是不稳定时,至少存在一个缓冲,它所包含的标记是无界的。利用这个特性,推导了有直接正反馈环和正反馈环系统稳定的充分条件。这些研究结果可以用于多种实际系统的稳定性分析。多种、复杂系统的控制、调度策略的稳定性是进一步的研究方向。3.3扩展时段时序推理机制扩展时段时序逻辑的提出更增强了模型描述的直观性和分析问题的能力,使模型更加完善。它的最大优势在于很好地描述了行为的持续时间段不确定的情况。我们在扩展时段时序逻辑的基础上提出的这种推理机制基于随机Petri网模型及基本不等式规则,可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系。对不确定时间段内发生的事件及其相互关系具有较好的描述能力。这种推理机制的优势在于定性地对扩展时段之间的时序关系进行推理分析。利用随机Petri网模型,可以对复杂时序逻辑关系进行化简,比单纯利用不等式规则的推理更直观,也更简单,是一种行之有效的方法。4主要研究进展本文综述了作者近期在清华大学信息学院“九八五”基础创新研究基金的资助下的研究成果,涉及多服务器多队列网络的模型和性能分析、SPN非乘积解系统的判定与界限求解、非乘积解系统模型的分解和近似求解、网络系统自相似业务到达的SPN模型及其性能评价、SPN模型的精化设计、含有非Markov过程的排队Petri网模型和性能分析、基于SPN的工作流系统模型的性能等价分析、基于SPN模型的缓冲优先调度策略稳定性分析、扩展时段时序逻辑的推理机制等方面。这些理论、模型以及应用等方面所取得的研究成果,对SPN领域的研究起到了一定的引导作用,同时也丰富了计算机网络和计算机系统性能评价的理论、方法、模型和技术。我们基于随机Petri网进行系统性能评价虽然取得了不少进展,但目前还有很多问题尚待解决,以下研究内容是进一步的工作重点:1)加强对非Markov