Concurrency Control
Concurrency control is the technique that ensures that the the above three conflicts don’t occur in the
database. There are certain rules to avoid problems in concurrently running transactions and these rules
are defined as the concurrency control protocols.
Concurrency control protocols
Concurrency control protocols ensure that the database remain in a consistent state after the execution of
transactions. There are three concurrency control protocols:
1. Lock Based Concurrency Control Protocol
2. Time Stamp Concurrency Control Protocol
3. Validation Based Concurrency Control Protocol
Lock based Protocol in DBMS
A lock is kind of a mechanism that ensures that the integrity of data is maintained. It does that, by locking
the data while a transaction is running, any transaction cannot read or write the data until it acquires the
appropriate lock. There are two types of a lock that can be placed while accessing the data so that the
concurrent transaction can not alter the data while we are processing it.
1. Shared Lock(S)
2. Exclusive Lock(X)
1. Shared Lock(S): Shared lock is placed when we are reading the data, multiple shared locks can be
placed on the data but when a shared lock is placed no exclusive lock can be placed.
To understand the lock mechanism let’s take an example of conflict:
You and your brother have a joint bank account, from which you both can withdraw money. Now let’s
say you both go to different branches of the same bank at the same time and try to withdraw 5000 INR,
your joint account has only 6000 balance.
Now if we don’t have concurrency control in place you both can get 5000 INR at the same time but once
both the transactions finish the account balance would be -4000 which is not possible and leaves the
database in inconsistent state.
We need something that controls the transactions in such a way that allows the transaction to run
concurrently but maintaining the consistency of data to avoid such issues.
Solution of the above problem using Shared lock:
For example, when two transactions are reading Steve’s account balance, let them read by placing shared
lock but at the same time if another transaction wants to update the Steve’s account balance by placing
Exclusive lock, do not allow it until reading is finished.
2. Exclusive Lock(X): Exclusive lock is placed when we want to read and write the data. This lock allows
both the read and write operation, Once this lock is placed on the data no other lock (shared or Exclusive)
can be placed on the data until Exclusive lock is released.
For example, when a transaction wants to update the Steve’s account balance, let it do by placing X lock
on it but if a second transaction wants to read the data(S lock) don’t allow it, if another transaction wants
to write the data(X lock) don’t allow that either.
So based on this we can create a table like this:
Lock Compatibility Matrix
__________________________
| | S | X |
|-------------------------
| S | True | False |
|-------------------------
| X | False | False |
--------------------------
Read this matrix:
There are two rows, first row says that when S lock is placed, another S lock can be acquired so it is
marked true but no Exclusive locks can be acquired so marked False.
In second row, When X lock is acquired neither S nor X lock can be acquired so both marked false.
Types of Lock Protocols
1. Simplistic lock protocol
This protocol is simplest form of locking the data while a transaction is running. As per simplistic lock
protocol any transaction needs to acquire the lock on the data before performing any insert, update or
delete operation. The transaction releases the lock as soon as it is done performing the operation. This
prevents other transactions to read the data while its being updated.
2. Pre-claiming lock protocol
• As the name suggests, this protocol checks the the transaction to see what all locks it
requires before it begins.
• Before the transaction begins, it places the request to acquire all the locks on data items.
• If all the locks are granted, the transaction begins execution and releases all the locks once
it’s done execution.
• If all the locks are not granted this transaction waits until the required locks are granted.
3. Two Phase locking protocol (2PL)
In two phase locking protocol the locking and unlocking of data items is done in two phases.
Growing Phase: In this phase, the locks are acquired on the data items but none of the acquired locks can
be released in this phase.
Shrinking Phase: The existing locks can be released in this phase but no new locks can be acquired in
this phase.
Note: The point at which the transaction acquires final lock and the growing phase ends is called lock
point.
2 PL Example: Let’s take an example to understand how two phase locking protocol works: In the
following example there are two transaction T1 and T2 running concurrently.
Transaction T1: In this example, growing phase of T1 is from Step 1 to Step 5. Shrinking phase is
from Step 7 to Step 9. Lock point is at step 5.
Transaction T2: Growing phase of T2 is from Step 2 to Step 10. Shrinking phase is from Step 11 to
Step 13. Lock point is at step 10.
T1 T2
---- ----
Step 1 lock-S(A)
Step 2 .. lock-S(A)
Step 3 lock-S(B)
Step 4 ... lock-S(B)
Step 5 lock-X(C)
Step 6 ..
Step 7 Unlock(A)
Step 8 Unlock(B)
Step 9 Unlock(C)
Step 10 lock-S(C)
Step 11 Unblock(A)
Step 12 Unblock(B)
Step 13 Unblock(C)
4. Strict Two Phase Locking Protocol (Strict – 2PL)
It is somewhat similar to 2PL except that it doesn’t have a shrinking phase. This protocol releases all the
locks only after the transaction is completed successfully and used the commit statement to make the
changes permanent in the database.
It doesn’t release locks after performing an operation on data items. It releases all the locks at the same
time once the transaction commit successfully.
Timestamp Ordering Protocol:
• Timestamp ordering protocol maintains the order of transaction based on their
timestamps.
• A timestamp is a unique identifier that is being created by the DBMS when a transaction
enters into the system. This timestamp can be based on the system clock or a logical counter
maintained in the system.
• Timestamp helps identifying the older transactions (transactions that are waiting in line
to be executed) and gives them higher priority compared to the newer transactions. This
make sure that none of the transactions are pending for a longer period of time.
• This protocol also maintains the timestamps for the last read and last write on a data.
• For example, let’s say an old transaction T1 timestamp is TS(T1) and a new transaction T2
enters into the system, timestamp assigned to T2 is TS(T2). Here TS(T1) < TS(T2) so the T1
has the higher priority because its timestamp is less than timestamp of T2. T1 would be
given the higher priority than T2. This is how timestamp based protocol maintains
the serializability order.
Timestamp ordering protocol works:
Let’s see how a timestamp ordering protocol works in a DBMS system. Let’s say there is data item A in
the database.
W_TS(A) is the largest timestamp of a transaction that executed the operation write(A) successfully.
R_TS(A) is the largest timestamp of a transaction that executed the operation read(A) successfully.
1. Whenever a Transaction Tn issues a Write(A) operation, this protocol checks the following
conditions:
• If R_TS(A) > TS(Tn) or if W_TS(A) > TS(Tn), then abort and rollback the
transaction Tn and reject the write (A) operation.
• If R_TS(A) <= TS(Tn) or if W_TS(A) <= TS(Tn) then execute Write(A)
operation of Tn and set W_TS(A) to TS(Tn).
2. Whenever a Transaction Tn issues a Read(A) operation, this protocol checks the following
conditions:
• If W_TS(A) > TS(Tn), then abort and reject Tn and reject the Read(A)
operation.
• If W_TS(A) <= TS(Tn), then execute the Read(A) operation of Tn and
update the timestamp R_TS(A).
Advantages of Timestamp based protocol
• Schedules managed using timestamp based protocol are serializable just like the two phase
protocols
• Since older transactions are given priority which means no transaction has to wait for longer
period of time that makes this protocol free from deadlock.
Validation Based Protocol in DBMS:
Validation based protocol avoids the concurrency of the transactions and works based on the assumption
that if no transactions are running concurrently then no interference occurs. This is why it is also
called Optimistic Concurrency Control Technique.
In this protocol, a transaction doesn’t make any changes to the database directly, instead it performs all
the changes on the local copies of the data items that are maintained in the transaction itself. At the end of
the transaction, a validation is performed on the transaction. If it doesn’t violate any serializability rule,
the transaction commit the changes to the database else it is updated and restarted.
Three phases of Validation based Protocol
1. Read phase: In this phase, a transaction reads the value of data items from database and
store their values into the temporary local variables. Transaction then starts executing but it
doesn’t update the data items in the database, instead it performs all the operations on
temporary local variables.
2. Validation phase: In this phase, a validation check is done on the temporary variables to
see if it violates the rules of serializability.
3. Write phase: This is the final phase of validation based protocol. In this phase, if the
validation of the transaction is successful then the values of temporary local variables is
written to the database and the transaction is committed. If the validation is failed in second
phase then the updates are discarded and transaction is slowed down to be restarted later.
Let’s look at the timestamps of each phase of a transaction:
Start(Tn): It represents the timestamp when the transaction Tn starts the execution.
Validation(Tn): It represents the timestamp when the transaction Tn finishes the read phase and starts
the validation phase.
Finish(Tn): It represents the timestamp when the transaction Tn finishes all the write operations.
This protocol uses the Validation(Tn) as the timestamp of the transaction Tn because this is actual phase
of the transaction where all the checks happen. So it is safe to say that TS(Tn) = Validation(Tn).
If there are two transactions T1 & T2 managed by validation based protocol and if Finish(T1) < Start(T2)
then the validation will be successful as the serializability is maintained because T1 finished the execution
well before the transaction T2 started the read phase.
