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; storing the contents of the data structure instance in a shared memory that is accessible to a plurality of concurrently executing computations; 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;in response to said detecting, invoking a contention management mechanism that is separate from the computation and that is configured to facilitate progress of the computation given the contention; wherein the method is employed in an implementation of software transactional memory that manages access to the data structure instance, and wherein the contention management mechanism includes a feedback mechanism; and supplying, by the feedback mechanism, an abort conflicting transaction indication in accordance with a then-current contention management policy.