基于构件的程序动态重构的有效性条件及应用分析

理论计算机科学电子笔记159（2006）227-239www.elsevier.com/locate/entcs基于实例的程序动态重构的有效性保证Nafiseh Fekrazad Nobakht3Rasool Jalili4谢里夫理工伊朗德黑兰Faranak Heydarian Dehkordi2谢里夫理工伊朗德黑兰摘要随着对长生命周期和高可用程序需求的增长，动态重构将成为一个重要的研究课题。动态重配置使软件系统在运行时改变，以减少其停机时间的情况下，任何更新，升级或在任何变化。运行时任何无效的重新配置都可能导致程序进入无效状态。本文在分析了现有文献的基础上，研究了基于构件的程序动态重构的有效性，给出了动态重构的有效性条件。我们发现，一般的有效性保证问题是不可判定的，也没有通用的算法来验证动态重构的有效性。为了有一个可计算的算法的有效性检查，我们提出了一些充分条件，实现有效性。关键词：基于代理的程序，重构，动态重构，有效性保证，状态转移1Email：Niamanesh@mehr. 是的。埃杜乌2Email：heeidaria n @me h r. 是的。埃杜乌3Email：fekrazad@ce. 是的。埃杜乌4Email：jalili@sharif. 埃杜乌1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.070228M. Niamanesh等人/理论计算机科学电子笔记159（2006）2271引言随着对长寿命和高可用程序需求的增长，动态重构将成为一个重要的研究课题。动态软件重配置是指在运行时对程序的体系结构进行更新、升级等任何更改。动态重配置有几个实际应用。例如，在具有高可用性的公共信息系统中以及在任务和安全关键系统中，在运行时重新配置可以通过消除系统关闭的风险来降低系统更新或升级的成本。此外，动态可重构程序可以提供改变程序中可用的特征集的能力。这种能力是普适计算的关键要求[17]，因为它可以使应用程序适应新的情况和上下文。在主动网络[15]中，路由器和交换机需要动态重新配置才能对数据包执行可定制的计算。此外，在软件定义无线电[19]中，其中通信协议栈的所有部分（包括无线设备的信号处理部分）都以软件实现，动态重新配置使设备能够在运行时改变它们的通信协议另一方面，基于组件的程序将在实践中很常见，并且具有许多优点。一般来说，基于组件的程序架构由组件和它们之间的链接组成[13]。这些程序的架构级别中的重新配置可以通过重新配置操作以非常系统的方式执行，如从架构中添加或移除组件或链路。动态可重构软件系统对高可用性的要求使其成为非常复杂的系统。因此，对它们执行动态重新配置时应特别小心。在本文中，我们将探讨的有效性，动态重构。本文的其余部分组织如下：在第二部分中，我们描述了背景和相关工作。在第三节中，我们解释了我们考虑解决有效性问题的程序模型。在第4节中，我们讨论了程序的动态重构。我们表明，基于组件的程序的有效性确定的问题是不可判定的，没有一般的算法来保证的有效性。然后在第5节中给出了一组有效性的充分条件。最后，在第6节中，我们总结并提出进一步研究的方向M. Niamanesh等人/理论计算机科学电子笔记159（2006）2272292背景软件中的架构更改可以发生在设计时、编译或构建时或运行时[14]。软件架构上的动态重配置在系统执行期间改变架构软件架构可以被看作是一个图，其中节点是组件，边是链接。组件通常封装数据或功能，而链接协调组件之间的通信。更具体地说，软件体系结构描述了程序到组件的分解，组件的互连和组件交互[1]。已经进行了一些关于动态重构的研究。文献中已经报道了开发动态可重配置系统，例如DAS操作系统、基于DiPS组件的协议栈[15]、CONIC [7]、ARGUS [18]和POLYLITH [1]。此外，还有一些支持编程语言的研究，如动态Java类[16]和C++的动态类[6]。也有用于描述动态可重构架构的语言，其中大多数是ADL的扩展[12]，例如C2SADEL [14]和RAPIDE [9]。关于动态架构描述语言的一个很好的调查可以在[8]中找到。虽然动态重构具有实际应用，许多研究人员都专注于开发工具，方法和形式化来支持它，但软件从业者缺乏使用。 这种缺失在外界尤为明显安全关键型和高可用性软件领域。在[2]中，Szyperski集中在缺乏可重构的基于组件的系统的实际用途。他认为动态可重构系统不被使用的主要原因是本文将构件化程序动态重构的正确性分为两部分：一是程序和重构规范的正确性，二是动态重构的正确性。 我们想研究的是，一个正确的程序规范和重构是否会导致一个正确的或“有效的”程序。直观地说，在这种情况下，有效性意味着程序的新行为是预期的新行为。执行有效的重新配置并不是一项简单的任务，因为正在运行的程序可能处于未准备好进行更改的状态。动态重配置可能需要将旧程序的状态转换为新程序的相应状态。这意味着，对于旧程序的某些状态，在新程序中没有对应的状态，并且即使使用程序的正确规范和重新配置，我们也不能在这种执行状态下执行任何有效的重新配置。Gupta和Jalote [3]给出了软件更新中变更软件更新是软件重构的一种特殊情况他们考虑了简单的过程和面向230M. Niamanesh等人/理论计算机科学电子笔记159（2006）227程序模型证明了对于简单过程模型，动态软件更新的有效性是不可判定的。在这篇文章中，我们考虑一般形式的动态重构，这意味着在运行时为任何目的的任何更改。我们希望将Gupta [ 4 ]的理论问题扩展3程序模型我们考虑一个基于组件的程序，这是由一个进程执行。它由一些组件和它们之间的链接组成。我们用一个标记的连通图来表示一个程序，如P=（B，L），其中B是一组节点或构建块，L是节点之间的一组链接3.1组件模型组件具有简单和通用的形式，包括两个端口，一个输入端口和一个输出端口，用于读取输入和写入输出消息（图1）。组件通过端口相互连接。每个端口都支持一些消息类型。我们考虑链接，从一个组件的入端口到另一个组件的出端口的连接每个入端口或出端口可以支持一些链路以将一个组件附接到其他组件。在该模型中，每个组件由元组ci=（r，p）指定，其中r是用于的输入端口的所需消息类型的有限集合，并且p是用于ci的输出端口的所提供消息类型的有限集合。我们把组件的操作看作是内部属性，通过端口来实现。输出端口港内图1.简单组件模型我们通过三元组（ci，cj，m）来指定链接，这解释了从ci到cj的链接，其中消息类型的集合m通过ci的输出端口和cj的输入端口。这表示ci作为一个例子，假设P是一个有三个组件和两个链接的程序（图2）。c1和c2之间支持的消息类型是m1和m2，c2和c3之间支持的消息类型是m3和m4。我们将ci.p视为组件ci的所有提供的消息类型的集合，并且将cj.r视为组件cj的所有需要的消息类型的集合。此外，对于链路（ci，cj，m），我们有组件M. Niamanesh等人/理论计算机科学电子笔记159（2006）227231）M.P和M.J.R。P=（B，L）B={c1，c2，c3}L={（c1，c2，{m1，m2}），（c2，c3，{m3，m4}）}港内）Out-port图2.程序P的体系结构、其组件、链接和消息类型请注意，程序的每个输入都被认为是传递给其组件的消息序列。3.2组件行为构件的行为通过一系列的状态来表征，每个状态都包含了构件在运行时某个时刻的全部特征。因此，程序的行为将是所有组件的状态序列的Cartesian积程序中的组件通过发送和接收消息相互通信。每个组件在接收到消息时都会经过一些状态。组件状态序列中的最终状态是1，它将一个消息实例输出到组件。组件的每个状态都包含组件的整个特征，通常包含局部变量、状态变量、进程堆栈的内容和程序计数器的值。4程序的动态重构在本节中，我们将了解什么是动态重新配置，以及如何在运行时执行它。在操作方面，我们可以把重构看作是改变程序的一组基本操作4.1重配置操作程序的重新配置改变了它的组件和/或链接。因此，我们认为一个重构作为一组操作，它可以改变程序的架构。定义4.1重构操作是一组用于改变程序体系结构的操作.以下列表被认为是我们的基本重新配置操作：• Add（ci）：添加组件ci）m1，m）2m3，m）4）C1C2C3232M. Niamanesh等人/理论计算机科学电子笔记159（2006）227C5C1• Delete（ci）：删除组件ci• Attach（ci，cj）：将零部件ci附着到cj• Detach（ci，cj）：从cj拆离零部件ci我们把操作Replace（ci，cj）看作是一个复合操作，它等价于两个后续操作Delete（ci）和Add（cj），而且从语义的角度来看，ci和cj是可替换的.我们将动态重配置定义为在运行时实现的重配置。我们将重新配置表示为新旧程序之间的减操作。为了进一步说明，假设需要将图2中的指定程序更改为图3中所示的新程序P′P′=（B′，L′）B′=B−{c2，c3}<${c4，c5，c6}L′=（L−{（c2，c3，{m3，m4}）}）<${（c5，c6，{m3，m4，m5}），（c4，c6，{m6}）}））港内m1和m2m3、m4、m5M67C4） ）Out-port图3.程序P′的体系结构、其组件、链接和消息类型根据P和P′的规范，很容易检查所需的重新配置如下：P′− P == Replace（c2，c5），Replace（c3，c6），Add（c4），Attach（c6，c4），Attach（c5，c6），Attach（c1，c5）.请注意，为了简单起见，我们假设删除一个组件，所有附加的链接也会被删除。4.2重新配置实现通过重构实现，我们指的是对进程执行的程序进行更改。在改变之后，进程从非初始状态执行另一个在描述如何实现重新配置之前，C6M. Niamanesh等人/理论计算机科学电子笔记159（2006）2272333在运行时，我们定义可达状态。定义4.2状态s被称为程序P的可达状态，当且仅当，从初始状态s0开始执行P的进程在某个时间对于某些输入可以到达s我们认为状态是过程的完全表征因此，如果进程从非初始可达状态开始，则进程的行为就像进程从初始状态开始到达该状态时换句话说，可到达状态可以由另一个进程创建。定义4.3在执行程序P的进程上实现动态重新配置分四个阶段执行（图4）：• 冻结：进程在可到达状态（如s）下停止• 更改：程序P的组件和链接被替换为新的组件和链接• 状态转移：程序P的状态，比如s，被转移到新程序• 重新执行：流程从新的状态状态s中的进程状态s'中的进程）的方式图4.在重构之后，程序P被改变为P ′。并且进程从非初始状态执行P ′。对于状态转移，我们有一个映射函数，它通过将状态的所有内容映射到值，将旧的程序状态映射到新的程序状态。换句话说，可能需要将某些变量的值映射到其他值，即使是不同类型的值。由于实现的原因，我们将映射函数的类限制为一个简单的类，其中函数不映射局部变量的值。1P24P′234M. Niamanesh等人/理论计算机科学电子笔记159（2006）2275重新配置有效性对进程的重新配置强制从非初始状态执行程序直观地说，当进程在改变阶段之后执行新程序时，重新配置是有效的，就像它从初始状态执行的情况一样。假设一个进程正在执行一个程序P，它需要将P重新配置为P′。进程执行P时的状态序列有一个初始状态，比如s0，以及一些可达状态。在重新执行之后，进程应该用另一个状态序列来执行程序P′，该状态序列有自己的初始状态和可达状态。如果我们假设最后重新配置是有效的，那么有两种可能性：• 进程从其可到达状态之一重新执行新程序• 在重新执行阶段之后，进程通过经过一些不可达状态继续运行，然后进入新程序的可达状态。在第二种情况下，新程序从一些不可靠的状态，然后进入程序的可达状态。值得注意的是，通常情况下，进程在不可靠状态下的行为最有可能影响新程序。在从旧程序状态转换到新程序状态时，需要语义知识来找到新程序中冻结状态的对应状态。如前所述，通过映射函数F执行旧程序和新程序之间的状态对应。该函数定义在旧程序的状态上，并确定新程序中的相应状态。 基于上述概念，现在我们定义有效的重新配置。定义5.1从程序P到程序P′的过程的动态重新配置是有效的，当且仅当在改变进程的状态进入可达状态P′。换句话说，在有效的重新配置中，不可靠状态的数量应该是有限的。引理5.2对于一个基于组件的程序P和一个输入消息序列，它是不可判定的，无论程序是否到达它的最终状态。证据 我们将证明这个问题的可判定性可以归结为停机问题的可判定性。假设我们要解决程序A的停机问题，输入为I。 我们建立了一个基于组件的程序P的一个组件，该组件的主体是程序A的代码，并获得输入I作为合适的消息序列，并产生A很明显，程序P的最后状态与消息序列的可达性等于程序的能力M. Niamanesh等人/理论计算机科学电子笔记159（2006）227235A在输入序列上暂停。因此，由于停机问题是不可判定的，我们的问题也是不可判定的Q定理5.3对于基于组件的程序P和P′，状态映射函数F，以及其中定义了F的程序P的可达状态s，使用映射函数F在状态s处从P到P ′的动态重构是否有效是不可判定的。证据 当发送到程序的消息序列将导致新程序的可达状态时，动态重新配置是有效的。假设F是一个将P的任何可达状态映射到P′的最终状态的函数。从P到P′的动态重构的有效性等于程序P′的最终状态，由于后者不可判定，前者也不可判定。问题的不可判定性有重要的结果。这意味着我们不能给出一个通用的算法来获得参数P，P′，F和s，以检查重构的有效性。换句话说，这意味着要有一个有效的和有保证的重新配置，它是必要的，找到一些充分条件的参数。Q5.1有效性条件对程序的任何重新配置都会影响某些组件。为了简单起见，它被认为是受影响的组件，使一个连接的子程序的一部分。定义5.4程序P中的重新配置对象的受影响区域AA（P，N）是通过重新配置而改变的一部分我们定义AA（P，n）.r为AA（P，n）和AA（P，n）的组件中不提供的必需消息类型的集合。p为AA（P，n）的组件中不需要的已提供消息类型的集合换句话说，我们将AA（P，N）视为一个大的复合组件，它具有一组必需和提供的消息类型。基于上述的四个阶段实施的动态重构，我们已经确定了三个参数的有效性保证的动态重构：类型的变化，冻结时间，状态转移。• 更改类型：从有效性的角度来看，我们不能对正在运行的程序执行任何更改。例如，在更换两个组件时，应该有一些条件。为此，我们定义了组件的增强版本。定义5.5组件c2是c1的增强版本，如果以下条件成立：如果s1是程序的可达状态，其中F是236M. Niamanesh等人/理论计算机科学电子笔记159（2006）227我一期+1定义，下一条指令是向组件c1的输入端口发送一条消息，在执行c1之后，程序进入状态s2，如果用组件c2代替c1的新程序将处于状态F（s1），那么在执行c2之后，它将处于状态F（s2）。上面的定义有助于我们从功能的角度比较组件• 冷冻时间：在重构的冻结阶段，程序的变化组件和链接应该处于适当的状态，以进行有效的重构。为此，我们定义了安全状态的重新配置。定义5.6程序P和重新配置的状态s是安全的重新配置点（以下简称SRP），如果没有AA（P，¯（bein）¯ ¯任何互动。• 状态转移：在将进程的程序改变为新程序之后，有效性强制进程应当到达新程序的可达状态。定理5.7如果组件c2是c1的增强版本，则对于定义了状态映射函数F的程序的每个可达状态s，在不存在任何交互且没有定义映射变量的情况下，如果F（s）被任何未改变的组件使用，则F（s）将是新程序的可达状态。证据我们证明了定理归纳的s，这是一个可达的状态。假设P是程序的状态序列，它是通过组件的输入消息序列生成的，s0是初始状态归纳的基础。P中的状态s0对应于P′中的F（s0）。唯一的区别可能是变量的值，因为在P的s0中具有零值的一些变量可以在P′的F（s0）中具有另一个值。诱导步骤。作为归纳假设，令定理对以s结尾的状态序列P成立。这意味着存在P′的状态序列，其以F（si）结束。让下一个可达状态是si+1，可以通过两种方式到达：（很明显，应该在si和si+1之间执行的语句与F（si）和F（si+1）之间执行的语句相同，因为控制点在运行时堆栈上的组件中，并且堆栈上的组件不能被更改）。• 组件c1执行后：在这种状态下，基于组件增强版本的定义，在P′中执行c2后，F（si+1）是下一个可达状态。• 在执行未更改的组件之后：在这样的状态下，让s′be组件执行后的下一个可达状态我们M. Niamanesh等人/理论计算机科学电子笔记159（2006）227237一期+1一期+1一期+1一期+1ii+1我想证明，=F（si+1）。 状态由值组件的状态变量、局部变量和进程栈的内容。PC的值在两个状态下是相同的。由于映射函数的收缩，局部变量在si和F（si）中具有相同的值，当然在si+1和F（si+1）中也是如此。由于根据假设，si和F（si）之间的语句不使用任何映射变量，因此局部变量的值在进行中不会改变。从si到si+1 从F（s）到s′. 因此，PC、本地变量和未映射的变量在si+1和s′中是相同的，因此′在F（si+1）和s′中 ，证明了s=F（s）.一期+1Q有效性的充分条件从程序P到P′的动态重新配置，其中重新配置是有效的，如果所有以下条件都成立：•c2是c1• P已在SRP• 已在% s中定义映射函数。P′−P= N的一般重构的第一个条件如下：AA（P′，N）是AA（P，N）的增强版本。这意味着，在某些情况下，受影响区域的组件不是增强版本，完整的重新配置是有效的。定理5.8进程的动态重构，从程序P到P′如果满足上述三个条件，则有效。证据 类似于定理2的证明。Q6结论和今后的工作动态重构是一种在不关闭软件执行进程的情况下对软件进行修改的方法。在高可用性的软件系统中，如主动网络中的交换机，或关键任务系统，如网上银行系统，或普适计算环境中的长寿命应用程序，动态重构是必要的。在本文中，我们提出了一个简单的基于组件的程序模型中的动态重构的有效性保证相关的问题。我们使用并扩展了Gupta我们已经表明，一般来说，238M. Niamanesh等人/理论计算机科学电子笔记159（2006）227基于组件的程序是不可判定的。我们提出了三个参数，并开发了实现有效性的充分条件。在本文中，我们考虑了简单的模型，基于组件的程序。将模型扩展到一般模型是我们研究的路线图引用[1] Hofmeister C.，珀蒂洛·JM.，分布式系统中的动态重配置：修改软件模块以进行替换。在Intl.Conf. on Distributed Computing Systems，第101-110页，1993年。[2] Szyperski C. ， 组 件 技 术 ： 什 么 ， 在 哪 里 ， 如 何 ？ 在 proc 的 Int.Conf. 软 件 工 程（ICSE），第684-693页，2003年。[3] 古普塔·D Jalote P.，使用进程之间的状态转移的在线软件版本更改，软件-实践和经验，卷。23岁，不。第9页。949-964，1993年。[4] 去吧。，“ On - l i n e S of t wa r re V er s io n C h n ge “ ， Ph D th e si s ， Dep artmentofComuterSci encean dEn g i n e e r i n g ， In d i a n In s t i t u t e of Te c h n o l o g y ， Ka n p u r ， 19 9 4 .[5] Tennenhouse D例如，主动网络研究综述，IEEE通信杂志，第35卷，第1期，第80 -86页。1997年1[6] Hjalmtysson G.，格雷河，Dynamic C++ Classes：A lightweight mechanism to updatecode in a running program，Proc. of USENIX Annual Technical Conference，pages 65-76，Berkeley，USA，June 15-19 1998.[7] 马 吉 ·J 克 莱 默 ·J ， Sloman M. ， Constructing distributed systems in conic ， IEEETransactions on Software Engineering，15（6）：663-675，1989.[8] 布拉德伯里，小科迪丁格尔·J Wermelinger M.，动态架构的形式规范分类，ACMSIGSOFT 2004第12届软件工程基础国际研讨会，2004年，10页。[9] 薇拉·J Perrochon L.，拉克姆湾C.的方法，动态软件系统基于事件的执行体系结构。第一次IFIP软件架构会议。1999年2月22-24页。德克萨斯州，圣安东尼奥[10] H icksM. ，“DynamicSotwareUpdatitingg“P h D thesis，UniversityofPennsylvania，Aug 2001.[11] Pasteels S.，Desmet L.，Janssens N.，Mahieu T.，Verbaeten P.，自适应并发：DMonA架构，在Garlan D.，克莱默·J，沃尔夫·A编者，Proceedings of the First WorkshoponSelf-HeealinggSystems（WOSS' 02），第43 - 48页，C h a r le s t o n，SC，U S A，2002。[12] Medvidovic N.，泰勒河，澳-地N.，软件体系结构描述语言的分类和比较框架，IEEE软件工程学报，26（1）：70-93，2000年。[13] 奥雷齐P.，软件体系结构运行时修改中的问题技术报告UCI- ICS-96-35，加利福尼亚大学，2008年8月。一九九六年。[14] 奥雷齐P.，泰勒河，澳-地N.， 关于软件体系结构在运行时系统重新配置中的作用，可配置分布式系统国际会议论文集，第61页。IEEE计算机协会，1998年。[15] Pasteels S.，Matthijs F.，沃尔雷文斯D Verbaeten P.，DiPS：一种开发系统软件的统一方法。以. D. Williams，编辑，Proceedings-The Eigth Workshop on Hot Topics in OperatingSystems，第175页。卡尔斯鲁厄大学，IEEE计算机学会，2001年。[16] Malabarba S.，潘迪河，格拉格·J Barr E.，巴恩斯，对类型安全动态Java类的支持，ECOOP 14，第337-361页，2000年6月。M. Niamanesh等人/理论计算机科学电子笔记159（2006）227239[17] Satyanarayanan M.，普适计算：愿景和挑战，IEEE PCM，2001年，第10页。10 - 17[18] 布鲁姆·TDay M.，Argus中的重新配置和模块替换：理论与实践，IEE Software Engineering Journal，8（2）：102-108，1993。[19] 法纳姆·T舒伯特， 灵活的协议栈框架：设计，验证和性能，2003年软件定义无线电技术会议和产品博览会论文集。特别提款权论坛2003年。