2013 · 34 citations · 16 references
ComputingComputer ScienceComputer SystemsCompilersData StructuresStorage SystemsData SynchronizationSynchronization PrimitivesAsynchronous MemoryCompare-and-swapNon-blocking Data StructuresShared Memory SystemsShared-memory Data Structures
We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations operate on a set of Data-records, each of which contains multiple fields. The operations are generalizations of the well-known load-link (LL) and store-conditional (SC) operations called LLX and SCX. The LLX operation takes a snapshot of one Data-record. An SCX operation by a process p succeeds only if no Data-record in a specified set has been changed since p last performed an LLX on it. If successful, the SCX atomically updates one specific field of a Data-record in the set and prevents any future changes to some specified subset of those Data-records. We provide a provably correct implementation of these new primitives from single-word compare-and-swap. As a simple example, we show how to implement a non-blocking multiset data structure in a straightforward way using LLX and SCX.
16
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
Nir Shavit, Dan Touitou · Distributed Computing · 1997 · 404 citations
Concurrent programming without locks
Keir Fraser, Tim Harris · ACM Transactions on Computer Systems · 2007 · 260 citations
A method for implementing lock-free shared-data structures
Greg Barnes · 1993 · 194 citations · Full text