Synchronizing Shared Abstract Types

Abstract

schedule, which is composed of operations on Q, a shared object of type FIFO Queue. The operations Q E n t e r and QRemove , respectively, append an In Section 4.4 we define a second kind of schedule, the invocation schedule, which reflects the concurrency of specific implementations. ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984. 228 • P.M. Schwarz and A. Z. Spector element to the tail of a FIFO Queue and remove one from it's head. Assume Q to be empty initially. T~: QEnter (Q, X) T2: QEnter (Q, Y) T3 : QRemove (Q) From this abstract schedule and the initial contents of the Queue, one can deduce the state of Q at any point in the schedule. Thus one may conclude that the QRemove operation returns X, and that only Y remains on the Queue at the end of the schedule. 3.2 Dependencies and Consistency By examining an abstract schedule, it is possible to determine what dependencies exist among the transactions in the schedule. The notation D: Ti:X --*o Tj:Y is used to represent the dependency D formed when transaction Ti performs operation X and transaction T i subsequently performs operation Y on some common object O. The object, transaction, or dependency identifiers may be omitted when they are unimportant. The set of ordered pairs {(T/, Tj)} for which there exist X, Y, and O such that D: T~:X --*o Ti:Y forms a relation, denoted <D. If Ti <D Tj, Ti precedes Tj and Tj depends on T/, under the dependency D. Examples of dependencies and their corresponding relations can be drawn from traditional database systems. For instance, consider a system in which no semantic knowledge, either about entire transactions or about their component operations, is available to the concurrency control mechanism. The only requirement is that each individual transaction be correct in itself: it must transform a consistent initial state of the database to a consistent final state. Under these conditions, only serializable abstract schedules can be guaranteed to preserve the correctness of individual transactions. Since all operations are indistinguishable, only one possible dependency D can be defined: T1 <D T~ if T1 performs any operation on an object later operated on by T~. Now, consider <~, the transitive closure of <D. A schedule is orderable with respect to {<D} iff <~ is a partial order. In other words, there are no cycles of the form T1 <D T2 <D "'" <D T. <D T~. In general, a schedule is orderable with respect to S, where S is a set of dependency relations, iff each of the relations in S have a transitive closure that is a partial order. The relations in S are referred to as proscribed relations, and we use orderability with respect to a set of proscribed dependency relations to describe ordering properties of groups of transactions. Abstract schedules that are orderable with respect to a specified set of proscribed relations are called consistent abstract schedules. It can be shown that orderability with respect to {<D} is equivalent to serializability [6]. Given a schedule orderable with respect to {<D}, a transaction T, and the set O of objects to which T refers, every other transaction that refers to an object in O can unambiguously be said either to precede T or to follow T. Thus T depends on a well-defined set of transactions that precede it, and a welldefined set of transactions depend on T. Each transaction sees the consistent database state left by those transactions that precede it and (by assumption) leaves a consistent state for those that follow. The set of schedules for which ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984. Synchronizing Shared Abstract Types • 229 <5 is a partial order constitutes the set of consistent abstract schedules for a system that employs no semantic knowledge. The scheme described above prevents cycles in the most general possible dependency relation; hence it maximally restricts concurrency. By considering the semantics of operations on objects, it is possible to identify some dependency relations for which cycles may be allowed to form. For example, consider a database with a Read/Write concurrency control. Such systems recognize two types of operations on objects: Read (R) and Write (W). Thus there are four possible dependencies between a pair of transactions that access a common object: DI: Ti: R --*oTj: R. Ti reads an object subsequently read by T/. D2: Ti: R --*oTj: W. Ti reads an object subsequently modified by Tj. D.~: Ti: W --*oT/: R. Ti modifies an object subsequently read by Tj. D4: Ti: W --*oTj: W. Ti modifies an object subsequently modified by Tj. The earlier scheme, by not distinguishing between these dependencies, prevents cycles from forming in the dependency relation <D, which is the union of all four individual relations. By contrast, Read/Write concurrency controls taken into account the fact that R --* R dependencies cannot influence system behavior. That is, given a pair of transactions, T1 and T2, and an abstract schedule in which both T1 and T.~ perform a Read on a shared object, the semantics of Read operations ensure that neither T1, T2, nor any other transaction in the schedule can determine whether T~ <D~ T2 or T2 <D, T~. Since these dependencies cannot be observed, they cannot compromise serializability, nor can they affect the outcome of transactions. We call dependencies meeting this criterion insignificant. Korth has also noted that when operations are commutative, their ordering does not affect serializability [12]. For the Read/Write case, the necessary condition for serializability can be restated as follows in terms of dependency relations: a schedule is serializable if it is orderable with respect to [<D2uD3uD4 } [8]. By allowing multiple readers, Read/Write schemes permit the formation of cycles in the <D, dependency relation, and in relations that include <D,, while preventing cycles in the relation that is the union of <D2, <D3, and <D,. For example, consider the following schedules, which have identical effects on the system state:

Topics

6 Figures and Tables

Download Full PDF Version (Non-Commercial Use)