Towards Automatic Lock Removal for Scalable Synchronization
Towards Automatic Lock Removal for Scalable Synchronization
复制标题
实现自动锁移除以实现可扩展同步
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
I. Keidar
中科院分区：
文献类型：
--
作者：
M. Arbel;Guy Golan;Eshcar Hillel;I. Keidar
我们提出了一个代码转换的并发数据结构，这增加了他们的可扩展性，而不牺牲正确性。我们的转换采用基于锁的代码，并将其中的一些锁定步骤替换为乐观同步，以减少争用。主要思想是只要没有共享内存位置被更新，就让每个操作执行数据结构的乐观遍历，然后继续执行悲观代码。转换后的代码继承了原始代码的基本属性，包括可线性化、可串行化和无死锁。
我们的工作补充了现有的悲观转换，使顺序代码线程安全通过添加锁。本质上，我们提供了一种通过减少同步瓶颈（例如，锁定树根）来优化此类转换的方法。结果代码可伸缩性很好，并且显著优于悲观方法。我们进一步将我们的合成代码与专家实现的最先进的数据结构进行比较。我们发现，它的性能是可比的，实现了定制的实现。因此，我们的工作表明，自动化的方法承担克服手工手工制作并发数据结构所涉及的困难的承诺。
We present a code transformation for concurrent data structures, which increases their scalability without sacrificing correctness. Our transformation takes lock-based code and replaces some of the locking steps therein with optimistic synchronization in order to reduce contention. The main idea is to have each operation perform an optimistic traversal of the data structure as long as no shared memory locations are updated, and then proceed with pessimistic code. The transformed code inherits essential properties of the original one, including linearizability, serializability, and deadlock freedom.
Our work complements existing pessimistic transformations that make sequential code thread-safe by adding locks. In essence, we provide a way to optimize such transformations by reducing synchronization bottlenecks for example, locking the root of a tree. The resulting code scales well and significantly outperforms pessimistic approaches. We further compare our synthesized code to state-of-the-art data structures implemented by experts. We find that its performance is comparable to that achieved by the custom-tailored implementations. Our work thus shows the promise that automated approaches bear for overcoming the difficulty involved in manually hand-crafting concurrent data structures.