没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记113(2005)65-83www.elsevier.com/locate/entcs实施并发时态行为Doron Peled和Hongyang Qu英国考文垂大学计算机科学系摘要验证软件的结果通常是一个“反例”,即,不满足规范的行为的动作和状态的列表。为了了解失败的原因,通常需要针对实际代码测试这样的执行。 这样我们 我们还可以找出我们是否有一个真正的错误或“假阴性”。 由于非决定论在并发代码中,即使没有进行抽象并且我们以规定的初始状态开始执行,也不能保证恢复实际程序上的错误行为。当测试人员必须证明一个可疑的场景实际上可以被执行时,他们也面临着类似的问题。这样的场景可能涉及一些复杂的调度,因此演示起来很虚幻。我们在这里描述了一个程序转换,它以这样一种方式转换程序,即它可以被验证,然后进行反向转换以测试可疑行为。由于转换意味着对原始代码的更改,因此我们努力将其对原始程序的影响降到最低。关键词:行为监控,并发,反例分析,模型检测,不确定性,时序逻辑,测试。1介绍验证用于查明软件中是否存在错误。验证过程的结果通常通过列出原子动作和全局状态的序列来给出,这些动作和全局状态包括不满足规范的行为,称为反例。由于通常不是代码本身被验证,而是它的一个模型,因此遇到“假阴性”的可能性不可忽略。也就是说,不符合实际程序行为的执行。由于假阴性经常发生,因此需要仔细检查可疑的错误执行。不幸的是,并发程序的执行在手动分析时可能相当长和复杂。当测试人员被要求证明在代码的某个运行过程中确实发生了某些可疑行为时,他们也会给定一个出现在1571-0661 © 2004由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2004.01.03466D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65对于一些不常见的调度,测试人员可能很难强制被测程序执行它。我们在这里感兴趣的是使被检查的代码根据给定的可疑执行行为,这可能是验证或测试的结果。我们希望能够在测试或验证的代码的上下文中重建和检查这种行为。由于与并发执行事件相关的不确定性,我们不能保证在不对检查的软件进行某些修改的情况下恢复给定的执行。因此,我们专注于最大限度地减少对原始代码的更改的影响我们建议一个简单的和自动的转换,可以应用于代码,以恢复可疑的行为。我们的方法为验证工程师或测试人员提供了一种工具,用于检查和证明代码中错误的存在。我们对建议的软件转换施加以下约束:• 尽量减少对软件的更改。我们希望尽可能少地偏离原计划。• 在选择适当的初始状态时,严格执行所需的执行当未选择此初始状态时,其他执行仍然可用。• 执行的动作之间的任何并发性或独立性都被保留。我们正在重建一个并发执行,而不是一个完全同步的一个,其中一个动作被执行的时间。因此,我们的解决方案是分布式的,而不是集中式的。• 保留选中的属性。并不是所有具有与原始反例相同的并发结构的执行序列都必须满足相同的时间属性。• 将构造应用于无限执行的有限表示,即,一个最终的周期序列。尽管我们的转换将针对给定的(类似Pascal的)语法进行演示,但它是独立于语言的。我们将在第7节讨论一些语言和实现问题。我们的架构如图1所示。为了执行验证,程序被转换成一组有限的原子动作。这种转换还可以包括简化已验证模型的抽象。转换的另一个组成部分是依赖关系,它包括不能同时执行的动作对,例如,这是由于使用了共享变量或消息队列。最后,翻译的第三个组件是带注释的代码,它具有指向文本中各个位置的指针,特别是与原子执行动作相关的代码文本的开始和结束。这些指针在以强制执行可疑行为的方式添加新指令(或更改现有指令)时非常有用。D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6567并发程序行动规格反例Modifiedcode依赖关系注释程序Fig. 1. 系统架构一些相关的工作集中于为消息序列图创建测试用例。在[9]中,证明了构造这样的测试用例的困难。(But注意,消息序列图的模型有些不同,因为它允许所有进程根据一个场景或另一个场景全局地决定行为;这是该模型本身需要分析的特性[2]。在[15]中,提出了一种基于添加协调消息的解决方案。我们的解决方案的差异,因为它不强加的变化,限制系统的并发性。[13]中建议了用于监视并发程序执行的转换。 我们的贡献是在分析这种转换的框架内的偏序语义和执行序列之间的等价性。我们还展示了如何处理最终周期序列(监控有限,但不是先验界,时间长度),以及如何保持检查属性。2预赛作为一个运行示例,考虑Dekker 图3中显示了该流程图。 此图使用PET测试系统自动从代码中获得[7]。假设我们以turn= 1开始执行。下列执行当过程P1进入临界区时,可以得到σ1每一行代表一个动作的发生。它由序列号、执行过程,后面是根据图3所涉及的流程图节点的编号(在括号中),后面是与操作对应的文本。对应于条件的操作后面还跟着"在这里,两个过程都通过分别将c1和c2设置为0(第7行和第8行)来发出它们想要进入它们的临界区的信号。因为turn= 1(在第11和12行检查turn),所以进程P1的优先级高于进程P2。这意味着进程P2通过将c2设置为1(第13行)而放弃尝试,而进程P1坚持等待c2变为1(第14行检查),然后进入其临界区(第15行)。1:(P1(0):开始)2:(P2(0):开始)3:[P1(1):c1:=1]代码转型翻译+抽象验证器68D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65P1::c1:=1;While true dobeginc1:=0;当c2=0开始时,boolean c1,c2 ;integer(1.. 2)转弯;P2::c2:=1;While true dobeginc2:=0;当c1=0开始时,如果回合=2,则开始c1:=1;while turn=2 dobegin/* no-op */end;c1:=0endend;/*临界区1*/c1:=1;turn:=2end如果turn=1,则开始c2:=1;while turn=1开始/* no-op */end;c2:=0endend;/*临界区2*/c2:=1;turn:=1end图二. 德克尔4:[P2(1):c2:=1]5:P2(12):true>yes 6:P1(12):true> yes 7:[P1(2):c1:=0]8:[P2(2):c2:=0]9:P1(8):c2=0?> 是的10:P2(8):c1=0?>yes 11:P1(7):turn=2?> no 12:P2(7):turn=1?>是13:[P2(3):c2:=1]14:P1(8):c2=0?> 是的15:[P1(9):/* 临界-1 */]在相同的初始状态下可以得到不同的执行σ2进程P2将c2设置为0(第7行),表示它要进入临界区. 它比进程P1更快,并且还设法检查c1是否D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6569是0(第8行),然后P1将其从1更改。因此,P2进入其临界区(第9行).1:(P1(0):开始)70D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65图三. 德克尔2:(P2(0):开始)3:[P1(1):c1:=1]4:[P2(1):c2:=1]5:P2(12):true>yes 6:P1(12):true> yes 7:[P2(2):c2:=0]8:P2(8):c1=0?> 没有9:P2(9):/* critical-2 */>程序的(全局)状态是一个函数,它为程序变量赋值,包括程序计数器。我们假设程序可以被翻译成一组原子动作A。每个原子操作都由一个条件和一个多重赋值(改变一些程序变量的值有些条件隐含在程序的文本中,例如,检查程序计数器是否具有特定值。同样,多重赋值的一部分不会出现D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6571⊆×直接从程序的代码;特别地,每个动作包括对程序计数器变量的改变。例如,图3中进程P1中节点3的转换可以具有条件pc1 = 3和多重赋值(pc1,c 1):=(5, 1)。也就是说,pc1得到值5,c1得到值1。这里pc1是进程P1的程序计数器.动作在不同的进程P之间划分。我们用A(pi)表示属于过程pi∈P的A的作用。执行序列(或行为)σ是状态和动作的交替序列s1,a1,s2,a2.α n−1sn,其中每个状态s i+1,对于1 ≤i< n,通过执行动作α i从其前一个状态s i获得。这意味着动作α i的条件在s i中成立,并且与α i相关联的多重赋值被应用于s i,导致状态s i+1。给定一个固定的初始状态s1,并且动作是确定性的(注意,这并不意味着代码是确定性的,因为可以启用在相同的状态下),我们可以等价地将执行表示为then对α1α2... α n− 1依赖关系D A A是动作上的一种自反对称关系.它捕获了不能同时执行操作的情况因此,(α,β)∈D,当• α和β在同一过程中,或• α和β使用或定义(更新)一个互变量1。这种依赖关系对应于第3节中使用的带有共享变量的并发程序的执行模型。不同的依赖关系可以为其他并发模型定义,例如,第5款.设σ是从A开始的动作序列。我们可以用k来索引α在σ上出现的第k次,得到αk。我们称αk为α在σ中的第k次出现。因此,代替动作序列ααβαβ,我们可以等价地将σ表示为发生序列α1α2β1α3β2。我们表示出现一个序列σ乘Eσ。在上面的例子中,Eσ={α1,α2,α3,β1,β2}。定义序列σ上出现的事件之间的二元关系→σ。让当下列条件成立时,序列σ上的αk→σβl(i) αk在σ上出现在βl之前。(ii) (α,β)∈D.因此,αk→σβl意味着α和β指的是同一个变量或属于同一个过程。因此,αk和βl不能同时执行。根据顺序σ,改进的顺序为αkβl。 L et→σ是→ σ的传递闭包完备化。这是一个偏序,因为它是传递的,对称的和不相关的。执行σ的偏序视图是<$Eσ,→<$σ<$。我们希望根据1取决于硬件,我们可以允许α和β是并发的,即使两者都只使用一个互变量,但它们都没有定义它。72D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65→→→123456789见图4。 后一次执行关系σ。 然而,这种关系包含许多对,这意味着大量的同步。这可能是不够的,以实现和诱导许多变化,从原来的代码。我们可以通过删除属于同一过程或在它们之间有一个相关(根据→σ)发生链的动作对αk→σβl来约化→σσ出现之间的约化关系用~σ表示。它被定义为满足以下条件的(唯一)关系:(i) ~σ的传递闭包是→σ。(ii) 不存在元素αk,βl和γm使得αk~σβl,βl~σγm和αk~σγm。由于并发程序的物理性质,按照~σ序保持同步是足够的。根据σ的其余顺序由传递性和顺序性保证, 个别过程。计算~σ from→σ的关系很简单。我们可以采用Floyd-Warshall算法[6,25]来计算→σ的传递闭包。每次发现一条新边作为现有边的组合时(即使该边已经存在于σ中),它也会被标记为被删除。最后,我们删除所有标记的边缘。图4包含与本节前面的执行序列σ2相图中的节点根据σ2中列出的序列号进行标记。从节点3到节点8的箭头对应于不同进程对同一变量(c1)的更新和使用(并且根据~σ),而其余箭头对应于属于同一进程的动作之间虽然一个执行是由一个序列表示的,但我们通常对等价执行的集合 为了定义执行之间的等价性,令σ|α,β是序列σ的投影,只保留α和β的出现。则σ<$Dρ当σ|α ,β= ρ|对于每对相互依赖的动作α和β,即,当(α,β)∈D.这也包括α=β的情况,因为D是自反的。这种等价也称为偏序等价或迹等价[14]。它将序列σ和ρ联系起来,原因如下:• 在σ和ρ中出现相同的情况。• 单个过程的动作的发生是相互依赖的(所有的动作都是相互依赖的)。D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6573单个进程的不同部分使用并定义相同的程序计数器)。因此,每个进程根据σ和ρ以相同的顺序执行相同的操作。这表明过程是顺序的。• 来自不同进程的任何一对依赖动作都不能并发执行,必须按顺序执行。根据σ和ρ,它们的相对顺序是相同的。• 没有被某个相互依赖的动作序列彼此分离的独立动作的发生可以并发执行。它们可能以不同的顺序出现在痕迹等效执行中。在强制执行时,我们不希望强加新的同步,这些同步将对可以并发执行的操作进行排序。另一种看待这一点的方式是,区分两个等价的执行只能通过全局时钟来完成,并且对并发系统进行昂贵且不自然的实验。偏序视图作为更传统的交织(线性)语义的替代方案被广泛研究[17,21]。交错语义的优点是,它可以用比偏序语义所需的工具更简单的数学工具(如线性逻辑[20]或布尔希自动机[23])来处理。另一方面,偏序语义给出了一个更直观的并发表示最近对并发系统的偏序表示的兴趣源于ITU消息序列图标准的流行[11]。我们提出的理由,恢复的并发执行相关的行为,而不是一个完全同步的线性执行,给出了另一个动机使用偏序语义。我们在执行序列上定义了几个运算符,表示为动作序列(因此,在这种情况下,忽略状态):HideB(σ)从集合B中移除(投影)动作后的序列σ。ClD(σ)通过在独立的相邻动作之间进行重复排列而从σ获得的序列集,即,与D无关也就是说,Cl D(σ)={ρ|ρDσ}。Lin(E,<)部分阶数的线性化(对全阶数的完备化)的集合.0;Vij:=Vij− 1设S(pi)≠A(pi)是过程pi中发生的动作的集合在σ中的一个事件和通过~σ与另一个过程中的一个动作的发生相关。因此,S(pi)是具有需要被同步的一些(但不一定是所有)发生的动作。因此,我们需要检查我们当前是否正在执行一个需要同步的动作α∈S(Pi)。设counti为进程pi的一个新的局部计数器变量。我们在每次S(pi)的动作发生之前递增counti添加代码(2)counti:=counti+1紧接着是α的代码。我们将iαk定义为在αk之前出现在σ中的S(pi)的出现次数。我们可以很容易地根据序列σ计算iαk。这也是变量counti在转换后代码执行期间的值,由于(2)中的递增语句。设αk~σβl,其中α∈A(pi),β∈A(pj),pj在αk添加以下代码:p j。 然后我们(3)如果计数i=iαk,则自由ij我们在βl添加以下代码:(4)如果计数器j=jβl,则等待ji的符号iαk和jβl应替换为适当的con-由σ计算的常数。 由于一个动作可能参与同一序列上的多个事件,因此可以添加类似于(3)和(4)的用于多个事件的不同代码。 我们可以通过不对在给定执行σ中只出现一次的动作进行计数(也不检查count i的值)来优化转换。类似地,我们也不需要计算所有需要相同的转换代码的动作另一个考虑因素是确定何时执行完毕。我们可以将每个进程pi的执行中最后出现的动作α加到S(pi)上。因此,我们在counti中也计算α的出现次数。设iαk是α在σ中最后一次出现时的计数i的值。我们在α的代码之后添加以下代码:(5)如果计数器i=iαk,则停止pi(Pascal中没有halt语句,所以它是使用goto实现的。同样,如果流程的最后一个动作是唯一出现的α,我们不需要计数。在这里,我们可能遇到并执行一个不在σ中的,并且依赖于另一个没有在σ中最后一次出现的过程的动作的pi的后续动作。这可能会导致一种与我们所研究的行为完全不同的行为。76D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65为了最小化额外代码对可疑执行之外的执行(或在WMD下与之等效的执行)的影响,我们使用额外的标记检查i(对于每个进程pi),其值在整个执行过程中保持只有当我们在我们想要重复可疑行为的模式下运行代码时,此标记才为真因此,除了执行的特殊初始状态之外,我们还强制检查每个进程pi的i=true。在所有其他情况下,我们最初设置checki=false。当checki=false时,即使我们根据可疑行为的初始状态开始执行,程序也可能遵循与可疑行为不同的执行。请注意,我们选择不检查一个全局变量,因为不同进程对它的不同引用是相互依赖的,因此会违背我们保持执行的并发结构的目标。现在,如果Code是由我们的转换生成的代码,如(2)如果检查i,则编码一些代码简化可能已经到位,例如,检查counti和checki的值可以组合成单个if语句。如上所述,将转换产生的附加代码建模为合并到原始代码的原子操作中是不现实的。结果代码的行为更好地对应于添加新操作。然而,我们已经仔细地构造了它,使它包含了大多数对进程来说是本地的附加操作,即,独立于其他进程的唯一的附加依赖动作是Free ij和Waitji形式的。然而,当这样一个对被添加时,Freeij将被某个作用αk所 引导 , 而 Waitji 被 一个 作 用βl 所 引导 , 使 得αk→σβl 。 这 些 动作(Freeij和Waitji)的依赖性与现有动作(αk和βl)的依赖性相同。此外,可以证明,在αk或自由ij(都在A(pi)中)之间不可能出现依赖于来自pj的作用的任何作用。类似地,Waitji和βl(均来自pj)的出现之间的所有出现都独立于来自pi的动作。因此,即使我们以更现实的方式打破转换后程序的操作,程序的并发结构也得到了我们可以将这个问题形式化为偏序语义下的action refinement [24]然而,我们更喜欢保持在直观的水平,而不是在理论上的形式之一的介绍先进的笔记。 为了避免引入不必要的延迟甚至死锁,我们必须保证Waitji的实现不能阻塞进程p i。具体地说,如果V ij为0,而进程pj正在等待它变为1,则进程p i需要能够前进,这将允许它最终递增V ij。这种阻塞可能存在,例如, 在一个单处理器多任务并发程序上,等待ji执行忙等待V ij变为1,调度程序对处理p i是不公平的。有趣的是D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6577⊃boolean c1,c2,check1,check2;boolean V12 initial 0;integer(1..2)转弯;P1::c1:=1;if check1 then V12:=1;While true dobegin如果检查1,则停止P1;c1:=0;当c2=0开始时,如果回合=2,则开始c1:=1;while turn=2 dobegin/* no-op */end;c1:=0endend;/*临界区1*/c1:=1;turn:=2endP2::c2:=1;While true dobeginc2:=0;如果检查2,则start wait V12> 0;V12:=0结束当c1=0开始时,如果turn=1,则开始c2:=1;while turn=1开始/* no-op */end;c2:=0endend;/*关键部分2*/如果检查2,则停止P2;c2:=1;turn:=1end图五. Dekker变换算法第6节中的序列σ3示出了与这种情况相关的Dekker算法中的情况(因此,我们将使用我们的运行示例来演示Dekker算法中的一个微妙的并发问题,我们需要在转换的实现中避免这个问题。引理3.1如果没有建模错误,并且给定可疑执行中的动作正确地遵循原始代码,那么我们的构造不会产生新的死锁。变换后的Dekker算法允许检查第2节中的路径σ2,如图5所示。添 加的 代 码 以 粗 体 显 示 。为了推理我们提出的程序变换,我们将用A来表示原始程序动作,用AJA来表示动作的扩充集合(可以在动作A上表示一些微小的改变,特别是对程序计数器值的改变,尽管在动作A上没有改变,但是在动作A上可以表示对程序计数器值的改变。78D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65¬对应于这些动作的代码我们用对称自反关系D<$A×A表示程序动作A之 间 的 依 赖 关 系 。 添 加 新 的 动 作 AJ\A 会 导 致 新 的 依 赖 关 系DJ<$AJ×AJ。我们有Dj(A×A)=D,即,编程转换不在原始过渡之间添加任何依赖关系。引理3.2设P是原程序,PJ是变换的结果.那么我们可以表示如下:(6)隐藏AJ\A(Exec(PJ))=ClD(σ)也就是说,当对转换后的程序,我们可以获得任何执行,相当于下D到序列σ。4保护财产到目前为止,我们的转换使我们能够以这样一种方式控制程序的执行,即我们被限制为与反例等价的跟踪执行。进一步假设执行σ是使用模型检查器获得的,该模型检查器用于验证某个并发程序是否满足性质σ。我们抽象地假设性质n对应于一组命题序列。在实践中,它可以被指定,例如,使用时间公式或(有限或无限)序列上的自动机。由于σ是一个反例,它通常满足条件。将L(n)表示为命题执行的集合(或动作序列,取决于指定的类型),当n在迹等价下不闭合时,困难出现[19]。也就是说,我们可以有ρ)。对于这种情况有几种解决方案。一种是使用在迹等价下封闭的规范形式主义(参见例如,[1、10、22])。另一种解决方案是使用一种不强制跟踪封闭性的规范形式主义,然后应用一种算法来检查跟踪是否封闭。这样的算法出现在[19]中。我们在这里提出了第三种可能性,在这里我们不强制将跟踪关闭。其思想是添加依赖项,以便细化迹等价,并且等价序列不会在满足条件时发生变化。我们构造了一个图G=<$σ,S,<$σ。 S中的每个节点代表一个执行序列从ClD(σ)。初始节点为σ∈S。存在边ρ<$ρJ,如果ρJ是使用单个相邻的独立对的切换从ρ获得的,行动从满足σ的σ开始搜索,我们检查每个后继节点是否满足σ。假设ρ满足π,但它的后继者ρJ满足π,我们添加同步,以防止ρ置换为ρJ。也就是说,如果对于某个前缀μ和su_xμJ,以及出现次数βl和αk,ρ=μαk βl μj和ρJ=μβl αk μj,我们添加一个同步αk→σβl。 注意为了优化,我们没有使动作α和β相互依赖,而是使两个特定的事件同步。我们可以使用D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6579⇒适应Floor-Warshall算法,如第2节所述。该算法提供了少量的额外的同步,以保持时间属性。然而,它的复杂性很高。ClD(σ)的大小在最坏的情况下可能与σ的长度成指数关系。其他启发式解决方案是可能的。例如,我们可以遵循偏序约简策略(充足集、持久集或顽固集),并检查哪些动作可能改变参与约简的命题。然后我们使所有这些行动相互依存。这个解决方案对于封闭的规范是很好的。细节和进一步的参考文献可以在例如,第10章[3]该解决方案具有更好的复杂性(动作数量的二次方),但是次优,因为它可能添加一些冗余同步。5分布式程序模型现在考虑一个不同的分布式系统模型,其中我们有一个握手(同步)消息传递,而不是共享变量。在本节和前一节的描述之后,可以以类似的方式处理其他模块,例如总线通信我们假设我们的程序有以下类型的操作:• 本地操作,与单个进程相关。• 沟通行动。这里我们假设握手通信,如Ada或CSP。这样的动作由一对进程联合(并且同时)执行。我们可以再次为动作分配依赖关系。当α和β参与一个相互作用过程时,我们有(α,β)∈D.请注意,特别是通信参与了一对进程,因此它依赖于来自两个进程的操作。我们使用以下语法结构:选择S1 [] S2 []. []Sn end其中用于S1的代码在潜在的本地条件(即,“保护”)之后以通信(发送或接收消息)开始。保护通信[8]的一种语法是gc,其中g是局部条件,并且c是一种沟通。反过来,c可以是形式P!e,其中P是一个进程,e是一个表达式,其计算值被发送到P,或Q?x,其中Q是进程,x是接收发送值的变量。 P!e在过程Q和Q上?x在进程P上就好像x:=e是由两个进程P和Q执行的。选择本身不会转换为操作。它只是一个关键字其允许在该位置处潜在地启用若干通信动作。我们再次为每个进程添加一个本地计数器计数i。计数器在选择内的每个通信动作之前递增。大家可以80D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65检查计数i的值是否为iαk,以便根据给定的执行进行选择。然后,我们可以将select语句替换为确定性代码,该代码根据可疑执行选择适当的通信。例如,考虑select语句selectβ []γ end假设β(以及来自另一个进程的匹配通信)在σ中作为βj和βk出现,γ作为γl和γm出现。我们将select语句替换为以下代码:案例计数i,iβj,iβk:β;iγl,iγm:γ端因此,如果counti是iβj或iβk,我们需要选择通信动作β。在其他两种情况下,我们需要选择γ。请注意,由于通信是在两个进程之间共享的,因此将由两个进程分别计数与具有共享变量的程序的情况一样,我们需要添加代码,以便仅在强制执行可疑执行时才激活附加检查,即,当检查i=true时。同样,我们在计数中包括每个进程中的最后一个动作,以便停止执行。请注意,由于没有共享变量,并且在握手通信下,转换中添加的代码对于进程来说是完全本地的。引理5.1如果没有建模错误,并且给定可疑执行中的动作正确地遵循原始代码,则转换不会引入新的死锁。请注意,如果我们想在所有跟踪等价于可疑执行(我们想要监视的执行)的执行上强制保留checked属性,我们可以应用第4节中给出的转换。这意味着要添加信号量,因此也要添加共享变量,即使原始代码只包含进程间通信。6将框架扩展到无限轨迹模型检查器可能会生成一个无法满足给定规范的无限执行。虽然是无限的,但这样的序列最终是周期性的[23]。它由一个有限前缀σ和一个有限递归序列ρ组成。 这通常表示为σρω。我们可以对两个有限部分σ和ρ做一些小的改变,然后应用我们的变换。当然,我们不能执行σρω,因为它是有限的,但我们可以测试它在任何给定的有限长度上的执行(取决于我们的耐心)。D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6581∗第一个变化是调整同步中所涉及的动作的计数,并且在每个进程的最后一个动作中根据σ和ρ表现不同。我们为每个进程pi添加一个变量phasei,初始化为0。我们不停止执行σ。相反,当我们到达最后一个在σ中的进程pi的操作(如第3节所述),我们将阶段i更新为1,并根据执行ρ进行操作。当我们到达σ的末尾,并且每次我们根据ρ到达最后一个当前进程动作时,我们将计数i重置为零。设G(ρ)=<$P,E<$是一个无向图,其结点是过程,且pi和pj之间存在一条边,如果存在ρ的出现αk,βl使得αk~σβl或βl~σαk,α∈A(pi),β∈A(pj).最终周期部分ρ有三种情况可以区分:(i) 图G(ρ)包括一个连通分支(节点的最大分支,使得该分支中的每对节点之间存在路径)中的所有过程在这种情况下,在强制执行中,由于并发性(独立性),ρ的第i次迭代的某些发生可能会被ρ的第i+1次迭代所取代然而,这种超越是有限的,并且来自第i+2次迭代的事件不能超越第i次迭代中的任何事件。(ii) 图G(ρ)由多个不相交的连通非单点分支组成。在这种情况下,行为就好像组件独立迭代,并且它们之间可以有无限超越2。当连接消息序列图时会获得类似的行为[16]。(iii) 图G(ρ)仅包括单例分量(即,每个节点由单个节点组成)。在这种情况下,有些进程可能没有得到公平的机会继续下去。然后,不保证该结构的行为符合σ ρω。运行转换后的程序可能会导致来自代表性不足的流程的附加操作被处决由于共享变量或消息传递,这可能会影响所表示的进程。因为我们的转换插入了一些代码,其中一个进程可能会根据可疑的执行等待另一个进程,所以我们的转换可能会导致死锁。事实上,在程序分析(验证,测试)过程中发现的执行与实际行为之间的差异是一个有用的信息。这表明分析没有考虑到一些重要的语义考虑(公平性),因此增加了给定执行是假阴性的可能性我们在这里提供一个最终周期序列σ3的例子,[2]这种区别与并发星算子c[4]及其相关无限形式cω的定义有关。 可疑行为被定义为σρω,但如果没有明确地同步ρ的每次重复,我们实际上可以实现σρcω。82D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65表示发生活锁。进程P1处于无限循环中,等待进程P1放弃进入临界区的尝试,而进程P2没有任何进展。σ3的极限值如下:1:(P1(0):开始)2:(P2(0):开始)3:[P1(1):c1:=1]4:[P2(1):c2:=1]5:P2(12):true>yes 6:P1(12):true> yes 7:[P1(2):c1:=0]8:[P2(2):c2:=0]9:P1(8):c2=0?> 是的10:P2(8):c1=0?>yes 11:P1(7):turn=2?> no 12:P2(7):turn=1?>是13:[P2(3):c2:=1]σ3的递归部分由以下两种情况组成14:P2(5):turn=1?>是15:[P2(4):/* no-op */]初始状态与前面的示例执行中的状态相同。在最终周期部分,进程P1不参与执行,而P2循环,等待turn变为2(第14和15行)。由于P1不执行,所以turn保持为1,P2永远不会退出循环.这种执行可能是不考虑公平性的分析的结果。公平地说,进程P1将继续,并将检查c 2的值,现在c2的值变为1;因此P1可以继续进入其临界区,并最终将turn设置为2。因此,P2最终将能够进入它的临界区.7实施与探讨该算法已由第二作者实现。它可以单独使用或作为PET系统的扩展[7]。该算法以一个并发Pascal程序作为输入,输出变换后的程序.我们使用PET系统以如下方式测试实现。PET旨在检查并发执行。给定手动选择的对应于给定程序的流图节点序列(通过点击来自流图的节点序列来选择,所述流图由PET从给定Pascal过程自动生成),其计算它们的路径条件。正如第2节所讨论的,由于非决定性,这样的条件不足以强制选择序列。因此,这里提出的算法正是强制选择路径所需的扩展(直到迹等价)。D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)6583我们现在可以提供转换后的代码,包括强制给定初始条件的赋值。通过该分配,跟踪等价于原始选择路径的每个序列的新路径条件为真。PET还允许通过选择第一个事件并单击鼠标来排列相邻独立事件对。我们也可以选择其他序列,不等同于原始序列。我们提出了一个程序转换,它强制程序根据给定的场景执行。 由转换激发的对程序代码的改变是最小的,当不从特定的给定初始状态(其中,特别地,对于每个进程pi检查i=真)开始时,允许它也具有其他执行。这种转换可以用来检查由模型检查器或定理证明引擎报告的可疑行为是否确实是错误的。测试人员也可以使用这个转换,他们需要证明发现的错误实际上发生了。由于并发程序的高度不确定性,可能很难实施可疑场景,这可能取决于不频繁的调度选择。转换保留了程序的并发结构。这样一个简单的转换可以被验证或全面测试,以获得对其正确性的信心。此后,它可用作测试验证工具结果的标准工具。引用[1] 阿尔河,Peled D.,W. Penczek(1995),因果性质的模型检验,LICS[2] H. Ben-Abdullah,S. Leue,Syntagical detection of process divergence and non-local choicein Message Sequence Charts,TACAS 1997,LNCS 1217,Springer,259[3] E. Clarke,O.Grumberg,D.张文,模型检验,清华大学出版社,1999年。[4] 诉Diekert,G.罗森伯格,《痕迹之书》,世界科学,1995年。[5] E. W. Dijkstra,The Structure of THE Multiprogramming System,Communication of theACM 9(1976),27[6] R.W.弗洛伊德算法97(最短路径)。ACM通信5(1962),pp. 365[7] E.L. Gunter,D.张文,并行系统的时序分析,2002年,上海,上海,2004。[8] C.A.R. Hoare,Communication Sequential Processes,Prentice-Hall,1985。[9] J. Grabowski,B.科赫,M。Schmitt,D. Hogrefe,基于SDL和MSC的分布式测试体系结构的测试生成,SDL 99下一个千年,Elsevier,1999年6月[10] S. Katz和D.佩尔德。交错集时序逻辑。理论计算机科学75,21[11] ITU-T建议Z.120,消息序列图(MSC),1993年3月。[12] L. Lamport,Time Clocks,and the Ordering of Events in a Distributed System,CACM 21(1978),558[13] T. J. LeBlanc,J. M.陈文辉,“并行程序设计与实时重放”,计算机学报,第36卷,第4期,第47184D. Peled,H.曲志红/理论计算机科学电子笔记113(2005)65[14] A. Mazurkiewicz , Trace Theory , Advances in Petri Nets1986 , Lecture Notes inComputer Science 255,Springer-Verl
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功