Flat combining (FC) is a synchronization paradigm in which a single thread, holding a global lock, collects requests by multiple threads for accessing a concurrent data structure and applies their combined requests to it. Although FC is sequential, it significantly reduces synchronization overheads and cache invalidations and thus often provides better performance than that of lock-free implementations. The recent emergence of non-volatile memory (NVM) technologies increases the interest in the development of persistent concurrent objects. These are objects that are able to recover from system failures and ensure consistency by retaining their state in NVM and fixing it, if required, upon recovery. Of particular interest are detectable objects that, in addition to ensuring consistency, allow recovery code to infer if a failed operation took effect before the crash and, if it did, obtain its response. In this work, we present the first FC-based persistent object implementations. Specifically, we introduce a detectable FC-based implementation of a concurrent LIFO stack, a concurrent FIFO queue, and a double-ended queue. Our empirical evaluation establishes that due to flat combining, the novel implementations require a much smaller number of costly persistence instructions than competing algorithms and are therefore able to significantly outperform them.
翻译:平板组合( FC) 是一种同步模式, 在一个单一线索中, 持有一个全球锁, 收集多个线索的请求, 以访问同时的数据结构, 并对其应用其合并请求 。 虽然 FC 是相继的, 但它会大大降低同步的间接费用和缓存无效功能, 因而往往比无锁的安装效果更好 。 最近出现的非挥发性内存( NVM) 技术提高了对开发持久性并存物体的兴趣 。 这些天体能够从系统故障中恢复过来, 并通过保留其在 NVM 中的状况和在恢复时加以修正来确保一致性来确保一致性来确保其一致性来确保其一致性。 特别感兴趣的是可探测到的物体, 除了确保一致性外, 允许回收代码来推断一个失败的操作是否在崩溃发生之前生效, 并且如果它得到了响应, 也因此能够提供比 FC 第一次基于 的持久性的物体执行效果更好的效果 。 具体而言, 我们引入一个基于可探测到的 FC 执行 LIFO 堆, 、 一个同时的 FIFO 队列 和 双队列 。 我们的经验评估确定由于平板的合并,, 因此, 新的执行需要大大的指令需要更小的更小得多的持久的指示。