Timestamp-Based Locking

by
Sadanand Sahasrabudhe

The 2-phase locking scheme that we saw earlier suffers from the problems of deadlock and cascaded aborts. We will now look at two timestamp based locking algorithms for concurrency control in distributed database systems. To recapitulate on the way unique time stamps can be generated in a distributed system check conflict between transactions the concurrency control algorithm makes a decision based on the result of the comparison of their timestamps. The use of timestamps is primarily to prevent deadlocks. Conflicts can be resolved uniformaly at all sites in the distributed system as each transaction will have the same timestamp everywhere.

A conflict is resolved by taking one of two possible actions.

Wait :
The requesting transaction is made to wait until the conflicting transaction either completes or aborts.
Restart :
Either the requesting transaction or the conflicting transaction is aborted and restarted. Restarting is achieved by using one of the following primitives:
- Die: The requesting transaction aborts and starts afresh.
- Wound: The conflicting transaction is tagged wounded and a "wounded" message is sent to all sites that were visited by the transaction. The concurrency control algorithm at a site aborts the wounded transaction if the message is received before the transaction has commited at that site, otherwise the message is ignored. The wounded transaction if aborted, is restarted. The requesting transaction continues after the wounded transaction has either completed or aborted.

Wait-Die Algorithm:

In this algorithm, if the requesting transaction T1 is older than the conflicting transaction T2, then T1 waits, otherwise T1 dies. Thus it is a nonpreemptive algorithm in which the requesting transaction never forces the transaction holding the requested data object to abort.

Wound-Wait Algorithm:

In this algorithm, if the requesting transaction T1 is older than the conflicting transaction T2, T1 wounds T2, otherwise T1 waits. Thus it is a preemptive algorithm.

Both the above algorithms produce serializable logs and guarantee that no transaction waits forever to prevent deadlocks.

Comparison between the algorithms:

Waiting Time :

In the Wait-Die algorithm , an older transaction is made to wait for a younger transaction. Hence, the older a transaction becomes the more it has to wait for younger transactions and the more it tends to slow down.

In the Wound-Wait algorithm, an older transaction wounds a younger transaction that conflicts with it. Hence, the older a transaction becomes, the less it tends to slow down.

Number of restarts :

In the Wait-Die algorithm, a younger requesting transaction dies and is restarted. If it is restarted with the same time stamp, it may conflict with the same older transaction. Thus a younger transaction may die and restart several times before it completes.

In the Wound-Wait algorithm the younger requester waits rather than continously dying and restarting.

Study Question:

What property of timestamps makes the time-stamp based algorithms free from deadlock?

References:

Singhal, M and Shivaratri, N., Advanced Concepts in Operating Systems, McGraw-Hill 1994, pp.18,335-342.

go to my Home Page or to the CS5204 Page

Last updated: 30 Apr 1995

sadanand@csgrad.cs.vt.edu