Concurrent Control Algorithms

There are two approaches used in algorithms to deals with the problems of concurrency control. These are:
• Pessimistic Approach
• Optimistic Approach

Pessimistic Approach: This approach causes transaction to be delayed in case they conflict with each other at the some time in the future.
Pessimistic Execution: The validate operation is performed first, if there is a validation according to compatibility of lock then only read, compute and write operations are performed

                   Validate |   Read    |     Compute    |     Write

There are two commonly used algorithms, which are based on Pessimistic Approach .
• Two phase locking protocol
• Time stamp ordering protocol
Optimistic Approach: The optimistic method of concurrency control is based on the assumption that conflicts of database operations are rare and that it is better to let transactions 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 time stamping techniques. Instead, a transaction is executed without restrictions until it is committed.

It allows transactions to proceed unsynchronized and only check conflicts at the end. This approach is based on the premise that conflicts are rare

Optimistic Execution: It perform read and compute operation without validation and perform validation just before write operation.

Read Composite Validate Write

Advantages of Optimistic Methods for Concurrency Control

The optimistic concurrency control has the following advantages:

• 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.

Problems of Optimistic Methods 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 transactions are more likely to have conflicts and may be repeatedly rolled back because of conflicts with short transactions.

Applications of Optimistic Methods for Concurrency Control

• Only suitable for environments where there are few conflicts and no long transactions.

• Acceptable for mostly Read or Query database systems that requires very few update transactions.

Two phase locking protocol (Pessimistic Approach)

A transaction follows the two phase locking protocol, if all locking operations precede the first unlock operation in the transaction. There are two phases in the Schedule. These are:

• Growing Phase: During which all locks are requested.

• Shrinking Phase: During which all locks are released.

Initially, a transaction is in the growing phase. The transaction acquires locks as needed.

Once the transaction releases a lock, it enters the shrinking phase and it can issue no more lock requests.

Transaction T3 and T4 are two phase. On the other hand transaction Tl and T2 are not two phase as shown below.

Note that the unlock instructions do not need to appear at the end of the transaction. For example, in the case of transaction T3, we could move the unlock(B) instruction to just after the lock-X(A) instruction and still retain the two-phase locking property: The point in the schedule where the transaction has obtained its final lock the end of its growing phase is called the lock point of the transaction.

Now, transactions can be ordered according to their lock points.

Problems with two-phase locking protocols

There are two problems with two-phase locking protocols. These are:

1.   Deadlock

2.   Cascading roll-back

Deadlock: As discussed above, two-phase locking does not ensure freedom from deadlock. As shown in transaction T3 and T4 are in two phase, but still there is problem of deadlock.

Cascading roll-back: As shown in partial schedule shown on next page each transaction observers two-phase locking protocol.

Let us consider, if transaction T5 fails after the read (A,a) operation of transaction ofT7. Then, T5 must be rollback, which also results into rollback of T6 and T7. Because, transaction T6 and T7 reads the value of A modified by transaction T5… Since transaction T5 fails and rollback, it means that transaction T5 obtain the original value of A and cancels’ the modified value of A, but the other transactions T6 and T7 process the modified value of A and into inconsistent state of database. In order to obtain the consistent state of database transactions T6 and T7, must also rollback and has to start again. It is case of dirty read.

Thus we can say that rollback of T5 results in to rollback T6 and T7 also. This problem is called as cascading of rollback.

Solutions to avoid cascading of rollbacks

There are two solutions to avoid cascading of rollback. These are:

• Strict two phase locking protocol

• Rigorous two phase locking protocol

Strict two-phase locking protocol: The strict two-phase locking protocol, requires, that in addition to locking being two-phase, all exclusive-mode locks taken by a transaction must beheld until that transaction commits. This requirement ensures that any data written by an uncommitted transaction are locked in exclusive mode until the transaction commits, preventing any other transaction from reading the data.

Rigorous two-phase locking protocol: It requires all locks to be held until the transaction commits. It can be easily verified that, with rigorous two-phase locking transactions can be serialized in the order in which they commit. Most database systems implement either strict or rigorous two-phase locking.