Lock-free and scalable multi-version software transactional memory
Lock-free and scalable multi-version software transactional memory
复制标题
无锁且可扩展的多版本软件事务内存
DOI：
10.1145/1941553.1941579
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
João P. Cachopo
中科院分区：
文献类型：
--
作者：
S. Fernandes;João P. Cachopo
软件事务存储器（STM）最初是作为一种无锁的并发控制机制提出的。早期的实现有效率限制，很快出现了无障碍的建议，以解决这个问题，通常简化STM实现。今天，大多数现代和性能最好的STM都使用阻塞设计，依靠锁来确保原子提交操作。这种方法在实践中表现得更好，部分原因是它的简单性。然而，当我们进入多核计算机时，它可能会有可伸缩性问题，需要进行微调和仔细编程以避免争用。在本文中，我们提出并讨论了我们在Java中对基于锁的多版本STM所做的修改，将其转换为无锁实现，我们已经测试了至少可扩展到192个核心，并提供了与当今一些性能最佳的基于锁的实现竞争，有时甚至超过它们的结果。新的无锁提交算法允许写事务并行进行，允许它们彼此独立地运行验证阶段，并在回写阶段求助于等待提交的线程。我们还提出了一个新的垃圾收集算法来处理旧的未使用的对象版本，允许异步识别不必要的版本，这最大限度地减少了它的干扰与其余的事务系统。
Software Transactional Memory (STM) was initially proposed as a lock-free mechanism for concurrency control. Early implementations had efficiency limitations, and soon obstruction-free proposals appeared, to tackle this problem, often simplifying STM implementation. Today, most of the modern and top-performing STMs use blocking designs, relying on locks to ensure an atomic commit operation. This approach has revealed better in practice, in part due to its simplicity. Yet, it may have scalability problems when we move into many-core computers, requiring fine-tuning and careful programming to avoid contention. In this paper we present and discuss the modifications we made to a lock-based multi-version STM in Java, to turn it into a lock-free implementation that we have tested to scale at least up to 192 cores, and which provides results that compete with, and sometimes exceed, some of today's top-performing lock-based implementations. The new lock-free commit algorithm allows write transactions to proceed in parallel, by allowing them to run their validation phase independently of each other, and by resorting to helping from threads that would otherwise be waiting to commit, during the write-back phase. We also present a new garbage collection algorithm to dispose of old unused object versions that allows for asynchronous identification of unnecessary versions, which minimizes its interference with the rest of the transactional system.