Lesson 5: Concurrency Control

5 Concurrency Control 5.1 Need for Concurrency Control In database management system several transactions are executed simultaneously. In order to achieve concurrent transactions, the technique of interleaving is used. But in this technique, there is a possibility for the occurrence of certain anomalies, as explained in the previous lesson. Concurrency Control ensures each transaction is concluded with the desired outcomes. Concurrency control is concerned with preventing loss of data integrity due to interference between users in a multiuser environment. In summary, the reasons for implementing concurrency control are;  To apply isolation through mutual exclusion between conflicting transactions  To resolve write-read, read-write, and write-write conflict issues  To preserve database consistency  To control interaction among concurrent transactions using concurrent-control schemes.  To ensure serializability 5.2 Concurrency Control Protocols Different concurrency control protocols offer different benefits between the amount of concurrency they allow and the amount of overhead that they impose. Following are the Concurrency Control techniques in DBMS:  Lock-Based Protocols  Timestamp-Based Protocols  Validation-Based Protocols 5.2.1 Lock-Based Concurrency Control Lock-Based protocols ensures that a transaction cannot perform a Read or Write operations on an object until it acquires an appropriate lock. It is the best method to control the concurrent access to the database objects by providing suitable permissions to the transactions. Also, it is the only method which takes less cost of time and less program complexity in terms of code development. Lock A Lock is a small object associated with database object which gives the information about the type of operations allowed on a particular database object. A Lock can be termed as a type of permission provided by the transaction manager to the transactions to do a particular operation on a database object. The transaction must get this permission from Transaction Manager to access any database object for alteration. Locking mechanisms are the most common type of 1 concurrency control mechanism. With locking, any data that is retrieved by a user for updating must be locked, or denied to other users, until the update is complete. In a binary locking mechanism, an object can either be on a lock state or in an unlock state. In Shared/ Exclusive locking mechanism, the DBMS uses separate locks for read and write operations. A read operation is given a shared lock while a write operation uses an exclusive lock. A Shared Lock(S) is type of lock established on a database object which is sharable within all active transactions. A database object can be shared-locked by more than one transaction. To get a shared lock on particular database object, the object should not be exclusively locked by any other transaction. Exclusive Lock (X). It is type of lock established on a database object which cannot be shared within the active transactions. It is dedicated to particular transaction; only that particular transaction can access and modify that object. To obtain the exclusive lock on a database object, the object should not be locked by any other transaction. Locking Protocols It is the set of rules to be followed by each transaction, to ensure that the net effect of execution of each transaction in an interleaved schedule will be same as, the result obtained when the transactions executed serially. 1. Two-Phase Locking Protocol (2PL) 2PL protocol ensures serializability by applying a lock to an object thereby blocking other transactions from accessing the same object simultaneously. Variants of the 2PL protocol are Strict 2PL Protocol, Rigorous 2PL Protocol, and Conservative 2PL Protocol i. Strict 2PL Protocol Strict Two-Phase Locking (Strict 2PL) is the most widely used locking protocol. It provides few rules to the transactions to access the database objects. Rule 1: If a Transaction “T” wants to read, and modify an object, it first requests a shared, and an exclusive lock on the database object respectively. Rule 2: All Locks held by the transaction will be released when it is completed. All exclusive-locks are held until the transaction commits or aborts. Strict Two-Phase Locking Protocol avoids cascaded rollbacks. However, it is not deadlock free. ii. Rigorous 2PL protocol This protocol requires that all the shared and exclusive locks to be held until the transaction commits. 2 iii. Conservative 2PL Protocol It is also called as Static Two – Phase Locking Protocol. It is almost free from deadlocks as all required items are listed in advance. It requires locking of all data items to access before the transaction starts. 5.2.2 Timestamp-based Protocols The System Time or Logical Counter as a timestamp is used to serialize the execution of concurrent transactions. This ensures that every conflicting read and write operations are executed in a timestamp order. The older transaction is always given priority in this method. This is the most commonly used concurrency protocol mechanism to resolve deadlocks. While lock-based protocols help to manage the order of execution between conflicting transactions, timestamp-based protocols manage conflicts as soon as an operation is created. 5.2.3 Validation Based Protocol It is also called Optimistic Concurrency Control technique. Local copies of the transaction data are updated rather than the data itself, which results in less interference with execution of the transaction. The Validation based Protocol is performed in three phases: Read Phase, Validation Phase, and Write Phase. In the Read Phase, the data values from the database can be read by a transaction but the write operation or updates are only applied to the local data copies, not the actual database. In Validation Phase, the data is checked to ensure that there is no violation of serializability while applying the transaction updates to the database. In the Write Phase, the updates are applied to the database if the validation is successful, else; the updates are not applied, and the transaction is rolled back. 5.3 Deadlock Deadlock occurs mainly due to the Lock- Based Concurrency Control. The exclusive lock type will isolate one particular database object from the access of other transactions. This will suspend all other transactions from requesting a shared lock on that particular object until the transaction holding the exclusive lock on the object is completed. This may create a loop in database leading to deadlocks within transactions. Whenever a deadlock occurs within the transactions in DBMS system, neither one of the transactions involved is committed. DBMS has to use suitable recovery systems to overcome deadlocks. Methods to Overcome Deadlocks 3 Mostly it is not possible to avoid the occurrence of Deadlock. Most of the methods available are detection and recovery based. 5.3.1 Dead lock detection Detection from the Average Waiting Time of the Transaction If more than two transactions are waiting for a long time, then it implies that at some part of the database, a deadlock has occurred. Deadlock Detection algorithm Deadlock detection algorithms are used to find any loops in the Database. The main advantage is that we can find the locked transactions quickly and it is enough to restart only those particular transactions. 5.3.2 Deadlock Recovery Once if Deadlock is found then we have several methods to release locked Transactions. Method 1: Release of Objects from Big Transaction In this method the transaction which holds the largest number of database objects will be restarted and all locks associated with that “Big Transaction” will thus be released. Example If Transaction say, T1 holds exclusive lock on four objects, T2 holds same on three objects and T3 holds same on two objects then if Deadlock occurred within these transactions, then T1 will be restarted. Method 2: Restarting the Locked Transactions In this method the database objects associated with locked transactions are released, and the transactions are restarted. 5.3.3 Starvation Starvation is the situation when a transaction needs to wait for an indefinite period in order to acquire a lock. This happens because: i. ii. iii. the waiting scheme for locked items is not properly managed resource leaks the same transaction is selected as a victim repeatedly by the deadlock recovery mechanism 4