next up previous
Next: Variable Granularity Locking Up: No Title Previous: Multiversion Timestamp Ordering

Optimistic Concurrency Control

The previous schemes do incremental synchronization checks on each read/write-- by using explicit locks or timestamps. There are several disadvantages of incremental checks:

Incremental checks can be expensive, specially when they involve accessing slow secondary memory.

They are an unnecessary overhead when there are no conflicts (consider readonly transactions).

They can reduce concurrency unnecessarily (because locks are kept longer than necessary to avoid cascaded aborts) or lead to cascaded aborts (consider Figure 1).

Optimistic concurrency control [ Kung Robinson ] divides a transaction into a read phase, a validation phase, and a writing phase. During (a) the read phase, a transaction performs writes on local buffers and no checking takes place, (b) validation phase, the system does synchronization checking, and (c) the write phase, the local writes are made global. It assigns each transaction a unique timestamp at the end of its read phase. A transaction TI is validated if one of the following conditions can be established for all transactions TJ with later timestamps:

Transaction TI completes its write phase before transaction TJ begins its read phase.

Transaction TJ does not read any of the items written by TI and transaction TI finishes its write phase before transaction TJ begins its write phase.

Transaction TJ does not read or write any items written by TI.

Transactions are aborted when validation cannot be done. In the example of Figure 1, one of the two transactions would be aborted. This approach works well when there are no conflicts (hence the term optimistic) but wastes work when there are conflicts. Aborting of transactions is a severe problem when the transactions are long and interactive, when manual/automatic merging is a better alternative.


Prasun Dewan
Wed Apr 7 11:52:42 EDT 1999