Timestamp and its protocol |Concurrency Control

TIMESTAMP BASED PROTOCOLS-

This protocol require that we must have prior knowledge about the order in which the transaction will be accessed.In order to ordering the transaction, we associate a unique fixed timestamp ,denoted by TS(Ti) to each transaction like Ti.This time stamp is assigned by the database system before the transaction Ti starts execution.If a transaction Ti has been assigned timestamp TS(Ti) ,and a new transaction Tj enters the system then

                                                  TS(Ti)<TS(Tj)

DRAWBACKS OF TIMESTAMP-

1. Each value stored in the database requires two additional timestamp fields one for the last time the field was read and one for the last update.

2. It increases the memory requirements and the processing overhead of database.

IMPLEMENTATION-

To implement this scheme ,we associate with each data item Q two timestamp values:-

1. W-timestamp(Q) denoted the largest timestamp of any transaction that executed write(Q) successfully.

2.  R-timestamp(Q) denoted the largest timestamp of any transaction that executed read(Q) successfully.

TIMESTAMP ORDERING PROTOCOL-

The timestamp-ordering protocol ensures that any conflicting read and write operations are executed in timestamp order.This protocol operates as follows-

1. SUPPOSE A TRANSACTION Ti ISSUES READ(Q)

(a) If TS(Ti)<W-timestamp(Q),then Ti needs to read a value of Q that was already overwritten.Hence the read operation is rejected and Ti is roll back.(Q)

(b) If TS(Ti)>=W-timestamp(Q),then read operation is executed and R-timesatmp(Q) is set to the maximum of R-timestamp(Q) i.e. TS(Ti).

2. SUPPOSE A TRANSACTION Ti ISSUES WRITE(Q)

(a) If TS(Ti)<R-timestamp(Q),then the value of Q that Ti is producing was needed previously and the system assumed that value would never be produced.Hence the write operation is rejected and Ti is roll back.(Q)

(b) If TS(Ti)<W-timestamp(Q),then Ti is attempting to write an obsolete value of Q. Hence the write operation is rejected and Ti is roll back.(Q).

(c) Otherwise the write operation is executed and W- timestamp(Q) is set o TS(Ti).

Read More

Cascading Rollback |Types of Cascading Rollback |Concurrency Control

CASCADING ROLLBACK

As shown in partial schedule each transaction observes two phase locking protocol. EG-

                    T5                 T6                 T7

                  Lock-X(A)                                                       

                  Read(A,a)

                  Lock-S(B)                                                       

                  Read(B,b)

                  Write(A,a)

                  Unlock(A)

                                        Lock-X(A)                                                       

                                        Read(A,a)

                                        Write(A,a)

                                        Unlock(A)

                                                               Lock-S(A)                                                       

                                                                Read(A,a)

                  Rollback

Let us consider if transaction T5 fails after the read(A,a) operation of transaction of T7. Then, T5 must be rolled back which also result into rolled back T6 & T7. Because transaction T6 & T7 reads the value modified by transaction T5. Thus,we can say that rollback of T5 results into rollback of T6 & T7 also. This problem is called a cascading of rollback.

SOLUTIONS TO AVOID CASCADING OF ROLLBACKS: -

1.) STRICT TWO PHASE LOCKING PROTOCOL:- It requires that in addition to locking being Two phase, all exclusive mode locks taken by a transaction must be held until that transaction commits.

2.) RIGOROUS TWO PHASE LOCKING PROTOCOL:- It requires all locks(Shared and Exclusive) to be held until the transaction commits.It can be easily verified that,this transaction can be serialized in the order in which they commit.                                                

Read More

Deadlock and their prevention |Concurrency Control

DEADLOCK-

In order to understand deadlock, let us consider the following example:

           

 T1                T2                CONCURRENCY CONTROLLER

 lock-X(A)                         Lock granted

                     lock-X(B)     Lock granted

 lock-X(B)                        Request is queued i.e T1 wait for T2 to                              release the lock on data item B.

                  lock-X(A)        Request is again queued i.e T2 will                                                 wait for T1 to release the lock on data                                                                                               item A.

As shown in partial schedule transaction T1 is waiting for transactions T2 to release its lock on data item B and transaction T2 is waiting for transaction T1 to release its lock on data item A. Such a cycle of transactions waiting for locks to be released is called a Deadlock.

DEADLOCK CONDITIONS:

1. Circular wait

2. No preemption

3. Mutual exclusion

4. Hold & wait

HOW TO PREVENT FROM DEADLOCK?

IST APPROACH:- To allow every transaction lock all the data items, it needs before it starts execution and if any of the data items can't be obtained then none of the data items should be locked.

DRAWBACKS: It is very difficult to acquires locks on 3 data items simultaneously.

2ND APPROACH:- It involves assigning an arbitrary serial order on the data item and ensure that data items are locked by the transaction in the order.

DRAWBACKS: It reduces concurrency.

3RD APPROACH:- Based on the concept of Time Stamp Values.This approach is used to decide whether a transaction has to wait or abort & rollback.

TIME STAMP VALUES: 
A time stamp is a unique identifier assigned to each transaction. It usually based on the order in which the transactions are started.

Two methods under 3RD Approach:-

1.) Wait Die- If T1 is the requesting transaction and T2 is requested transaction then

CASE 1 - t(T1)<t(T2) then T1 is allow to wait.

CASE 2 - t(T1)>t(T2) then T1 is abort and rollback.

where t represents time stamp value.

2.) Wound Wait-If T1 is the requesting transaction and T2 is requested transaction then

CASE 1 - t(T1)<t(T2) then T1 is abort and rollback.

CASE 2 - t(T1)>t(T2) then T1 is allow to wait.

where t represents time stamp value.

DEADLOCK DETECTION:

For detecting a deadlock information requires are:

1.) The current set of transactions.

2.) Information about the current allocations of the data item to each of the transactions.

3.) Current set of data items for which each transaction is waiting.

Wait for graph method is used.In this we have to make graph for all transaction.Each node represent the active transaction and edges represents the waiting request.If the cycle is formed then it is in deadlock otherwise not.

DEADLOCK RECOVERY:
There are three methods in which deadlock will recover which are:-

1.) SELECTION OF VICTIM: We should rollback those transactions that will incur the minimum cost. When a deadlock is detected the choice of which transaction to abort can be made using following criteria:

1.) The transaction which have the fewest locks

2.) The transaction that done the least work

3.) The transaction that is farthest from competition.

2.) ROLLBACK: Once we have decided that a particular transaction must be rolled back, we must determine how far this transaction should be rolled back.The simplest solution is to total rollback;Abort the transaction and then restart it. However it is necessary to rollback the transaction only as far as necessary to break the deadlock. But this method requires the system to maintain additional information about the state of all the running system.

3.) PROBLEM OF STARVATION: In a system where the selection of victim is based primary on cost factors, it may happen that the same transaction is always picked as a victim. As a result this transaction never completes its designated task. This situation is called Starvation. The most common solution is to include the number of rollbacks in the cost factor. 

Read More

Concurrency Control algorithm in transaction management |Database management system

CONCURRENT CONTROL ALGORITHMS-

There are two approaches used in algorithms to deals with the problems of concurrency control.These are:-

1.) Pessimistic Approach

2.) Optimistic Approach

1.) PESSIMISTIC APPROACH- This approach causes transaction to be delayed in case they conflict with each other at the some time in 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 operation are performed.

                           VALIDATE | READ | COMPUTE | WRITE

There are two commonly used algorithms,which are based on pessimistic approach:

a.) Two phase locking protocol

b.) Time stamp ordering protocol

2.) 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 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.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 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:-

1.) This technique is very efficient when conflicts are rare. The occasional conflicts result in the transaction rollback.

2.) The roolback 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:

1.) Conflicts are expensive to deal with, since the conflicting transaction must be rolled back.

2.) 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:

1.) Only suitable for environment where there are few conflicts and no long transactions.

2.) Acceptable for mostly Read and Query database systems that requires very few update.

Read More

Lock in transaction management | concurrency control

WHAT IS LOCK?

A lock is a variable associated with a data item that describes the status of the item with respect to possible operations that can be applied to it.Generally,there is one lock for each data item in the database.Locks are used as a means of synchronizing the access by concurrent transactions to the database items.

WHY WE NEED LOCKING TECHNIQUES?

When the transactions are running concurrently the various locking methods are used to ensure serializability of the schedule i.e.to make the non-serial schedule produce the same result as that of a serial schedule.

LOCKING TECHNIQUES FOR CONCURRENCY CONTROL- The various techniques of concurrency control are:-

1.)Binary Locks-A Binary lock has two states or values:Locked and Unlocked.Represented as LOCK( ) and UNLOCK( ). 

                    EG-Suppose there is a data item A and there is two transaction T1 and T2.If transaction T1 locks data item A (LOCK(A))then it is set to 1 and the other transaction(T2) is forced to wait.When the transaction is through using the item,it issues an UNLOCK(A) operation ,which sets it to 0 so that (A) may be accessed by other transaction.Hence a binary lock enforces mutual exclusion on the data item.We use binary locks to avoid Lost Update Problem.

                           

                                    T1                                   T2

                                     

               (Set to 1)      LOCK(A)                       (wait)

                                    Read A

                                    A=A+200

                                    Write(A)

               (set to 0)      UNLOCK(A)

                                                                            LOCK(A)

                                                                            Read A

                                                                            A=A+300

                                                                            Write(A)

                                                                            UNLOCK(A)

DISADVANTAGES OF BINARY LOCK:- It is too restrictive for database items.So, binary locking system cannot be used for practical purpose.

2.)SHARE/EXCLUSIVE(READ/WRITE LOCK)-Share lock can be used for read purpose only.However,if a transaction is to write an item A,it must have exclusive access to A.Share lock is represented as (LOCK S(A)) and exclusive lock is represented as (LOCK X (A)).Also known as read/wrie lock. EG-

                        T1             
             

                         LOCK X(SUM)   (exclusive lock on data item SUM)

                         SUM=

                         LOCK S(A)     (Share lock on data item A)

                         Read A

                         SUM=SUM+A

                         UNLOCK(A)

                         LOCK S(B)     (Share lock on data item B)

                         Read B  

                         SUM=SUM+B

                         Write(SUM)

                         UNLOCK(B)

                         UNLOCK(SUM)

Read More

Concurrency Control in transaction management | Database management

CONCURRENT EXECUTION-

Transaction processing systems usually allow multiple transactions to run concurrently.By allowing multiple transactions to run concurrently will improve the performance of the system in terms of increased throughput or improved response time but this allows causes several complications with consistency of the data.

EXAMPLE-To illustrate the concept of concurrency control, consider two travelers who go to electronic kiosks at the same time to purchase a train ticket to the same destination on the same train. There's only one seat left in the coach, but without concurrency control, it's possible that both travelers will end up purchasing a ticket for that one seat. However, with concurrency control, the database wouldn't allow this to happen. Both travelers would still be able to access the train seating database, but concurrency control would preserve data accuracy and allow only one traveler to purchase the seat.

ADVANTAGES OF CONCURRENT EXECUTION-

1. Improved throughput

2. Reduced Waiting time

CONCURRENCY CONTROL-

Process of managing simultaneous execution of transactions in a shared database, to ensure the serializability of transactions, is known as concurrency control.

WHY WE NEED CONCURRENCY CONTROL?

Simultaneous execution of transactions over a shared database can create several data integrity and consistency problems:-

 1.Lost Updates(write-write conflict)

 2.Dirty Read Problem(write-read conflict)

 3.Unrepeatable reads(Read-Write conflict)

PROBLEMS OF CONCURRENCY CONTROL OR TYPES OF CONFLICT OPERATIONS-

1.Lost Updates(write-write conflict)-A lost update problem occurs when two transactions that access the same database items have their operations in a way that makes the value of some database item incorrect. E.G.- if Transaction T1 and T2 both read a record and then update it,the effects of the first update will be overwritten by the second update.It occurs in case of write-write conflict.

2.Dirty Read Problem(write-read conflict)-A dirty read problem occurs when one transaction updates a database item and then the transaction fails for some reason. The updated database item is read or accessed by another transaction before it is changed back to the original value. E.G.- a transaction T1 updates a record ,which is read by the transaction T2 then T1 aborts and T2 now has values which have never formed part of stable database or we can say T1 reads a dirty data.It occurs in case of write-read conflict.

3.Unrepeatable reads(Read-Write conflict)-Read-Write conflict occurs if a transaction writes a data object previously read by another transaction.It means a transaction reads several values from a database while second transaction updates some of them.

Read More