共享内存程序的无粒度足迹语义研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记308（2014）65-86www.elsevier.com/locate/entcs共享内存程序的无粒度足迹语义研究斯蒂芬·布鲁克斯美国匹兹堡卡内基梅隆大学计算机科学系摘要我们为共享内存并行程序开发了一种改进的无粒度指称语义，基于早期基于痕迹的模型与当地状态和足迹的想法[4]。关键的新想法是一种更精细的竞争检测方法，从而产生具有更好抽象属性的模型。 而不是治疗竞争条件作为一个与之前的工作一样，我们以符合Dijkstra我们得到一个模型，其中只有同步操作（用于锁定和解锁二进制信号量）被认为是原子的，其以抽象方式匹配这些构造的通常实现。 除此之外，没有其他的原子性假设，所以我们的模型是真正的无颗粒。我们的语义支持组合程序分析的基础上“顺序”推理顺序代码片段，即使当此代码发生在并行上下文中，并产生一个简单的语义表征的种族免费代码。该语义验证了并发编程方法[6，9]中对“关键变量”的静态约束部分正确性，如并发分离逻辑[8]。 对种族检测的新处理允许对种族程序进行更精细的分析。通过以一种普遍的方式来构建我们的想法和概念，我们希望我们的结果可以在更广泛的环境中应用关键词：并发，共享内存，原子性，粒度，部分正确性，竞争条件，指称语义介绍共享内存程序很难推理，因为在更新同一块共享状态时，并发进程之间可能会发生干扰在构建共享内存程序的语义模型时也会出现类似的困难。大多数传统模型都假设执行的粒度是固定的，例如原子分配或原子读取和写入[2，10]。这样的假设1本研究由美国国家科学基金会资助，资助号为CCF-1017011。 本文件所载的观点和结论是作者的观点和结论，不应被解释代表任何赞助机构、美国政府或任何其他实体的官方政策，无论是明示的还是暗示的。http://dx.doi.org/10.1016/j.entcs.2014.10.0051571-0661/© 2014 Elsevier B. V.保留所有权利。66S. Brookes/Electronic Notes in Theoretical Computer Science 308（2014）65可能在实践中不成立，也不普遍成立，因此基于这些模型的程序分析仅对有限范围的实现有效相比之下，在顺序设置中，忽略粒度是安全的，因此传统的顺序程序语义模型只关注程序执行的初始和最终状态众所周知，这种简单的方法不适用于并行程序[10]：由c1和c2表示的状态转换不能由c1和c2表示的状态转换确定。理想情况下，我们需要为并行程序设计一个语义模型，该模型既具有状态转换语义的简单性，又保留了足够的中间状态信息，以便于对并发干扰进行推理，同时又不做过于具体的粒度假设。这种关注已经刺激了一个研究者为共享内存并发设计雷诺兹试图通过将原子动作分解为瞬时片段来避免粒度作者开发了一个“足迹跟踪”模型，这是本文所述方法的先驱，但现在回想起来，我们发现这个模型过于复杂，无法完全抽象。在这里，我们提供了一个更精简的足迹跟踪语义版本，具有更好的抽象属性。主要的新思想涉及对竞争条件的更精细的描述，这是一个在语义构建中具有深层分支的明显简单的思想。我们将我们的语义模型归类为“无粒度”，因为模型构造抽象出了关于什么构成原子操作的不相关信息，而不是通常的信息。（和合理的）假设，同步的原始操作（锁定和解锁资源）是原子的，资源的行为就像二进制信号量：在程序执行的所有阶段，每个资源由至多一个进程保持（已经被锁定并且尚未解锁）。我们的想法应该推广到其他原子同步结构（例如信号量上的Dijkstra风格的P和V操作），但我们在这里不考虑细节我们在本文中处理一个简单的共享内存语言，省略指针。我们的开发建立在我们之前对跟踪模型[2]和并发分离逻辑[3，4]的工作基础上，其中我们将可变状态与并发结合起来，因此我们希望能够通过将状态作为存储与堆配对来适应这里提出的新思想。对指针和可变状态的扩展确实引入了新的特性，比如存储分配和释放，所以我们需要仔细调整技术细节。合并局部范围的声明是很简单的，就像c中的blockconstructresourcer声明了一个名为r的局部资源，仅供c使用。由于空间的原因，我们推迟这些扩展和一些语义的细节和证明，以一个更完整的版本的文件。S. Brookes/Electronic Notes in Theoretical Computer Science 308（2014）65671静态语义和静态语义我们考虑一个简单的共享内存并行语言，而程序扩展与并行组合和条件临界区域。标识符（或程序变量）i是可分配的整数值变量，区域名称（或资源）r取值0和1，表示标识符的集合Ide和资源名称的集合Res是不相交的。将资源名和定义符分开是有意义的，因为它们的语法规则不同（资源不出现在赋值命令或表达式中），而且我们对它们的实现做了假设（资源只在进入和退出关键区域时原子地更新，而我们不假设赋值是否是原子的）。整数表达式e和布尔表达式b的语法是标准的，具有通常的算术和布尔结构。例如，表达式的抽象语法包括：e ：：= n|我|e1 + e2|......这是什么？B ：：= 真正|虚假|e1 = e2|......这是什么？其中n的范围超过整数。表达式的静态语义如下所示。定义1我们定义了标识符的自由集（e）和自由集（b），其中e是和b，分别通过结构归纳：free（n）={}free（i）={i}free（e1+e2）=free（e1）free（e2）free（true）={}free（false）={}free（e1=e2）=free（e1）free（e2）命令（或进程）c的语法由下式给出c：：= skip|i：= e|c1; c2|如果b那么c1否则c2|而b做c|c1-c2|当b做c时，条件临界区域的形式为当b

下载后可阅读完整内容，剩余1页未读，立即下载