How to Optimization Methods for concurrency Control in RDBMS
Optimization Methods for concurrency Control.
• The optimization method of concurrency control is based on the assumption that conflicts of database operations are rare and that it is better to let transaction run to completion and only check for conflicts before they commit .
• An optimistic concurrency control method is also known as validation or certification methods .
• No checking is done while the transaction is executing. The optimistic method does not require locking or timestamping techniques. Instead , a transaction is executed without restrictions until it is committed. In optimistic method ,each transaction moves through the following phase :
o Read phase
o Validation or certification phase
o write phase.
1) Read Phase :
• In read phase, the updates are prepared using private copies of the granule. In this phase, the transaction reads values of committed data from the database , executes the needed computations, and makes the updates to a private copy of the database values.
• All update operations of the transaction are records in a temporary update file, which is not accessed by the remaining transaction. These set of transaction are those who have finished their read phase since the start of the transaction being verified.
2) Validation Phase :
• In a validation phase, the transaction is validated to assure that the changes made will not affect the integrity and consistency of the database.
• if the validation test is positive , the transaction goes to the write phase, If the validation test is negative , the transaction is restarted, and the changes are discarded.
• Thus, in this phase the list of granules is checked for conflicts. If conflicts are detected in this phase, the transaction is aborted and restarted. The validation algorithm must check that the transaction has
o seen all modification of transactions committed after it starts.
o not read granules updated by a transaction committed after its start.
3) Write Phase :
• In a Write phase, the changes are permanently applied to the database and the updated granules are made public. Otherwise, the updates are discarded and the transaction is restarted. This phase is only for the Read-Write transaction and not for Read-only transaction.
• This technique is very efficient when conflicts are rare. The occasional conflicts result in the transaction roll back.
• The rollback involves only the local copy of data, the database is not involved and thus there will not be any cascading rollbacks .
2 Problems of optimistic method for concurrency control
• The optimistic concurrency control suffers from the following problems :
• conflicts are expensive to deal with , since the conflicting transaction must be rolled back.
• Longer transaction are more likely to have conflicts and may be repeatedly rolled back because of conflicts with short transactions.
3 Applications of optimistic method for concurrency control :
• only suitable for environments where there are few conflicts and no long transactions.
• acceptable for mostly read or query database system that requires very few update transactions .
4 Deadlock Handling :-
• A system is in a deadlock state if there exists a set of transaction such that every transaction in the set is waiting for another transaction in the set.
• More precisely, there exists a set of waiting transactions {T0, T1,…..,Tn} such that T0 is waiting for a data item that T1 holds, and T1 is waiting for a data item that T2 holds, and …., and Tn-1 is waiting for a data item that Tn holds, and Tn is waiting for a data item that T0 holds.
• There are 2 principal methods for dealing with the deadlock problem.
• We can use a deadlock prevention protocol to ensure that the system will never enter a deadlock state.
• Alternatively, we can allow the system to enter a deadlock state, and then try to recover by using a deadlock detection and deadlock recovery scheme.
5 Deadlock prevention :-
• There are 2 approaches to deadlock prevention.
• One approach ensures that no cyclic waits can occur by ordering the requests for locks, or requiring all locks to be acquired together.
• The other approach is closer to deadlock recovery, and performs transaction rollback instead of waiting for a lock, whenever the wait could potentially result in a deadlock.
• The simplest scheme under the first approach requires that each transaction locks all its data items before it begins execution.
• Moreover, either all are locked in one step or none are locked.
• There are 2 main disadvantages to this protocol:
1) It is often hard to predict, before the transaction begins, what data items need to be locked;
2) Data-item utilization may be very low, since many of the data items may be locked but unused for a long time.
• Another approach for preventing deadlocks is to impose an ordering of all data items, and to require that a transaction lock data items only in a sequence consistent with the ordering.
• The second approach for preventing deadlocks is to use pre-emption and transaction rollbacks.
• In pre-emption, when a transaction T2 requests a lock that transaction T1 holds, the lock granted T1 may be pre-empted by rolling back of T1, and granting of the lock to T2.
• To control the pre-emption, we assign a unique timestamp to each transaction.
• The system uses these timestamps only to decide whether a transaction should wait or roll back.
• 2 different deadlock prevention schemes using timestamps have been proposed.
1) The wait-die scheme is a non-pre-emptive technique. When transaction requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj. Otherwise, Ti is rolled back.
For example, suppose that transaction T22, T23 and T24 have timestamps 5,10, and 15, respectively. If T22 requests a data item held by T23, then T22 will wait. If T24 requests a data item held by T23, then T24 will be rolled back.
2) The wound –wait scheme is a pre-emptive technique. It is a counterpart to the wait-die scheme. When transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj. Otherwise Tj is rolled back.
Returning to our example, with transaction T22, T23, and T24, if T22 requests a data item held by T23, then the data item will be pre-empted from T23, and T23 will be rolled back. If T24 requests a data item held by T23, the T24 will wait.
• There are, however, significant differences in the way that the 2 schemes operate:
o In the wait-die scheme, an older transaction must wait for a younger one to release its data item. Thus, the older the transaction gets, the more it tends to wait. By contrast, in the wound-wait scheme, an older transaction never waits for a younger transaction.
o In the wait-die scheme, if a transaction Ti dies and is rolled back because of requested a data item held by transaction Ti and Tj may reissue the same sequence of requests when it is restarted. If the data item is still held by Tj then Ti will die again.
o When Ti is restarted and requests the data item now being held by Tj, Ti waits.
o Thus, there may be fewer rollbacks in the wound-wait scheme.
6 Deadlock detection and Recovery :-
• If a system does not employ some protocol that ensures deadlock freedom, then a detection and recovery scheme must be used.
• An algorithm that examines the state of the system is invoked periodically whether a deadlock has occurred.
• If one has, then the system must attempt to recover from the deadlock. To do so, the system must:
o Maintain information about the current allocation of data items to transactions, as well as any outstanding data item requests.
o Provides an algorithm that uses this information to determine whether the system has entered a deadlock state.
o Recover from the deadlock when the detection algorithm determines that a deadlock exists.
• The optimization method of concurrency control is based on the assumption that conflicts of database operations are rare and that it is better to let transaction run to completion and only check for conflicts before they commit .
• An optimistic concurrency control method is also known as validation or certification methods .
• No checking is done while the transaction is executing. The optimistic method does not require locking or timestamping techniques. Instead , a transaction is executed without restrictions until it is committed. In optimistic method ,each transaction moves through the following phase :
o Read phase
o Validation or certification phase
o write phase.
1) Read Phase :
• In read phase, the updates are prepared using private copies of the granule. In this phase, the transaction reads values of committed data from the database , executes the needed computations, and makes the updates to a private copy of the database values.
• All update operations of the transaction are records in a temporary update file, which is not accessed by the remaining transaction. These set of transaction are those who have finished their read phase since the start of the transaction being verified.
2) Validation Phase :
• In a validation phase, the transaction is validated to assure that the changes made will not affect the integrity and consistency of the database.
• if the validation test is positive , the transaction goes to the write phase, If the validation test is negative , the transaction is restarted, and the changes are discarded.
• Thus, in this phase the list of granules is checked for conflicts. If conflicts are detected in this phase, the transaction is aborted and restarted. The validation algorithm must check that the transaction has
o seen all modification of transactions committed after it starts.
o not read granules updated by a transaction committed after its start.
3) Write Phase :
• In a Write phase, the changes are permanently applied to the database and the updated granules are made public. Otherwise, the updates are discarded and the transaction is restarted. This phase is only for the Read-Write transaction and not for Read-only transaction.
- Advantages of optimistic method for concurrency control
• This technique is very efficient when conflicts are rare. The occasional conflicts result in the transaction roll back.
• The rollback involves only the local copy of data, the database is not involved and thus there will not be any cascading rollbacks .
2 Problems of optimistic method for concurrency control
• The optimistic concurrency control suffers from the following problems :
• conflicts are expensive to deal with , since the conflicting transaction must be rolled back.
• Longer transaction are more likely to have conflicts and may be repeatedly rolled back because of conflicts with short transactions.
3 Applications of optimistic method for concurrency control :
• only suitable for environments where there are few conflicts and no long transactions.
• acceptable for mostly read or query database system that requires very few update transactions .
4 Deadlock Handling :-
• A system is in a deadlock state if there exists a set of transaction such that every transaction in the set is waiting for another transaction in the set.
• More precisely, there exists a set of waiting transactions {T0, T1,…..,Tn} such that T0 is waiting for a data item that T1 holds, and T1 is waiting for a data item that T2 holds, and …., and Tn-1 is waiting for a data item that Tn holds, and Tn is waiting for a data item that T0 holds.
• There are 2 principal methods for dealing with the deadlock problem.
• We can use a deadlock prevention protocol to ensure that the system will never enter a deadlock state.
• Alternatively, we can allow the system to enter a deadlock state, and then try to recover by using a deadlock detection and deadlock recovery scheme.
5 Deadlock prevention :-
• There are 2 approaches to deadlock prevention.
• One approach ensures that no cyclic waits can occur by ordering the requests for locks, or requiring all locks to be acquired together.
• The other approach is closer to deadlock recovery, and performs transaction rollback instead of waiting for a lock, whenever the wait could potentially result in a deadlock.
• The simplest scheme under the first approach requires that each transaction locks all its data items before it begins execution.
• Moreover, either all are locked in one step or none are locked.
• There are 2 main disadvantages to this protocol:
1) It is often hard to predict, before the transaction begins, what data items need to be locked;
2) Data-item utilization may be very low, since many of the data items may be locked but unused for a long time.
• Another approach for preventing deadlocks is to impose an ordering of all data items, and to require that a transaction lock data items only in a sequence consistent with the ordering.
• The second approach for preventing deadlocks is to use pre-emption and transaction rollbacks.
• In pre-emption, when a transaction T2 requests a lock that transaction T1 holds, the lock granted T1 may be pre-empted by rolling back of T1, and granting of the lock to T2.
• To control the pre-emption, we assign a unique timestamp to each transaction.
• The system uses these timestamps only to decide whether a transaction should wait or roll back.
• 2 different deadlock prevention schemes using timestamps have been proposed.
1) The wait-die scheme is a non-pre-emptive technique. When transaction requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj. Otherwise, Ti is rolled back.
For example, suppose that transaction T22, T23 and T24 have timestamps 5,10, and 15, respectively. If T22 requests a data item held by T23, then T22 will wait. If T24 requests a data item held by T23, then T24 will be rolled back.
2) The wound –wait scheme is a pre-emptive technique. It is a counterpart to the wait-die scheme. When transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj. Otherwise Tj is rolled back.
Returning to our example, with transaction T22, T23, and T24, if T22 requests a data item held by T23, then the data item will be pre-empted from T23, and T23 will be rolled back. If T24 requests a data item held by T23, the T24 will wait.
• There are, however, significant differences in the way that the 2 schemes operate:
o In the wait-die scheme, an older transaction must wait for a younger one to release its data item. Thus, the older the transaction gets, the more it tends to wait. By contrast, in the wound-wait scheme, an older transaction never waits for a younger transaction.
o In the wait-die scheme, if a transaction Ti dies and is rolled back because of requested a data item held by transaction Ti and Tj may reissue the same sequence of requests when it is restarted. If the data item is still held by Tj then Ti will die again.
o When Ti is restarted and requests the data item now being held by Tj, Ti waits.
o Thus, there may be fewer rollbacks in the wound-wait scheme.
6 Deadlock detection and Recovery :-
• If a system does not employ some protocol that ensures deadlock freedom, then a detection and recovery scheme must be used.
• An algorithm that examines the state of the system is invoked periodically whether a deadlock has occurred.
• If one has, then the system must attempt to recover from the deadlock. To do so, the system must:
o Maintain information about the current allocation of data items to transactions, as well as any outstanding data item requests.
o Provides an algorithm that uses this information to determine whether the system has entered a deadlock state.
o Recover from the deadlock when the detection algorithm determines that a deadlock exists.
How to Optimization Methods for concurrency Control in RDBMS
![How to Optimization Methods for concurrency Control in RDBMS]()
Reviewed by Unknown
on
04:03:00
Rating:
No comments: