Two-Handed Emulation: How to build non-blocking implementations of complex data-structures using DCAS

摘要

This paper partly addresses the question of whether, in principle, there is any point in adding richer hardware synchronization primitives when the existing set is "universal", and therefore sufficient to synchronize any data structure in a non-blocking manner. The context of this paper is the ongoing investigation of the utility of adding a DCAS instruction to modern processors to aid the design and performance of non-blocking algorithms. We add one more piece of evidence in support of this instruction. In particular, we demonstrate that DCAS is sufficient to enable a technique called "two-handed emulation" which yields efficient and understandable implementations of a class of data structures. We present a non-blocking implementation of a doubly-linked list to show the basic technique. We describe a non-blocking implementation of a dynamically resizable hash-table to illustrate how the technique is amenable to optimizations that improve performance and increase concurrency.