Research in Wait-Free Synchronization

摘要

The goal of our research is to develop systematic understanding of the theory andpractice of highly concurrent data objects. Despite impressive progress in hardware that has made multiprocessors readily available for parallel processing, there is little agreement on the relative merits of competing architectures, and it has often proved difficult to realize these machines' potential for parallelism. Our research exploits the theory of abstract data types to derive: (1) impossibility results, showing that certain kinds of concurrency simply cannot be achieved with certain primitives; (2) new techniques for specifying and reasoning about the behavior of concurrent objects; and (3) synchronization algorithms permitting new, higher degrees of concurrency. The resulting theory yields consequences for algorithm and programming language design. We view a concurrent system as a collection of sequential processes that communicate through shared objects. Each object has a type, which defines a set of possible values, and a set of primitive operations that provide the only means to create and manipulate that object. This model is general, encompassing both message passing architectures in which the shared objects are message queues and shared-memory architectures in which the shared objects are data structures in memory. Traditionally, interprocess synchronization theory has centered around the notion of mutual exclusion. We do not rely on mutual exclusion as the sole means to synchronize processes. Implementation of a concurrent object is WAIT-FREE if it guarantees that any process will complete any operation within a fixed number of steps, independent of the level of contention and execution speeds of other processes.