没有合适的资源?快使用搜索试试~ 我知道了~
分离逻辑中的资源变量处理
理论计算机科学电子笔记155(2006)247-276www.elsevier.com/locate/entcs分离逻辑中作为资源的变量理查德·博尔纳特英国伦敦米德尔塞克斯大学计算机科学学院R. mdx.ac.uk克里斯蒂亚诺·卡尔卡尼奥英国伦敦帝国理工学院计算机系。ccris@doc.ic.ac.uk梁洪锡ERC-ACI,首尔国立大学,韩国首尔。hyang@ropas.snu.ac.kr摘要分离逻辑[20,21,14]开始作为Burstall对列表变异程序[ 8 ]的处理的扩展形式化而存在它很快就变得清晰起来,它可以说的更多:到目前为止,这种处理还不完整,因为它只处理堆单元,而不处理作为资源的(堆栈)变量在Hoare逻辑中,将“变量上下文”(在最简单的情况下,拥有的变量列表)添加到断言中允许对变量进行资源处理。看来,一个正式的处理别名也是可能的。 它给出了一个完整的正式处理临界区(第一次,据我所知)。关键词:分离,变量,验证,证明1背景分离逻辑,预先许可,在[21,14]中描述。它开始作为BurstallBurstall认识到,如果商店中的列表是分开的,我们可以分别对每个列表进行突变推理。Reynolds在[20]中将这一思想扩展到所有类型的堆数据结构的变化。他,的1571-0661© 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.059248R. Bornat等人/理论计算机科学电子笔记155(2006)247−›→[15]和[7]中详细描述了分离逻辑的当前状态以及您可以使用它做什么我在此对有关问题作一个非常简短的总结。分离逻辑具有经典谓词演算的正常连接词和数量词,• emp是空堆;• E EJ是具有地址E和内容EJ(E和EJ)的必须是• E<$→是k·(E<$→k)的简写• A*B是一个堆,可以分为两部分,一部分由A另一个是B;• A是一个由A同时又由B描述的堆;• A *B是一个堆,如果我们添加一个单独的部分满足A,将满足B。理论上证明(*)是乘法合取(上下文的一部分证明A,另一部分证明B),而()是加法合取(整个上下文证明A,同一上下文证明B)。类似地,(−*)是乘法蕴涵,(→)是加法蕴涵。在实践中,到目前为止,大多数研究人员在逻辑中建立分离,使得对堆变异程序进行非常优雅的证明成为可能,使早期的尝试(例如,我自己的in [3])看起来笨拙而过于复杂。但是布鲁克斯在[7]中指出,这个想法是合理的。[4]中的权限概念-尚未被证明是合理的,但有一个令人信服的模型-允许部分程度的所有权,特别是只读共享堆缓冲器。一切还没有尘埃落定特别是变量--雷诺兹术语中的“堆栈”--存在困难(*)运算符作用于堆,但堆栈由副条件处理。例如,框架规则允许我们关注命令执行其工作所需的资源Q和R,{Q}C{R}(修改C变量P=P){P * Q}C{P * R}(一)逻辑的框架属性是微妙的:非正式地,如果命令C在给定堆中是安全的(R. Bornat等人/理论计算机科学电子笔记155(2006)247249heap可以被跟踪到原始heap中的某个执行[22]。如果P与Q分离,而C将Q变换为R,那么,根据框架性质,当C完成时,我们肯定有R和-分离,因此不变- 还是P是的,但是如果C改变了P中出现的变量之一,那么P的意义就改变了;这个附带条件正好排除了这种可能性,这个规则是合理的。这个附带条件不容易检查:修改赋值可能出现在C中,前提是它们并发性由两个相关的规则和命名资源束的概念来处理。并发规则:{Q1}C1{R1}··· {Qn}Cn{Rn}{Q1*···*Qn}(C1<$···<$Cn){R1*···*Rn}(2)有两个附带条件:在一个线程中更改的变量当ji时,修改Qj或Rj中的自由变量。CCR规则:1{(Q* Ib)G}C{R* Ib}{Q}与b当G做Cod{R}(3)也有两个附带条件资源包bCCRP(m)是(四)(稍后我们将看到对计数信号量的类似处理,其命令体是n−−和n++,而不是m:= 0和m:= 1)。这种治疗1CCR用于条件临界区:C(命令)是临界区,G(保护)是条件。在[12]中,Hoare引入了CCR。 霍尔称b为“资源”;我称之为“资源争夺”,简称为“捆绑”。这里的处理,取自250R. Bornat等人/理论计算机科学电子笔记155(2006)247›→颠倒了通常将信号量视为“禁止”障碍的处理这虽然在本文中,我试图通过消除附加条件来完善框架和并发规则,但重要的是要认识到它们已经很了不起了。框架属性位于框架规则的后面:如果程序组件舞台魔术实行新的和处置,与公理{emp}x:=new(){x<$→}{E<$→}disposeE{emp}(五)即使在堆资源被创建和重新声明的时候,也保留框架属性。在并发规则中,如果我们有框架属性,并且每个线程都遵循资源包不变规则,我们就可以单独推理线程分离属性是指分离的行为良好的线程保持分离。关键的是,这允许解释关键部分如何工作,就堆而言:如果我有一个堆资源E,我使用CCR从资源包中获得,我可以确定你如果临界区需要堆资源来完成它的工作,我们不可能同时获得资源因此,如果我们是独立的行为良好的线程--据我所知,这个论点是新的,在我看来,它似乎是对临界区如何工作的这个论点对堆缓冲器来说是可行的,但是我们对变量做什么呢临界区的互斥通常取决于变量的所有权(例如,考虑图4中的变量c,它只能在P(m)和V(m)之间的临界区使用)。变量应该是资源,由逻辑正式处理,而不是在附带条件中含糊地处理。似乎有两种方法来解决这个问题。一个是对待变量就像对待堆缓冲器一样。这种方法,虽然如果它是合理的,它会有相当大的优势特别是,我们似乎不得不放弃霍尔的变量赋值公理(7)的美丽的简单性,我们的另一种方法是像兰开夏郡人说的R. Bornat等人/理论计算机科学电子笔记155(2006)247251X›→并以这样一种方式描述变量所有权,即它这就是这里采取的办法。2问题总结分离逻辑只允许有限范围的赋值。如果E是一个纯表达式,只提到变量和常量,但不提到堆,则允许• x:=E(变量到变量);• int x:= [E];• [E]:=EJ(变量堆);• x:= new()(展开堆并赋值给变量)。语言中的所有其他公式-条件、循环和过程参数-必须是纯表达式。然后框架规则让我们通过“小公理”(new的公理在(5)中给出)关注赋值所使用的堆资源{E<$→EJ}x:=[E]{E<$→E J<$x=E J}如果x在E或EJ中不自由出现(6){E<$→}[E]:=EJ{E<$→E J}对纯表达式E和EJ的限制意味着我们这些公理有不过,边值条件纯表达式到变量的赋值{RE} x:= E {R},前提是x在R中没有别名。(七)这允许简单的机械计算,这很好,给出了最弱的预测,这甚至更好,并且没有值得担心的副作用,因为分离逻辑没有混淆堆栈变量的手段特别是,因为堆是从Nat到Int的部分映射,所以它可以很好地与R中的E EJ断言一起工作。举例来说{x+ 1<$→2(x+1)}x:=x+ 1{x<$→2x} (8)252R. Bornat等人/理论计算机科学电子笔记155(2006)247›→›→∃·›→›→∧赋值并不影响堆的所有权--赋值之前我们拥有一个单元格,赋值之后- 但它确实改变了我们描述所有权的方式。我们先用地址x+ 1来描述单元格,然后用x来描述同一地址。这一切都很好,完全显而易见,就像它应该的那样。 它支持阅读[15]这是一个很好的例子,它可以被理解为一个“阅读”。2.1赋值我想把所有权和权限的概念扩展到堆栈变量。重要的为了避免竞争,如果你执行x:=x+ 1,你必须拥有变量x。要推理赋值语句如何与后置条件x= 2y交互,您还必须具有读取y的权限--再次,为了避免竞争,为了在您暂停呼吸时阻止其他线程/进程写入y{x+1 = 2y}x:=x+1{x = 2y}(9)在作业之前和之后,你必须拥有x并且能够阅读y。你可能认为你可以从赋值和前置条件和后置条件的自由变量中推导出来,但事实并非如此。如果是这样的话,那么转让将是一种间接的所有权:{y= 3}x:=y{x= 3}(10)在我看来,我们不能指望从普通霍尔逻辑断言的等式和不等式推导出所有权和许可约束。3寻找解决方案首先想到的方法是去掉堆栈,将变量放在堆中,并使用()和(*)来处理它们。毕竟,这与硬件的方式相对应(尽管在许多机器上,寄存器但到目前为止,还没有一个优雅的解决方案,基于这一想法。特别是,它变得很难写简单的断言,如x > y:相反,你必须写像X,Y((xX* yY)的 X > Y)。逻辑学家的简单性不一定是程序员的简单性:我们R. Bornat等人/理论计算机科学电子笔记155(2006)247253E∧也许有一天我们将不得不接受这种方法的复杂性,但肯定不是在我们下一个最明显的方法是使用所有权谓词来描述使用堆栈的权限,并将其与关于x值的注释一起使用。2.如果我们使谓词对替换免疫(很简单:例如,替换已经遵守了绑定变量的限制),那么我们可以合理地写{(Own(x)*Own(y))x+1 = 2y}和x:=x+1{(Own(x)*Own(y))<$x= 2y}(十一){(Own(x)*Own(y))y= 3}x:=y{(Own(x)*Own(y))x=3}(12)如果你允许的话,这些例子确实遵守霍尔拥有(x)x是Own(x)。 替换的解读是必要的,转让Own(x)是一个谓词,如果堆栈由一个名为x的变量组成,则该谓词为真,您因此,Own(x)*Own(y)将两个单变量堆栈放在一起以形成双变量堆栈,Own(x)*Own(x)应该为false,Own(x)Own(y)应该意味着x和y命名相同的变量(即x和y是别名),Own(x)Own(y)表示我并且<$(Own(x))表示一个栈,它不是一个包含x的单例。这使得堆栈声明Own(x)<$x = 3与堆声明10›→3非常相似。我可以使用堆权限背后的思想来处理部分所有权[4]。部分权限3或计数读取权限允许读取但不允许写入;源权限允许创建计数读取权限。自己的0。5(x)是部分读取权限; Own>(x)是计数读取权限; Ownn(x)是源权限,其中n[2]这是在不同的时间和不同的人向我提出的建议--至少是朱尔斯·比恩和杨洪锡。很愚蠢,我一个都没听。相反,我从一个看似合理的形式主义开始往回走,直到最后才意识到我3我已经知道分数并不完全是这样,因为它们我已经知道如何解决这个问题,但分数254R. Bornat等人/理论计算机科学电子笔记155(2006)247⇐⇒ ∧∧⇒≥⎛⎜⎝⎠∧∧∧∧计数读取权限已被提取;未修饰的Own(x)等于Own 1。0(x)或Own0(x)-所有这些都是通过与堆任务E<$0 的 语 法 类 比 。 5−−→,E>和E<$n−→。obvvvy中的部分子元素-例如Ownz(x)*OwnzJ(x)Ownz+zJ(x) z>0zJ>0- 它允许某些扣除-例如OwnE(x)E0的情况。次在OwnE(x)中的置换可以是E的置换,但不能是x。你可能会合理地期望这个逻辑的模型是由Own谓词定义的分离堆栈或多或少是这样的,但转让不等于所有权的原则意味着我们需要更多的东西。Hongseok Yang给我的模型是一个拥有变量的集合O和一个将变量映射到整数的堆栈S堆栈(O,s)*(OJ,sJ)= ifO<$OJ =0<$s=sJ then(O<$OJ,s)else unfined(13)(O,s)<$Own(x)i <$x∈OO1、O2存在于s.t.(O,s)P1*P2i(O 1,s)*(O 2,s)=(O,s)且(O1,s)αP1和(O2,s)αP2(O,s)P1P2i(O,s)P1and(O,s)P2(O,s)P1P2i(O,s)P1or(O,s)P2(O,s)P1 not((O,s)P)(十四)该模型允许我们判断一个特定的断言是有良好支持的:定义3.1当(O,s)≠P时,P是良好支持的,那么对于任何栈sJS.T. 对于所有的o在O s(o)=SJ(o),(O,SJ)<$P.这允许P提到由s映射但在O之外的变量,只要这些变量的特定值这允许我说Own(x)完全等价于Own(x)y=y,并且两者都得到了很好的支持。类似地,(Own(x)y= 3)*(Own(y)y= 3)也得到了很好的支持,等价于Own(x)*Own(y)y= 3。这两个属性简化了下面对变量赋值的处理。该逻辑仅限于对得到良好支持的断言的推断,但我为了简化讨论,我这让人感觉有点懦弱,为了恢复我的自豪感,我⎞⎟R. Bornat等人/理论计算机科学电子笔记155(2006)247255∧···∧¬4可变上下文为了简化断言、替换和良好作用域的概念,我引入了一些符号。P::=ΓQ|P*P|PP|PP( 15)其中变量上下文Γ是一个逗号分隔的变量名列表(可能用权限修饰),Q是一个传统的谓词逻辑断言(堆外没有任何东西:no›→,noemp,no*,no*)−。上下文断言x1,x2,...,xnQ是(Own(x1)*)拥有(x2)** Own(xn))Q.它断言所有且仅变量在上下文和真理的Q.逗号模仿*,所以它是结合的和可交换的。如果公式的所有自由变量都在上下文中拥有,或者如果它可以通过等价转换转换为一个良好作用域的断言,则上下文断言是良好作用域的。显然,范围良好的断言得到了很好的支持。如果变量context不止一次地声明一个变量,则上下文断言为false(仅仅因为Own(x)*Own(x)为false)。不受支持的断言不一定是假的,但是由于它P1*P2,其中P1和P2是上下文断言,拆分堆栈。因为你总是可以使用部分权限, 所 以你总是可以拆分上下文断言。你也可以把它们连接起来:(Γ<$Q)*(Δ<$R)等价于Γ, Δ<$Q R。特别地,这意味着如果Γ,Δ不止一次声明同一个变量,则它你也可以做明显的学习,如将P1*(P2<$P3)转换为(P1*P2)<$(P1*P3)。很4.1信号量权限在硬件术语中,信号量只是一个变量。在软件术语中,它这在本文的示例信号量m的总权限分为三部分:mP、mV和mS。S权限由信号量资源包本身持有,并允许读取和写入。P和V权限是存在权限,4[4]说你在这里提供细节会分散注意力256R. Bornat等人/理论计算机科学电子笔记155(2006)247∧并且根本不允许访问变量,但它们分别允许P和V。P和V是无限可分的,允许任意共享信号量,但我将在本文中省去这种符号上的复杂性:在我的示例中,为了简单起见,我将假设每个信号量只有一个用户。5规则在演绎中,我只允许有良好作用域的断言,并且这种限制取代了以前限制变量使用的附加条件。框架规则现在几乎没有任何修饰,但它确实需要一个附加条件(您{Q}C{R},前提是P范围明确{P * Q}C{P * R}(十六)C不覆盖P的自由变量的附带条件已经成为良好作用域[5]由于变量赋值规则(19)坚持被覆盖的变量必须是完全所有的,因此结果就是我们所需要的:C不能覆盖P的自由变量,因为P的上下文必须至少声明部分所有权,然后P* Q中的并发规则与(2)没有变化,但现在不需要附加条件,因为断言必须有良好的作用域,因此得到良好的支持和堆栈分离。CCR规则现在在进入命令C时合并堆栈,并在退出时拆分它们。它需要一个额外的前置条件,因为必须有(不一定是全部)读取资源包b的权限。b的不变量I b的良好作用域是一个附带条件:这又一次几乎是语法上的,并且在任何情况下都是处理b的声明的规则(这里没有显示)直接要求的Q→(Own(b)*true){(Q* Ib)<$G}C{R* Ib},条件是I{Q}withb whenG doC od{R}范围很广(十七)前置条件(Q* Ib)G给出了一个小问题。G是一个程序公式,我们必须把它理解为一个断言[5]任何明智的工具编写者肯定会坚持P必须在语法上有良好的作用域,不需要等价转换。BR. Bornat等人/理论计算机科学电子笔记155(2006)247257EEE(not必须是一个作用域良好的断言),它将Q和Ib和G分布在结果中6例如:Q:mP,t>ptrueIm:(mS<$m= 0)<$(mS,c,tc<$c≥0)G: m=1(mP,t>,mSm=0m=1)(十八)(Q* Im)(mP),t>,mS,c,tc<$c≥0<$m = 1)变量赋值公理变成了一条规则,它的前提条件甚至比上面的副条件更符合语法R→(Own(x)*true){Rx}x:=E{R}(19)不存在混叠边条件(无需隐藏在分离逻辑:参见第6.1节),但当然R和Rx一定要有很好的范围。这个定义有一些有趣的后果(i) 使用(*)拆分堆栈,然后应用变量赋值是很好的:{(xy= 3)*(yy= 3)}x:=y{(xx= 3)*(yy= 3)}(20)这个前提条件看起来很奇怪,因为xy= 3是病态作用域。如果我们在后置条件中组合堆栈,然后应用公理{x,y<$y= 3<$y = 3}x:=y{x,y<$x= 3<$y = 3}(21)一切都很正常事实上(ii) R和Rx必须有良好的作用域,并且两者都必须包含Own(x),但是否则x不一定出现在R中。这使得惊喜,{xtrue}x:=y+1{x true}(22)如果你不注意,就我258R. Bornat等人/理论计算机科学电子笔记155(2006)2476 我相信这就是杨的模型所说的意思,但我详细解释了一下,以防你发现它像我一样令人惊讶。R. Bornat等人/理论计算机科学电子笔记155(2006)247259E∧可能性但它也可以给人一个惊喜:{x<$y+1 =y+1}x:=y+1{x<$x=x}(23)这个前提条件得到了很好的支持,而且它6行动中的规则由于霍尔逻辑对资源没有任何说明,我们可以做出误导性的推论,如{y=1}x:= 7{y =1}(24)他们逃避展示任务所有成果的义务在分离逻辑中,框架规则抓住了黄鼠狼,因为边条件不允许演绎{y= 1}x:= 7{y = 1}{x= 3*y= 1}x:= 7{x = 3*y= 1}(25)因为x:= 7在x= 3中自由地改变了一个变量。变量上下文也会在两个陷阱中捕捉到恶意者。一个不拥有x的前件{yy=1}x:= 7{yy=1}{(xx= 3)*(yy= 1)}x:= 7{(xx= 3)*(yy= 1)}(26)失败,因为它没有资源来支持分配。声称x{x,y<$y=1}x:= 7{x,y<$y=1}{(x<$x= 3)*(x,y<$y= 1)}x:= 7{(x<$x= 3)*(x,y<$y= 1)}(27)can’t6.1变量别名和上下文在变量赋值规则(19)中,我们必须拥有被赋值的变量x,R或Rx中提到的任何变量必须在上下文中命名。以来上下文描述了一个以 *分隔的Own谓词列表,这就是别名:不能有x的但我可以做得更好,控制锯齿。Own(x)Own(y)描述了一个具有两260R. Bornat等人/理论计算机科学电子笔记155(2006)247个名称的堆栈。在与BI的大胆类比中,我可能会使用逗号来分隔变量,使用逗号来标识变量。取代R. Bornat等人/理论计算机科学电子笔记155(2006)247261-是的{{mPV,mS,c<$m= 0<$c≥0}{mPV,c,mSE⎜EΣ∴⎟⎜Σ∴⎟{mPVtrue}。(mPV)*.(mS<$m = 0)<$(mS,c <$m =1 <$c ≥ 0)ΣΣ∧m=1}∴⎞(mPV,mStruem= 0m= 1)(mPV,mS,c truem= 1c≥ 0m= 1)P(m):{mPV,mS,c<$m= 1<$c≥ 0}单位:= 0⎜⎝{(mP V, c►c≥ 0)*.(mSm=0)}⎟Σ⎟⎠{(mPV,c<$c≥0)*{mPV,cc≥0}C++{mP V, cc>. 0}(mS<$m= 0)<$(mS,c<$m= 1<$c≥ 0)}.ΣΣ- 是的{ (mPV,cc>0)*(mS<$m= 0)<$(mS,c<$m=1<$c≥ 0)true}(mPV,c,mSc>0m=0 true)(mPV,c,mS,cc>0m=1c≥0 true)V(m):{mPV,c,mS<$c>0<$m = 0}单位:= 1⎜⎝{,(mPV►true)*(.mS, c<$m=1<$c≥0)}⎟Σ,⎟⎠{mPVtrue}(mPV)*(mS<$m= 0)<$(mS,c<$m= 1<$c≥ 0)Fig. 1.互斥体之间的变量所有权转移必须是上下文敏感的,这Γ,x,y<$yx<$ yΓ,x;y<$yx <$E(二十八)塔拉,清!就像我们在60年代常说的那样。为了避免把水搅浑,我框架规则在没有重要的附加条件的情况下工作,变量别名也在控制之下,这引入变量上下文的目的是使用CCR解释变量所有权转移。262R. Bornat等人/理论计算机科学电子笔记155(2006)247∨∧≥P(m);c++; V(m)...P(m);c−−; V(m)P(m);c++; V(m)...P(m);c−−; V(m)...P(m);c++; V(m)...P(m);c−−; V(m)图二、 c ≥ 0是不变的吗?7互斥和变量所有权转移考虑程序片段P(m);c++; V(m)(29)信号量m是一个互斥体(一个二进制信号量,其中m= 0m = 1),它拥有/包含一个整数变量c,并保护一个临界区,在这种情况下是单个指令c++。我程序将c从信号量中取出,并将其递增,把它放回V(m)。通过类比在临界区之外的正常或C0 ;在临界区中处于“已签出”状态,我们需要mSm= 0.因此,不变量为(mS<$m= 0)<$(mS,c<$m= 1<$c≥ 0)(30)证明(29)保持信号量不变量如图1所示。唯一棘手的是对V(m)入口的简化。第二行中的第二个析取符为false,因为它两次声明c。这就是工作中的分离属性:如果每个线程都遵守规则,并且如果一个线程具有c权限,则信号量必须处于mSm= 0状态。临界区(c++)与使用相同互斥体的任何其他临界区是互斥的,因为程序获得了访问c的独占权限。即使是这个简单的例子,也需要大量繁琐的计算来证明一个简单的所有权转移无论如何,在其他例子中,我将省略进入信号量时的重排和退出信号量时的结果步骤(图1中P(m)和V(m)的第一行和最后一R. Bornat等人/理论计算机科学电子笔记155(2006)247263⎜{⎟≥≥{mPV,mS,c,t≥−−► m= 0c> 0}⎠⎛⎟c−1P(m){mPV,c,tc<$c≥0}C++{mPV,c,tc−1<$c>0}{mPV,c,tc,t><$c>0}V(m){mPV,t>Vtrue}...{mP V,t>Pt.rue}(mPV,t>,mStruem= 0m = 1)(mPV,t>,mS,c,tc{mPV,mS,c,tc−1<$m= 1<$c≥0}<$M,m,c,t c−1m= 1c0c10P(m):{mPV,mS,c,tc−1<$m= 1<$c>0}m:= 0⎜ ⎟{(mPV,c,tc−1<$c>0)*(mS<$m= 0)}{mPV,c,tc−1<$c>0}c−−{mPV,c,tc<$c≥0} V(m){mPVtrue}图三.票证允许变量递减以保持不变8辅助票务换乘读者和作者的例子(图4)呈现了一个特殊的权限-会计困难。读取器互斥体包含各种资源,其中包括计数变量c;我们希望保证c 0是信号量不变量的一部分。count变量在阅读器序言中递增,并且可以像图1中那样进行逻辑处理。但在后记中,计数减少了:如果我们所能依赖的是来自不变量的c0,那么c可以使c为负,不变量被破坏。展示问题的最简单的方法是编写大量的一个程序,它首先递增,然后递减计数,每次在临界区,如图2所示。很明显,这个程序做的问题是通过局部推理来证明它解决方案依赖于使用辅助t来跟踪已发生的增量和减量的数量,使用权限来记录264R. Bornat等人/理论计算机科学电子笔记155(2006)247≥-≥≥差异。7回想一下,与堆权限类似,tN是计数源权限,t>是计数读权限:那么信号量不变式为(mS<$m= 0)<$(mS,c,tc<$m= 1<$c≥ 0)(31)在第二个析取符中我证明现在很简单,如图3所示。我请注意,程序从第一个P中出现,具有源权限tc;递增c意味着它可以在后面的V中放回tc,并且仍然留下t>。还要注意c++的前置条件和后置条件:替换会在上下文中删除源代码权限公式。动作都在第二个P里。第一个推论是标准的,根据m的值选择一个不变的替代方案。但是,当我们将来自信号量的tc与来自线程的t>结合起来时,我们得到tc−1,根据计数权限的性质,我们可以推导出c1 0,因此c>0。再一次,分离属性在起作用:如果我们真的有读权限,而信号量真的有源权限,那么重新组合将是另一个有效的源权限。由于计数权限的工作方式,拥有读权限t>是一个保证,在某处有一个源权限tN,N1。在这个程序中,我们知道它在哪里:锁在互斥体中,或者在临界区签出。ticket变量t是一个完美的辅助变量。程序对此一无所知,因为我们Shazam!- 它的工作原理,与本地推理,分离属性,和一个信号量不变。我9读者和作家充分的准备:我现在准备攻击读者和作者的例子的堡垒,在图4中或多或少显示了它的原始形式。信号量m(原始中的互斥体)持有变量c(原始中的readcount),当c>0时,它还持有对共享[7] Matthew Parkinson和我独立地设计了解决方案,使用辅助堆缓冲器上的读权限作为票据。 Cristiano Calcagno指出,只允许访问变量就可以了。R. Bornat等人/理论计算机科学电子笔记155(2006)247265⎛⎜⎜⎝⎟⎠⎜⎛⎜⎝⎠∧阅读器和书写器开场白:P(m);c++;如果c= 1,则P(w)else skip fi;V(m);P(w);..........阅读发生写作发生..........V(w);结语:P(m);c−−;如果c= 0,则V(w)else跳过fi;V(m)图四、读者和作者(来自[9],有缩短的名字和明确的跳过)可以在序言和尾声之间的“阅读发生”部分阅读的资源信号量w(写入原始)拥有对同一共享资源的总W的不变量非常简单:(wS<$w= 0)<$(wS,y<$w= 1)(32)m的不变量稍微复杂一些(mS<$m=0)(mS,wPV,c, t<$m=1<$c=0)(mS,wPV,c,tc,yc<$m=1<$c >0)(三十三)我们需要tickett,因为变量y,代表由m和w控制的关键资源,如果读取器具有t>权限,那么我们可以确定m信号量不在m S,w P V,c,t m= 1中c=0状态,因为这将要求0 μ ct资源。也就是说,t>ticket保证当我们输入结语关于读取器和写入器的真正有趣的事情是,写入器的临界区与“读取发生”区是互斥的,后者不受互斥的当然,互斥是由分离属性提供的:读取器图5显示了读者的序言证明是如何进行的。这个证明又一次非常乏味。它可以减少一点,⎞⎟⎞⎟266R. Bornat等人/理论计算机科学电子笔记155(2006)247⎛⎜⎧⎪⎨拉克什茨C⎪⎟⎜⎜⎝⎜⎩⎭,(mPV,mS,wPV,c,t<$c=0<$m=0)但是,⎟⎛⎜{mPVtrue}(mPV,mStruem= 0m = 1)(mPV,mS,wPV,c, ttruem=1c=0m=1),⎫⎪⎬∴⎞,P(m):(mPV,mS,wPV,c, t<$c=0<$m=1)(mPV,mS,wPV,c,tc,yc<$c >0<$m=1)m:= 0mm好吧.(mPV,wPV,c, t<$c=0)(米)PV,wPV*(m)► m=0){(mPV,wPV,c, t<$c=0)<$(mPV,wPV,c,tc,yc<$ c >0)}c++{(mPV,wPV,c, t<$c−1=0)<$(mPV,wPV,c,tc−1,yc−1<$c−1>0)}如果c= 1,则{(mPV,wPV,c, t<$c −1=0<$c=1)<$(mPV,wPV,c,tc−1,yc−1<$c−1>0<$c=1)}<${mP V,wP.V,c, t<$c=1}(mPV,wPV,c,t,wS, y<$c=1<$w=1<$w=1)(mPV,wPV,c,t,wSc=1w=0w=1)P(w): {mPV,wPV,c,t,wS, y<$c=1<$w=1}w:= 0{mPV,wPV,c,t,wS, y<$c=1<$w=0}{(mPV,wPV,c,t, y<$c=1)*(wS<$w=0)}{mPV,wPV,c,t, y<$c=1}{mPV,wPV,c,tc−1,yc−1<$c=1}else{(mPV,wPV,c, t<$c −1=0<$c/=1)<$(mPV,wPV,c,tc−1,yc−1<$c−1>0<$c/=1)}<${mPV,wPV,c,tc−1,yc−1<$ c >1)}skip{mPV,wPV,c,tc−1,yc−1<$ c >1)}fi{mPV,wPV,c,tc−1,yc−1<$c≥1)}{mPV,wPV,c,tc,t>,yc,y>c≥1)}⎛⎧⎪⎨(mPV,wPV,c,tc,t>,yc,y>,mS►c≥1∧m=0∧true)∨⎫⎪⎬⎞∴(mPV,wPV,c,tc,t>,yc,y>,mS,wPV,c, t(mPV,wPV,c,tc,t>,yc,y>,mS,wPV,c,tc,ycV(m):<${mPV,wPV,c,tc,t>,yc,y>,mS<$c≥1<$m=0}<$m:= 1{mPV,wPV,c,tc,t>,yc,y>,mS<$c≥1<$m=1}(mPV,t>,y>true)*(mS,wPV,c,tc,ycm=1c >0){mPV,t>,y>Vtrue}图五. 读者序言⎟,c,tc,yc<$c>0)S⎞⎟⎟⎠⎜⎟、⎟⎠
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功