Temporally Bounding TSO for Fence-Free Asymmetric Synchronization
Temporally Bounding TSO for Fence-Free Asymmetric Synchronization
复制标题
DOI：
10.1145/2694344.2694374
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
Adam Morrison;Y. Afek
中科院分区：
文献类型：
--
作者：
Adam Morrison;Y. Afek
本文介绍了一个时间限制的总存储订购（TBTSO）存储器模型，并表明它可以使非无盖栅栏的解决方案用于非对称同步问题，例如在存储回收和有偏置锁定中产生的问题。 TBTSO通过将商店从商店缓冲区排入存储器所需的时间来增强TSO内存模型。该结合使设计无围栏的算法针对非对称问题，这需要至关重要的快速路径与不经常执行的慢速路径同步。我们通过构建（1）危险指针记忆填海方案的无围栏版本和（2）无围栏的偏置锁定算法与无托管环境兼容，因为它不依赖于安全点或类似的机制，因此证明了这一点。我们进一步认为，可以在硬件中实现TBTSO对现有TSO体系结构进行适度的修改。但是，我们的设计对商业硬件的专有实施细节做出了假设。因此，它最好是讨论硬件TBTSO实现的可行性的起点。我们还展示了最小OS支持如何使TBTSO算法适应X86系统。
This paper introduces a temporally bounded total store ordering (TBTSO) memory model, and shows that it enables nonblocking fence-free solutions to asymmetric synchronization problems, such as those arising in memory reclamation and biased locking. TBTSO strengthens the TSO memory model by bounding the time it takes a store to drain from the store buffer into memory. This bound enables devising fence-free algorithms for asymmetric problems, which require a performance-critical fast path to synchronize with an infrequently executed slow path. We demonstrate this by constructing (1) a fence-free version of the hazard pointers memory reclamation scheme, and (2) a fence-free biased lock algorithm which is compatible with unmanaged environments as it does not rely on safe points or similar mechanisms. We further argue that TBTSO can be implemented in hardware with modest modifications to existing TSO architectures. However, our design makes assumptions about proprietary implementation details of commercial hardware; it thus best serves as a starting point for a discussion on the feasibility of hardware TBTSO implementation. We also show how minimal OS support enables the adaptation of TBTSO algorithms to x86 systems.