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.
Tr is the requesting transaction
with HIGHER PRIORITY.
Th is the lock holding
transaction with LOWER PRIORITY. */
if
(P(Tr)>P(Th) then
Tr WAIT;
Th inherits the priority of
Tr;
else
Tr 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
No comments:
Post a Comment