嵌入式系统中的事件代数扩展SaveCCM触发机制的新方法

理论计算机科学电子笔记141（2005）107-121www.elsevier.com/locate/entcs嵌入式系统JanCarlson1，2andMikaelsonAkerholm1瑞典国立大学计算机科学与电子机械系摘要在这篇文章中，我们提出了如何组件触发SaveCCM，一个组件模型，用于嵌入式车辆系统，可以通过事件代数扩展。该扩展允许组件由复杂的事件模式触发，而不仅仅是时钟信号或单个外部事件。将触发条件的检测与被触发服务的定义分离，允许更通用的组件，从而提高组件的可重用性。在组件模型中提供事件检测机制意味着触发条件在设计时可显式地用于系统分析。事件代数用于定义复杂的触发条件。该代数具有相对简单的声明性语义和有据可查的代数属性，这有利于系统的正式和非正式推理。该代数还确保了触发条件的检测可以在有限的资源下有效地实现，这在嵌入式应用中是至关重要的。保留字： 嵌入式系统，事件检测，软件架构。1引言SaveCCM [1]是一个用于开发车载系统软件的组件模型。由于对可预测性和运行时间1Email：{jan.Carlson，mi ka el. ak e r hol m}@mdh. se2 由CUGS（国家计算机科学研究生院）资助。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.02.049108J. Carlson，M.《理论计算机科学电子笔记》141（2005）107在预期领域的效率。我们使用事件代数扩展了SaveCCM的触发机制，它允许组件由复杂的事件模式触发，而不仅仅是时钟信号或单个外部事件。作为一个运行的例子，我们考虑一个系统与外部事件，包括一个按钮B，和内部警告事件P和T所产生的组件监测压力和温度，分别。只要在两秒钟内按下按钮两次，系统就应该执行由第三个组件提供的服务，除非其间有任何一个报警组件发出信号。实现这一点的一种方法是设计一个新的组件，负责检测这种特定情况，并在正确的情况下触发该组件这意味着触发条件在系统设计级别上是不可见的，因此不容易用于分析。本文中概述的替代方案是将复杂事件模式的检测作为组件模型的一部分复杂的触发条件在高层次上进行了详细说明，具有定义良好的形式语义，当对组件源代码的访问受到限制时，它支持在设计时进行形式分析在编译时，自动生成检测特定情况的代码触发条件由事件代数的表达式指定例如，上面描述的情况可以由表达式（B;B）2−（P <$T）来定义 代数被设计为尽可能直观，在限制下，它应该是有效地实现有限的资源，因为我们主要针对嵌入式应用程序。操作员具有直观，声明语义，我们提出了一些代数法，促进正式和非正式的推理。本文的其余部分组织如下：第2节调查相关的工作和第3节给出了SaveCCM的概述。在第4节中给出了对提议的扩展的描述，包括对事件代数的非正式介绍。在第5节中，事件代数被更正式地呈现，并且我们概述了这个特定代数的属性如何影响扩展的最后，第6节对本文进行了总结。2相关工作近年来，学术界和工业界都在开发适用于不同类型嵌入式系统的组件技术相对于我们的专业知识，其中一些支持不同的触发类型，高级实时约束的规范和运行时可扩展性。在这一节中，我们将brie-brie-brie-de-J. Carlson，M.《理论计算机科学电子笔记》141（2005）107109从汽车、消费电子和自动化领域划出一个示例Rubus组件技术[10]是一种用于汽车行业的商业技术它与Rubus操作系统紧密集成。 Rubus组件是静态调度的，并且可以指定复杂的时序要求，例如，发布时间、截止日期、最坏情况执行时间和周期时间。主要的限制是只能定期激活组件。Koala [14]是飞利浦内部开发和使用的组件技术。组件绑定灵活性可以通过开关来实现，如SaveCCM。交换机在运行时在不同组件提供的接口之间进行选择，并在编译时可能减少静态。ROBOCOP [5]是增强考拉模型的延续，例如，支持实时约束和分析。基于端口的对象（PBO）[13]是卡内基梅隆大学高级机械手实验室专门用于可重构机器人应用的组件技术该技术支持通过应用传递函数对闭环或开环系统的给定输入的输出响应还支持实时分析。PECOS [15]是ABB和学术界之间的一个合作项目，旨在开发一种适合现场设备的技术Pecos支持与组件相关的不同类型的事件;它们可以是被动的、主动的或事件类型的。被动组件没有自己的执行线程，必须由其他类型的组件触发。活动组件有自己的周期性触发的线程。事件组件是由外部事件触发并具有控制线程的组件。在基于组件的体系结构领域各种类型的事件检测机制被用于广泛的领域。例如，一些大型分布式系统具有基于事件订阅者和发布者的体系结构在这样的系统中，不是让订阅者注册他们对简单事件类型的兴趣，并执行他们自己的过滤和模式检测，这个功能可以由发布者提供。订阅者注册事件模式，例如在事件代数中指定。发布者执行事件检测，并在检测到各个订阅者的模式时通知它们。已经提出了许多这种类型的系统，例如，由Gruber等人提供的READY事件通知服务，它包含一个简单的事件代数，用于注册事件模式[9]。在中间件平台中，事件检测技术通过允许消费者订阅cer，110J. Carlson，M.《理论计算机科学电子笔记》141（2005）107taineventpatartherthantossingleeventtypes.例如，S′anchezet al.提出了一种事件相关语言，其中事件表达式被翻译成类似自动机的嵌套Petri网[12]。我们使用的事件代数的操作符，以及基于区间的语义和限制检测的概念，都受到主动数据库领域工作的Snoop [4]，Ode [8]和SAMOS [7]是主动数据库系统的例子，其中事件代数用于指定反应行为。这些系统的差异主要在于检测机制的选择。SAMOS基于Petri网，而Snoop使用事件图。在Ode中，事件定义等价于正则表达式，可以被状态自动机检测到Galton和Augusto已经表明，将复杂事件模式的发生与单个时刻相关联会导致某些操作组合的非预期语义[6]。他们还提出了一个替代的，基于区间的，语义处理问题的核心我们使用一个类似的语义基础，我们的代数，但扩展它的限制政策，让代数，gebra实现有限的资源，同时保留所需的代数属性。据我们所知，没有现有的事件代数提供援助的开发人员在代数属性或事件表达式等价理论，而在同一时间，确保检测可以正确地执行有限的资源。3SaveComp组件模型SaveCCM基于文本语法，但UML2的组件图的一个稍微修改的子集被用作图形符号。在本文中，我们只给出了图形符号，并请读者参考[1]了解文本语法的细节。3.1建筑元素系统由相互连接的组件构建，即，封装的行为单元，具有定义良好的接口，定义为输入和输出端口，这些端口是组件与其外部环境之间的交互点该模型区分了端口的两个方面：数据流和控制流。前者由数据端口捕获，即，一个元件存储器，其中可以写入和读取给定类型的数据。控制流是根据控制组件激活的触发端口来定义的最后，端口可以具有触发和数据功能。这些端口类型的符号如图所示1.一、J. Carlson，M.《理论计算机科学电子笔记》141（2005）107111。。。D>、纯数据输入端口仅触发输入端口带触发和数据的D z> zz仅数据输出端口仅触发输出端口带触发和数据的基本组成部分组件开关部件（（开关电源（（大会发言人）（（SaveComp浏览器Fig. 1. SaveCCM的图形表示法基本组件通过入口函数与可执行文件相关联可选地，可以给出质量属性以指定组件的特定特性，例如，最坏的执行时间除了基本组件，该模型还包含两种组件类型：组件是封装的子系统。内部互连和组件对系统的其余部分是隐藏的，只能通过程序集的端口访问。交换机是用于动态改变组件互连结构的轻量级组件。交换机指定了许多连接模式，即，从输入端口到输出端口的部分映射每个连接模式都由一个逻辑表达式保护，可能是在输入端口可用的数据上，该表达式定义了使用该模式交换机只执行连接模式保护的计算3.2执行模型和运行时框架在系统级别上，执行可以由时钟或外部事件触发。然后，控制根据触发端口连接在系统中传播一旦一个组件的所有输入触发端口都被激活，该组件就被触发。如果一个以上的输出触发端口连接到同一个输入触发端口，则一旦所连接的输出端口之一被激活，该输入端口就被激活。112J. Carlson，M.《理论计算机科学电子笔记》141（2005）107当一个组件被激活时，它首先从所有输入端口读取数据，然后执行相关的计算。然后，将输出写入输出端口，这包括激活组件的所有输出触发端口最后，所有输入触发端口都被重置为非活动状态。嵌入式系统的应用领域需要一个适合该领域当前实践的小型运行时框架。例如，在一个示例中，该原型为RTXC实时操作系统[11]生成代码，其中系统被实现为一组周期性任务，具有已知的最坏情况执行时间、最后期限和控制执行顺序的优先级。在编译时，组件被分配给任务的方式，触发条件，优先关系和组件通信被保留。分析阶段从组件属性和系统架构中导出任务属性响应时间和可扩展性分析。最后，为每个任务生成目标特定的代码，其中对组件入口函数的调用与处理任务内组件之间以及与其他任务之间的数据交换的代码交错4扩展触发我们提出了一个扩展的触发机制，允许更多的触发条件被指定。该功能以事件代数的形式提供，即，一系列运算符，从中可以构造表示复杂触发条件的表达式。首先，我们给出了代数运算符的非正式描述，并展示了如何将事件代数纳入SaveCCM。在第5节中讨论了代数的形式语义和一些重要性质。对于代数的详细描述，包括实现细节，读者可以参考[2]或[3]。4.1运营商表达式是从原始事件递归构建的，原始事件由输入端口名称和代数运算符表示图2列出了操作符，以及对其含义的非正式描述。作为一个例子，在介绍性例子中的触发条件，即B在两个时间单位内出现两次，并且P和T在其间都不出现，将由表达式（B;B）2−（P <$T）定义。J. Carlson，M.《理论计算机科学电子笔记》141（2005）107113操作者符号非正式意义析取A组B组当A或B（或两者）发生时发生。结合A+B当A和B发生时发生（以任何顺序，可能不是同时发生）。否定A-B当A发生时发生，在此期间B不发生。序列A;B当A的出现之后是B的出现时，发生。内Aτ当出现短于τ时间单位的A时发生图二. 代数运算符的非正式描述。4.2扩充记法为了将代数合并到组件模型中，SaveCCM表示法扩展了一个名为事件的新元素。这种结构的一个例子如图所示3 .第三章。一个事件元素有多个命名的输入端口和一个输出端口。为了说明这些端口的语义与普通端口不同，它们没有以图形方式表示。事件元素还与一个代数表达式相关联，该代数表达式定义了它负责检测的事件模式按钮。（（大会发言人）>）B（B;B）−（P T）压力传感器。（（大会发言人）>）。 > 产品介绍）P2）T、z温度传感器（（大会发言人）（（SaveComp浏览器控制。 >）>温度>，v>Response，），z.zz图三. 包含事件元素的系统设计示例。目前，事件元素的语义是根据原始符号定义的。这样做的主要动机是，扩展可以包含在原型工具中，并具有最小的扩展。将来，我们打算为事件元素开发更直接的语义，并在分析和代码生成阶段显式地处理它们，以避免不必要的开销。>114J. Carlson，M.《理论计算机科学电子笔记》141（2005）107（（SaveComp浏览器> B> ，。（（开关电源z，> S>z。、z、。（（SaveComp浏览器>A1>定义4.1一个有n个输入端口的事件元素被看作是一个基本成分B、一个开关S和n个辅助基本成分的集合四、.....z。（（SaveComp浏览器>An>见图4。 一个事件元素（左）和它在原始符号中的对应物（右）。基本组件B负责正确检测事件模式所需的计算和状态信息这个组件的代码是根据事件元素的表达式自动生成的，遵循[2]中给出的代数实现。开关S基于B的输出来确定触发是否应当被转发。连接模式条件与要检测的表达式无关另外，为事件元件的n个输入端口中的每一个生成辅助分量Ai这些组件非常小，并且仅用于在将数据中继到B之前用时间戳和相应的端口名标记数据。为了确保一个输入端口的激活在被另一个端口的激活覆盖之前被B处理，我们要求B被赋予比辅助组件更高的优先级。我们认为，辅助部件所带来的间接费用是相当低的。它们通常会在现有任务结束时分配，并且组件代码可以由编译器内联，因为它只能从一个点访问。在代码生成阶段显式处理事件元素5事件代数详细信息从代数的角度来看，事件元素的输入端口被视为事件源。相反，对于系统的其余部分，输出端口充当事件源，每当传入的事件序列与代数表达式定义的模式匹配时，就会发出触发信号注意，SaveCCM触发信号是瞬时的，但是算法关联事件实例，即，端口激活和子表达式的检测，以及时间间隔，以确保所需的代数属性。）p1）.）.J. Carlson，M.《理论计算机科学电子笔记》141（2005）107115在我们考虑代数语义之前，必须定义一些基本概念，将代数与组件模型中的概念联系定义5.1设时域T是所有自然数的集合，设P是包含事件元素的输入端口名称的集合对于每个p∈ P，让type（p）表示p的数据类型。5.1输入端口输入端口的激活由端口名称、发生时间和相关数据来表征形式上，我们表示每个激活作为一个单例集，允许原始和复杂的事件实例的统一处理。在系统生存期内，某个端口的所有激活定义5.2如果p∈ P，τ∈type（p）且τ∈ T，则单例集{p，，τ}是原始事件实例。 原始事件流 是一组原始事件实例，所有这些实例都标有相同的端口名称和不同的时间戳。解释是单个执行场景的正式表示，因为它定义了事件组件的输入端口可以被激活的可能方式之一。定义5.3解释是映射每个输入端口p∈P到一个基本事件流，其实例标记为p。作为示例，令P ={T，P}，type（T）= N并且type（P）={high，low}。现在S={{T， 12， 2}，{T， 14， 3}，{T， 8， 5}}和SJ={{P，low， 4}}是原始事件流的 使得I（T）= S和I（P）= SJ的解释I表示T在时间2、3和5处被激活并且P在时间4处被激活的场景。5.2事件表达式事件表达式由输入端口名和代数运算符构建，如第4节所述。作为定义表达式含义的第一步，我们将上面为输入端口定义的实例和流的概念扩展到事件表达式。定义5.4事件实例是n个原始事件实例的联合，其中0b（b∈[[B]] I<$start（a）≤start（b）<$end（b）≤end（a））}[[A;B]]I={a<$b|a∈[[A]]I<$b∈[[B]]I<$end（a）AJ时。因此，应当明确在适用限制时，上述法律在多大程度上仍然适用。定理m5.9如果AAJ且rem（[[A]]I，S）成立，则rem（[[AJ]]I，S）成立。证据从定义5.7可以很容易地得出这个结论，因为AAJ意味着[[A]]I=[[AJ]]I。Q因此，AAJ确保实现检测A的结果总是AJ的有效结果。任何基于代数语义和限制策略的推理，而不是基于特定检测算法的细节，对于等价表达式将同样有效。5.5分析用事件代数扩展组件模型的一个论点是，与为每个触发条件开发新组件相比，它有助于在系统设计级别上进行分析上面提出的代数定律如在早期工作[2]中提出的变换算法所示。从组件模型的角度来看，我们希望能够J. Carlson，M.《理论计算机科学电子笔记》141（2005）107119基于连接到事件元素的组件的表达式和属性来推断事件元素的多个属性存储器要求事件元素的内存需求可以直接从表达式和输入端口的类型中与早期的事件代数工作不同，当前的实现可以检测内存有限的任何表达式最坏情况执行时间为检测组件生成的代码的特点是非常简单的控制流程。例如，没有嵌套循环，也没有函数调用。一旦内存分析得出所需的存储结构大小，所有循环都是平凡有界的。这意味着可以使用标准的最坏情况执行时间技术来分析代码。或者，直接从表达式中确定抽象的最坏情况执行时间（根据赋值、比较、算术运算等的数量）应该是相当简单的。触发频率为了保证在系统活动的一部分是非周期性的情况下及时响应，必须了解给定组件被触发的频率在实时调度理论中，术语“零星”用于两个连续的时间间隔（最小到达间隔时间）的下限已知的活动如果已知连接到事件元素的端口的最小到达间隔时间，则也可以为输出端口导出此属性然而，像析取和合取这样的运算符会导致表达式的最小到达间隔时间为零。我们定义了一个更一般的最大出现次数的概念，由一个函数occ计算，该函数保证在任何长度为τ的区间内，至多有occ（A，τ）个表达式A的检测。如果已知事件元素[2]的输入端口的最小到达间隔时间或occ值，则可以针对任意表达式和间隔长度计算该值6结论和今后的工作我们已经提出了如何在SaveCCM，一个组件模型，用于嵌入式车辆系统的组件触发，可以通过一个事件代数扩展使用代数运算符，复杂的触发模式120J. Carlson，M.《理论计算机科学电子笔记》141（2005）107可以定义端口激活，只要激活与此模式匹配，就会触发相关组件。将触发条件的检测与被触发服务的定义分离，允许更通用的组件，从而提高组件的可重用性。将事件检测作为组件模型的一部分提供，而不是在普通组件中实现它，这意味着它可在设计时进行分析事件代数的开发考虑了两个主要因素：它应该遵守代数运算符直观上应该成立的定律，并且应该有一个正确检测内存有限的任何表达式的实现简单的操作符语义，和表达式等价律，促进了系统中触发条件的正式和非正式推理我们正在进行的工作包括为事件元素定义更直接的语义，而不是根据其他架构元素来定义它原型工具的编译时阶段应该相应地修改，以便尽可能有效地实现事件检测活动然后，应进行案例研究，以评价该方法的效用，并确定可能的改进。引用[1] M. ，因此，如果两种方法都适用于车辆控制系统，则LicetiatethesisNo。 44（2005），Mal？lard alenUniverer sity，S we d en.[2] 卡尔森，J.，一个直观的和资源效率高的事件检测代数，执照论文第29号（2004），M？alardalenUniver sity，S we d en.[3] Carlson，J. and B. Lisper，An event detection algebra for reactive systems，in：Proc.4th ACMInt Conference on Embedded Software（EMSOFT）（2004）。[4] Chakravarthy，S.和D. Mishra，Snoop：An expressive event specification language for activedatabases，Data Knowledge Engineering14（1994）. 1比26[5] de Jonge，M.，J. Muskens和M. Chaudron，基于组件的软件系统中运行时资源消耗的基于场景的预测，在：Proc. 第六届国际基于组件的软件工程研讨会：自动推理和预测（2003）.[6] Galton ， A. 和 J. C. Augusto ， Two approaches to event definition ， in ： Proc. 13th Int.Conference on Database and Expert Systems Applications ， Lecture Notes in ComputerScience2453（2002）.[7] Gatziu，S.和K. R.陈文，面向对象数据库系统中的事件，见：第一届数据库系统（1993）。[8] Gehani，N.，H. Jagadish和O. Shmueli，COMPOSE：一个用于复合材料规格化和检测的系统，在：高级数据库系统，计算机科学讲义759（1993）。[9] 格鲁伯河，B. Krishnamurthy和E.陈文辉，事件通知服务的架构，载于：第十九届IEEE国际分布式计算系统会议论文集，中间件研讨会，奥斯汀，德克萨斯州，美国，1999。J. Carlson，M.《理论计算机科学电子笔记》141（2005）107121[10] Lundbéack，K. -L。，J. Lundb aéckandM. Lind berg，Devlopmenofdependablereal-timeapplications（2004）.网址http://www.arcticus.se[11] Quadros Systems Inc，RTXC内核用户指南（2004）。 网址http://www.quadros.com[12] 是的，C。、S. 是的，H。 Si p ma，T. Zhang，D. Dil l and Z. 陈文，事件相关性：语言与语义，收录于：第三届嵌入式软件国际会议论文集，计算机科学讲义2855（2003）。[13] 斯图尔特，D。B、R. A. Volpe和K. Khosla，Design of dynamically reconfigurable real-timesoftware using port-based objects，IEEE Transactions on Software Engineering23（1997），pp. 759-776。[14] van Ommering，R.，F. van der Linden，K. Kramer和J. Magee，消费电子软件的Koala组件模型，计算机33（2000），pp. 78比85[15] 等一下，M。、T. GennBageller，C. Christoph，O. 我也是，S. 杜卡塞河 我们走吧，G。你好，M.米勒角，澳-地Stich和S.陈文辉，嵌入式软件组件--PECOS方法，载于：第二届国际组合语言，2002年。