没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记229(2009)133-153www.elsevier.com/locate/entcs基于半环定时约束的异步开放分布式系统协调岳宇,任尚平1伊利诺伊理工学院Chicago,IL60616,USA卡罗琳·塔尔科特2SRI InternationalMenlo Park,CA 94025,USA摘要对于异步和开放的分布式系统,动态性,开放性和严格的服务质量要求提出了巨大的挑战,建模和开发这样的系统。行动者-角色-协调者(ARC)模型是为了应对这些挑战而提出的。模型中的角色概念通过提供参与者行为的抽象来解决动态性和开放性问题。在本文中,我们专注于协调演员和角色,通过基于事件的时间约束的基础上的消息操纵。此外,将不同类型的时间约束推广到基于半环的约束结构中,并利用闭半环上的全对极值路径算法导出最严格的约束,这些约束是原始约束集的逻辑蕴涵.导出的隐式约束进一步用于测试约束包含和决定时间约束集的可行区域之间的交集。ARC模型和基于半环的时序约束模型的集成使用Maude,重写逻辑语言原型。我们进一步使用所提出的方法来解决餐厅用餐哲学家的问题,并说明了表达的ARC和基于半环的时间约束模型的外源性和组合协调的开放系统。保留字:协调模型,时间约束模型,ARC,Maude1引言嵌入式设备的激增和无线网络技术的显著进步导致了新的应用,这些应用涉及越来越多的异步交互的对象的动态变化系统。这些对象通常必须一起满足多种类型的服务质量(QoS)1电子邮件:{yyu 8,ren}@ iit.edu2电子邮件:clt@cs.stanford.edu1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.06.033134Y. Yu等人理论计算机科学电子笔记229(2009)133要求.因此,需要一种新的范例来降低这些应用程序的复杂性并简化其开发。将异步和开放分布式应用程序视为协调和并发计算的组合,可以简化协调和计算,并允许更高级别的抽象。然而,只有满足以下两个基本要求,才能充分实现这些优点。首先,必须有一个协调模型,该模型关注约束条件下的协调,并且是分散的、外生的、可扩展的,并且能够处理动态并发计算,而本身不是动态的。其次,为了推理约束,必须提供一个能够统一表示这些不同类型约束的形式化模型。我们早期对协调模型的研究产生了一个分层协调模型,即行动者-角色-协调员(ARC)模型[26],该模型专门针对第一个需求。本文件旨在解决上述第二项要求。1.1相关工作协调是异步和开放分布式应用的一个重要范例。广泛的协调策略已被提出来捕捉这些应用程序的功能方面。在具有里程碑意义的调查[24]中,Papadopoulos等人得出结论,协调模型可以分为两类,数据驱动和控制驱动。Linda [16]及其移动扩展,Lime [25],KLAIM [13]及其随机扩展[14]代表数据驱动的类别;而IWIM或流形[2]代表控制驱动或“外源”类别。Tuple center [21]和ReSpecT [20]提供混合视图。控制驱动模型将功能实体视为黑盒,从而隔离了协调例如,抽象行为类型(ABT)模型[4]及其语言Reo [3]通过将计算和协调组件视为可组合的ABT来扩展IWIM。Reo的重点是连接器,以及它们施加在组件上的协调和通信模式,而不 是 作 为 被 协 调 实 体 ( coordinatees ) 的 组 件 此 外 , 在 Reo 的 定 时 数 据 流(TDS)语义中支持定时约束的指定一些控制驱动的模型,如带有ACC的TuC-SoN [22],CoLaS [11]和ROAD [10],通过组的概念解决了开放分布式系统ARC模型[26]将协调分为两个不相交的类别,即,角色内和角色间协调,并分别使用角色和协调器来抽象这些行为(参见第2节)。ARC模型中的坐标对象是Actor[1],它们是通过异步消息交换进行交互的计算实体。ARC中的协调是通过对协调参与者透明的空间和时间上的外生消息操纵(约束消息目的地和调度时间)来实现的。我们早期的论文[28]详细比较了ARC模型与Reo和Rexect Russian Dolls(RRD)[18]协调模型。Y. Yu等人理论计算机科学电子笔记229(2009)133135虽然消息的空间操作是通过基于角色策略将消息重路由到目的地的角色来执行的[26],但本文提出了一种用于指定和验证消息的时间操作的将时间概念纳入协调模型并不新鲜。Pa- padopoulos [23]将IWIM与时间并发约束编程[27]的工作结合起来;在[17]中引入了Linda的几个具有不同时间概念的扩展。本文不同于以往的工作,我们提供对时序要求的更高抽象,不依赖于任何规范时间限制的类型。半环已被提出作为一个框架,用于生成,组合和关联服务质量约束[6,12];并且它已被证明适用于基于组件的模型[7,29],其中连接器上的权重(表示QoS约束)以及它们的组合由半环建模。因此,通过半环来抽象不同类型的时间约束是很自然的。在本文中,我们使用约束半环来推广时间约束,更重要的是,我们研究了一组基于半环的时间约束所允许的可行域的性质。基于闭半环[15]的有向图极值路径问题求解算法允许我们导出一般形式的隐式时间约束。 这样的隐式约束是至关重要的,在比较可行的区域半环为基础的时间约束。1.2主要贡献本文的主要贡献是双重的。首先,将协调约束映射为基于半环的时间约束,研究了它们对行动者计算的影响。最短路问题的线性规划模拟允许我们给出实时情况下时间约束集的可行域之间包含关系的充要条件。 结果是毛皮-进一步推广到基于半环之间态射的基于半环的时间约束。其次,ARC模型和基于半环的时间约束通过Maude [9]规范语言集成,以建模开放系统的外生和可组合协调。我们使用一个典型的开放分布式系统的例子,哲学家餐厅[8],来说明这样的集成。1.3路线图本文的其余部分组织如下:对于自包含,第2节简要描述了ARC模型。 ARC模型的详细描述可以在[26,28]中找到。第3节讨论了基于半环的时间约束及其性质。第4节介绍了Maude中ARC模型和基于半环的时序约束的规范,并给出了一个例子来说明这种正式规范如何促进协调属性的推理。 最后,我们在第5节结束。136Y. Yu等人理论计算机科学电子笔记229(2009)133第二章行动者-角色-协调者模型角色-角色-协调器(ARC)模型[26,28]是一种基于角色的协调模型,其中角色是底层角色共享的一组行为的静态抽象。Actor模型[1]用于对分布式系统的底层计算进行建模角色的功能是协调其成员。这种类型的协调称为角色内协调。角色内协调是通过基于策略的消息重路由和同一角色内的参与者之间的重排序来实现的不同角色之间的协调,另一方面,角色间协调由协调员完成协调者约束角色然而,行为者和协调员对彼此是透明的。因此,行动者系统中固有的动态性对协调者是隐藏的此外,由于个体参与者根据其行为按角色分组,因此协调在大规模系统中变得更具可扩展性。图1描述了ARC模型。Fig. 1. 角色协调模型从被协调者的角度来看,协调是外生的,分布在角色和协调者之间。角色和协调员对事件的反应与行动者对信息的反应相同。当计算实体(参与者)和协调实体(角色和协调者)的公共状态发生变化时,它们都会发出事件。基于观察到的事件和它要维护的协调不变量,角色不仅做出关于其成员资格的决定,而且还做出关于成员集中的消息传递时间和位置的决定。协调是角色内策略和角色间约束的组合。角色间约束存储在分布式协调器中。如果一个角色受到多个协调员的约束,则必须满足来自不同协调员的约束的合取。如果一个参与者属于多个角色,则角色也存在类似的情况。 分区 行动者的集合,并最大限度地减少协调员之间的约束重叠 可以降低ARC系统的复杂度在ARC模型中,约束的表示是建立在与消息调度相对应的事件上的。作为说明性示例,考虑由三个传感器和决策单元组成的传感器系统,该决策单元聚集从三个传感器感测的数据(例如,通过投票机制)。显然,决策单元聚合数据的事件必须发生在原始数据Y. Yu等人理论计算机科学电子笔记229(2009)133137≺∈{∞}从三个传感器提供。此外,如果我们对三个传感器提供的数据有一致性要求,我们可以限制传感器提供数据的事件发生时间之间的差异(详见例3.1更具体地说,我们可以将优先约束和实时约束视为协调策略,执行以下内容:优先约束:考虑一个分布式系统,它有一组可扩展的事件E. 形式为ei的优先约束ej(ei,ejE)限制ei的发生先于ej 的发生。实时约束:考虑一个具有一组观测值的实时系统, eventsE.定时 约束 的 的 形式 t(ei)−t(ej) ≤d(ei,ejE和dR++的)将事件限制为不晚于事件发生后的D个时间单位发生。虽然时间约束和约束满足在实时社区中得到了广泛的研究,但这些研究是从资源(如处理器)可扩展性的角度进行的,并且集中在特定类型的约束上,而不是从编程语言和约束模型的角度。此外,由于ARC模型中的协调约束分布在协调员和角色之间,并且这些约束联合应用于受约束的参与者,因此我们必须有一种统一的方式来组合不同的约束集,并且之后能够正式推理组合和满足性。3基于半环的时间约束模型及其可行域包含如前所述,协调约束可以是分布式的,但需要联合应用于受约束的参与者;因此,对于一对事件,可能会有多种类型的约束强加给它们。对于重叠约束,通常存在可从给定约束集导出的隐式约束,其对事件对的约束比任何显式指定的约束更严格。然而,不同约束类型的存在使得隐式约束的推导复杂化。在这一节中,我们将优先和实时约束统一在基于半环的时间约束模型中,利用闭半环上的所有对极值路径算法来导出最严格的隐式约束,并发展关于基于半环的时间约束的可行区域的理论(包含和相交)。3.1基于半环的时间约束约束半环已被提出作为统一QoS约束的框架[6]。一个约束半环S是一个元组(A,B,B,0,1 B, ≤S),其中A是载体集,0,1∈A; B是交换的,结合的,幂等的,并有0作为它的单位; C是交换的,结合的,分布在C上,并有1作为它的单位元,0作为它的吸收元; ≤S是由A诱导的偏序138Y. Yu等人理论计算机科学电子笔记229(2009)133≤≤⊕ ∀ ∈≤⊕.ΣΣΣ一、二联系我们∈ θ {∞} ≥惠≤操作的等同性,即,a ,b A:a Sbi ab=b. 0是S的最小元素,1是S的最大元素。框架在约束系统状态之间的转换或组件之间的连接器方面的应用可以分别在[7]和[29]中找到下面是在协调参与者中应用约束半环的示例例3.1在第2节提到的传感器系统中,我们假设发送数据的三个传感器参与者的相应事件分别为e1、e2和e3。为了保证投票的一致性,我们使用如上所述的实时约束将三个事件t(e1)、t(e2)和t(e3)的发生时间之间的差异约束在一定范围内。 约束集 及其相应的约束矩阵在(1)中给出。t(e1)−t(e2)≤6,t(e2)−t(e1)≤6,t(e1)−t(e3)≤7,t(e3)−t(e1)≤3,t(e2)−t(e3)≤9,t(e3)−t(e2)≤14;D(0)=0 6 76 0 93 14 0(一)其中D(0)是由事件的下标索引的约束矩阵例如,由于约束t(e1)− t(e2)≤6,我们在D(0)中有d(0)= 6。在(2)中给出了D(0)的定义 约束集也可以表示为加权有向约束图,如图1所示。2(a),其中隐式约束可以由Floor-Warshall所有对最短路径算法导出。直觉,在(a)(b)(c)(d)图二、时序和优先约束图。给定约束集,约束t(e3)-t(e1)≤ 3和t(e1)-t(e2)≤ 6意味着约束t(e3)−t(e2)≤ 3 + 6 = 9。此外,这个隐含的约束也适用于与约束t(e3)− t(e2)≤ 14相同的事件对,因此我们有t(e3)− t(e2)≤ min(14,9)= 9。在 该示例中,实时约束可以自然地映射到约束半环(R + R {+∞},min,+,+∞,0 ∞,≥),其中R++是约束值的集合,min用于两个约束的并行合成,其中两个约束事件一致;并且+用于两个约束的顺序合成,其中在两个约束中存在在它们的符号上不同的公共事件。 +∞表示(ei,ej)不受约束3,而0表示最严格的约束。 R+ ∞ {+∞}上的序关系≥表示约束的严格性,a,b R++:aB一S b,即,约束值越小,约束越严格换句3.约束具有方向性。因此,(ei,ej)不受约束的事实并不意味着(ej,ei)不受约束。Y. Yu等人理论计算机科学电子笔记229(2009)133139≤⊕ ⊗ ⟨ ⊕ ⊗⟩联系我们D=≤i、j∞我-我.ΣΣΣ∞− ∞ { {\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}⟨{∞ −∞}∞{∞}∞⊕ ⊗ ⟨∪换句话说,我们说约束t(e1)-t(e2)≤b比约束t(e1)−t(e2)≤a,如果a≥b(或a≤Sb)。Q类似地,约束半环(true,false,false,true,S),其中falseS true,可以表示优先约束。 图2(c)和2(d)是两组不同的优先约束的例子,其中约束矩阵中的对应e ntry是true,当且仅当ei=ej(在图中表示为ei−→ej)或i=j。给定来自不同协调器的一组初始约束,重要的是要知道约束组合的含义,即,从给定的约束集导出的隐式约束。 有两种情况, 可能出现新的隐含约束,即,两个给定的约束在同一对事件上(约束图中的平行边),或者在具有不同符号的两个约束中存在共同的事件(约束图中的连接边)。 这两种情况分别对应于约束并行和顺序组合。相应地,半环A,0,1的与运算被用于这些运算。在此模型下,闭半环上的极值路径算法4[15]可以直接应用于导出所有约束事件对之间的隐式约束(附录A),其中集合上的初始矩阵D(0)外部观测量e i,i = 1,.,n表示为5(0)i、j如果i=j,则≤S的最大元如果i=j且(ei,ej)受约束,则(ei,ej)的约束值当ii=j且(ei,ej)不受约束时,≤S的最小元素nt(二)d(n)是对应约束图中ei和ej之间的路径长度n的传递闭包,因此是最严格的约束(关于S上)之间存在可从原始约束集导出的每个元素e i和e j。我们将所有对的极值路矩阵记为D。例如,在示例3.1中,用于导出隐式实时约束的Floor-Warshall算法是算法1(附录A)的特殊情况,其中分别用min和+代替i和i;并且d(0),i = 1,., n,设置为0,单位为+,所有其他无约束条目设置为+,单位为min。因此,我们认为,所有事件对之间的最严格约束如下:t(e1)−t(e2)≤6,t(e2)−t(e1)≤6,t(e1)−t(e3)≤7,t(e3)−t(e1)≤3,t(e2)−t(e3)≤9,t(e3)−t(e2)≤9;D=D(3)=0 6 76 0 93 9 0(三)4 一 关闭半环 需要的和是 关闭 超过 A.作为 一 反例,R+,min,+,+,0不是闭合的,因为无穷多个负元素的和是结果,其中不是R的元素+.R+、,min,+,+,0也是有问题的,因为min的单位元素,即,+ ,不再是+的吸收元素,违反了半环的定义。在这些情况下,算法1将不起作用。[5]不失一般性,我们假设每对事件最多有一个约束。如果在一个e ve nt对(ei,ej)上有多个约束,则可以使用≤ S操作并删除其他操作。.140Y. Yu等人理论计算机科学电子笔记229(2009)133{}--−→≺- − −3.2基于半环的时间约束集的可行域协调约束消除了系统的其他可能的计算。给定两组不同的约束C和CJ。通过证明C允许的计算包括CJ允许的计算,我们避免了针对不同的协调约束集重复检查计算。例如,考虑图1所示的两组优先约束2(c)和2(d),其中e 为ej表示eiej。图图2(c)的所有迹集Tc=e1e3e2e4,e1e3e4e2,e3e1e2e4,e3e1e4e2,e3e4e1e26; 2(d)允许迹集Td=e1e3e2e4,e3e1e2e4。显然,Td Tc。因此,如果图2(c)中的约束导致保证安全要求的消息传递顺序,2(d)也将保证相同的属性。类似地,实时计算的定时跟踪可以表示为定时数据流7[5]。满足给定的实时约束条件的所有定时数据流的集合是一个凸集,在本文中,我们将该集合称为(实时约束条件集合的)可行域。例如,图3(a)中示出了(1)中给出的实时约束集合的可行域,其边界用粗线标记(a) 约束集的可行域(1).(b)列入两个可行区域。图3.第三章。可行域和可行域包含。根据图3(a),表示约束的每个平面平行于向量z =(1)x1+(1)x2+(1)x3,其中向量x1、x2和x3表示分别是事件E1、E2和E3的时间轴。因此,为了便于讨论可行域包含,我们在 图 中 沿 z 方 向 观察空间。3(b). 我们可以看到,约束集(1)(灰色粗线)包括约束集(4)(黑色光线)。6由于ARC模型的同步事件控制机制在第2节中提到,并在第4节中详细介绍,事件顺序将指示相应的消息传递顺序。还要注意的是,虽然我们只约束了一个预定义的有限事件集,但包含所有事件的完整迹可以通过置换不受约束的事件来形成,并且包含关系仍然成立。 此外,假定系统是稳定的,则可以获得这样有限的约束事件集图7事件集E上的定时数据流是一对(a,α),其中a是具有来自E的元素的序列,α是一个单调递增序列,其元素来自R+ ∞ {+ ∞}。Y. Yu等人理论计算机科学电子笔记229(2009)133141.ΣΣΣ≤D=falsetruefalsetrue和DJ=falsetruefalsetrue(6)联系我们现在,考虑(4)中给出的另一组实时约束。t(e1)−t(e2)≤5,t(e2)−t(e1)≤3,t(e1)−t(e3)≤5,t(e3)−t(e1)≤2,t(e2)−t(e3)≤15;DJ(0)=05530152+∞0(四)约束集(4)的可行域可以被示出为包括在(1)的可行域内,如图3(b)所示。引理3.2与定理3.3一起表明,实时约束集的所有对最短路径矩阵都可以用于这种比较。引理3.2当所有事件对之间的约束被从算法1(附录A)导出的隐式约束替换证明:在附录B中给出了形式证明。Q例如,当约束条件为t(e3)−t(e2)≤14变为t(e3)−t(e2)≤9。定理3.3给定同一事件集上的两组实时约束C和CJ。 令它们对应的最严格隐式约束矩阵(即,所有对最短路径矩阵)分别为D和Dj。Cj的可行域包含在C的可行域中当且仅当D≥DJ(i,j:di,j≥DJi,j),其中e≥是定义在半环(R+{+∞},min,+,+∞,0,≥)上的序关系.证明:形式证明在附录C中给出。Q由于下面的注入,这个结果可以很容易地扩展到优先约束({true,false}, false,true,≤S)f(true)=0f(fa−ls→e)=+∞(R+{+∞}, min, +,+∞,0, ≥)(五)例如,图1中的两组优先约束的传递闭包矩阵。2(c)和2(d)是truetruefalsefalse真的假的真的假的真的假的其中d∈i,j或d∈i,j是false当且仅当i真的假的真的假的真的假的j和eid oes不先于ej。基于(true,false,,)上的排序关系,,假,真,S),我们有 DSDJ,因此本节开始时观察到的包含关系如下。对于一般的基于半环的时序约束,包含关系可以通过以下方式测试:[8]请注意,两个约束集的事件集不需要相同,以便两个跟踪集具有可比性。通过添加不受约束的事件,始终可以将两个事件集扩展为同一个事件集142Y. Yu等人理论计算机科学电子笔记229(2009)133≤(i) 应用具有特定约束半环的算法1以得到约束集的所有对极值路径矩阵;以及(ii) 利用约束半环上的序关系S确定所有对极值路矩阵之间的支配关系。根据引理3.2,对于定时约束集合的可行区域之间的交点,可以给出类似的结果。两个约束集的交集(不一定在同一事件集上)可以用于导出满足两个约束集的约束集。通过形成约束集的并集并将算法1与相应的约束半环一起应用来导出这样的交集。由于凸集的交仍然是凸的,所以可以得到类似的证明。4通过Maude集成基于ARC和半环的在本节中,我们使用一个规范的开放系统示例,哲学家餐厅[8],来说明ARC模型的表达能力以及ARC和基于半环的时序约束模型的集成。例4.1哲学家的餐厅:一家餐厅有一张桌子,上面有n把叉子和n个座位。餐厅里的顾客是m(m > n)个哲学家,如果有空位,他们可以坐下,如果没有叉子,他们可以随时站起来腾出当一个哲学家坐着的时候,如果他能抓住两把叉子,他就吃,否则他就想9。值得指出的是,该问题与经典的用餐哲学家问题不同,哲学家可以随时自由地加入或离开餐桌,从而为系统引入了动态性和开放性。此外,多个约束可能共存。例如,避免僵局的约束和对特定座位给予偏好的约束,这样坐在那里的哲学家总是先吃饭。这个问题可以用ARC模型自然地表达出来。更具体地说,在ARC模型下,哲学家和叉子都是演员。 两种类型的角色,即, 引入了seat角色和fork角色,以保护协调器的动态性:n个座位角色和n个叉子角色像哲学家吃饭的原始问题一样循环排列。哲学家和分叉演员可以随时加入和离开相应的角色。但是,任何角色在任何时刻最多只能容纳一个参与者。 为了简化演示而不丢失模型的相关特性,我们假设fork actors是静态的,即, 每个分叉角色拥有一个分叉参与者,并且成员资格不变。 另一方面,座椅9m > n的要求来自于[ 8 ]中的原始问题。然而,正如我们将看到的,这并不是说在哲学家们被允许吃饭之前,桌子应该是满的,因为避免死锁的优先约束实际上可以完全分配给每个哲学家。然而,哲学家之间的约束,比如我们引入的偏好约束,可能会阻止某些低优先级座位上的哲学家在桌子没有坐满的情况下吃饭。但这并不会导致livelock,因为哲学家总是可以自由活动的优先级更高的座位Y. Yu等人理论计算机科学电子笔记229(2009)133143角色引入多个协调器来对角色施加协调约束,以便可以强制执行无死锁和首选项等属性。在本节的剩余部分,我们将详细介绍如何使用ARC模型结合基于半环的时间约束来解决哲学家就餐的餐厅问题。我们使用Maude [9],一个非常适合指定和验证分布式系统的工具,来编写规范并验证无死锁和优先级属性。4.1演员在Maude在Maude中,分布式系统状态被建模为参与者和消息的多集(配置)[9]。配置是由从单例对象(演员)和消息开始的多集联合形成的。这是由以下Maude声明形式化的11排序配置.子排序对象消息<配置。opnone:->配置。op:配置配置->配置[ctor aslogid:none]。典型的参与者系统配置具有以下形式演员_1. actor_m msg_1. msg_n每个参与者都有一个id、一组属性,以及用于缓冲传入和传出消息的入队列和出换句话说,一个actor对象的形式是[id :cid|属性|in:inQ,out:outQ]在参与者系统中,消息顺序没有指定,只要消息的目标与接收参与者匹配,就可以在任何时候传递消息,如下面的消息传递重写规则(rl)rl[in]:[id :cid|属性|in:inQ,out:outQ] msg(id,id',cv)=> [id:cid|属性|in:(inQ,msg(id,id',cv)),out:outQ ].类似地,下面的重写规则规定,当消息位于参与者的输出队列的头部时,rl[out]:[id :cid|属性|in:inQ,out:(msg(id ',id,cv),outQ)] => [id:cid|属性|in:inQ,out:outQ]msg(id ',id,cv).在没有协调约束的情况下,Maude的传统餐饮哲学家系统的餐厅的初始配置如下[o(“p-i”):Phil|状态:1,R:(o(“f-i”),0),L:(o(“f-j”),0)|in:nil,out:nil][o(“f-i”):Fork|获得?:虚假|输入:无,输出:无]其中i= 1,.,n,如果i n,则j=i + 1,如果i = n,则j = 1。哲学家表示他是在等待就座(0)、坐下思考(1)、等待两个叉子(2)还是吃饭(3);R/L中的属性表示哲学家10虽然在本例中,每个角色在任何给定时间最多有一个成员,但通常情况下,一个角色可能有多个参与者。11在Maude中,sorts用于声明类型,排序上的子排序关系与这些排序的预期模型中的元素集合上的子集关系平行,运算符用关键字op声明,并且asort,asort和id可以被声明为指定等式公理,分别表示结合性,交换性和恒等式还要注意,本文中使用Object表示参与者144Y. Yu等人理论计算机科学电子笔记229(2009)133−→fork actor 很明显,在上述规范中,开放性和动态性不受支持,因为哲学家演员需要明确地知道他们左边的名字,右叉演员因此,如果哲学家被允许离开、加入或移动,他们将不知道发送请求或释放消息的正确的fork actors。此外,死锁配置如下(当m=n=3时)[o(“p1”):Phil|状态:2,R:(o(“f1”),2),L:(o(“f2”),1)|输入:无,输出:无][o(“p2”):Phil|状态:2,R:(o(“f2”),2),L:(o(“f3”),1)|输入:无,输出:无][o(“p3”):Phil|状态:2,R:(o(“f3”),2),L:(o(“f1”),1)|输入:无,输出:无][o(“f1”):分叉|获得?: 真正|输入:(msg(o(“f1”),o(“p2”),“请求”)),输出:无][o(“f2”):分叉|获得?: 真正|输入:(msg(o(“f2”),o(“p3”),“请求”)),输出:无][o(“f3”):分叉|获得?: 真正|输入:(msg(o(“f3”),o(“p1”),“请求”)),输出:无]可以达到P1保持请求F2的F1,P2保持请求F3的F2,以及P3保持请求F1的F3。在Maude中,死锁配置可以通过search命令找到。从上面我们看到,需要一些额外的机制来允许动态性和协调约束是必要的,以避免僵局。4.2角色Maude角色在Maude中被建模为响应式俄罗斯娃娃(RRD)模型的特殊情况,其中分布式状态被嵌套,可以被视为分布式汤而不是演员和消息的汤。 两 在ARC情况下,层次嵌套配置由角色(元层次对象)和角色消息(元层次消息)组成,角色的配置由协调的参与者(基本层次对象)和参与者消息(基本层次消息)组成。角色的形式是[rid:cid|属性,{配置} |in:inQ,out:outQ]其中配置是参与者和消息的混合汤在一个角色中定义了三成员更改、向上和向下;以及它们对应的条件重写规则(CRL)非正式地表示如下• crl[membership-change]保证每个参与者在任何时候只能扮演一个角色。为了让一个参与者改变它的角色成员资格,它离开s一个角色R(导致R的状态改变),成为s一个具有另一个行为的参与者(导致自身状态改变),并加入s另一个角色RJ(导致Rj的状态改变)。 leave、become和join操作必须以原子方式完成,以避免出现悬空的 参与者。↓离开=成为加入↑• CRL[up]解决了开放性问题:它从角色中的配置中提取消息到角色因为演员有时是匿名的Ratts1RAJTTS2AATTS3RAJTTS5Ratts4AATTS6Ratts4AATTS3RAJTTS2Ratts4AATTS6RAJTTS2Y. Yu等人理论计算机科学电子笔记229(2009)133145在开放系统中,角色负责重新路由发送的消息 由它下面的一个演员到一个适当的目的地角色。• crl[down]解决了角色内协调问题:它将消息从角色的输入队列中取出,并将其放入角色的配置中。 由于角色下的参与者共享共同的行为,并且也有差异,因此角色负责选择适当的参与者来处理发送给它的消息。在crl[up]和crl[down]中使用的重路由消息的特定策略应该在特定的角色实例中定义。当角色被添加时,协调是基于角色而不是基于特定的行为者。在哲学家用餐的餐厅问题中,角色可以用来模拟“桌子的座位”,以解决开放性和动态性,因为“座位”是稳定的,但随着时间的推移可以被几个不同的哲学家占据。现在,系统的初始配置变为[o(“default”):DefaultRole|{1}[o(“p-k”):Phil|状态:0,R:(o(“n/a”),0),L:(o(“n/a”),0)|...]个文件夹|...][o(“S-i”):座位角色|占用:假,R:o(“F-i”),L:o(“F-j”),{none}|. . . ][o(“F-i”):ForkRole|{[o(“f-i”):Fork|获得?:虚假|......】的情况。个文件夹|......】的情况。其中i= 1,.,n,j=i + 1,如果in,且1,如果i=n,k= 1,.,m和每个"in:nil,out:nil"的出现被替换为".“为了简单起见。DefaultRole包含等待就座的参与者(状态:0)。原子角色成员关系更改规则crl[membership-change]以及Phil的become、SeatRole的join和DefaultRole的leave确保当一个哲学家将其状态更改为1(思考)时,只要角色的occupied属性为false(原子地更改为true),它就可以坐在某个SeatRole中;哲学家离开座位的机制是类似的。 还要注意,philoso- pher现在不需要知道它的左分叉和右分叉; SeatRole将根据它的R和L属性将消息重新路由到正确的ForkRole。比如说,参与者级别soup中的msg(o(“n/a”),o(“p1”),“request”)将被重新路由 为 角 色 级 别 soup 中 的 msg ( o ( “F1” ) , o ( “S1” ) , “request” ) 。SeatRole记录处理回复消息所需的信息可以看出,开放式-性和动态性问题是使用角色来解决的,而不需要对定义的原始参与者进行任何更改。4.3Maude中基于半环的时间约束协调器在哲学家餐厅用餐 问题, 我们也 需要 约束, 避免 僵局 和 实现 偏好要求. 一古典主义 溶液 的 避免 僵局 是到 打破 的 对称通过让每个哲学家先拿起叉子 与 的 低 number. 这 可以 被做通过限制msg(o(“S1”),o(“F1”),“可用”)(o(“F1”)'s答复 到msg(o(“F1”),o(“S1”),“request”),如果o(“F1”)尚未被获取)被取消-有肝的beforemsg(o(“F2”),o(“S1”),“request”).此外,可以通过将“可用”消息限制为在来自所有其他SeatRole的“请求”消息之前传递的o(“S1”)来强制执行在下文中,我们将讨论-146Y. Yu等人理论计算机科学电子笔记229(2009)133讨论了协调器如何通过外部的基于事件的消息控制来强制约束。4.3.1Maude中基于半环的时间约束在Maude中,半环的概念被定义为泛函理论[9],而算法1(附录A)可以被定义为一般半环上的参数化泛函模块,其中fmod MATRIX实现算法1(op APXP)。fmod矩阵{X:: SEMIRING}是pr(ARRAY *(sort Entry{X,Y}to Entry{Y},sortArray{X,Y}to Matrix{Y})){IndexPair,X}。op APXP(_,_):Matrix{X} Nat -> Matrix{X}....... *由于页面限制endfm而省略因此,偏序约束模型可以被定义为从一般半环A,0,1A到布尔代数A,0A到布尔代数 A,0查看BOOL-SEMIRING从SEMIRING到BOOL是排序Elt到Bool。第1话真的OP 0为false。op X:Elt * Y:Elt到term X:Bool和Y:Bool。OPX:Elt + Y:Elt到术语X:Bool或Y:Bool。恩代夫并且相应的约束矩阵可以通过使fmod MATRIX取特定半环的参数BOOL-SEMIRINGfmod布尔半环矩阵是保护矩阵{布尔半环}*(sortEntry{BOOL-SEMIRING}到BoolMatrixEntry,将Matrix{BOOL-SEMIRING}排序到BoolMatrix,opempty到zeroMatrix)。endfm在R+∞ {+∞}, min, +,+∞, 0 ∞上的实时约束可以类似地定义4.3.2协调员在Maude如果没有协调,参与者/角色遵循第4.1节中的通信机制rl[in]和rl[out]。然而,对于外生协调,消息msg(id,id ',cv)的对应事件in(id,例如,给 定 时 序 约 束 模 型 , 在 偏 序 约 束 下 , 协 调 器 是 四 重 [APXP ( M ) ] ,|ESET|EMAP| n],其中M是由1到n索引的初始约束矩阵,m是已经发生的感兴趣事件的索引集合(并且满足M中的约束),emap是从感兴趣事件集合到索引集合的映射,并且n是感兴趣事件的数量(也是M的维度)。因此,当协调器存在时,消息不能像rl[in]中那样自由传递;相反,为了将消息传递到其目标参与者,我们首先需要检查消息传递的相应事件是否受到约束,如果没有,则传递消息crl[in-uncoord]:Y. Yu等人理论计算机科学电子笔记229(2009)133147[id :cid |atts| in:inQ,out:outQ] msg(id,id',cv)[M|ESET |EMAP|n 个]=>[id :cid |atts| in:(inQ,msg(id,id',cv)),out:outQ][M|ESET |EMAP| n] if emap[in(id,id',cv)] == undefined.当事件受到约束时,我们必须检查事件是否满足所有约束在Mcrl[in-coord]:[id :cid |atts| in:inQ,out:outQ] msg(id,id',cv)[M|ESET |EMAP|n 个]=>[id :cid |atts| in:(inQ,msg(id,id',cv)),out:outQ] [M| insert(emap[in(id,id',cv)],cv)|EMAP|n个]if(tell([M|ESET|EMAP|n],在(id,id ',cv))中)。其中optell([M|ESET|EMAP| n],e)决定是否emap[e]的所有前趋都已经出现(在n中)12。out的协调机制与in的定义是对称的。在哲学家用餐的餐馆问题中,为了避免僵局,我们只需要把下面的协调员放在上面定义的角色汤中。这导致以下初始配置(当m=4和n=3时)[APXP([1,2]|-> true;[3,4]|-> true;[5,6]|-> true,6)|空|(in(o(“S1”),o(“F1”),“available”)|-> 1,out(o(“F2”),o(“S1”),“request”)|-> 2,in(o(“S2”),o(“F2”),“available”)|-> 3,out(o(“F3”),o(“S2”),“request”)|-> 4,in(o(“S3”),o(“F1”),“available”)|-> 5,out(o(“F3”),o(“S3”),“request”)|-> 6)| 6][o(“default”):DefaultRole|{1}[o(“p1”):Phil|状态:0,R:(o(“n/a”),0),L:(o(“n/a”),0)|......】的情况。[o(“p2”):Phil|状态:0,R:(o(“n/a”),0),L:(o(“n/a”),0)|......】的情况。[o(“p3”):Phil|状态:0,R:(o(“n/a”),0),L:(
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)