Two Phase Locking Wait Promote 2PL WP Protocol

Two Phase Locking - Wait Promote Protocol for real-time database

2PL Wait-Promote (2PL-WP)

This is one of the pessimistic concurrency control protocols. This protocol works as follows;

2PL-WP algorithm includes priority inheritance mechanism. With this mechanism, whenever a request of a higher-priority transaction (requester) is blocked by a lower-priority transaction (lock holder), then the priority of the lock holder gets promoted to that of the requester.

In other words, the lock holder inherits the priority of the lock requester, and the holder retains this elevated priority until it either commits or is restarted (due to deadlock resolution).

When a data item is locked by more than one transaction, then the transactions with lower priority than the requester inherit the priority of the requester.

This can be represented in pseudo code as follows;

/* P(T) denotes the priority of a transaction T.

T_r is the requesting transaction with HIGHER PRIORITY.

T_h is the lock holding transaction with LOWER PRIORITY. */

if (P(T_r)>P(T_h) then

          T_r WAIT;

          T_h inherits the priority of T_r;

else

          T_r WAIT;

endif

Discussion:

Let us assume a Transaction T1 with higher priority is requesting for data items A, B, and C. Also assume a transaction T2 with the priority value lower than T1 and is requesting for data items C. If C is locked by T2 before T1, then T1 has to wait for T2 to unlock (release) C. That means, currently T1 (higher priority transaction) is blocked by T2 (lower priority transaction). At this stage, 2PL-WP assigns the higher-priority value of T1 to T2, ie., upgrade T2 to the priority equal to that of T1 and continues the transactions. As a result, T1 waits, T2 is promoted.

Merits:

• 2PL-WP algorithm retains the resource-conservation features of 2PL

• It guarantees that every transaction holding a lock on a data item has a priority that is at least as high as that of the highest priority transaction waiting for the lock.

• Locked resources need not be released like 2PL.

• It reduces the waiting time of higher priority transactions because of priority inheritance.

Demerits:

• The waiting time of a higher priority transaction is uncertain in their duration.

• Priority inheritance makes all the transaction executions with the same priority in a system where data conflicts are high. This makes the RTDB sometimes as conventional database system.

References:

Abbott, R., and Garcia-Molina, H. 1989. Scheduling real-time transactions with disk resident data, Proc ofl5th Intl. Conf. on Very Large DataBases. August.

***********************

Go back to real-time database pessimistic protocols page

Go back to concurrency control in real-time database page

Go to REAL TIME DATABASE Home page