定时MSC形式语义及应用研究：基本概念和实时系统支持

85URL：http://www.elsevier.nl/locate/entcs/volume65.html15页定时MSCTongZhenga;1;2FErhatKhendeka;1;3Lo你好b电气与计算机工程康科迪亚大学1455年由Maisonneuve W.蒙特利尔（P.Q.）加拿大H3G 1M8bIRISA/ INRIA，法国摘要消息序列图（MSC）是由ITU-T开发的图形和文本规范语言。它广泛应用于电信软件工程中，用于指定行为场景。最近，MSC'2000引入了时间概念。为了支持使用定时MSC的实时系统的规范和真实性，我们需要对其形式语义进行建模。 在本文中，我们使用定时语句作为语义模型，并给出了定时MSC的形式语义。我们首先将定时MSC中的事件作为定时事件，然后为定时基本MSC、定时结构MSCs和高级MSCs提供形式语义。在本文中，我们还讨论了与定时MSC相关的一些重要问题。1引言消息序列图（MSC）[4]语言广泛用于电信软件工程。它可用于描述用例和场景，验证分布式系统的动态行为，或指定测试用例。为了支持MSC的使用，需要形式语义。形式语义学精确地说出了语言。它避免了解释中的歧义。此外，它对于构建模拟或veri阳离子工具是必要的。在MSC'92和MSC'96标准中，使用过程代数方法来执行形式语义。还有一些其他的方法，如自动机[7]，偏序[1，3，5]。MSC的最新版本，MSC'20001 这项工作得到了加拿大国家科学和工程研究委员会（NSERC）的部分支持。我们要感谢评论家们非常有帮助的评论。2 电子邮件地址：zhengt@ece.concordia.ca3 电子邮件地址：khendek@ece.concordia.cac2002年出版b和爱思唯尔科学B. 五. OPEN接入和ERC B Y-NC-N Dlicense.86添加更多概念以增强其表达能力。其中一个新概念是时间限制。它允许用户指定具有量化时间要求的实时系统。 要在正式设置中使用定时MSC，我们需要 它的语义。在不同的语义模型中，我们选择偏序模型来实现定时MSC的语义。在我们看来，MSC在事件之间没有任何偏见。时间限制量化订单。Cally，我们不是一个时间标记的偏序集（lposet）。 MSC的指称语义是以复合方式构建的。我们不再把事件的语义学当作有时间的陈述。然后，使用Ned对定时位的运算来获得MSC的语义。基于此语义，我们讨论了与定时MSC相关的一些潜在问题。本文组织如下。在第2节中，我们介绍了MSC和MSC'2000中的时间概念。然后，在第3节中，我们建议使用定时的lposets作为定时的MSC的语义模型在第4节中，我们将以组合的方式讨论MSC的语义。在第5节中，我们将讨论一些问题，如时间一致性、循环中的时间约束以及定时场景的可实现性。在第6节中，我们讨论了MSC语义学的现有工作。我们在第7节结束。2MSC'2000和时间概念MSC[4]由基础MSC（bMSC）和高水平MSC（HMSC）组成。bMSC描述分布式进程之间的通信。通信是一对一且异步的。没有关于通信体系结构的明确信息。进程或实例由垂直轴表示。进程之间的消息显示为连接轴的箭头。除了消息交换之外，bMSC还可以包含内部操作、定时器事件和指示进程子集的状态的条件。它们沿实例轴排序。在标准MSC中，bMSC还可以包含诸如共区域、内联表达式和MSC引用之类的一些结构。核心区域是实例中可以按任何顺序执行事件的区域。通过内联表达式，可以在MSC中实现事件的替代、并行组合和迭代。MSC参考文献用于引用MSC内的其他MSC。在本文中，我们将有结构的bMSC与没有结构的bMSC区分开来。术语bMSC仅用于无结构的MSC。HMSC以图形方式描述了MSC是如何组合的。HMSC是有向图。它包含开始节点、结束节点、MSC引用、条件或并行框架，其中多个MSCs并行运行连接点可用于改进HMSC的布局。这些连接点不影响HMSC的语义最近，MSC引入了更多功能，包括概念87MSc TI：实例标签a out m1到j时间[@0];标签d in m2 from j;标签e out m3 to j time @[3，4]，[3，4] a; i：端实例;j：实例;标签b在m1中从i时间[1，2] a;标签c在m2到i中;标签f in m3 from i time [2] c;j：结束实例;endmsc;图1. MSC的图形和文本符号数据、时间和控制。在本文中，我们将范围限制为定时MSC。在MSC'2000标准中，时间概念如下：MSC中的所有实例的时间进度相同。所有事件都是即时的。 它们不消耗时间。时间域可以是密集的或离散的。 它必须是一个完全有序的至少是最后一个要素。时间域可以是非负有理数。时 间约束可用于指定任何两个事件之间的延迟（相对延迟）或指定事件发生的时间（绝对延迟）。当指定相对延迟时，时间约束可以是具有最小和最大边界的间隔或具体的时间值。例如，两个事件之间的延迟可以表示为[3s，4s]。这意味着延迟在3到4秒之间。如果延迟正好是3秒，我们可以将其指定为[3s]。事 件的发生时间使用绝对延迟指定。例如，要指定事件正好在MSC中的第一秒发生，我们写入[@1s]。如果事件发生在第三和第四秒之间，则时间约束可以写成@[3s，4s]。时间限制的示例如图1所示。提供了图形和文本语法。 我们标记事件的名称（a，b，c，...） 在古鲁。此MSC规范是实例i和j之间的消息m1、m2和m3的交换。事件a和b、a和e、c和f之间的相对延迟被规范化。在MSC'2000标准中，定时MSC的语义由正常事件之间具有特殊时间事件的事件跟踪来表示。例如，图1中MSC的迹线为fa、t1、b、t2、c、t3、d、t4、e、t5、FG，其中1 st 1 <2 s，t 3+ t 4+ t 5 = 2 s，3 st 1+ t2+ t 3+ t 44秒。 如果两个正常事件之间没有时间事件，则意味着它们同时占据。此语义是非正式描述的，在标准中并不完整。 为了以形式化的方式进行语义学，我们需要一个模型，MSC可以映射到该模型，并且该模型可以表示所有的痕迹。MSC T iJ[@0s][3s 4s]d@[3s，4s]AM1BEm2m3Cf[1s（2秒）[2s]883MSC的偏序模型3.1定时寄存器有各种偏序模型，如事件结构、pomset（分序多集）、lposets（标记偏序集）。为了满足定时MSC的要求，我们使用了配备两个延迟功能的系统。我们使用Time来表示时间域，它可以是一组非负数的实数或整数。P（Time）是时间的幂集，即时间的所有子集的一个定时的lposet是一个元组（A; E;; L; D;T），其中A是一组标签。E是一组事件。：EE是E上的偏序。L：E! A是将事件与标签相关联的标签函数。它可以是局部函数。D：E!P（T ime）是将事件与一组时间值相关联的绝对延迟函数。这是一个事件可能占据的范围。T：E E!P（T ime）是将一对事件与一组时间值相关联的相对延迟函数。两个事件之间不可能有延迟标签集实际上是事件的"意义"。在本文中，我们考虑事件可能是：消息输出、消息输入、内部操作、启动计时器、停止计时器或超时。因此，我们不标记以下内容：send（i，j，m）：实例i向实例j发送消息m，receive（i，j，m）：实例i从实例j接收消息m，操作（i，a）：实例i执行内部操作a，starttimer（i，T，n）：实例i设置了具有超时周期n的计时器T，stoptimer（i，T）：实例i取消计时器T，timeout（i，T）：正在执行的计时器T到期。我们将MSC中的每个事件与一个标签相关联。如果一个实例向另一个实例发送了两次消息m，我们将它们重新标记为m1和m2。 在标准MSC中，消息输出或消息输入事件可以与消息实例名称相关联，以确保文本表示法与图形表示法相对应。因此，可以合理地认为MSC中包含的消息始终是二身份验证的。类似地，定时器T也可以与标准中的定时器实例名称相关联。我们认为计时器也是经过身份验证的。一个定时事件的迹线被定义为一个（可能在nite中）定时事件序列（e1; t1）;（ e2;t2）：：（en;tn），其中ei2 E，ti2 T对所有i和j，0 i n，0 M意味着M将至少执行n次并且最多执行m次。 如果M中的某个事件受绝对时间约束，则执行M的次数可以是ected。绝对延迟可能与95MSCL@[1我M1Jb@[5s]MSCA我M1JB图5。绝对延迟环路边界。例如，我们有一个表达式循环<2; 3> L，其中L如图5所示。在MSC L中，事件b受绝对延迟约束。它指定事件b只能在该绝对时间点（第五秒）占用。因此，事件b只能占用一次。如果我们允许MSC L按照环路边界的规定运行两到三次，则事件a可能会在事件b发生之前占用两到三次。这会导致在第二次发送消息m1时没有接收事件的问题。因此，我们只允许MSC在一个循环中执行一次，如果它包含一个受绝对时间点延迟约束的事件。如果在一个循环中，一个事件受到一个绝对延迟的约束，该绝对延迟是一个范围，则该事件的所有实例都必须在该范围内。例如，weh ave是一个表达式loopL0，其中chL0 与图5中的MSC L类似，不同之处在于事件b的绝对延迟为@[2s，5s]。如果我们选择非负数实数作为时间域，则事件a可以在1和3之间的任何时间执行，事件b可以在2和5之间的任何时间执行，因为事件在MSC'2000中是瞬时的。但是，如果我们选择非负积分器作为时间域，则事件a和b只能执行3次。时间再次限制了环路边界。如果MSC中的所有事件都不受绝对延迟的约束（或者所有绝对延迟都是[0，1]），则MSC可以在循环中执行的次数仅由循环边界确定。但是，相对延迟可能会强制某些事件的发生 例如，我们有一个表达式loop M，其中M如图5所示。如果事件a和b之间没有相对延迟，则可以在不发生事件b一次的情况下在几个小时内执行事件a。然而，如果我们选择非负积分器作为时间域，则相对延迟将强制事件b在某个时间发生。在不限制时间域选择的情况下，循环的语义可以定义为以下集合之一：M[loopi;j>A]=8（ try seqf ail）） seq（ try seq成功）如果我们使用TF代表ntM[trysqfail]，并使用TS代表ntM[trysqsuccess]，则T F=M[t ry]M[fail]=（A）[00：00]l（e0）、l（r）、l（t）g、DT在为什么CHT（r;t）=[5]。（为了简单起见，省略了实际标签和对等标签。）M[loop<0; n>（t ryseqfai l）]=f";TFFTF;T F T FTF; ：g. （我们需要重新标记TF中的消息事件和计时器事件，以确保它们在展开循环时是唯一的。）TS=M[t ry]M[成功]=（A，fe;e0;f0;r;sg，f（e;e0），（e;r），（f;f0），（a）（a）（b）（a）（a）（b）（b）（c）（c）（D）（d）TS、TTS）在其中TTF（r; s）=（0; 5）。(re为了简单起见，省略了exive对和具体标签因此，此HMSC对应于一组项：f T S; TF T S; TF TF T S; TF TF TF TFTS，... g.对于e v ery l p 2 M [ H ]，H的迹线集为Tr（H）=STr（lp）。F或HMSCH对应于一组lP和M[H]，但不对应于5定时MSC在前面的章节中，我们讨论了定时MSC的语义。 通常，MSC可以映射到一组域。在bMSC的情况下，这一组MSC成功IJnfT1F尝失成功MSC尝试iJT1 [5]ERM1E'MSC失败IJT1R98仅包含一个lposet。对MSC增加时间限制会带来一些新问题。如前所述，时间约束是循环的语义。循环执行的次数不再由循环边界单独确定。我们需要知道一个循环实际执行的次数。更重要的是，相对延迟可能迫使一些事件在循环中占用。因此，具有循环的HMSC的事件痕迹将通过相对延迟来检测。这类MSC的特性值得进一步研究。MSC标准允许对MSC中的任何两个事件施加相对的时间限制。这带来了可实现性的问题。如果在MSC中具有相对延迟的两个事件在它们之间不具有因果顺序，则在没有事件所占用的进程之间的附加同步的情况下，不能实现MSC在[6]中，讨论了没有时间限制的MSC的可实现性。例如，图4中的MSC S是可实现的。但是，如果我们在事件和事件之间添加相对延迟[2s，3s]，并且f，此MSC不再可用。任何事件E或F都可以占用rst，但一旦一个事件发生，另一个必须等待至少2秒，最多3秒。实际上，实例i不知道实例k中发生了什么，反之亦然。为了检查给定MSC中是否存在这样的时间约束，我们可以在语义框架中检查具有相关性的两个事件之间是否存在相对延迟。定时MSC的另一个重要问题是时间约束和因果顺序之间的一致性。例如，对于两个事件e和f，如果e发生在f之前，但e具有绝对时间延迟[4，6]，并且f具有绝对时间延迟[2，3]，则时间约束与因果顺序一致。时间限制可能不一致。例如，两个事件e和f分别具有绝对时间延迟[2，3]和[4，6]，但是它们之间的相对时间延迟是[5，7]。根据我们对MSC的语义和时间跟踪的概念，我们将MSC的时间一致性描述如下：对于对应于给定集合M[H]的MSC H，H是时间一致的，如果并且仅如果对于每个LP2 M[H]存在时间跟踪。开发一种算法来检查MSC是否具有时间一致性是一项具有挑战性的任务，因为与MSC相对应的一组lposets可能在nite中。此外，轨道的存在可能取决于时间域的选择。6相关作品非定时MSC的语义已经使用基于其本身的不同方法。CHI自动机，PROC代数或偏序。 P. B. Ladkin和S. Leue[7]对MSC给出了nite状态解释。然而，MSC中的非本地选择可能需要不受限制的历史变量，这导致了全球国家的数量减少。在这种情况下，一个nite状态语义99不适用于MSC。S. 莫和M。A. Reniers[9，10]将MSC转换为过程代数项。然后是Ned的过程代数项的运算语义。过程代数项通常很长，并且需要许多推理规则。MSC的偏序语义看起来更自然、更简单。R. Alur et al.[1]认为bMSC的语义是事件的部分顺序。J.P. Katoen 和 L. Lambert[5] 为 bMSC 和 HMSC 提 供 了 一 种 组 合 式denotational语义学bMSC映射到偏序多集（pomset）。HMSC的构造函数对应于对pomset的适当操作。S. Heymer[3]使用标记的偏序集（lposets）而不是pomset来进行语义学。F或定时MSC，P。L. Maigat和L. 你好和[8]将MSC转换为订单自动机。它们将MSC中的每个事件和每个通信与持续时间相关联。在MSC'2000中，持续时间可以在任何两个事件之间指定，而不仅仅是[8]中的成对通信事件。R. Alur et al.[1]将定时MSC解释为具有定时函数的部分顺序，该定时函数将部分顺序中的每对事件映射到时间间隔。在它们的定时MSC中，时间约束只能对成对的事件施加。他们不考虑事件占用的绝对时间限制，只解决发送和接收事件的bMSC。类似地，H.本-阿卜杜拉和S. Leue[2]使用定时延迟间隔和定时器事件来表示定时约束。MSC被解释为与事件的部分顺序一致的跟踪。它们不具有为跟踪中的每个事件分配时间戳的计时分配。他们也不考虑绝对的时间限制。7结论时间限制在MSC'2000中是新的。为了支持实时系统的规范和验证，本文提出了定时MSC的正式语义。我们选择了定时左置模型，并为MSC建立了一个denotational语义。我们的工作将现有的偏序语义扩展到定时MSC。本文研究了bMSC、HMSC和具有共区、MSC引用、内联表达等结构的我们将bMSC的非核心事件视为基本单元，以便于将MSC的语义与结构结合起来。bMSC被认为是事件的组合，因此MSC的子集可以从语法构造。 然后，使用分层运算以相同的组合方式建立了bMSC、HMSC和具有结构的MSCs的语义。MSC标准中的一些概念在这里没有被考虑，例如：一般排序、实例分解、门和条件。一般顺序指定一些附加顺序，这些附加顺序可以很容易地用我们的语义表示。我们相信实例分解和门不会100MSC的动态语义学。将条件建模为事件可能是实现条件语义的一种可能方法。本文不考虑内联表达式和引用表达式中的opt和exc运算符。我们认为它们是alt运算符的特殊情况。这个语义是进一步研究定时MSC的问题的起点。我们未来的工作是开发一种算法来检查MSC的时间张力，特别是在nite循环中的HMSC其他感兴趣的工作可能是定时场景的可实现性，以及定时场景的比较参考文献[1] 阿鲁，R.，G. J.霍尔茨曼和D. Peled，信息序列图分析器，第二届系统构建和分析工具和算法国际研讨会论文集，计算机科学讲座笔记，1055（1996），35{48}。[2] 本-阿卜杜拉，H.，和S。Leue，在消息序列图规范中表达和分析定时约束，技术报告97-04，电气和计算机工程系，滑铁卢大学，1997年。[3] 海默，S.，MSC的非重叠语义学，SAM'98，德国柏林，1998年6月。[4] ITU-T，"消息序列图"，ITU-T建议Z.120，1999年。[5] 卡顿，J.P.，和L.Lambert，消息序列图的Pomsets， SAM'98，德国柏林，1998年6月[6] 肯德克，F.，G.罗伯特，G. Butler和P. Grogono，消息序列图的可实现性，SAM'98，德国柏林，1998年6月[7] Ladkin ， P.B. 和S 。 Leue ， 解释 消 息流 图， 计 算的 形式 方 面， 7 （ 5 ）（1995），473{509}。[8] Maigat，P. L.、 和L. 你好A（MAX，+）消息序列图中时间的应用程序，第五届离散事件系统研讨会，比利时根特，2000年8月。[9] 莫，S.和M. A. Reniers，MSC'96的操作语义，计算机网络和ISDN系统，31（17）（1999），1785-1799。[10] 莫，S.和M. A. Reniers，高级消息序列图，SDL论坛'97：测试时间-SDL，MSC和趋势，法国埃夫里，1997年9月。