基于标记令牌的自动性能分析方法

理论计算机科学电子笔记232（2009）75-88www.elsevier.com/locate/entcs基于标记令牌的广义随机Petri网以客户为中心的自动性能分析作者：Nicholas J. Dingle，William J. Knottenbelt伦敦帝国理工学院计算机系，180 Queen英国伦敦SW72BZ。{njd200，wjk}@ doc.ic.ac.uk摘要由于广义随机Petri网（GSPN）模型中的令牌是不可区分的，因此并不总是能够推理以客户为中心的性能指标。为了弥补这一点，我们提出了在这种方案下，结构受限的网络中的一个令牌被然后，性能查询可以根据标记的标记的位置来措辞。迄今为止，标记客户或代币一直是一个耗时、手动和特定于模型的过程。相比之下，我们在这里提出了一个完全自动化的方法标记的令牌分析的GSPN。我们首先描述了一种直观的图形化方法，用于指定所需的标记配置，以及对GSPN结构的约束，这些约束必须被观察以使标记的令牌被合并。然后，我们提出了将具有用户指定的标记结构的GSPN自动转换为彩色GSPN（CGSPN）所需的映射，然后转换为展开的GSPN，可以通过现有工具分析其感兴趣的性能指标我们进一步展示了我们的方法如何与性能树相结合，性能树是一种性能查询规范的形式主义。我们已经实现了我们的方法，在开源的PIPE Petri网工具，并使用此来说明额外的可表达性授予标记令牌通过分析一家医院的事故和急诊科的GSPN模型关键词：广义随机Petri网，标记令牌，性能树1介绍性能建模的形式化提供了一种方便的方法来抽象和推理复杂并发系统中的客户和资源的流程在这些形式主义中，广义随机Petri网（GSPN）[2]被广泛使用，因为它们在概念上易于理解，本质上是图形化的，并且得到大量理论和大型工具库的良好支持。GSPN的动态行为围绕着令牌1571-0661/© 2009 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2009.02.05176新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）表示系统中的客户和资源1。这些标记彼此不可区分，这意味着不可能总是从单个客户的角度来推理建模系统的性能。然而，需要这样的分析来回答诸如“在t个时间单位内为客户提供服务的概率是否大于90%”之类的问题这种性质的以客户为中心的查询非常重要，因为它们越来越多地用于许多系统中的服务水平协议（SLA），包括医疗保健系统，邮政服务和通信网络。因此，本文提出了使用这个概念是一个变体的本文的贡献有三个方面。首先，我们提出了一个直观的图形化方法的基础上的“标记弧”的概念然后，我们提出了从带有标记弧的GSPN到有色广义随机Petri网（CGSPN）的自动映射[11]。这比直接指定CGSPN更可取，因为它不需要建模者熟悉更复杂的CGSPN形式主义。最后，我们描述了一种有效的方式展开的CGSPN表示成GSPN的连续时间马尔可夫链（CTMC）可以分析的性能指标的利益，使用现有的工具。在随机Petri网（SPN）中使用标记令牌计算性能指标的先前工作是有限的。Miner [12]描述了SPN模型中响应时间的计算，其中系统中的一个实体（由多个令牌中的一个表示）被标记。这与这里介绍的工作具有完全相同的动机-即提取以客户为中心的性能指标。然而，与这里介绍的方法不同，标记过程是手动的，并且是特定于模型的。同样，以前的工作很少存在于马尔可夫模型中的标记客户分析提供工具支持。阿根廷-卡特瓦拉等al [3]提出了一种自动化的方法，通过使用随机探针跟踪性能评估过程代数（PEPA ）[9]模型中的各个实体[5]已经开发了MRMSolve 工 具 来 支 持 马 尔 可 夫 奖 励 模 型 中 的 标 记 客 户 分 析 然 而 ，MRMSolve在我们的工作中有两个局限性。首先，分析并非完全自动化，因为从嵌入模型的稳态分布到奖励模型的初始概率向量的（非平凡且依赖于模型的）映射必须手动指定。这可能需要建模者的大量专业知识。其次，MRMSolve计算所需性能度量的矩，并使用这些矩来估计实际感兴趣分布的上界和下界，而这里描述的技术可以与许多现有工具一起使用，以精确计算分布。本文的其余部分组织如下：第2节简要介绍了GSPN和CGSPN的背景理论和相关符号。第3节1以下我们仅指客户。新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）77提出了直观的图形“标记弧”机制，允许用户将标记令牌纳入现有的GSPN模型，以及必须遵守的结构限制，这样做。第4节描述了将带有标记弧的GSPN映射到CGSPN，然后第5节给出了将该CGSPN展开为标准GSPN的有效方案，该标准GSPN可以使用现有工具进行分析。 第6节展示了如何使用性能树来指定涉及标记令牌的查询，第7节演示了在医院急症室模型中分析服务质量指标时标记令牌所赋予第8节作出结论并提出今后工作的领域。2背景Petri网最初被设计为描述分布式系统中的并发和同步的图形形式主义。以最简单的形式，也被称为位置转换网[4]。广义随机Petri网（GSPN）[2]通过引入时间信息扩展了位置-变迁网。定义2.1GSPN是8元组GSPN=（P，T，T1，T2，W，I−，I+，M0），其中：• P ={p1，...，p n}是一个有限且非空的位置集合。• T={t1，...，t m}是一个有限且非空的转换集。• PT=• T1T是定时转换的集合。• T2<$T是立即转换的集合，其中T1<$T2=1且T=T1<$T2。.Σ• W=w 1，.，W|不|依赖）是一个数组，其条目wi∈R+是一个（可能标记· 当过渡ti∈T1时，指定点火延迟的负指数分布（也记为λi）的速率，或· 当ti∈T2时，• I−，I+：P×T→N0分别是后向和前向关联函数。•M0：P→N0是初始标记。GSPN的标记（或状态）是一个整数向量，表示模型每个位置上的标记数量。如果转换的输入位置至少包含由后向关联函数指定的标记数量，在触发时，根据向后和向前关联函数，从转换的输入位置中删除一些标记用M（p）表示标记M中位置p上的标记数，转移t的使能条件的形式定义为M（p）≥I−（p，t），p∈P。转换t的输入位置集（也称为t的预设），记为·t，以及t的输出位置集（或后置集），t·，定义为：78新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）•t：={p ∈ P|I−（p，t）> 0}t·：={p∈P|I+（p，t）> 0}（1）时间转移具有指数分布的触发率λi。即时转换在零时间内启动。仅启用定时转换的标记是可纠缠的，而启用任何立即转换的标记是消失的。我们用T表示有形标记的集合，用V表示消失标记的集合。由GSPN的底层可达图描述的随机过程然而，通过使用消失状态消除技术，可以将包含消失状态的GSPN的可达性图减少到CTMC。有色广义随机Petri网（CGSPNs）[11]通过将颜色作为标记扩展GSPNs。因此，一个地方的标记是一个多集合，包含每种颜色的不同数量的标记。转换具有不同的触发模式，这些模式取决于其输入位置上的标记的颜色，并在触发时改变其输入和输出位置上的多组标记这种更丰富的行为被编码在CGSPN例如，如果I-（pi，tj）（x）={a}，并且pi是转换tj的唯一输入位置，则当且仅当输入位置pi上存在一个或多个颜色a的标记时，tj才在模式x中被启用。如果tj随后以这种模式发射，则颜色a的一个令牌将从位置pi移除。相应的前向切口-模式x的dence函数I+（pk，t）（x）将指定添加到输出位置pk的多组彩色标记。标记颜色的集合由C（p）表示，过渡点火模式的集合由C（t）表示。CGSPN的启用规则是在模式cJ中启用转换当且仅当M（p）（c）≥I−（p，t）（cJ）（c），其中M（p）（c）是标记M中位置p上颜色c的记号的个数。定义2.2CGSPN是9元组CGSPN=（P，T，T1，T2，C，W，I−，I+，M0）其中[4]：• P、T、T1、T2与GSPN的定义相同。• C是一个色函数，定义为从P到有限和非空集合。• W= .Σw1，.，W|不|是一个数组，其条目wi是函数[C（ti）→R+]，这样的证明了<$cJ∈C（ti）：wi（cJ）∈R+是· （可能依赖于标记）负指数分布（也记为λi）的速率，当ti∈T1时，指定模式cJ中的点火延迟，或· （可能依赖于标记）模式cJ中的发射权重，当ti∈T2时。• I−、I+是后向和前向关联函数，使得：I−（p，t），I+（p，t）∈[C（t）→C（p）MS]，<$（p，t）∈P×T其中SMS表示集合S上的所有有限多重集的集合。• M0是定义在P上的一个函数，它描述了初始标记，使得M0（p）∈C（p）MS，其中P∈P.新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）79回顾Eq. 1中，我们将模式cJ中的转换t的预设，·（t，cJ）和后置集，（t，cJ）·定义为：•（t，c，J）：={（p，c）|p∈P，c∈C（p）：I−（p，t）（cJ）（c）> 0}（t，c，J）·：={（p，c）|p∈P，c∈C（p）：I+（p，t）（cJ）（c）> 0}3标记令牌GSPN模型(a) 原始的SPN。（b）用户标识的标记结构。图1.一、一个简单的读者-作者模型的标记版本的图形说明从第2节的描述中可以看出，传统Petri网中的令牌是易失性和非原子的;也就是说，它们通过触发转换来创建和销毁，并且不需要在触发转换后，在输出位置上存在与输入位置相同数量的令牌。这种波动性使得在有意义的情况下跟踪单个令牌在网络中的进展成为问题。因此，我们引入了“标记令牌”的概念，以允许这种跟踪。这进一步需要“标记弧”的概念作为建模者可以指定如何在网络中路由标记令牌的机制。标记弧通过添加一个小正方形“标记”与正常弧区分开来当检查是否启用了转换以及转换触发时令牌将被移除和放置的位置普通令牌可以由标记弧和普通弧两者传输。带标记的令牌作为正常令牌计数，以确定在特定标记中是否启用转换。为了推断标记弧的存在（或不存在），我们用函数A−，A+：P×T→ {0，1}扩充定义2.1。A−（p，t）= 1，如果标记的弧从位置p通向过渡t，否则为0;类似地，A+（p，t）= 1，如果标记的弧从过渡t通向位置p，否则为0图图1（a）示出了具有两个读取器和一个写入器的读取器-写入器系统的简单GSPN模型假设建模者希望从一个读者的角度来检查系统的性能这些由两个代表80新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）相同的令牌，因此不能区分，除非使用带标签的令牌。图中p0的粗边框1（b）表示该位置上的其中一个令牌被标记。然后，建模者指定通过系统的路线，读者可以通过标记适当的弧来采取，如图所示。请注意，建模者3.1结构性限制我们的方法要求GSPN中只有一个标记的令牌。广告标记的令牌不能被引入到网络中，并且唯一标记的令牌不能从网络中删除。这导致了以下（易于验证的）结构限制，建模者在将标记的弧和令牌合并到GSPN中时必须遵守这些限制：(i) 在GSPN中必须有一个标记的令牌，并且必须在网络的初始标记中指定(ii) 任何具有标记弧的输入弧的过渡都必须具有相应的输出标记弧。(iii) 一个转换必须最多有一个输出标记弧，尽管不需要对输入标记弧的数量进行限制（以便标记令牌可以通过网络经由不同的路由到达转换请注意，尽管触发带有标记的输入和输出弧的转换必须保留标记的标记，但不需要对创建设置任何限制或破坏正常代币。我们同样不对标记或未标记弧的多重性（权重）4自动CGSPN转换在用户为GSPN模型指定标记结构后，它可以自动转换为CGSPN。这允许通过使用不同的颜色将标记的标记与正常标记区分开。4.1代币颜色只有一个标记的颜色为t，表示标记的标记;所有剩余的标记都是颜色为ut，表示它们的未标记状态。因此C（p）：={t，ut}。4.2过渡击发模式存在两个对应的过渡点火模式t{t我们解释这些模式如下。在模式t在这种模式下的过渡射击也可以消耗和产生UT-彩色代币。在模式“ut新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）814.3过渡点火重量和速率可以在两种点火模式下同时启用单个转换。例如，图1（b）中的t0在t在这种情况下，触发模式是基于转换每个启用模式。具体地，模式t'和ut'中的转换tj.wj（tMaxΣI−（pi，tj）M（pi）（t）WJpi∈·tjM（pi）（t）+M（pi）（ut）wj（ut请注意，当考虑两种击发模式时，此定义保留了原始GSPN中的跃迁击发速率tj4.4发生率函数CGSPN转换的向后和向前关联函数不仅取决于网络的物理结构，还取决于其输入位置上的令牌的触发模式和由于有两种过渡模式和两种标记颜色，CGSPN因此具有四个向后和四个向前入射函数。过渡tj的后向关联函数为：⎧<$I−（pi，tj）<$pi∈·tjI−（pi，tj）（ut0.00否则I−（pi，tj）（ut ⎧<$I−（pi，tj）−M（pi）（t）<$pi∈·tjI−（pi，tj）（t0.00否则⎧1⎨∈·t jif<$pi∈·tjM（pi）（t）=0I−（pi，tj）（tM（pi）（t）<$pi∈·tjif<$pi⎪⎪∈·tj M（pi）（t）/= 00.00否则对于I−（pi，tj）（t在第一种情况下，我们设置向后关联函数，要求标记的token出现在所有输入位置上，这显然是不可能的，以确保禁用转换相应的前向入射函数为：⎪82新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）I+（pk，tj）（ut⎧<$I+（pk，tj）<$pk∈tj·0.00否则I+（pk，tj）（ut pk∈P⎧I+（pk⎨，tj）−1ifA+（pk，tj）= 1I+（pk，tj）（tI+（pk，tj）如果A+（p，t）= 0，p ∈t·I+（pk，tj）（t克jkj我在想，⎧如果A+（pk，tj）= 1，则为0.00否则5高效CGSPN分析我们希望使用现有的性能分析工具，如DNAmaca [10]和HYDROGEN [8]来分析CGSPN的稳态概率和响应时间分布等指标。虽然这些工具不是设计来直接分析CGSPN的，但CGSPN可以唯一地自动展开为适合分析的（未着色，未标记）GSPN，如下所示[4]：• p ∈ P，c ∈ C（p）创建GSPN的一个位置（p，c）。• 建立GSPN的一个变迁（t，cJ），其速率或权重为w t（cJ）.• 将GSPN的关联函数定义为：I−（（p，c）（t，cJ））：=I−（p，t）（cJ）（c）I+（（p，c）（t，cJ））：=I+（p，t）（cJ）（c）• GSPN的初始标记为：M0（p，c）：=M0（p）（c），m∈P，c∈C（p）因此，展开的GSPN由下式给出：.Σ（p，c），（t，cJ），wt（cJ），I−，I+，M0p∈Pc∈C（p）t∈TcJ∈C（t）t∈TcJ∈C（t）如果对存储器和存储器进行优化，则如果不合理地执行此展开，将导致展开的GSPN中的位置和转换数量加倍。然而，第3节中的结构限制允许我们减小展开的GSPN的大小，从而更有效地进行后续分析。特别地，由于CGSPN将仅具有一个t颜色令牌，因此我们仅需要向展开的GSPN添加单个位置，其标记表示标记的令牌当前驻留的位置的索引。因此，我们避免了名额加倍。⎪新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）83此外，那些没有标记输入和输出的转换84新泽西Dingle，W.J.Knottenbelt/Electronic Notes in Theoretical Computer Science 232（2009）弧将仅在模式ut6使用性能树的令牌管理性能树[14，15]是一种表示性能相关查询的形式.它们结合了指定性能要求（即旨在确定特定属性是否适用于系统模型的查询）和提取性能度量（即可量化的性能指标）的能力图二.性能树查询示例。性能树查询表示为由节点和互连弧组成的树结构。节点可以有两种角色：操作节点是与性能相关的功能，例如计算通过时间密度，而值节点是这些功能的输入，例如一组状态，一个动作，或者简单的数字或布尔常数。当前支持的性能分析操作节点的完整列表可以在[15]中找到。性能树支持抽象状态集指定机制，使用户能够指定与感兴趣的性能度量相关的状态。对于GSPN，可以使用形式为（M（pi）da x）的构造的合取和析取来指定一组状态，其中da∈ {≤，，=，≥，>}。图2示出了性能树的示例。 它对应于查询“Does the model transit from a state in the set 与此相关，我们必须定义状态集S1和S2;例如：S1：=（M（p1）= 2）<$（M（p2）3）

下载后可阅读完整内容，剩余1页未读，立即下载