FastLane Is Opaque - a Case Study in Mechanized Proofs of Opacity
FastLane Is Opaque - a Case Study in Mechanized Proofs of Opacity
复制标题
FastLane 是不透明的 - 机械化不透明证明的案例研究
DOI：
10.1007/978-3-319-92970-5_7
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Schellhorn M. Wedel O. Travkin J. König H. Wehrheim
中科院分区：
文献类型：
--
作者：
G. Schellhorn M. Wedel O. Travkin J. König H. Wehrheim
软件事务存储器（STM）算法为程序员提供了并发编程的高级同步技术。STM保证通过事务对共享状态的“看似原子的”访问。这种表面上的原子性是STM实现的标准要求，并在不透明度的概念中得到了形式化。不透明性的标准证明技术是viarefinement：STM实现被证明是细化一个IO自动机称为TMS 2，这本身是已知的opaque。本文提出了一个案例研究证明不透明性通过TMS 2细化。我们的案例研究涉及STM的FastLane实现，它是专门设计来实现不同的竞争，以实现良好的性能：它支持不同的模式，低和高线程数加上提供了一个模式之间的切换方案。这个基本概念为验证提供了新的挑战：除了必须证明每个模式本身的不透明度之外，我们还需要证明切换不会使不透明度无效。对于这两个部分，我们提出了完全机械化的不透明性的证明进行了互动定理证明KIV。
Software Transactional Memory (STM) algorithms provide programmers with a high-level synchronization technique for concurrent programming. STMs guarantee “seemingly atomic” access to shared state via transactions. This seeming atomicity is the standard requirement on STM implementations and formalized in the concept ofopacity. The standard proof technique for opacity is viarefinement: the STM implementation is shown to refine an IO automaton called TMS2 which itself is known to be opaque.This paper presents a case study of proving opacity via TMS2 refinement. Our case study concerns theFastLaneimplementation of STM which is specifically designed to achieve good performance on varying contention: it supports different modes for low and high thread counts plus provides a switching scheme between modes. This basic concept provides new challenges for verification: besides having to prove opacity of every mode itself, we also need to show that switching does not invalidate opacity. For both parts, we present fully mechanized proofs of opacity carried out in the interactive theorem prover KIV.
登录
查看更多内容
DOI：
10.1007/s10009-014-0308-3
发表时间：
2015-11-01
影响因子：
1.5
作者：
Ernst, Gidon;Pfaehler, Joerg;Reif, Wolfgang
通讯作者：
Reif, Wolfgang
影响因子：
1
作者：
Doherty, Simon;Groves, Lindsay;Moir, Mark
通讯作者：
Moir, Mark
FastLane：提高软件事务内存的性能以实现低线程数
影响因子：
0.9
作者：
Jons;C. Fetzer;P. Felber;E. Rivière;Gilles Muller
通讯作者：
Gilles Muller
证明悲观 STM 的不透明性
DOI：
10.4230/lipics.opodis.2016.35
发表时间：
2016
期刊：
影响因子：
--
作者：
Simon Doherty;Brijesh Dongol;John Derrick;Gerhard Schellhorn;Heike Wehrheim
通讯作者：
Heike Wehrheim
使用 Spin 检查事务内存的模型
DOI：
10.1145/1400751.1400816
发表时间：
2008
期刊：
2009 29th IEEE International Conference on Distributed Computing Systems
影响因子：
--
作者：
J. O'Leary;Bratin Saha;M. Tuttle
通讯作者：
M. Tuttle