Showing posts with label Real Time Database. Show all posts
Showing posts with label Real Time Database. Show all posts

Monday, March 28, 2016

Optimistic concurrency control protocols in real-time database

Optimistic concurrency control protocols in real-time database, real-time database variants of optimistic concurrency control (OCC) protocols, OCC-Broadcast Commit, OCC-Sacrifice, OCC-Wait, and Wait-50 protocols


Optimistic Concurrency Control Protocols


They follow a concept called validation (or certification) of transactions’ operations. This validation is done at the end of the transaction. As the name suggests, these protocols do not prevent any transactions from accessing any data items they require. The idea is to check all the necessary formalities at the end of the transaction before commit.
In optimistic concurrency control, any numbers of concurrent transactions are permitted (even some of the transactions work on same data items). The conflict of transactions, i.e., read-write, write-write on same data items, is validated at the end of the transaction. If any conflict is found during validation, the victims are chosen and rolled back. This avoids the unnecessary blocking of resources.
The following are the variants of OCC protocol where the classical OCC algorithm is slightly changed to accommodate real-time database environments;


  • OCC – Wait
  • Wait – 50



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



Go to REAL TIME DATABASE Home page









Saturday, March 26, 2016

Two Phase Locking High Priority 2PL-HP Protocol

Two Phase Locking High Priority (2PL-HP) Protocol, 2PL-HP Concurrency Control Protocol for real-time database


2PL High-Priority (2PL-HP)


It is one of the pessimistic concurrency control protocols. It modifies the basic 2PL protocol by incorporating high priority conflict resolution scheme. It works as follows;

When a higher priority transaction (requester) is requesting a lock on an object held by lower priority transactions (lock holder) in a conflicting mode, the lock holders are aborted or restarted and the requester is granted the lock.
If the requester’s priority is lower than the lock holders’ priority then requester will wait for the object to be released.
A new reader can join the group of lock-holding readers only if its priority is higher than that of all the writers waiting for the lock.

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
          Th ABORTs;
Tr continues;
else
          Tr WAIT;
endif

Discussion:
Let us assume a transaction T1 with higher priority is requesting a data item held by a transaction T2 with lower priority. The 2PL-HP forces (wound) the lower priority transaction T2 to restart or abort. This action will release the lock held by T2, then T1 acquires the lock and continue.

If T1’s priority is lower than that of T2’s priority, then 2PL-HP forces T1 to wait for the object to be released by T2.

2PL-HP shows the properties of “priority based wound-wait” under conflict resolution.

Merits:
  • 2PL-HP serves a deadlock prevention mechanism.
  • 2PL-HP ensures urgent higher priority transactions to meet their deadlines.

Demerits:
  • A transaction restarted by a higher-priority transaction may miss its deadline and discarded.
  • Lower priority transactions always restarted due to the higher priority transactions end in wastage of system resources used by lower priority transactions.
  • More number of lower priority transactions with conflicting locks will lead to wasted restarts thus results in performance degradation of the system.

Comparison:

The experimental results showed real-time concurrency control algorithms based on High-Priority perform considerably better than those based on Priority-Inheritance. Furthermore, it was found that the 2PL-HP outperforms the 2PL-WP scheme in the context of a RTDB environment, and it was concluded that the basic priority-inheritance is inappropriate for conflict resolution under 2PL.

References:
Abbott, R., and Garcia-Molina, H. 1988. Scheduling real-time transactions: a performance evaluation, Proc. of 14th Intl. Conf. on Very Large DataBases. August




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








Go to REAL TIME DATABASE Home page














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.
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 to REAL TIME DATABASE Home page













Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery