Synchronizing shared abstract types

Abstract

The synchronization issues that arise when transaction facilities are extended for use with shared abstract data types are discussed. A formalism for specifying the concurrency properties of such types is developed, based on dependency relations that are defined in terms of an abstract type's operations. The formalism requires that the specification of an abstract type state whether or not cycles involving these relations should be allowed to form. Directories and two types of queues are specified using the technique, and the degree to which concurrency is restricted by type-specific properties is exemplified. How the specifications of types interact to determine the behavior of transactions is also discussed. A locking technique is described that permits implementations to make use of type-specific information to approach the limits of concurrency.