没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记164(2006)27-43www.elsevier.com/locate/entcs以业绩为导向的业绩衡量指标的具体Alessandro Aldini1 Marco Bernardo2Universit`diUrbino摘要系统性能建模的正式符号需要配备合适的符号来指定性能度量。这些伴随符号传统上基于奖励结构,最近则基于时序逻辑。在本文中,我们提出了一种混合的方法,其目的是通过允许设计人员以面向组件的方式表达它们来促进性能指标的规范化。由此产生的测量规范语言MSL,这是集成在martamilia/TwoTowers,被解释为行动标记的连续时间马尔可夫链和随机过程代数。后一种解释提供了一个组成框架的性能敏感的模型操作,并强调增加的表现力相对于传统的奖励结构的建模符号,其中状态的概念是隐含的。关键词:进程代数,连续时间马尔可夫链,奖励结构,一阶逻辑,性能评估1引言在系统设计的早期阶段,需要评估系统的定量特征,这在学术界促进了将传统的功能方面与性能方面相结合的正式方法的发展。这导致了不同的系统建模符号,具有互补的优点和缺点,其中我们提到随机过程代数(SPA:参见,例如,[14,13,7]以及其中的参考文献)和随机Petri网(SPN:参见,例如,[2]和其中的参考文献)。SPA和SPN都配备了精确定义的语义和分析技术,在性能评估的情况下从可用性的角度来看,上面的建模符号迫使系统设计人员熟悉它们的技术细节,其中一些并不容易1 电子邮件地址:aldini@sti.uniurb.it2 电子邮件地址:bernardo@sti.uniurb.it1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.07.01028A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27要学习.此外,这样的符号不支持建模系统的完全阐明的面向组件的方式,这在处理由许多交互部分组成的复杂系统时特别期望。这个可用性问题最近已经通过EMPAmilia [8,5]的开发得到了解决,EMPAmilia是一种基于EMPAgr[7]的架构描述语言,用于系统家族的文本和图形表示。算法清楚地将系统行为的规范与系统拓扑的规范分开,从而隐藏了SPA的静态运算符的许多技术细节。这是通过将一种植物规格分为两部分来实现的。在第一部分中,设计者通过SPA方程(其中只有更容易的动态算子才能出现)定义了构成系统的组件类型的行为,以及它们与系统其余部分的相互作用。在第二部分中,设计者声明了系统中存在的先前定义的组件类型的实例,以及它们相互连接的方式,以便使组件进行通信。出于性能评估的目的,前面提到的建模符号根据[18,12]中提出的分类,我们有瞬时度量,表示在特定时刻收到的收益/损失,以及时间间隔(或累积)度量,表示在某个时间间隔内收到的总体收益/损失。这两种测量都可以指稳态或瞬态。文献中出现的大多数用于表达各种绩效指标的方法都是基于对系统模型底层CTMC的奖励结构的定义[15]在SPA和SPN等建模符号的框架中,我们的想法是奖励结构不应该在CTMC状态和转换的级别上定义,而是在系统模型的级别上定义,然后由其底层CTMC自动继承。在SPN的情况下,奖励可以自然地与净标记和净转换/活动相关联[9,17]。在SPA的情况下,奖励关联更难,因为建模符号是基于动作的,因此状态的概念是隐式的。在[10,11]中,通过适当的模态逻辑公式挑出必须附加某些奖励的CTMC状态,而在[7,6]中,奖励直接在系统规范中发生的动作中指定,然后在CTMC构造期间转移到CTMC状态和过渡。相反,在[20]中,引入了时间奖励公式,它能够表达CTMC状态序列上的累积原子奖励,并允许通过计算长期平均值的技术来评估性能度量最后,一种不同的、基于非奖励的方法依赖于分支时间时序逻辑CSL [3],该逻辑用于直接指定性能度量并将性能评估减少到模型检查。基于时间的进展可以被视为奖励的获得,在[4]中随后提出了CSL的一个变体,称为CRL,其中假设奖励已经附着在CTMC状态上。性能建模符号的可用性问题显然扩展了A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2729到用于表示性能度量的伴随符号特别是,我们观察到,上述调查的建议都不允许设计师以面向组件的方式指定性能度量,这再次是非常可取的。从设计者的角度来看,即使使用像Cummilia这样的面向组件的建模符号,如果伴随着一个辅助符号,其中性能度量的规范并不容易,那么也可能是不充分的。这是在拉奎拉大学对一些研究生和本科生进行的可用性相关实验的结果。这些学生熟悉软件工程的概念和方法,但不熟悉SPA等正式方法,他们以前接触过SPA以及[6]中提出的基于奖励的伴随符号,然后他们接触过Approximilia以及相同的伴随符号。在这个过程的最后,在建模方面,学生们对他们想要建立的通信的正确性感到更加自信另一方面,他们仍然抱怨用符号来指定性能度量的困难,这迫使他们根据状态和转换而不是组件进行推理。最重要的是,他们认为度量的定义是性能专家的一项任务,因为对他们来说,决定使用哪种类型和值的奖励,以获得甚至简单的指标,如系统吞吐量或资源利用率,这一点并不简单虽然选择适当的奖励值的困难是一个内在的限制基于奖励的方法来指定的性能指标,在本文中,我们声称,一个显着的改进,这种方法的可用性可以通过结合的想法,从行动为基础的方法和逻辑为基础的方法在一个面向组件的方法。更具体地说,我们将提出一种建立在简单的一阶逻辑基础上的度量规范语言(MSL),通过这种逻辑,奖励被附加到CTMC底层面向组件的系统模型的状态和转换上一方面,当使用像SPA这样的建模符号时,这种依赖于奖励和逻辑结构的集成方法比经典的基于奖励的方法更具表现力,其中状态的概念是隐含的。另一方面,在MSL中,面向组件是通过一种机制来实现的,该机制定义了相对于单个组件或其行为的特定部分可以执行的活动而参数化的度量本文的另一个贡献是提供了一个解释的MSL的核心逻辑的基础上SPA,它允许性能敏感的组合推理。本文的其余部分组织如下。在第2节中,我们回顾了一些关于面向组件的系统建模、动作标记CTMC和奖励结构的背景知识。在第3节中,我们通过定义其核心逻辑及其CTMC解释来介绍MSL。在第四节中,我们介绍了测量定义机制,30A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27与MSL相关的Nism。在第五节中,我们对MSL的核心逻辑最后,在Sect。6.最后,我们报告了对今后工作的一些看法2把所述语境我们在本文中提出的性能度量的规范化的正式方法是为面向组件的系统模型设想的,其底层随机过程是动作标记的CTMC。2.1面向代理的系统模型根据[1]中提出的指导原则,面向组件系统的形式化模型至少应该包括两部分:单个系统组件类型的描述和整个系统拓扑结构的描述。系统组件类型的描述应该至少通过指定其名称、其(与数据相关和与性能相关的)参数、其行为和其交互来提供 行为应该表达组件类型可以执行的所有可选活动序列,而交互是在行为中发生的那些活动,这些活动由组件类型用于与系统的其余部分进行通信。交互可以用表示其属性的限定词来注释,例如,方向(输入与输出)或形式(点对点、广播、客户端-服务器等)他们可以参与的交流。系统拓扑结构的描述应该通过声明组成系统的组件类型的实例来提供,同时说明它们的交互应该如何相互连接,以便使组件进行通信。如果交互用限定词注释,则附件应与它们一致然后,拓扑的描述应该通过作为整个系统的接口的组件交互的可能指示来完成,这对于支持分层建模是有用的。下面我们考虑一个到达率λ∈R>0,无缓冲器,服务率μ1,μ2∈R>0 的排队系统M/M/2[16]。该系统表示配备有分别以速率μ1和μ2处理请求的两个服务器的服务中心服务提供给无限的客户群体,其根据速率为λ的泊松过程到达服务中心。当两个服务器都空闲时,进入的客户有相同的概率被两个服务器服务。因此,整个系统包括两个组件类型:到达过程和服务器。在体系结构描述语言Rumilia [8]的框架中,这样的组件类型将被建模如下:ARCHI_TYPE QS_M_M_2(速率lambda、速率mu1、速率mu2)[3]这个通用框架允许分支时间和线性时间模型,并包括不同的形式主义,如进程代数和Petri网。A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2731ARCHI_ELEM_TYPESELEM_TYPE到达_类型(到达_率)行为到达(无效)=. Arrivals()INPUT INTERACTIONSvoid输出交互或到达ELEM_TYPE服务器类型(速率service_rate)行为Server_Idle(void)为<到达,_>。Server_Busy();Server_Busy(void)=. Server_Idle()INPUT INTERACTIONS UNI到达输出交互无效系统拓扑结构包括到达类型的一个实例和服务器类型的两个实例,它们适当地彼此连接,如下面在图1中所建模的:ARCHI_TOPOLOGYARCHI_ELEM_pathologiesArr: Arrivals_Type(lambda); S1:Server_Type(mu1);S2:Server_Type(mu2);ARCHI_互动voidARCHI_ATTACHMENTSFromArr.arrive TOS1.arrive;FromArr.arrive TOS2.arrive端2.2ACTMC和奖励结构出于性能评估的目的,我们假设从所考虑的面向组件的系统模型中可以提取有限状态、有限分支、动作标记的CTMC。定义2.1有限动作标记CTMC(ACTMC)是一个四重M=(S,Act,−→M,s0)其中S是一个有限的状态集,s0∈S是初始状态,Act是一个非空的活动集,而−→M<$S×(Act×R>0)×S是一个有限的转移关系。从面向组件的系统模型中获得的ACTMC的每个状态实际上是表示系统配置的全局状态,可以将其视为局部状态的向量,这些状态是各个组件的当前行为每个转换对应于由单个32A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27到达S1.Server_BusyS2.Server_Busy到达S1.Server_IdleS2.Server_Busy到达S1.Server_BusyS2.Server_Idle组件,或者由几个通信组件同时执行的一组附加交互。作为一个例子,图1显示了在第2.1节中使用Escherichia建模的嵌入系统的ACTMC。到达,到达,到达S1.serve,服务器S2.serve,服务器S2.serve,服务器S1.serve,服务器到达,到达,到达Fig. 1. ACTMC模型的装配系统实例就基于ACTMC、面向组件的模型的分析而言,绩效衡量规范的典型方法依赖于奖励结构[15]。这需要将实数与系统行为和活动相关联,然后将其分别转移到ACTMC的适当状态(速率奖励)和过渡(瞬时奖励)。速率奖励表示在相关状态逗留期间积累收益(或损失,如果数字为负)的速率。相比之下,即时奖励指定了执行相关转换所隐含的即时收益(或损失)。通过奖励策略指定的绩效度量的瞬时值可根据以下等式计算:ACTMCM=(S,Act,−−→M,s0)t:(一)Σ ΣRr(s)·π(s)+Ri(s,a,λ,SJ)·φ(s,a,λ,SJ)s∈ S(s,a,λ,sJ)∈−−→M其中:• Rr(s)是与s相关联的速率奖励。• π(s)是在所考虑的时刻处于s中的概率。• Ri(s,a,λ,sJ)是与转换(s,a,λ,sJ)相关联的瞬时奖励• φ(s,a,λ,sJ)是在所考虑的时刻的跃迁(s,a,λ,sJ)的频率,其由π(s)·λ给出。例如,假设在调度系统示例中,我们对计算吞吐量和利用率感兴趣。系统吞吐量被定义为每个时间单位服务的客户的平均数量。为了计算它,我们应该设置:到达S1.Server_IdleS2.Server_IdleA. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2733⎪⎧如果s =(Arr. 到达,S1。服务器忙,S2。服务器空闲)⎪(Arr. 到达,S1。服务器空闲,S2。服务器总线y)Rr(s)=如果s =(Arr. 到达,S1。服务器忙,S2。服务器忙)ifs=(Arr. 到达,S1。服务器空闲,S2。服务器空闲)等价地,我们可以设置 Ri(,a,,)= 1,对于a∈ {S1. 发球S2serve}和对于a ∈{ arrive },Ri(,a,,)= 0。相反,系统利用率被定义为至少一台服务器繁忙的时间百分比为了计算它,我们应该设置Rr(s)= 1,如果s包含S1之间的至少一个作为局部状态。服务器繁忙和S2。服务器忙,否则Rr(s)= 0。3MSL:核心逻辑和ACTMC解释MSL基于将奖励与ACTMC底层面向组件的系统模型相关联的核心逻辑。核心逻辑反过来又基于一组第一-或者,当在ACTMCM=(S,Act,−−→M,s0)中存在所有不确定性时,其可以在关于活动集ACTAct的量化范围内。为了达到令人满意的表达程度,核心逻辑中至少需要四个公式模式。一方面,必须允许设计者决定是否需要状态奖励或过渡奖励来定义某个性能度量。 另一方面,在一个基于行动的设置,设计者必须被允许决定是否在一个给定的集合中的所有活动有助于某个性能指标的值,或只有其中之一两组两个选项的组合产生了四种可能性,可供设计师使用。定义3.1MSL的核心逻辑是由以下四个公式模式组成的一阶逻辑:(i) ∀a∈A(is trans(s, a, λ, sJ)⇒eq(partial contrib(s,a,λ,sJ),rew(a,λ))eq(state rew(s),sum partial contrib(s,A))(ii) <$a∈A(is transs(s,a,λ,sJ)<$eq(transrew(s,a,λ,sJ),rew(a,λ)(iii) ∃a∈A(is trans(s, a, λ, sJ))⇒eq(state rew(s),choose state rew(s,A,cf))(iv) ∃a∈A(is trans(s, a, λ, sJ))⇒eq(transrew(choose transs(s,A,cf)),choose transrew(s,A,cf))由于它们最初的量化,我们称前两个公式模式为泛公式,后两个公式模式为存在公式。直观地说,第一个通用公式模式建立了所有用活动a∈A标记的转换偏离M的当前状态的值提供值rew(a,λ)的贡献34A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27在这种状态下获得奖励的速率。 由于几个有贡献的跃迁可能偏离当前状态,我们假设它们的所有部分贡献必须相加(部分贡献可加性假设)。 第二个通用公式模式建立了所有的transi-用活动a∈A标记的行动获得值rew(a,λ)的瞬时奖励无论何时被处决。在调度系统示例中,系统吞吐量可以通过类型(i)的公式来指定,其中:A={S1. 发球S2serve},rew(S1. serve,)= μ1,rew(S2. serve,)=μ2S1单独的吞吐量仍然可以通过类型(i)的公式来指定,其中:A={S1. serve},rew(S1. serve,)=μ1最后,系统吞吐量可以通过类型(ii)的公式来指定,其中:A={S1. 发球S2serve},rew(S1. serve,)= rew(S2. = 1第一个存在公式模式确定,如果M的当前状态可以执行至少一个标记为活动a∈A的转换,则它在停留在那里的同时对奖励累积的速率做出贡献。这种贡献的值必须通过将选择函数cf应用于与偏离当前状态的活动a∈A标记的所有转换相关联的奖励rew(a,λ)来选择。 通过选择函数,我们意味着一个函数,简单地返回它的参数之一,例如max和min。第二个存在公式模式建立了只有一个标记有活动a∈A,离开M的当前状态,在执行时获得即时奖励。这样的转移是通过选择函数cf来选择的,该选择函数cf考虑了标记转移的活动a∈A的回报rew(a,λ偏离当前状态的频率乘以跃迁频率。在调度系统示例中,系统利用率可以通过类型(iii)的公式来指定,其中:A={S1. 发球S2serve},rew(S1. serve,)= rew(S2. 服务,)= 1,cf= minS1的单独利用仍然可以通过类型(iii)的公式来指定,其中:A={S1. serve},rew(S1. 服务,)= 1,cf = min最后,实际到达率可以通过类型(iv)的公式来指定,其中:A={arrive},rew(arrive,)=1,cf=min为了形式化MSL的核心逻辑的语义,我们现在提供下面的基于ACTMC的对出现在Def中的语法谓词和函数的解释。3.1:• 是transS×Act×R>0×Ssucthat:<$1如果(s,a,λ,sJ)∈−−→M是transs(s,a,λ,sJ)=0.00否则• 等式R×R使得:A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2735⎧如果x=y,则为 1eq(x,y)=0.00否则• rew:A×R>0→R使得rew(a,λ)是活动a∈A在标记速率为λ∈R>0的转移时给出的奖励贡献。• 状态rew:S→R,使得状态rew(s)是在状态s时获得奖励的速率。• transrew:−→M−→oR su ch atransrew(s,a,λ,sJ)是一种新的奖励,它是每次执行转换(s,a,λ,sJ)时获得的奖励。• partialcont ri b:−→M−o→R su c hh atpartialcont rib(s,a,λ,sJ)是转移(s,a,λ,sJ)对在s处获得状态奖励的速率的p a r t i a l贡献。• 求和部分贡献:S× {A}→R,使得:Σsum partial contrib(s,A)=n-部分贡献(s,a,λ,sJ)a∈A(s,a,λ,sJ)∈−−→M其中,当s不能执行标记为a∈A的转换时,和为0。• 选择状态rew:S× {A}×CF→R,使得:选择状态rew(s,A,cf)=联系我们|rew(a,λ)|a ∈ A sJ∈ S. 是transs(s,a,λ,sJ)|}其中CF={f:2R→R |f(n)=0n∈N>0. f({x1, . . ,xn})∈{x1, . . ,xn}}是选择函数的集合。• choosetrans:S×{A} ×CF−o→−−→Msuc hthat:choose transs(s,A,cf)=(s,a,λ,sJ)我说:rew(a,λ)·φ(s,a,λ,sJ)=联系我们|rew(b,μ)·φ(z,b,μ,zJ)|b ∈ A ∈A,则是transs(z,b,μ,zJ)|}• choosetrew:S×{A} ×CF−o→Rsuchthat:选择transrew(s,A,cf)=rew(a,λ)我说:对于SJ∈S.choose transs(s,A,cf)=(s,a,λ,sJ)根据上述ACTMC对MSL的核心逻辑的解释,我们观察到等式(1)关于活动集合A和选择函数cf被重新表述如下:ΣΣURr(s,A)·π(s)+ΣURi(s,a,λ,sJ)·φ(s,a,λ,sJ)+(二)s∈SΣa∈A(s,a,λ,sJ)∈−−→MΣs∈ S36A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27ERr(s,A,cf)·π(s)+ERi(s,A,cf)·φ(s,A,cf)s∈SA. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2737等式(2)的每个奖励元素映射到定义3.1的相应MSL公式模式,如下所示:(i) URr(s,A)是关于A的在停留在s时累积的普遍状态奖励,其由sum partialcontrib(s,A)给出。(ii) URi(s,a,λ,sJ)是执行转换(s,a,λ,sJ)时获得的通用转换奖励等的 一∈一、 这 是 给定 通过 transrew(s,a,λ,SJ).(iii) ERr(s,A,cf)是关于A和cf的存在状态奖励,其累积而呆在s,这是给定通过选择状态rew(s,A,cf)。(iv) ERi(s,A,cf)是相对于A和cf的存在转移奖励,当执行的过渡返回通过choose transs(s,A,cf),它由choose transrew(s,A,cf)给出。类似地,φ(s,A,cf)是这种转变的频率,其由下式给出:φ(选择transs(s,A,cf))。4MSL的测度定义机制MSL配备了基于其核心逻辑之上的面向组件的度量定义机制。该机制的目的与可用性问题有关。首先,该机制允许性能指标被赋予助记符名称,只要它是从通过MSL核心逻辑的一组公式模式指定的奖励结构导出的。其次,它允许性能度量相对于组件活动和组件行为进行参数化。第三,假设性能指标的标识符表示在某个ACTMC上计算的指标值,它允许通过通常的算术运算符和数学函数组合指标标识符。在MSL中定义性能度量的语法,可能是相对于一组面向组件的参数进行参数化的,如下所示MEASUREanamed(aparametersd)ISabodyd在实践中,我们可以设想处理基本测度定义和导出测度定义的库。基本度量定义的主体是MSL核心逻辑的一组公式模式。相比之下,派生度量定义的主体是一个表达式,涉及先前定义的度量的标识符(每个标识符表示在给定ACTMC上计算的相应度量的值),算术运算符和数学函数。度量标识符的参数可以包括组件活动以及组件行为以及可能关联的实数。组件活动和组件行为导致活动集出现在MSL公式模式的量化中,而实数表示MSL公式模式中活动的奖励贡献(即,它们用于定义rew函数)。使用这种机制,使用MSL可以定义典型的瞬时时间38A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27以面向组件的方式进行性能测量其思想是,度量规范的困难应该隐藏在定义体中,因此设计人员在使用度量标识符时只需提供面向组件的实际参数。为了说明这一点,我们现在考虑以下四类性能指标,它们在排队理论和实践中经常出现:系统吞吐量、资源利用率、平均队列长度和平均响应时间。一个易于使用的系统吞吐量的定义应该只要求设计者指定对吞吐量有贡献的组件活动,而统一的转换奖励在定义体中与每个这样的活动透明地关联。使用点表示法以C. a的形式表示组件活动,我们对吞吐量有以下定义MEASURE吞吐量(C1.a1,.,Cn.an)ISa∈ {C1.a1,. ..,Cn.an}必须被给予单位瞬时奖励。同样的方法来定义相同的意义,确定的是指定每个状态累积奖励的速率是在该状态下启用的对吞吐量有贡献的活动的速率之和:MEASURE吞吐量(C1.a1,.,Cn.an)ISa ∈ {C1.a1,.,Cn.an}(is transs(s,a,λ,sJ))<$eq(partial contrib(s,a,λ,sJ),rew(a,λ))<$eq(state rew(s),sum partial contrib(s,{C1.a1,. ,Cn.an})),其中rew(a,λ)= λ,每当a = Ci. ai,对于某些i = 1,. ,n.在利用资源的情况下,设计者应该足够指定对该资源的利用进行建模的组件活动,而在定义主体中,单位奖励与至少一个这样的活动被启用的每个状态透明地关联:测量利用率(C.a1,.、C.an)ISa∈ {C.a1,.,C.an}(is transs(s,a,λ,sJ))<$eq(state rew(s),选择state rew(s,{C.a1,.. ,C.an},min))其中rew(ai)= 1,每当a = C.ai,对于某些i = 1,. ,n. 根据ACTMC对MSL核心逻辑的解释,上述定义意味着每个状态启用{C.a1,.,C.an}必须被给予单位速率奖励。请注意,资源利用率是性能度量的一种特殊情况表示处于可以执行某些活动的状态的概率。平均队列长度表示等待服务的客户的平均数量,设计人员只需指定管理客户排队的组件行为的每个部分使用A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2739用C.B的形式表示组件行为部分的点表示法,我们有以下定义:测量平均队列长度(C.B1(k1),...,C.Bn(kn))IS<$a∈activities(C.B1)(is transs(s,a,λ,sJ))<$eq(state rew(s),choose state rew(s,activities(C.B1),min)).∃a∈activities(C.Bn)(is trans(s, a, λ, sJ)) ⇒eq(state rew(s),choose state rew(s,activities(C.Bn),min))其中activities是一个内置函数,用于检索行为部分可以执行,并且rew(ai)= ki,每当a∈activities(C.Bi),对于某些i = 1,.,n.根据ACTMC对MSL核心在逻辑上,上述定义意味着,包括所考虑的行为部分之一的每个状态,其中至少一个转换离开,该转换被标记为行为中发生的活动之一,必须被给予为该行为指定的数量作为速率奖励平均响应时间可以通过考虑客户的到达率λ来类似于平均队列长度来定义,这归功于利特尔这是通过将ki替换为ki/λ(i = 1,.,n.到目前为止,所有的例子都说明了基本的度量定义。导出度量的一个例子是给出了一个系统的平均队列长度,有m个排队组件C1,C2,.,Cm,其定义如下:测量总平均队列长度(C1.B1,1(k1,1),.,C1,B1,n1(k1,n1),C2.B2,1(k2,1),.,C2,B2,n2(k2,n2),.Cm.Bm,1(km,1),.,Cm.Bm,nm(km,nm))IS平均队列长度(C1,B1,1(k1,1),.,C1.B1,n1(k1,n1))+是说 队列长度(C2.B2,1(k2,1),.,C2,B2,n2(k2,n2))+.是说队列 长度(Cm.Bm,1(km,1),.,Cm.Bm,nm(km,nm))5MSL的SPA解释在本节中,我们提供了基于SPA的MSL核心逻辑的解释,旨在验证是否可以开发一个框架,在该框架中,可以在不改变MSL指定的即时性能度量值的情况下对系统模型进行组合我们还将讨论一些与MSL相对于传统语言的表现力增强有关的问题。40A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27在处理SPA等建模符号时,奖励结构,其中状态的概念是隐含的。5.1SPA与普遍和潜在的奖励为了实现组合性,我们采用了EMPAgr1 [7]的子演算,扩展了普遍和存在性奖励。在这个演算中,每个动作都是a<,λ,(uy,ub ,ey ,eb )>或,其中:• a∈Act是动作类型(如果是不可见的,则为τ• λ∈R>0表示指数时间动作的速率。• 表示具有反应权重w∈R>0的被动动作。• (uy,ub,ey,eb)是一个奖励4元组,其中如果动作是指数时间的,则每个奖励都属于R,如果动作是被动的,则每个奖励都属于R在指数时间动作的情况下,这样的奖励表示在定义3.1的四个MSL公式模式中发生的动作贡献rew(a,λ),其中普遍收益奖励uy与(i)相关,普遍奖金奖励ub与(ii)相关,存在收益奖励ey与(iii)相关,存在奖金奖励eb与(iv)相关。因此,通过相对于活动集合A量化的MSL公式模式定义的性能度量是通过将MSL公式模式中出现的奖励rew(a,λ)插入到类型在A中的指数时间动作的奖励4元组的适当位置来呈现的。为计算MSL所界定的表现计量的即时价值这意味着,当保持在某个状态时,累积奖励的总速率是与在该状态下启用的指数定时动作(其类型为A)相关联的通用收益奖励的总和。相比之下,在给定状态下同时启用的行动的存在性收益回报不能被总结,因为这将与存在性量化背后的直觉相冲突。相反,选择函数被应用于指数时间动作的存在性收益回报,其类型在A中,在该状态下被同样,在普遍和存在性奖金奖励的情况下,我们可以根据ACTMC对MSL核心逻辑的解释进行论证。这种具有普遍和存在奖励的演算的形式语法和语义是[7]中给出的语法和语义的自然扩展像往常一样,我们把自己限制在封闭和保护项的集合G上,我们用E表示G的性能封闭项的集合。5.2一致性结果我们现在证明,有可能为扩展了普遍和存在性奖励的SPA定义一个性能度量敏感的聚集这意味着A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2741−−−−−−−−−→{|·ub|−−−−−−−−−→−−−−−−−−−→−−−−−−−−−→J∈ C。EEJ|}速率(E、a、exp、C)我们可以为系统模型的组合操作提供一个正式的框架,该框架不会改变MSL中表示的性能度量的值我们将要介绍的基于奖励的马尔可夫行为等价是[6]中基于互模拟的等价的扩展本质上,这种等价集合了标记为相同类型并从相同状态出发到达相同等价类的状态的转换。更确切地说,这些转换的速率和通用收益奖励被求和,而它们的通用奖金奖励在被求和之前乘以执行相应转换的概率。存在性收益奖励和存在性奖金奖励受制于选择函数的应用,而不是加法。这样做,我们与ACTMC的解释是一致的通过等式(2)总结。定义5.1我们定义了偏函数聚合率-回报RR:G ×Act×{exp,n}×2G−o→R>0×(R<${n})4by:RR(E,a,I,C)=(速率(E,a,I,C),UY(E,a,I,C),UB(E,a,I,C),EY(E,a,l,C),EB(E,a,l,C))其中:Σ速率(E,a,exp,C)={|λ|你好,你好,你好。Ea,λ,(uy,ub,ey,eb)−−−−−−−−−→Σ速率(E,a,C)= {|W |EJa,w,(,)∈C. E−→EJ|}UY(E,a,exp,C)={|uy |λ,ub,ey,eb。 EJ∈ C。 Ea,λ,(uy,ub,ey,eb)EJ|}ΣUB(E,a,exp,C)=λ速率(E、a、exp、C)好吧,是的,EB。 EJ∈ C。 Ea,λ,(uy,ub,ey,eb)EJ|}EY(E,a,exp,C)= cf {|EY |λ,uy,ub,eb。 EJ∈ C。 Ea,λ,(uy,ub,ey,eb)EJ|}EB(E,a,exp,C)= cf {|λ·eb|别急,别急。 EJ∈ C。 Ea,λ,(uy,ub,ey,eb)EJ|}UY(E,a,n,C)=UB(E,a,n,C)=EY(E,a,n,C)=EB(E,a,n,C)=n其中cf是选择函数,RR(E,a,l,C)=0,只要上面的多集为空。定义5.2等价关系B <$G × G是一个基于报酬的马尔可夫互模拟i <$,只要(E1,E2)∈ B,则对于所有的动作类型a∈Act,水平 l∈ {exp,n},等价类C∈ G/B:RR(E1,a,l,C)=RR(E2,a,l,C)很容易看出,所有基于奖励的马尔可夫互模拟的联合是最大的基于奖励的马尔可夫互模拟。这样的联合,表示为RMBRMB,被称为基于奖励的马尔可夫双相似性。定理5.3当cf对于非负数乘法是交换的、结合的和分配的时,则cf对于所有过程代数算子和递归都是同余。42A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)27证据就比率和普遍报酬而言,证明与[6,7]的相应定理相同在存在奖励的情况下,我们可以很容易地观察到,cf所要求的性质与在使用加法算子时在泛奖励的情况下所使用的性质完全相同。Q例如,min和max是满足上述同余定理假设的选择函数。定理5.4设E1,E2∈ E.如果E1=E2,则E1和E2的基于奖励的绩效度量值相同。证据 我们可以像证明Thm那样进行类似的论证。5.3.Q5.3公理化我们现在提供了一个健全的和完整的公理化的RMBs。假设ARMB是[6]的公理集,扩展了普遍的和存在的奖励,其中表示速率和奖励的聚合的公理被改写如下:.E+.E=.Eλ1+λ2λ1+λ2.E+.E=.E请注意,这样一对公理反映了聚合利率奖励函数RR的定义(见Def.1)。5.1)。定理5.5当cf满足与Thm相同的约束时。5.3,则Ded(ARMB)对于G的非递归项集上的A RMB是可靠的和完备的.证据 我们可以像证明Thm那样进行类似的论证。5.3.Q为了在不损失一致性的情况下增强人民币的聚合力,如[6]所示,可以联合考虑普遍收益奖励和普遍奖金奖励,从而得到一种范式,其中只有使用通用收益奖励实际上,像.E+这样的公理.E=.E是正确的相反,在存在奖励的情况下,类似的公理会导致组合性的丧失。直观地说,以交错方式应用加法和选择函数并不保留性能度量的值,如下所示,在选择函数为max的情况下E =Δ。E+< a,λ2,(0,0,ey2,eb2)>. E,其中底层ACTMC具有单个状态,该单个状态具有标记为A. Aldini,M.Bernardo/Electronic Notes in Theoretical Computer Science 164(2006)2743a,其速率为λ1+λ2。然后考虑一个关于{a}存在量化的E的性能度量。这种性能度量的瞬时值由ERr(E,{a},max)+ERi(E,{a},max)= max(ey1,ey2)+max(λ1·eb1,λ2·eb2)给出相比之下,如果我们用存在产出回报来表示存在红利回报,我们得到max(ey1+λ1·eb1,ey2+λ2·eb2)。现在假设ey1= 1,ey2= 2,λ1·eb1= 2,λ2·eb2= 1。在前一种情况下,我们得到
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 探索数据转换实验平台在设备装置中的应用
- 使用git-log-to-tikz.py将Git日志转换为TIKZ图形
- 小栗子源码2.9.3版本发布
- 使用Tinder-Hack-Client实现Tinder API交互
- Android Studio新模板:个性化Material Design导航抽屉
- React API分页模块:数据获取与页面管理
- C语言实现顺序表的动态分配方法
- 光催化分解水产氢固溶体催化剂制备技术揭秘
- VS2013环境下tinyxml库的32位与64位编译指南
- 网易云歌词情感分析系统实现与架构
- React应用展示GitHub用户详细信息及项目分析
- LayUI2.1.6帮助文档API功能详解
- 全栈开发实现的chatgpt应用可打包小程序/H5/App
- C++实现顺序表的动态内存分配技术
- Java制作水果格斗游戏:策略与随机性的结合
- 基于若依框架的后台管理系统开发实例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功