Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms

摘要

We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.

主权项

1. A method of operating a computing machine, the method comprising:
creating an instance of a data structure defined using one or more programming language constructs, wherein the data structure instance includes at least one transactional location for which ownership is mediated through use of a single-target synchronization primitive; storing the contents of the data structure instance in a shared memory that is accessible to a plurality of concurrently executing computations; introducing a retry construct into a flow executable to wrest ownership of the transactional location from a current owner; executing a computation that, when executed on one or more processors that access the memory, performs concurrent obstruction-free access operations on the data structure instance, wherein the obstruction-free access operations appear to execute in a one-at-a-time order and are non-blocking, but do not themselves ensure progress of the computation in the presence of contention, wherein said executing comprises: detecting contention between one of the obstruction-free access operations performed by the computation and another access operation performed on the data structure instance; and in response to said detecting, invoking a given contention management mechanism that is separate from the computation and that is configured to facilitate progress of the computation given the contention; replacing the given contention management mechanism with a substitute contention management mechanism during a course of the computation that employs the obstruction-free access operations; and subsequent to said replacing, invoking the substitute contention management mechanism, rather than the given contention management mechanism, in response to detecting contention between a subsequent one of the obstruction-free access operations performed by the computation and another access operation performed on the data structure instance.