没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记276(2011)335-351www.elsevier.com/locate/entcs并发分离逻辑与操作语义维克托·瓦菲亚迪斯Max Planck Institute for Software Systems(MPI-SWS)德国摘要本文提出了一个新的可靠性证明并发分离逻辑(CSL)的标准操作语义。该证明给出了CSL判断的直接意义,可以很容易地适应CSL的扩展,例如权限和可存储锁,以及更高级的程序逻辑,例如RGSep。 此外,它清楚地解释了为什么资源不变量在证明中应该是“精确的” 使用conjunction rule。关键词:分离逻辑;并发;可靠性;竞争条件1介绍并发分离逻辑[15](CSL)是一种并发程序逻辑,是证明并发程序正确性的形式系统。它基于资源所有权的概念,其中资源通常是动态分配的存储器(即,heap)。自从O 'Hearn提出以来,它已经变得非常流行,因为它允许一些复杂的并发指针程序的优雅的正确性证明,这些程序跟踪它们的内存消耗并显式地处理-定位任何未使用的CSL的扩展数量(例如,权限[2,1],堆中的锁[9,13],作为资源的变量[16],可重入锁[11])。除了有许多扩展,CSL也有许多可靠性证明。一些证明[3,12,10]是关于普通CSL的,一些[5,9,13,11]是关于特定扩展的,而另一些[6,4]是抽象的。在Brookes在这样的语义中,获取和释放锁,通常更新单个位的操作,而是分配或释放堆的一部分(从共享资源接收或发送)。的1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.09.029336诉Vafeiadis/理论计算机科学电子笔记276(2011)335中间语义的充分性通常由“擦除”定理来证明,该定理其他一些证明[11,14,9,10]则完全是语法性的:它们从不定义CSL判断的含义,而是建立一个全局不变量,以确保数据竞争自由,并在执行步骤中保留。这种证明技术类似于类型系统可靠性证明中常见的“进步和保存”策略,并且相当脆弱。如果,例如,一个新的结构被添加到语言中,现有规则的合理性将不得不受到谴责。此外,由于CSL判断的含义从未被定义,除非可能是封闭的在本文中,我们采取直接的方法来证明CSL的可靠性我们直接根据编程语言的标准具体操作语义来定义CSL判断的含义。我们的定义是简洁的,结果是一个相对简单的可靠性证明,我们已经在Isabelle/HOL中正式化了。1我们的稳健声明有三个重要的好处:(i) 它包括分离逻辑的框架方面。因此,证明在技术上不要求操作语义满足(ii) 它并不坚持资源不变量是精确的。 与Gotsman相似等人[10],我们证明(a)CSL可能不精确的资源不变量和没有合取规则是合理的,(b)合取规则是合理的,只要范围内的资源不变量是精确的。这两个证明使用相同的语义CSL判断。(iii) 它可以很容易地适应CSL扩展,例如权限[2,1],RGSep [19],拒绝/保证和并发抽象谓词[7]。论文大纲。出于教学的原因,我们将首先关注CSL的简化版本,其中同步的唯一结构是在一个原子步骤中执行的原子块(§ 2)。我们将给出编程语言和分离逻辑断言的语法和语义,以及CSL证明规则。然后,我们将仔细定义CSL判决的语义(§3),并证明证明规则是合理的(§4)。稍后,在§5中,我们将考虑O'Hearn的原始设置,其中多个命名的条件临界区域以非原子方式执行,但相互排斥,并证明CSL的数据竞争自由结果。最后,我们将调整我们的正确性声明来处理CSL的扩展,例如权限(§6)和RGSep(§7)。[1]验证脚本可在http://www.mpi-sws.org/~ viktor/cslsound[18]获得诉Vafeiadis/理论计算机科学电子笔记276(2011)335337121212defdef(SE q1)(skip;C),σ→C,σC,σ→跳跃,σ′(汤姆)2 2(原子C),σ→skip,σC1, σ→C1′,σ′(SEq2)C,σ→C′,σ′(C;C),σ→(C′;C),σ′11(第1段)1212(C<$C),σ→(C′<$C),σ′C1,σ→中止(SEqA)C,σ→C′,σ′(C;C),σ→中止22(第2段)(C1<$C2), σ→(C1<$C2′),σ′σ=(s,h)[B]](s)(如果B则C1否则C2),σ→C1,σσ=(s,h) <$[[B]](s)(如果BthenC1elseC2),σ→C2,σC,σ→中止原子C,σ→中止(IF 1)(IF 2)(ATOMA)(skipskip),σ→skip,σC1,σ→中止(C1<$C2),σ→中止C2,σ→中止(C1<$C2),σ→中止(第3段)(A1栏)(A2栏)(LOOP)(whileBdoC),σ→(ifBthen(C;whileBdoC)else skip),σ(ASSIGN)x:=E,(s,h)→skip,(s[x:=[E]](s)],h)(READ)x:= [E],(s,h)→skip,(s[x:=v],h)如果h([[E]](s))=v(READA)x:=[E],(s,h)→abort如果[E]](s)∈fdom(h)(W RI)[E]:= E′,(s,h)→skip,(s,h [[E]](s):=[[E′]](s)])if [E]](s)∈ dom(h)(WRIA)[E]:=E′,(s,h)→abort如 果 [E]] ( s )∈/dom(h)(ALL)x:=alloc(E),(s,h)→skip,(s[x:=l],h[l:=[E]](s)])其中l∈/dom(h)(FREE)dispose(E),(s,h)→skip,(s,h [E]](s):= k])if[E]](s)∈ dom(h)(FREEA)dispose(E),(s,h)→a bortif[E]](s)∈/dom(h)Fig. 1.命令的小步操作语义2并发分离逻辑考虑以下简单的命令语言E::= x|n|E + E|E−E|......这是什么?B::= BB|B|E = E|E≤E|... ...这是什么?C::=跳过|x:= E|x:= [E]|[E]:= E|x:= alloc(E)|处置(E)| C1-C 2|如果B那么C 1否则C 2|而B做C|原子碳|atomic C算术表达式E由程序变量、整数常量和算术运算组成。布尔表达式B由算术等式、不等式和布尔运算组成。命令,C,包括空命令,变量赋值,内存读取,写入,分配和释放,顺序组成,并行组成,条件,循环和原子命令。我们假设一个变量名域(VarName)、一个内存位置域(Loc)和一个包含内存位置和定义的值域(Val以下复合域:s∈Stackd=efVarName→Valstacks(变量的解释)h∈Heap=Loc~finValheaps(动态分配内存)′338诉Vafeiadis/理论计算机科学电子笔记276(2011)335σ∈State=Stack×Heap程序状态诉Vafeiadis/理论计算机科学电子笔记276(2011)335339②⇐⇒⇐⇒⇐⇒⇐⇒§算术表达式和布尔表达式分别被解释为从堆栈到值或布尔值的总函数[[]]:Exp→Stack→Val[[]]:BoolExp→Stack→ {true,false}[[x]](s)d=efs(x)[[B1<$B2]](s)d=ef[[B1]](s)<$[[B2]](s)[[E1+E2]](s)d=ef[[E1]](s) +[[E2]](s) [[E1≤E2]](s)d=ef[[E1]](s)≤[[E2]](s)在图1中,命令被赋予了一个小步操作语义。配置是命令和状态的对(C,σ)。存在从一种配置到另一种配置的转换,以及从配置到中止的转换,以确定执行错误,例如访问未分配的内存位置。并行组合交错执行其两个组件,而原子命令执行他们的身体,C,在一个过渡。在ATOM的前提中,→表示零个或多个→转换。2分离逻辑断言包括布尔表达式、所有经典连接、一阶量化和与分离逻辑相关的五个断言它们是空堆断言(emp)、指向断言(E1E2)、索引假 设 堆 由 一 个 地 址 为 E1 、 内 容 为 E2 的存 储 单 元 组 成 , 分 离 合 取 ( separatingconjunction)、分离蕴涵(separating implications )和分离合取(separatingconjunction)的迭代P,Q,R,J::= B|P ν Q |P ∧ Q|欧元/英镑|P Q|你好 P|你好P| 第一季第二集|PQ|P−Q|②i ∈I Pi|②i∈IPi断言表示状态集合 它们的语义作为建模关系给出s,h| = P,说明状态(s,h)满足断言P。s,h |= emps,h |= E ›→EJs,h| =PQs,h |= P− Qdefdefdefdefdom(h)=dom(h)=[[E]](s)h([[E]](s))=[EJ]](s)H1,H2。 h = h1h2(s,h1|= P)n(s,h2|= Q)1. de f(hh1)n(s,h1|=P)=P(s,hh1|=Q)这里,h1h2代表两个堆h1和h2的并集,除非dom(h1)= dom(h 2)=dom(h2),否则它是unfined的。 我们定义f(X)来表示X的定义。其他断言被经典地解释。最后,我们写E<$→ −作为v的简写。 其中v∈/fv(E).一类重要的断言是所谓的精确断言,它是任何给定堆的最多一个子堆满足的断言。形式上,如果满足两个这样的堆,h1和hJ1,则两者必须相等:定义2.1断言P对所有h1,h2,hJ1和hJ2都是精确的,如果def(h1h2)和h1h2 =hJ1hJ2和s,h1|= P和s,hJ1| = P,则h1 = hJ1。2通常,除了ATOM之外,还应该有另一个原子块体的无限执行规则为了简单起见,我们省略了这样的规则。在5中,我们将提出一个不同的语义,不涉及→不存在此问题。340诉Vafeiadis/理论计算机科学电子笔记276(2011)335(S基普)J{P}skip{P}JP1C1Q1J{P2}C2{Q2}x∈/fv(J)J{[E/x]P}x:=E{P}x∈/fv(E,E′, J)(ASIGN)(读)fv(J,P1,C1,Q1)wr(C2)=fv(J,P2,C2,Q2)wr(C1)=J{P1<$P2}C1<$C2{Q1<$Q2}(PAR)J<${E<$→E′}x:=[E]{E<$→E′<$x=E′}(WRITE)J<${E<$→−}[E]:=E′{E<$→E′}JR{P}C{Q}J{PR}C{QR}J{P}C{Q}(S兔)x∈/fv(E,J)J{emp}x:=alloc(E){x<$→E}(ALLOc)fv(R)wr(C)=J{PR}C{QR}(FRAME)(FREE)J<${E <$→ −}dispose(E){emp}J{P}C{Q}P′P QQ′(CONSEq)J{P}C1{Q}J{Q}C2{R}J{P}C1;C2{R}J{PB}C1{Q}J{PB}C2{Q}J{P}ifBthenC1elseC2{Q}J{PB}C{P}J{P}whileBdoC{PB}emp{PJ}C{QJ}J{P}原子C{Q}(SEq)(一F)(WHILE)(ATOM)J{P′}C{Q′}J{P1}C{Q1}J{P2}C{Q2}J{P1 $>P2}C{Q1$>Q2}J<${P}C{Q}x∈/fv(C)我的天。 P} C{\displaystyle{\cHFFFFFF}{\3cH2F2F2F}{\4cH000000} P} C{\displaystyle{\cHFFFFFF}{\3cH2F2F2F}{\4cH000000} P} C{\4cH000000} Q} J{P1} C{Q1}J{P2}C{Q2}J精密J{P1 $>P2}C{Q1$>Q2}(D是J)(EX)(CONJ)图二、并发分离逻辑证明规则。CSL判断的形式为J<${P}C{Q},其中J被称为资源不变量,P为前提条件,Q为后置条件。非正式地,这些规范说,如果C是从满足PJ的初始状态执行的,那么J将在整个执行过程中得到满足,并且最终状态(如果命令终止)将满足QJ。另外,在规范中还附加了一个所有权的含义,即命令唯一的保证是它总是满足资源不变量J。证明规则如图2所示。 在这些证据规则中,有些是部分的-特别值得注意。 读取和写入都要求被访问是前提条件的一部分:这确保了小区被分配(因此,访问将是安全的),并且没有其他线程并发地访问它一个汤姆允许原子块的主体使用资源不变量J,并要求它们诉Vafeiadis/理论计算机科学电子笔记276(2011)335341在后置条件下重建它PAR允许我们在parallel当且仅当它们的先决条件描述堆的不相交部分。这可以防止内存位置上的数据竞争副条件确保程序变量上也没有数据竞争-在这里,fv返回命令或断言的自由变量集,而wr(C)返回变量集为-342诉Vafeiadis/理论计算机科学电子笔记276(2011)335由命令C签名。3共享允许我们在任何时候扩展资源通过分离地结合局部状态的一部分而不变,R。框架允许我们为了忽略局部状态的一部分,即帧R,它不被命令使用确保R在后置条件下仍然为真最后,合取规则CONJ有一个可能令人惊讶的附带条件。如雷诺数例[ 15,§11]所示,这一副条件对于合理性是必要的。大多数演讲都要求在所有的判断中都要有精确的J。然而,这是不必要的:只有CONJ需要精度。3CSL判决的含义我们用一个辅助谓词safen(C,s,h,J,Q)来定义CSL判断的语义,说明命令C与堆栈s和局部堆h一起执行,对于资源不变量J和后置条件Q,对于多达n个执行步骤是安全的一个CSL判决,J| ={P}C{Q},简单地说,程序C对于J和Q是安全的,对于每个满足前提条件P的初始局部状态,以及对于任何数量的步骤:定义3.1(配置安全性)• 安全0(C,s,h,J,Q)始终有效。• 安全n+1(C,s,h,J,Q)成立当且仅当(i)如果C = skip,则s,h| = Q;以及(ii))对于所有的h J和hF,如果s,h J|= J和(hHJf)定义,则C,(s,hhJhF)/→中止;以及(iii))对于所有的CJ,h J,hF,hJ和sJ,如果s,h J|= J,且(hh J(F)定义为,和C,(s,h,h,JhF)→CJ,( SJ, HJ),则存在HJJ和 HJJ使得HJ=hjjhjJhF和SJ,HJJ| = J和安全n(CJ,SJ,HJJ,J,Q)。定义3.2J| ={P}C{Q}当且仅当对于所有n,s和h,如果s,h| = P,则安全n(C,s,h,J,Q)。直觉上,任何配置对于零步都是安全的。对于n+ 1步,它必须(i)满足后置条件,如果它是一个终端配置,(ii)不中止,(iii)在任何一步之后,重新建立资源不变量,并在另外n步中是安全的。步骤的数量只是确保定义在结构上是递减的。更详细地说,h是由命令“拥有”的堆的一部分:该命令可以更新h,并且没有其它命令可以并行地访问它。在条件(ii)和(iii)中,hJ表示堆中线程共享的部分,因此必须满足资源不变量。因此,条件(iii)确保在转换之后可以找到新的这样的组件hJJ。最后,hF表示由系统的其余部分拥有的堆的剩余部分。在条件(ii)中,命令必须不中止,不管剩余部分是什么。[3]为了简单起见,我们强加了严格的可变附加条件。因此,只有堆单元可以在线程之间共享,因为J不能提及任何可更新的变量。诉Vafeiadis/理论计算机科学电子笔记276(2011)335343是.在条件(iii)中,命令不能改变堆中可能由另一个线程拥有因此,hF必须是新堆hJ的子堆。安全单调框架属性。 hF量化的目的是承认框架规则。在条件(ii)中,hF本质上起着“安全单调性”的作用不中止),则(C,hhF)也是安全的。类似地,在条件(iii)中,hF扮演了“框架性质”的角色条件(iii)并不完全意味着框架性质,因为它不要求Ci(s,h)→Ci,(s,h,J)。相反,它考虑了跃迁C1(s,h)→Cj,(sJ,H J),即使它可能不存在。这种差异是相当微妙的。特别地,如果操作语义满足安全单调性和框架性质(在我们的例子中是这样的),我们可以放弃hF量化。 (See[18]一个证明。 然而,量化对于某些CSL扩张(见§ 6)是至关重要的,甚至简化了正规CSL(P AR和FRAME)的某些证明。讨论定义3.1的一个好的方面是,关于复合命令安全性的直接引理通常已经是归纳的,从而使可靠性证明中最具挑战性的部分变得微不足道。唯一的例外是关于资源声明规则的引理5.3(用于定义3.1的扩展以处理多个命名的CCR),这可以说是证明中最具挑战性的部分第二个好处是,我们不严格要求中止语义来证明CSL的可靠性:如果我们从定义3.1中删除条件(ii),我们仍然可以证明CSL的可靠性,而无需引用中止语义。相比之下,依赖于安全单调性和框架属性的证明严重依赖于中止语义(例如,[3、4、5、6、9、10])。4可靠性证明我们从语义的一些基本但重要的属性开始。在下文中,令[s <$sJ] X代表<$x∈X。s(x)= SJ(x)和X是集合X的补数。四号提案。1如果C,(s,h)→CJ,(sJ,hJ),则fv(CJ)<$fv(C),wr(CJ)<$wr(C),且[s <$sJ] wr(C).命题4.2(i)如果[s<$sJ] fv(E),则[[E]](s)=[[E]](sJ)。(ii) 如果[s sJ] fv(B),则[[B]](s)=[[B]](sJ)。(iii) 如果[s <$sJ] fv(P),则s,h |= P当且仅当sJ,h |= P。(iv) 如果[s sJ] fv(C)和C,s → abort,则C,sJ→ abort。(v) 若X∈fv(C)且[s∈sJ]X且C,s→C1,s1,则存在SJ1使得344诉Vafeiadis/理论计算机科学电子笔记276(2011)335C,SJ→C1j,SJ1和[s1$>SJ1]X.现在,考虑定义3.1。通过构造,safe相对于n是单调的:如果一个配置对于步数n是安全的,那么它对于更小的步数m也是安全的。(这是通过对m的归纳证明的。)引理4.3若n(C,s,h,J,Q)是安全的且m ≤ n,则m(C,s,h,J,Q)是安全的.此外,作为命题4.2的推论,安全n(C,s,h,J,Q)仅取决于C,J,Q中提到的变量的值。引理4.4若安全n(C,s,h,J,Q)且[s ∈ sJ] fv(C,J,Q),则安全n(C,sJ,h,J,Q)。CSL的可靠性定理如下:定理4.5(CSL可靠性)如果J <${P} C {Q},则J |={P} C {Q}。我们的证明策略是,如果我们替换所有的证明规则,|=.然后,定理遵循一个简单的规则归纳。为了简洁起见,我们只展示最有趣的规则的证明(SKIP)skip的规则直接从下面的引理得出,其证明是微不足道的,因为从skip没有转换。引理4.6对于所有n,s,h,J和Q,如果s,h |= Q,则安全n(skip,s,h,J,Q)。(ATOM)我们需要一个辅助引理来处理在原子块中执行的代码引理4.7如果 safen(C,s,h,emp,Q)和def(hhF),则(i) -(C,(s,hhF)→C_abort);以及(ii) 此外,如果C,(s,hhF)→C,(sJ,hJ),则存在hJ J,使得hJ=hJJhF和sJ,hJJ|= Q。这个引理是由关于→n迹的长度的归纳法证明的,而不是-当J=emp时,定义3.1的第二个子句简化为安全n+1(C,s,h,emp,Q),当且仅当(i)如果C = skip,则s,h| = Q;以及(ii))对于所有hF,如果def(hhF),则Ci(s,hhF)/→中止;以及(iii)对所有hF,CJ,SJ,HJ,若Cj(s,hhF)→CJ,(SJ,HJ),则存在HJJ使得HJ=hjjhF和安全n(CJ,SJ,HJJ,J,Q).原子命令的主要引理如下:引理4.8如果emp |={P <$J} C {Q <$J},则J |={P}原子C {Q}。证据 假设(*)emp |={P <$J} C {Q <$J},并选取任意s,h |= P且n. 我们必须证明安全的n(原子C,s,h,J,Q)。如果n= 0,这是平凡的;所以考虑n=m+1。条件(i)是平凡的,因为原子C跳过。(ii)如果原子C,(s,hhJhF)→abort,然后从操作语义诉Vafeiadis/理论计算机科学电子笔记276(2011)335345C,(s,hHJhF)→abort,这与引理4.7相矛盾。346诉Vafeiadis/理论计算机科学电子笔记276(2011)335||(iii)对于原子C,(s,hhJhF)→CJ,(SJ,HJ)的唯一方法是如果CJ= skip并且C1(s,hhJhF)→skip,(SJ,HJ)。 因此,根据假设(*)和引理4.7,存在hJJ,使得hJ= hJJhF和sJ,hJJ|= QJ. 因此,存在HJJJ和HJJ使得HJJ= HJJJHJJ,SJ,HJJJ= Q,并且SJ,HJJ=J。 最后,从引理4.6,我们得到安全的m(skip,sJ,hJJJ,J,Q)。Q对于并行复合,我们需要以下辅助引理:引理4.9如果安全n(C1,s,h1,J,Q1),安全n(C2,s,h2,J,Q1),h1H2定义为,fv(J,C1,Q1)wr(C2)=,且fv(J,C2,Q2)wr(C1)=,则安全n(C1<$C2,s,h1h2,J,Q1<$Q2).是的。 通过归纳n。在感应步骤中,我们知道IH(n)d=efC1,h1,C2,h2. 安全n(C1,s,h1,J,Q1)安全n(C2,s,h2,J,Q1)安全f(h1h2)fv(J,C1,Q1)=安全的n(C1<$C2,s,h1h2,J,Q1<$Q2)我们必须证明IH(n+ 1)。因此,选择任意的C1,h1,C2,h2,并假设(1)safen+1(C1,s,h1,J,Q1),(2)safen+1(C2,s,h2,J,Q2),(3)def(h1h2)和(4)可变边条件,并试图证明safen+1(C1<$C2,s,h1h2,J,Q1<$Q2).条件(i)是平凡的。(ii))如果C1→C2,(s,h1h2hJhF)→abort,则根据操作语义C1,(s,h1h2hJhF)→abort或C2,(s,h1h2hJhF)→中止,与我们的假设(1)和(2)相矛盾。(iii))选取任意CJ,h J,hF,sJ,hJ,使得s,h J|= J,(h1H2HJhF)有定义,C1<$C2,(s,h1h2hJhF)→(CJ,sJ,hJ)。 操作语义对于C1到C2有三种可能的转换.案例(PAR1)。 CJ=C1J<$C2和C1,(s,h1h2hJhF)→C1J,(sJ,hJ)。由(1)可知,存在HJ1和HJJ,使得HJ=HJ1HJJ(h2hF),SJ,HJJ安全n(C1J,SJ,hj1,J,Q1).|= J, and根据(2)和命题4.3,我们有安全n(C2,s,h2,J,Q2).然后,由命题4.4和4.1以及假设(4),我们得到安全n(C2,SJ,h2,J,Q2).另外,由命题4.1和(4)可知,fv(C1J,Q1)<$wr(C2)=1,且fv(C2,Q2)<$wr(C1J)=1,且d因此从IH(n)出发,saf en(C1J<$C2,SJ,HJ1h2,J,Q1<$Q2)。案例(第2页)。这个案例是完全对称的。案例(第3页)。C1=C2=CJ=跳跃,hJ=h1H2HJhF.从(1)和(2),展开安全的定义,我们有s,h1|= Q1和s,h2|= Q2。 那么s,h1H2|= Q1<$Q2,并且,从引理4.6,安全n(skip,s,h1h2)。Q(框架)框架规则是平行合成规则的简化版本。它直接从下面的引理得出:引理4.10如果安全n(C,s,h,J,Q),fv(R)=fwr(C)=fwr,定义hs,h R|= R,则安全n(C,s,hh R,J,Q <$R)。证据 通过归纳n。 基本情况是微不足道的。 对于归纳步骤,假设诉Vafeiadis/理论计算机科学电子笔记276(2011)335347JJJJJJJJ(*)安全n+1(C,s,h,J,Q),(†)f v(R)w r(C)=n,andnd(R)s,hR|=R. 现在,我们必须证明安全n+1(C,s,hhR,J,Q<$R)。(i))从(*),我们得到s,h| = Q和so,使用(S),s,hh R|= QR。(ii))选取hJ和hF。 然后,从(*),C,(s,hhRHJhF)/→中止。(iii))ifC,(s,hhRhJhF)→CJ,(SJ,HJ),则由(*),存在HJJ,HJJ使得hJ=hJJhJJ(h RhF)且sJ,hJJ| = J和安全 n( CJ, SJ, HJJ,J,Q)。现在,从(†),(),Prop。 4.1和4.2,wgetsJ,hR|=R且f v(R)= r(CJ)=r。因此,根据归纳假设,安全n(CJ,sJ,hJhR,J,QR)。Q(S)我们需要下面的引理,它与前面的引理类似引理4.11若定义安全n(C,s,h,J<$R,Q),hh R,且s,h R|= R,则安全n(C,s,hh R,J,Q<$R)。证据 通过归纳n。 对于感应步骤,(i)根据我们的假设,s,h |= Q和s,h R|= R,所以s,hh R|= Q R。(ii)C,(s,hhRhJhF)/→abort直接由我们的假设得出。(iii)若C,(s,hhRhJhF)→ CJ,(SJ,HJ),则根据我们的假设,存在HJJ,HJJR使得HJ= hjjhJRhF且SJ,HJJR|= J <$R和安全n(CJ,sJ,hJJ,J <$R,Q)。由定义可知,存在hJJ和hJR,使得hJJR = hJJhJR和sJ,hJJ |= J和sJ,hJR| = R.因此,从归纳假设出发,安全n(CJ,sJ,hJJhJR,J,Q<$R),如所要求的。Q(CONJ)现在考虑合取规则。其合理性取决于以下含义的有效性:安全n(C,s,h,J,Q1)安全n(C,s,h,J,Q2)=安全n(C,s,h,J,Q1<$Q2)。自然地,人们会期望通过对n的归纳来证明这个推论,其中归纳假设在所有C和h上量化。基本情况是平凡的;所以考虑n+ 1的情况。前两个子情况很容易,所以考虑子情况(iii)。从第一个假设,我们知道存在h1和h1,使得hJ=h1h1和h1|= J和安全n(CJ,h1,J,Q1)。同样,根据第一个假设,h2和h2使得HJ= h2H2和H2|= J和安全n(CJ,h2,J,Q2),但是,一般来说,我们不知道h1=h2,这将允许我们完成证明。自从,然而,J必须是精确的,那么(根据定义2.1)h1=h2,因为是cancellative,我们也有h1=h2,结果如下通过应用归纳假设。Q5多资源数据竞争自由在本节中,我们考虑O'Hearn [ 15 ]和Brookes [ 3 ]使用的编程语言该编程语言用两个新的构造和一个中间体取代了原子命令原子C348诉Vafeiadis/理论计算机科学电子笔记276(2011)335(C1,σ)→(C1′,σ′)locked(C1′)<$locked(C2)=<$(C1<$C2,σ)→(C1′<$C2,σ′)(第1段)(C2,σ)→(C2′,σ′)locked(C1)locked(C2′)=n(C1<$C2,σ)→(C1<$C2′,σ′)(第2段)(accesses(C1,s)writes(C2,s))(accesses(C2,s)writes(C1,s))=/∅(C1<$C2,(s,h))→中止(RES 1)C中的资源r,σ→C′,σ′中的资源r,如果C,σ→C′,σ′(RES 2)资源rin skip,σ→skip,σ(WITH 1)withrwhenBdoC,σ→withinrdoC,σifσ =(s,h)and[B]](s)(WITH 2)withinrdoC,σ→withinrdoC′,σ′ifC,σ→C′,σ′(WITH3)withinrdo skip,σ→skip,σ(RES A)C中的资源r,如果C,σ→中止,则σ →中止(与A)在r内做C,σ→中止,如果C,σ→中止图三. CCR的操作语义(RA cE DetecT)命令形式:C::=... |当B做C时,|在r do C内|within r do C第一个声明了一个新的互斥锁r,在CSL术语中称为资源或资源束第二个结构表示条件关键区域(CCR),它相对于具有相同锁的任何其他CCR隔离运行。执行CCR会阻塞,直到资源可用且条件B为真,然后与作用于同一资源的其他CCR隔离地执行主体C。这是通过在测试是否B是满足和执行其机构。最后,在r中,doC表示一个部分执行的CCR:一个已经获得锁,测试了条件,但仍然必须执行C的CCR。我们将locked(C)定义为C语法锁定的区域集合:那些r,其中C在r内包含adoCJ子项。操作语义由图1的规则(不包括PAR 1、PAR 2、ATOM、ATOM A)和图3中所示的新规则给出。 减持规则对于并行组合(PAR 1,PAR 2),已经被修改以检查两个线程不同时持有相同的锁。这在简单的设置中是不必要的,因为原子块在一个步骤中执行为了显示没有数据竞争,我们添加了一个规则(RA cE DETE cT),每当观察到数据竞争时,该规则就会这里,函数access(C,s)和writes(C,s)分别返回C访问或修改的堆位置集 其正式定义可参见[18]。针对多个资源的CSL判断具有形式Γr{P}C{Q},其中Γ是从资源名称r到其对应的资源不变量的映射,资源不变量是正常断言。我们有图2中的证明规则此外,我们还有以下两个关于资源声明和CCR的规则:Γ,r:J{P}C{Q}在C{Q<$J}中的资源Γ{(P<$J)<$B}C{Q<$J}当B做C{Q}时,r,r:J∈{P},其中r第一个规则类似于S共享规则:它允许我们声明一个新的诉Vafeiadis/理论计算机科学电子笔记276(2011)335349\J J J J②JJ J J J ②J JJ J资源束r,并将资源不变量与之关联。 第二规则类似于ATOM,允许验证者假设相关的资源不变量在CCR开始时单独保持,并要求他在CCR结束时重新建立它配置安全的定义修改如下:定义5.1• 安全0(C,s,h,Γ,Q)始终成立• 安全n+1(C,s,h,Γ,Q)当且仅当(i)如果C = skip,则s,h| =Q;以及(ii))对于所有hF,如果(h如果定义了hF),则C,(s,hhF)/→中止;以及(iii))访问(C,s)随机域(h);以及(iv))对于所有C,hΓ,hF,s,h,L,如果s,hΓ|=r∈locked ( C′) \locked ( C)Γ(r),且(C,(s,hhΓhF),L)→(CJ,(sJ,hJ),LJ),则存在hJ J和hJΓ使得hJ=hhΓhF和s,hΓ|=r∈locked(C)\locked(C′)Γ(r)和安全n(C,s,h,Γ,Q).类似于定义3.1,这里h是命令所拥有的堆的一部分;hΓ是属于明确未获取的资源的一部分(因为属于当前获取的资源的任何内存单元都是持有该资源锁的线程的本地堆的一部分);hF表示帧,即属于系统其他部分的内存单元。集合locked(CJ)locked(C)表示从C到CJ的转换所获得的锁的集合:对于所有这些,我们假设资源不变式成立。相反,locked(CJ)\locked(C)是转换释放的锁的集合:对于所有这些锁,我们检查是否建立了资源不变式最后,新的conjunctaccesses(C,s)conjuncdom(h)被包括在内,这样我们就可以证明安全程序没有任何数据竞争。与前面一样,三元组的语义是根据安全谓词给出的:定义5.2 Γ |={P} C {Q}当且仅当对所有n,s,h,如果s,h |= P然后安全n(C,L,s,h,Γ,Q)。稳健性的证明和以前一样进行,并在Isabelle/HOL中完全形式化。详情请参见[18]。我们说一个命令是格式良好的,当且仅当它没有两个不同的子命令同时获得相同的CCR锁,因为这在正常执行中不会发生。为了证明这两个新规则的可靠性,我们使用以下引理:引理5.3如果安全n(C,s,h,(r,r:R),Q)和C是良构的并且fv(R)≠ wr(C)=那么,(i) 若r∈/l oc ked(C),则f或a llhR,ifdom(h)ndom(hR)=n且s,hR|=R,则安全n(C中的资源r,s,hh R,r,Q<$R);以及(ii) 如果r ∈ locked(C),则n是安全的(C中的资源r,s,h,Γ,Q <$R)。引理5.4如果安全n(C,s,h,Γ,Q<$R)且在r内doC是良构的,则安全n(在r内为C,s,h,(r,r:R),Q)。350诉Vafeiadis/理论计算机科学电子笔记276(2011)335›→1122未定义,否则这些引理的证明可以在[18]中找到。我们的形式化还包括局部变量声明以及Brookes原始证明中的辅助变量消除规则6权限堆[2,1]是对标准堆模型的扩展,支持并行线程之间的例如,考虑霍尔三元组:{10<$→ −}x:= [10]y:= [10]{ 10<$→ −}。 标准CSL无法验证程序满足其规范,因为要从[10]读取,两个线程都必须知道小区被分配(即,10-作为前提条件),但断言10→ − 10→ −(并行组合规则所要求的)是不满意的-fable. 对于权限,可以将10<$→ −分为两个半权限,(10→0. 5−)(10<$→0. 5-),并将一个给定到一个ch线程。这种想法是这样的,部分权限是只读的:它们允许单元格被读取,但不允许更新。这是由以下新的证明规则捕获的:x∈/fv(E,EJ,EJJ, J)J<${ EE′EJJ}x:=[E]{EE′EJJ<$x=EJJ}(阅读2)在后置条件中,两个半权限被收集并连接以返回10› →−,其中ch只是表示10→1−的速记符号。权限模型是一个集合K,它有一个特殊元素T ∈K,称为完全权限,和一个可交换和可结合的部分运算符,表示两个权限的相加,满足以下性质:k ∈ K。<$def(T <$k)和<$k ∈ K\{T}. kJ∈ K。 k kJ= T第一个等式说T是最大的权限,因为它不能与任何其他权限组合。第二个等式说,每个非完全权限都有一个补充权限,当添加到它时,它会提供完全权限。我们之前看到的模型被称为部分权限。K是范围(0,1]中的数的集合,K是普通加法,当结果落在范围之外时,K是未定义的,T= 1。分数许可k的补数就是1 −k。为了对具有权限的堆进行建模,我们扩展了Risk来对权限-值对进行操作,如下所示:(k, v)n(k, v)d=ef.(k1<$k2,v1)ifv1=v2和def(k1<$k2)我们还把它推广到作用在允许堆上,PHd=efLoc~(Perm×Val),为如下 我们认为h1<$h2是有定义的,当且仅当h1(a)<$h2(a)是对所有a∈(dom(h1)dom(h2)).如果定义了h1<$h2,则它有domaindom(h1)<$dom(h2)诉Vafeiadis/理论计算机科学电子笔记276(2011)335351⎧⎪⎨⎩⇐⇒1J12使用以下值:(h1<$h2)(a)d=efh1(a)<$h2(a)如果a∈(dom(h1)<$dom(h2))h(a)如果a∈(dom(h)\dom(h))如果a∈(dom(h2)\dom(h1)),则n = h2(a)正如预期的那样,添加两个权限堆的定义是,每当它们重叠的每个位置,堆存储相同的值和可以添加在一起的权限。结果是一个权限堆,其对重叠位置的权限只是各个堆的总和断言现在由权限堆PH建模。 新的断言形式E1›→E2
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)
![](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://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 电力电子系统建模与控制入门
- SQL数据库基础入门:发展历程与关键概念
- DC/DC变换器动态建模与控制方法解析
- 市***专有云IaaS服务:云主机与数据库解决方案
- 紫鸟数据魔方:跨境电商选品神器,助力爆款打造
- 电力电子技术:DC-DC变换器动态模型与控制
- 视觉与实用并重:跨境电商产品开发的六重价值策略
- VB.NET三层架构下的数据库应用程序开发
- 跨境电商产品开发:关键词策略与用户痛点挖掘
- VC-MFC数据库编程技巧与实现
- 亚马逊新品开发策略:选品与市场研究
- 数据库基础知识:从数据到Visual FoxPro应用
- 计算机专业实习经验与项目总结
- Sparkle家族轻量级加密与哈希:提升IoT设备数据安全性
- SQL数据库期末考试精选题与答案解析
- H3C规模数据融合:技术探讨与应用案例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)