没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记304(2014)167-182www.elsevier.com/locate/entcs一种类C语言TraianFlorinS,erbaunut,1991,2布加勒斯特大学计算机科学系摘要本文展示了如何轻松地将编程语言的K定义转换为运行时验证工具。 为了增加这些运行时验证工具可用于测试真实世界程序的信心,本文使用了KERNEL C,这是C编程语言的一个子集,包含函数,内存分配,指针运算和输入/输出,可用于执行和测试真实的C程序。 内核C扩展了线程和同步结构,并从其顺序语义派生出两种并发语义。第一个语义定义了一个顺序一致的内存模型,可以很容易地转换成一个运行时验证工具,用于检查数据空间和死锁自由度。第二种语义以相对最小的方式定义了一个基于x86-TSO内存模型的宽松内存模型通过探索Peterson互斥算法在两种定义下的实现,证明了该算法保证了顺序一致模型的互斥,但不能保证放松模型的互斥,而且通过允许语言中的栅栏操作,该算法也可以被固定并证明对TSO模型是正确的关键词:验证,工具,数据区,死锁,Peterson1介绍本文简要介绍了使用编程语言的形式定义作为测试和分析工具的过程我们认为K[21,22]定义可以直接用于测试和分析用现实语言编写的程序的执行,或者通过扩展它们成为运行时分析工具。K定义的重写逻辑表示使他们能够通过Maude重写引擎获得重写逻辑的通用工具:状态空间探索,LTL模型检查,归纳定理证明等。这些分析工具的集合本身就足以提供更多关于程序行为的信息,而不是简单地使用该语言的解释器或编译器测试程序然而,定义的关键是1这项工作得到了合同161/15.06.2010,SMISCSNR 602-12516(DAK)的支持。2电子邮件:traian. fmi.unibuc.rohttp://dx.doi.org/10.1016/j.entcs.2014.05.0091571-0661/© 2014 Elsevier B. V.保留所有权利。168T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167语义的回报不止一种:通过对定义的相对较少的修改,人们可以使用相同的通用工具来获得类型检查器和类型推断器[9],静态策略检查工具[13,14],运行时验证工具[20],甚至Hoare类程序验证工具[19]。贡献在本文中,我们重点分析了使用K框架的编程语言的并发方面,并表明通过稍微调整语言的定义,可以很容易地获得针对数据缓存和死锁的运行时验证工具为了强调此外,我们展示了如何以最小的代价获得一个类似x86-TSO [15]的KERNEL C松弛内存模型,并通过探索两种模型下程序执行的可能行为,使用它来测试各种内存一致性模型之间的差异。能够分析并发程序在各种内存一致性模型下的行为,无论是在语言设计的早期阶段,当人们可以决定如何加强内存一致性时,还是一旦一种语言已经在使用中,它允许检测和解决用该语言编写的程序中的本文仅提供了一个概念证明,即可以直接从语言定义中推导出这些工具;然而,我们认为基于相同的想法构建更有效的工具并为了控制论文的大小,我们假设用户已经熟悉K框架[22,21],包括使用K工具[23]编写,执行和探索K定义本文的其余部分组织如下。第二节介绍了KERNEL C的语法。第3节给出了其纯顺序结构的完整语义和并发部分的简单顺序一致语义。第4节展示了如何使用Kernel C来探索程序的行为,以及如何调整KERNELC第5节定义了一种基于x86- TSO内存模型[15]的宽松内存模型的内存访问和并发构造的替代语义,并表明可以使用可用的工具测试该模型与顺序一致模型之间的差异第6节结束。相关工作除了本文中描述的思想之外,KERNEL C已经被用来展示如何直接从语义中轻松获得强内存安全的运行时验证工具[20],或者集成到基于匹配逻辑的重写程序验证工具[18]中,这是一种基于K的新验证逻辑[19]。虽然在本文中,我们使用KERNEL C,但我们提出的结果已被改编并应用于C语言的全面K定义[8,7]。T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167169由于在宽松的记忆模型下推理的复杂性以及大多数程序员对执行顺序一致性所做的假设,最近有许多检测非顺序一致执行的研究成果[16,1,2,3,11,12,4]。我们的方法与其他方法的不同之处在于,它是基于被分析语言的形式定义,并直接从它派生出来。尽管仍处于初期阶段,但它表明,基于重写的定义可以用来获得编程语言的工具。2KernelCExp::=#Int| #ID| DeclId| PointerId| Exp+ Exp [strict]| Exp-Exp[严格]| Exp== Exp [strict]| Exp<=Exp[strict]| ! Exp| Exp &&Exp| Exp ? Exp:Exp| (int*)malloc(Exp*sizeof(int))[strict]| *实验| 有效期[有效期]| Exp=Exp[strict(2)]| #Id(Exps)[strict(2)]| printf(“%d;",Exp)[strict]Stmt:={}|联系我们| Exp;[strict]| if(Exp)Stmt| if(Exp)Stmtelse Stmt [strict(1)]| while(Exp)Stmt| DeclId DeclId{StmtList}| return Exp;[strict]StmtList::=Stmt| StmtListStmtListPgm::= StmtListDeclId::= int Exp|void PointerIdPointerId::=#Id|*PointerId[strict]#Id::= mainFig. 1. KerneL C序列片段的克隆图1描述了凯尔内尔克使用类似BNF的符号。 语法尽可能接近C语法允许相当大的C程序类被解析和执行,C的定义。尽管如此,语法是相当小的,只涵盖了C语言的33个结构。函数声明包含一个DeclId,即一个类型标识符,后跟一个DeclId列表(应该用括号括起来,尽管不是必需的),然后是函数的主体。KER nEL C允许的语句非常简单,从表达式语句开始, 到块,条件和循环语句。2.1使用线程KERNELC的基本语法扩展了几个多线程操作,如线程创建、锁同步和线程连接。为了保持简单,我们采用了一组非常有限的同步原语和语法,虽然不像新的C标准中提出的语法,但在我们的模型中更容易使用170T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167⟨⟩⟨⟩Exp::= spawn Exp| join( Exp )[strict]| 获取(Exp)[严格]| release(Exp)[strict]我们为线程创建语句“spawn”选择了一个表达式作为其唯一的参数,该表达式应该是函数的调用。 直觉告诉我们函数的参数将在当前线程中被评估,而函数调用在新产生的线程中执行。“spawn” returns an identifier等待指定的线程结束后再继续。“ acquire” and “ release” can acquire and release any value;however, in our examples only memory locations are used as3基本内核C语义K定义通过明确执行状态的配置结构和提供一组规则来描述编程语言的执行模型,这些规则指定在执行期间如何更改执行状态。 一个程序。KERNEL C序列片段的结构非常简单。在顶层,我们有两个单元格,T表示正在运行的程序的状态,result表示已完成的程序。T单元包含计算单元k、将(局部)变量映射到值的环境单元env、将函数的名称映射到它们的定义的funs单元、用于在调用函数时保存控制上下文的函数堆栈单元fstack、输出单元out、将位置(表示为自然值)映射到值(整数)的存储器单元fstack、用于维护关于存储器块分配大小的信息的ptr单元、以及用于生成新位置和整数的计数器单元next与T单元并行的结果单元用于在计算成功完成后向用户输出更简洁的结果。因此,T细胞和结果细胞是相互排斥的;“?“符号附加到他们的名字指定,他们中的任何一个都可以错过一个运行配置。配置文件:..Σ·列表..·Kk。·M.阿普伦河·Ma。我的朋友。Σ“”mem·地图PTR0出来·地图- 是 的“结果呢?T?一个重要的设计选择是,我们已经决定清楚地区分堆分配的内存(保存在内存单元中)和局部变量内存(保存在env单元中),作为从变量到值的直接映射。由于这种选择,不可能获得变量的地址,这是由于KERNEL C中不存在引用运算符而强制执行的。另一个简化设计的决定是不处理范围。下面给出的语义规则假设,一旦声明了一个变量,它在封装函数执行的其余部分都是可见的,因此在函数执行期间不应该重复声明同一变量f叠下T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167171⟨⟩⟨⟩N′..N+NatN′→undefN+IntN′我们将只关注与内存访问和函数调用相关的规则,而不是呈现整个语义,这对于顺序片段来说局部变量。新声明的变量在环境中映射到特殊的undef计算常量,该常量不是值,因此无法读取。上下文鲁尔···⟩公司简介int_=Q第十章虚空k环境环境[undef/X]K上下文指定了评估策略,确保了一个上下文的某些参数在给出结构本身的执行规则之前,先对声明变量的K规则几乎是不言自明的:如果X的声明位于由k单元格表示的执行堆栈的顶部,那么用void替换它并设置X的值在环境中被破坏。k单元格右侧的省略号 第一个。这条规则还表明,K中的变换是局部指定的,方法是在要替换的部分下面加下划线,并将其替换写在这条线下面。KERNELC中的局部变量是受限制的。它们不能被共享,不能被处理,因此驻留在称为环境的单独空间中。鲁尔X···k···X<$→ V···env鲁尔X=V······V V V堆分配和解引用。下面的规则定义了一个非常简单的内存分配机制,它基本上是按顺序分配内存,从最后一个分配位置之后的位置开始。鲁尔intn(int*)malloc(N*sizeof(int))···intk= 0···地图···中国N′N′→N⎜ ⎟⎝⟨····Map···⟩mem⟨N′⟩next⎠下面的规则指定了对堆内存的原子访问(确保按顺序一致的语义),用于读和写操作。上下文* Q=_勒夫规则*N···V[过渡]规则与和平*N=V··· __V V[过渡]我们使用transition标签的规则表达的语义的操作,以指示K工具,其交互的顺序应被认为是在执行的过渡图。用户声明的函数。在遇到函数声明时,函数简单地保存在函数映射中。鲁尔intF Xl{Sts}····KF›→intF Xl{Sts}此外,我们将void函数转化为返回特殊值void的整数函数,以避免对后者进行特殊172T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167⎜⎝配置文件:鲁尔voidFintFXl{Sts}Sts返回void;当调用一个函数时,一个三元组被压入函数栈,由函数名、当前环境和计算的剩余部分组成。然后,当前计算被函数体替换,环境被参数到其传递值的映射替换。当返回时,环境和计算被恢复,函数调用被返回值替换。将函数名压入函数堆栈的原因是,这有效地公开了调用堆栈以供分析之用。鲁尔F(VI)aKbindTo(Xl,Vl)aSts⟩k⟨Env⟩env⎞⎟···F›→intF Xl{Sts}···F#环境#K···鲁尔返回V;a_k_Env_#Env#K···Env堆栈VaK鲁尔Env·K鲁尔bindTo(,)···bindTo(X,Xl,V,Vl)···bindEnv谢琴夫·KbindTo(Xl,Vl)环境[V/X]输出. 输出只是简单地附加到输出输出单元格。规则和规则printf(“%d;",I)····切出虚空[过渡]I3.1一种KERNELC线程为了执行多线程程序,必须更新配置以将计算、局部变量和调用堆栈分组在一个线程单元中,该线程单元由id标识。多个线程分组在一个线程单元中。此外,所有已完成线程的id都收集在cthreads单元中。. . . .·Kk。·映射环境。·列出堆栈。0个ID的线程的线程。·地图锁. “. ·网站地图funs. “出来. ·网站地图mem. ·网站地图PTR.1Σ下.·套装cthreadsT?结果呢?请注意,虽然配置发生了变化,但现有规则不需要改变,因为变化只是结构性的。给定一个配置,K工具使用其结构来具体化规则并使其可执行。spawn的语义是线程语法中提到的语义。我们首先有一个上下文来评估函数调用的参数(不调用函数),然后我们将函数调用委托给一个新线程。上下文spawn_(Q)⎜⎛T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167173⎛⎞−−⎜⎟鲁尔⟨spawnX(Vl)···⟩k⟨T公司简介不[过渡]T+Int1···一个锁如果还没有被任何线程获取,那么它可以被获取。请注意,我们鲁尔⟨acquire(N)···⟩k⟨T⟩id⟨Locks·地图锁定⎝鲁尔虚空[过渡]N›→Twhen<$BoolNin keysLocks解锁(N)···kTid···N›→T···锁虚空[过渡]·地图在完成时,线程在已完成线程的集合中注册其id,该id用作连接的信号。鲁尔····箱包····设置···螺纹不鲁尔join(T)···04并发程序上面的定义为我们的KERNELC并发构造提出了一个简单的顺序一致的语义。我们将在这里展示这个定义如何直接用作分析和观察程序执行的工具,以及如何通过定义一个简单的扩展来进一步开发它,该扩展允许检查程序执行的数据空间自由度。下面的银行例子是一个Java类的C实现,展示了一个并发错误模式[10]。这个类试图定义一个帐户和一些基本的操作:创建,存款,余额,取款和转移到另一个帐户。图2展示了它的C实现,它将对象编码为保存可用金额的位置,将类的方法编码为将接收者对象的位置作为其第一个参数的函数此外,与Java类似,我们通过在函数开始时锁定接收器对象的位置并在返回之前解锁它来建模方法的synchronized属性检查程序行为的最简单方法我们可以使用krun命令:$krunpAccount.c100;20;300;220;输出是预期的结果,两个余额都增加了200,这在正常执行中可能会发生。但是,如果我们使用krun搜索执行的所有可能结果,$krunpAccount.c搜索搜寻结果:⎠174T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167−⟨⟩⟨⟩⟨⟩public intfindDuplicate(intfindDuplicate){publicintfindDuplicate(intfindDuplicate,intfindDuplicate);m =m;returna;}publicintfindDuplicate(intfindDuplicate){(a);a= a+m;release(a);}public intfindDuplicate(intfindDuplicate){return(a);return( b);returnpublicintfindDuplicate(intfindDuplicate){(a);if(m<= 0){{\displaystyle\mathbb {\mathbb {m}release(a);}public intfindDuplicate(intfindDuplicate,intnums){(a);if(m<= 0){a =b= b+m;}release(a);}}voidrun(inta,intb){ deposit(a,300);withdraw(a,100);transfer(a,b,100);}intmain()函数{publicintfindDuplicate(“% d;”); publicintfindDuplicate(“%d; ");printf(“%d;",balance(b));int t1=spawn(run(a,b));intt2=spawn(run(b,a));join(t1);join(t2);printf(“%d;");printf(“%d;");返回0;}图二、pAccount.c:Account解决方案1,状态626:结果“100;20;200;20;”/结果.....解决方案11,状态674:结果“100;20;100;220;”/结果解决方案2,状态665:结果“100;20;300;220;”/结果我们注意到另外10种可能出乎意料的解决办法。我们可以猜测它一定是由于数据空间,但要找到它,我们需要更强大的工具。搜索数据缓存T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167175让我们在下面说明如何检测数据字符,尝试修复它们,然后重新检查程序的数据字符。我们采用了一个简单的定义:一个数据区可以被观察到,如果在程序的执行过程中,有一个时刻,两个线程可以作为下一个执行步骤的转换访问同一个内存位置,并且至少有一个访问试图更新位置。176T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167⟨⟩⟨⟩⟨⟩⟨⟩⟨⟩−− −− − ⟨ ⟩ ⟨⟩⟨⟩⟨⟩⟨⟩|−∼⟨⟩⟨⟩|−∼⟨⟩⟨⟩∼⟨⟩⟨⟩|−∼|−⟨⟩⟨⟩⟨⟩∼虽然我们可以将此属性表示为状态上的断言,然后使用Maude如果找到一个,就会产生一个显示比赛的配置;如果没有,由于krun工具会探索由于调度而导致的所有可能的交织,因此该程序被有效地证明是无数据空间的(对于给定的输入)。为此,我们添加两个新单元作为现有单元的替代,race作为k单元的替代,raceDetected作为顶部单元T的替代,以及两个分别捕获写-写和写-读数据区的规则:鲁尔 *N=_.& lt;/K种族>> *N=_.& lt;/K > >种族 *N=_.& lt;/K种族>> *N.& lt;/K>种族这两个规则确保了对于被识别为处于竞争中的两个线程停止任何进一步的计算,并且使它们在表现出竞争的配置中的识别变得容易。请注意,这些规则实际上是重命名计算单元,将其名称(k)重写为race,而不更改其内容。除此之外,我们还添加了另一条规则,一旦检测到竞争,就会改变顶部计算本身,因此我们可以轻松地识别整个配置,一场赛跑鲁尔. B.K.B.R..& lt;/T>raceDetected在新的定义下,简单地执行程序,就能得到和以前一样的输出。然而,当搜索所有在顶部具有raceDetected的配置时,我们获得了16个种族候选者,第一个是以下:$krunpAccount.csearchxsearch pattern='=>检测到的种族B:Bag/ raceDetected '搜索结果:解决方案1, 状态299:...线程...线程...种族122 = 120>.../racefstackListItem(transfer#a>1b>2 #孔; >return void;)ListItem(运行编号。#.)/fstack...螺纹/螺纹/线程...线程...种族∗ 2>.../racefstackListItem(deposit #a>2b>1 #HOLE;>return(a);>... return void;)ListItem(运行编号。#.)/fstack...螺纹/螺纹T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167177−−⟨ ⟩⟨⟩⟨⟩−−⟨⟩在分析反例配置(包括fstack单元格)时,可以注意到竞争的发生是因为对transfer函数中帐户b的访问没有同步。解决这个问题的一个简单方法是在转账函数中额外锁定b账户。在应用这个补丁后,我们可以使用前面的命令验证测试驱动程序确实没有数据空间然而,当在固定数据空间后搜索所有可能的结果时,除了期望的结果外,我们还获得了一个未完成的计算$krunpAccount.c搜索搜寻结果:溶液1,状态184:T...在线客服螺纹接头克雷奇获取(1)./k⟨id⟩/ID...螺纹/螺纹...螺纹/螺纹阿罗克斯1|−> 32|−> 4/锁.../T解决方案2,状态253:结果“100;20;300;220;”/结果螺纹接头克雷奇获取(2)./k⟨id⟩中文(简体)...螺纹/螺纹通过分析这个配置,我们可以检测到两个要传输的调用之间的死锁。通过遵循Dijkstra实现这一点的方法是在任何线程中始终以相同的顺序获取资源,例如:如果(!(a<= b)){获取(a);获取(b);}否则{获取(b);获取(a);}使用这个传递函数的新实现,我们现在可以有效地检查我们的测试驱动程序是否无数据空间和死锁:$krunpAccount.c搜索搜寻结果:解决方案1,状态244:结果“100;20;300;220;”43178T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167⟨⟩⟨⟩¬/结果5一种松弛的内核C存储模型让我们展示如何为并发版本的KERNEL C给出另一个更现实的内存模型语义,并使用可用的分析工具来分析其行为,并将其与第4节定义的KERNEL C的顺序一致版本进行比较。我们将这种语义基于x86-TSO内存模型[15],将线程视为处理器,将局部变量视为寄存器。放松传统的存储器访问顺序一致性语义,这要求对存储器的读取和写入被视为原子,放松的存储器一致性模型允许处理器基本上拥有自己的存储器视图,并且仅在执行中的指定点同步。 这些模型允许更多的并行性,从而更有效地执行多线程程序;然而,这些模型更难推理,因为它们不太直观,更多的可能行为。本节中使用的x86-TSO内存模型将写缓冲器与每个进程(或线程,在我们的情况下)相关联,它收集内存变量的本地更新,并通过考虑这些缓冲器来定义内存访问和同步的语义因此,在我们的K定义中,所有涉及的语言结构的规则都需要改变;然而,除了它们和配置之外,没有其他东西需要改变。另外两个单元需要添加到缓冲线程单元中:一个缓冲单元保存缓冲写入的队列,另一个阻塞单元包含一个缓冲标记,该标记指示线程是否在等待锁定时被阻塞。此外,我们添加了一个列表项构造函数bwrite来表示一个bufferedwrite,它将一个位置和一个值作为参数;我们定义了一个locations函数,它从一个buffered write列表中检索一组位置:syntAXK::=bwrite(#Nat,Val)合成斧Set::=locations列表鲁尔位置·列表·设置鲁尔locations bwrite(A,V)内存位置内存在下文中,我们提出了K规则,它指定了并发KER nEL C的新的宽松内存模型语义,前面是从原始TSO文章[15]中逐字获得的自然语言描述:(i) 如果p未被阻塞,则p可以从地址a处的内存读取v,到a,并且存储器确实在a处包含v;RULEeg- deR ef*A···V当BoolAin locationsMem[过渡]T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167179¬¬¬请注意,线程没有缓冲写入的事实在规则中被建模为附带条件,该条件要求当前写入缓冲器(由变量Mem表示)没有为我们想要从中读取的地址A(ii) 如果p未被阻止并且在其缓冲器中具有作为对a的最新写入的v,则p可以从其用于地址a的写入缓冲器读取v;RULEeLOCAL-deR ef*A···V当BoolAin locationsMem[过渡]通过在将V写入A之后匹配缓冲器的全部内容并通过检查(在边条件中)它不包含任何其他对A的写入,可以确保V是对缓冲器中位置A的最新写入。(iii) p可以在任何时候从其寄存器r读取存储值v由于我们将局部变量视为寄存器,并且由于规则是无约束的,因此现有的读/写局部变量的规则保持不变。(iv) p可以在任何时候将v写入其地址a的写缓冲器RULEeBUFFER-wRI te*A=V···Vbwrite(A,V)此外,在KER nEL C中,我们需要定义在内存位置递增值的规则,与常规读取规则(i)和(ii)类似,这些规则有两个变量:取决于位置是否在适当的写入缓冲器中:RULEeLOCAL-I nC*A++···我当BoolAin locationsMem[过渡]bwrite(A,I+Int1)RULEeg-InC*A++···Ibwrite(A,I+Int1)当BoolAin locationsMem[过渡](v) 如果p未被阻塞,则它可以静默地将最旧的写入从其写入缓冲器出列到存储器;RULEeCOmmI t-wRI tefalse[过渡]清单五(vi) p可以在任何时候将值v写入其寄存器r之一与第(iii)项相同,现行规则无须更改。(vii) 如果p3对于x86处理器,内存围栏(MFENCE)操作确保在围栏命令之前的所有加载和存储操作将在围栏之后发出的任何加载和存储之前提交。180T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167¬我们在这里假设线程同步结构,例如创建、终止和联接都生成MFENCE操作:上下文spawn_(Q)规则⟨spawnX(Vl)···⟩k⟨T下一页·列表下一页·袋鲁尔不[过渡]T+Int1·······箱包····设置···螺纹不鲁尔连接(N)···链接·列表链接···N···链接线程0(viii) 如果锁没有被持有,并且p鲁莱-阿克奎雷⟨acquire(N)···⟩k⟨T⟩id⟨·List⟩buffer⟨Locks·地图锁定虚空当BoolNinkeys[过渡]N›→T(ix) 如果p持有锁,并且它的写缓冲器为空,则它可以结束已删除RULEeReL eAS erelease(N)···虚空[过渡]·地图另外两个规则用于更新被拦截单元格的标记:鲁尔获取(N)···真鲁尔获取(N)···假when<$BoolNin keysLocks第一条规则说,如果线程试图获取一个已经被持有的锁,那么线程就会被阻塞,而第二条规则则在锁被释放后解除线程的阻塞。因此,对于每个并发构造只有一个规则,并且不改变不相关的语言构造,我们定义了一个具有宽松内存模型的KERNEL C使用这种语义,我们可以测试,例如,依赖于忙等待同步的程序不能从顺序一致的内存模型移植考虑Peterson的互斥软件解决方案的KERNELC所呈现的实现使用具有三个参数的函数,flag、turn和t。 flag是一个(动态分配的)数组,turn指向内存中的整数,t用作线程标识符。为了标记临界区,我们分别为0和1标识的线程的临界区开始打印-1和-2,临界区结束打印1和2。T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167181- −−- -−−−−#includestdio.h>#includestdlib. h>intfindDuplicate(intfindDuplicate,intfindDuplicate,intfindDuplicate){findDuplicate [ t]=1;1 t= 1 t;while(int [1 t] int ==1 t){}printf(“%d;",1 t);printf(“%d;",1 + t);printag [ t]= 0;}intmain()函数{int[0]= 0;int[1]= 0;int [1]= 0;int t1 =(int t2)malloc(1); int t1 =spawn(peterson(t2)); int t2 =spawn(peterson(t3)); int t2 =spawn(peterson(t3)); int t1 =spawn(t3); int t2 = spawn(t3);int t3 = spawn(t3); int t4 = spawn(t4); int t5 = spawn(t5); int t6 =spawn(t5); int t6 = spawn(t6);int t6 = spawn(t6); int t7 = spawn(t6); int t7 = spawn(t7); int t8 =spawn(t8); int t8 = spawn(t9);int t8 = spawn(t8); int t9 = spawn(t8); int t8 = spawn(t9); int t8 =spawn返回0;}图3.第三章。Peterson算法的一个C语言实现使用前面K er-nEL C的并发性定义(顺序一致),可以验证互斥是确保要求krun搜索运行程序时可获得的所有最终状态。$krunpPeterson.c搜索搜寻结果:解决方案1, 状态66:联系我们“-1;1;-2;2;”/结果解决方案2, 状态67:联系我们“-2;2;-1;1;”/结果所得结果有力地说明了两个临界区的陈述不能交错。然而,当在并发K ernEL C的松弛内存模型定义中探索同一程序的执行时,互斥并不保证:实际上krun找到了同一任务的6个解决方案,表明序列-1,1和1是相同的。-2,2可以以各种可能的方式交织$krunpPeterson.c搜索搜寻结果:解决方案1, 状态433:联系我们“-1;1;-2;2;”/结果解决方案4, 状态436:联系我们“-2;2;-1;1;”/结果解决方案2, 状态434:联系我们“-1;-2;1;2”/结果解决方案5, 状态437:联系我们“-2;-1;1;2;”/结果解决方案3, 状态435:联系我们“-1;-2;2;1”/结果解决方案6, 状态437:联系我们“-2;-1;2;1;”/结果因此,通过对我们的K定义应用一个简单的、通用的和已经可用的重写逻辑工具,我们已经表明,对于在3.1节定义的顺序一致性假设下实现互斥的程182T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167序,不能依赖本节定义的KERNEL C的松弛记忆模型来实现互斥。我们甚至可以更进一步。假设我们决定实现对函数mfence的额外库函数调用,其语义是强制执行内存围栏(即,缓冲器被清空),然后继续:鲁尔合成斧Exp::=mfence()mfence()···虚空T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167183−−通过这个简单但功能强大的库调用,我们可以通过在while循环之前插入mfence()调用来调整Peterson程序这足以保证互斥,如使用krun工具探索所有交织时所示$krunpPeterson.c搜索搜寻结果:解决方案1, 状态66:联系我们“-1;1;-2;2;”/结果6结论解决方案2, 状态67:联系我们“-2;2;-1;1;”/结果我们已经展示了如何将编程语言的K个定义(可以忽略不计)转化为运行时分析工具,用于测试和分析并发程序的执行。此外,对于相同语言特征的语义具有不同的变体(例如,不同的内存模型)在同一个(可执行)框架中形式化,为测试和分析语言的不同可能语义之间的关系打开了大门。这对语言设计者来说是一个非常有用的工具,允许他们在决定实现哪种语义之前,通过测试一套基准程序来测试同一功能的不同可能语义。我们在这里并不是说,在K框架中几乎免费获得的工具完全消除了用“真正的”编程语言编写专用分析工具的需要尽管如此,我们坚信K框架可以被看作是一个快速原型化和试验这些分析工具的工作台。此外,我们相信编译技术可以直接从K定义中生成(更多)有竞争力的分析工具。引用[1] Atig,M. F.、A. Bouajjani,S. Burckhardt和M. Musuvathi,关于弱记忆模型,在:POPL,2010年,pp.7比18[2] Burckhardt,S.,R. Mr. M. K. Martin,Checkfence:Checking Consistency of Concurrent DataTypes on Released Memory Models,PLDI,2007,pp.12比21[3] Burckhardt,S.和M. Musuvathi,放松记忆模型的有效程序验证,在:CAV,LNCS5123,2008,pp.107-120[4] Burnim,J.,K. Sen和C. Stergiou,放松记忆模型,在:TACAS,LNCS6605,2011年,第11页。11-25[5] Clavel,M.,F. Duran,S. Eker,J.Meseguer,P. Lincoln,N. Martí-Oliet和C. Talcott,[6] Dijkstra,E. W.,并发程序控制中的一个问题的解决。ACM8(1965),p. 569.[7] 埃里森角,澳-地 Thesis,University of Illinois(2012).[8] 埃里森角和G. Roanzu,An executable formal semantics of C with applications,POPL533-544.184T. F. Serbanuta/ElectronicNotesinTheoreticalComputerScience304(2014)167[9] 埃里 森角,澳 -地 T. F. S, erbnut,G. Ros, u , A rewriting logicapp roachtotypeinfereen ce, in:WADT'08,LNCS 5486(2009),pp. 135-151[10] Farchi,E.,Y. Nir和S. Ur,Concurrent bug patterns and how to test them,in:IPDPS(2003),p.286.[11] 弗拉纳根角,澳-地和S.N. 弗罗因德,检测破坏性种族的对抗性记忆,在:PLDI,2010年,pp.244-254[12] Gopalakrishnan,G.,Y. Yang和H. Sivaraj,Qb or not qb:An efficient execution veri fication toolfor memory ordering,in:CAV,LNCS3114,2004,pp.401-413[13] 希 尔 斯 , M. , F.Chen 和 G.Ros , u , A rewriting logicapp roachtostaticcheckingofunitsofmeasurerementin C , in : RULE'08 , 2008
下载后可阅读完整内容,剩余1页未读,立即下载
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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://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)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)