Concurrency Control:

• Concurrency control concept comes under the Transaction in database

management system (DBMS). It is a procedure in DBMS which helps
us for the management of two simultaneous processes to execute
without conflicts between each other, these conflicts occur in multi
user systems.
• Concurrency can simply be said to be executing multiple transactions
at a time. It is required to increase time efficiency. If many
transactions try to access the same data, then inconsistency arises.
Concurrency control required to maintain consistency data.
• For example, if we take ATM machines and do not use concurrency,
multiple persons cannot draw money at a time in different places. This
is where we need concurrency.
Main problems in using Concurrency
The problems which arise while using concurrency are as follows −
• Updates will be lost −
One transaction does some changes and another transaction deletes that change.
One transaction nullifies the updates of another transaction.
• Uncommitted Dependency or dirty read problem −
On variable has updated in one transaction, at the same time another transaction
has started and deleted the value of the variable there the variable is not getting
updated or committed that has been done on the first transaction this gives us
false values or the previous values of the variables this is a major problem.
• Inconsistent retrievals −
One transaction is updating multiple different variables, another transaction is in
a process to update those variables, and the problem occurs is inconsistency of
the same variable in different instances.
To avoid concurrency control problems and to maintain consistency and
serializability during the execution of concurrent transactions some rules are made.
These rules are known as Concurrency Control Protocols.

• Lock-Based Protocols
• Time-based Protocols
• Validation Based Protocol
• Multiple Granularity
• Multiversion Schemes
Lock Based Protocol:
• To attain consistency, isolation between the transactions is the most important
tool. Isolation is achieved if we disable the transaction to perform a read/write
operation. This is known as locking an operation in a transaction. Through lock-
based protocols, desired operations are freely allowed to perform locking the
undesired operations.
• There are two kinds of locks used in Lock-based protocols:
• Shared Lock(S): The locks which disable the write operations but allow read
operations for any data in a transaction are known as shared locks. They are also
known as read-only locks and are represented by 'S'.
• Exclusive Lock(X): The locks which disable both the write and read operations
for any data in a transaction are known as exclusive locks. They are represented
by 'X'.
Compatibility Function:
• Given a set of lock modes, the compatibility function can be defined
as:
• Let A and B represent arbitrary lock modes. Suppose that a transaction Ti
requests a lock of mode A on item Q on which transactions Tj Currently holds
a lock of mode B.
• If transaction Ti can be granted a lock on Q immediately, in spite of presence
of the lock of mode B, then we say that mode A is compatible with B. Such a
function can re represented conveniently by a matrix. Compatibility of two
modes of lock is given in compatibility matrix:
S X
S True False
X False False
Starvation of Locks:
• Starvation or Livelock is the situation when a transaction has to wait for an indefinite
period of time to acquire a lock.
• Reasons for Starvation –
• If the waiting scheme for locked items is unfair. ( priority queue )
• Victim selection (the same transaction is selected as a victim repeatedly )
• Resource leak.
• Via denial-of-service attack.
• Starvation can be best explained with the help of an example –
• Suppose there are 3 transactions namely T1, T2, and T3 in a database that is trying to
acquire a lock on data item ‘ I ‘. Now, suppose the scheduler grants the lock to T1(maybe
due to some priority), and the other two transactions are waiting for the lock. As soon
as the execution of T1 is over, another transaction T4 also comes over and requests a
lock on data item I. Now, this time the scheduler grants lock to T4, and T2, T3 has to wait
again. In this way, if new transactions keep on requesting the lock, T2 and T3 may have
to wait for an indefinite period of time, which leads to Starvation.
Two Phase Locking(2PL) Protocol:
• A transaction is said to follow the Two-Phase Locking protocol if
Locking and Unlocking can be done in two phases.
• Growing Phase: New locks on data items may be acquired but none
can be released.
• Shrinking Phase: Existing locks may be released but no new locks can
be acquired.
• Note – If lock conversion is allowed, then upgrading of lock( from S(a)
to X(a) ) is allowed in the Growing Phase, and downgrading of lock
(from X(a) to S(a)) must be done in shrinking phase.
• Let’s see a transaction implementing 2-PL.
Let’s see a transaction
implementing 2-PL.
T1 T2

1 lock-S(A)
2 lock-S(A)
3 lock-X(B)
4 ……. ……
5 Unlock(A)
6 Lock-X(C)
7 Unlock(B)
8 Unlock(A)
9 Unlock(C)
10 ……. ……
Variations of Two Phase Locking:
• There are three categories:
• Strict 2-PL
• Rigorous 2-PL
• Conservative 2-PL
Strict 2-PL
• This requires that in addition to the lock being 2-Phase all Exclusive(X)
locks held by the transaction be released until after the Transaction
Commits.
Following Strict 2-PL ensures that our schedule is:
• Recoverable
• Cascadeless
• Hence, it gives us freedom from Cascading Abort which was still there
in Basic 2-PL and moreover guarantee Strict Schedules but
still, Deadlocks are possible!
Rigorous 2-PL
• This requires that in addition to the lock being 2-Phase all Exclusive(X)
and Shared(S) locks held by the transaction be released until after the
Transaction Commits. Following Rigorous 2-PL ensures that our
schedule is:
• Recoverable
• Cascadeless
• Hence, it gives us freedom from Cascading Abort which was still there
in Basic 2-PL and moreover guarantee Strict Schedules but
still, Deadlocks are possible!
Conservative 2-PL:
• A.K.A Static 2-PL, this protocol requires the transaction to lock all the
items it access before the Transaction begins execution by
predeclaring its read-set and write-set. If any of the predeclared items
needed cannot be locked, the transaction does not lock any of the
items, instead, it waits until all the items are available for locking.
• Conservative 2-PL is Deadlock free and but it does not ensure a Strict
schedule. However, it is difficult to use in practice because of the
need to predeclare the read-set and the write-set which is not
possible in many situations. In practice, the most popular variation of
2-PL is Strict 2-PL.
Basic Timestamp Method:
Every transaction is issued a timestamp based on when it enters
the system. Suppose, if an old transaction Ti has timestamp TS(Ti),
a new transaction Tj is assigned timestamp TS(Tj) such that TS(Ti)
< TS(Tj). The protocol manages concurrent execution such that the
timestamps determine the serializability order. The timestamp
ordering protocol ensures that any conflicting read and write
operations are executed in timestamp order. Whenever some
Transaction T tries to issue a R_item(X) or a W_item(X), the Basic
TO algorithm compares the timestamp of T with R_TS(X) &
W_TS(X) to ensure that the Timestamp order is not violated.
This describes
• Whenever the Basic TO protocol in the following two cases.
a Transaction T issues a W_item(X) operation, check the following conditions:
• If R_TS(X) > TS(T) or if W_TS(X) > TS(T), then abort and rollback T and reject the operation. else,
• Execute W_item(X) operation of T and set W_TS(X) to TS(T).
• Whenever a Transaction T issues a R_item(X) operation, check the following conditions:
• If W_TS(X) > TS(T), then abort and reject T and reject the operation, else
• If W_TS(X) <= TS(T), then execute the R_item(X) operation of T and set R_TS(X) to the larger of TS(T)
and current R_TS(X).
Timestamp Ordering Protocol:
• The main idea for this protocol is to order the transactions based on their
Timestamps. A schedule in which the transactions participate is then
serializable and the only equivalent serial schedule permitted has the
transactions in the order of their Timestamp Values. Stating simply, the
schedule is equivalent to the particular Serial Order corresponding to
the order of the Transaction timestamps. An algorithm must ensure that, for
each item accessed by Conflicting Operations in the schedule, the order in
which the item is accessed does not violate the ordering. To ensure this, use
two Timestamp Values relating to each database item X.
• W­_TS(X) is the largest timestamp of any transaction that
executed write(X) successfully.
• R_TS(X) is the largest timestamp of any transaction that
executed read(X) successfully.
Thomas Write Rule:
• Timestamp Ordering Protocol states that if Ri(X) and Wj(X) are conflicting operations then Ri (X) is
processed before Wj(X) if and only if TS(Ti) < TS(Tj). Whenever a schedule does not follow a
serializability order according to the Timestamp, a user generally rejects it and rollback the
Transaction. Some operations on the other hand are harmless and can be allowed.
• Thomas Write Rule allows such operations and is a modification on the Basic Timestamp Ordering
protocol. In Thomas Write Rule users ignore outdated writes. Moreover, of all the Concurrency
Protocols that have been discussed, Concurrency is imposed on Schedules that are Conflict
Serializable, in Thomas Write Rule, the most important improvement is a user can achieve
Concurrency with View Serializable schedules.
• First, let’s state what is Thomas Write Rule and then what are the modifications and improvements it
succeeds over the Basic TO protocol.
• If R_TS(X) > TS(T), then abort and roll back T and reject the operation.
• If W_TS(X) > TS(T), then don’t execute the Write Operation and continue processing. This is a case of
Outdated or Obsolete Writes. Remember, outdated writes are ignored in Thomas Write Rule but a
Transaction following Basic TO protocol will abort such a Transaction.
• If neither the condition in 1 or 2 occurs, then and only then execute the W_item(X) operation of T and
set W_TS(X) to TS(T)
For Example: Thomas Write Rule:
Locks With Multiple Granularity:
• Granularity – It is the size of the data item allowed to lock. Now Multiple Granularity means
hierarchically breaking up the database into blocks that can be locked and can be tracked needs
what needs to lock and in what fashion. Such a hierarchy can be represented graphically as a
tree.
• For example, consider the tree, which consists of four levels of nodes. The highest level
represents the entire database. Below it is nodes of type area; the database consists of exactly
these areas. The area has children nodes which are called files. Every area has those files that
are its child nodes. No file can span more than one area.
• Finally, each file has child nodes called records. As before, the file consists of exactly those
records that are its child nodes, and no record can be present in more than one file. Hence, the
levels starting from the top level are:
• database
• area
• file
• record
Example:

Figure – Multi Granularity tree Hierarchy

Intention Lock Mode:
• Intention Mode Lock –
In addition to S and X lock modes, there are three additional lock modes
with multiple granularities:

• Intention-Shared (IS): explicit locking at a lower level of the tree but only
with shared locks.
• Intention-Exclusive (IX): explicit locking at a lower level with exclusive or
shared locks.
• Shared & Intention-Exclusive (SIX): the subtree rooted by that node is
locked explicitly in shared mode and explicit locking is being done at a
lower level with exclusive mode locks.
Dynamic Database
Concurrency(Phantom Problem):
• The phantom read problem occurs when a transaction reads a
variable once but when it tries to read that same variable again, an
error occurs saying that the variable does not exist.
• In the above example, once transaction 2
reads the variable X, transaction 1 deletes
the variable X without transaction 2’s
knowledge. Thus, when transaction 2 tries
to read X, it is not able to do it.
Optimistic Concurrency Control
• All data items are updated at the end of the transaction, at the end, if any data item is found inconsistent with respect to
the value in, then the transaction is rolled back.
• Check for conflicts at the end of the transaction. No checking while the transaction is executing. Checks are all made at
once, so low transaction execution overhead. Updates are not applied until end-transaction. They are applied to local
copies in a transaction space.
• Phases
• The optimistic concurrency control has three phases, which are explained below −
• Read Phase
• Various data items are read and stored in temporary variables (local copies). All operations are performed in these
variables without updating the database.
• Validation Phase
• All concurrent data items are checked to ensure serializability will not be validated if the transaction updates are actually
applied to the database. Any changes in the value cause the transaction rollback. The transaction timestamps are used and
the write-sets and read-sets are maintained.
• Write Phase
• The transaction updates applied to the database if the validation is successful. Otherwise, updates are discarded and
transactions are aborted and restarted. It does not use any locks hence deadlock free, however starvation problems of
data items may occur.
Multi Version Concurrency Control:
• Multiversion Concurrency Control: Multiversion schemes keep old versions of data item to
increase concurrency. Multiversion 2 phase locking: Each successful write results in the creation
of a new version of the data item written. Timestamps are used to label the versions. When a
read(X) operation is issued, select an appropriate version of X based on the timestamp of the
transaction.
Deadlock Handling Methods:
• Deadlock is a state of a database system having two or more
transactions, when each transaction is waiting for a data item that is
being locked by some other transaction.
• There are two different types of resources deadlocks:
• Single resources: Only one resource of Each time
• Multiple resources: More than one resource of each type
Methods for Handling Deadlocks:
1. Deadlock Detection:
• While a database transaction, if a task waits indefinitely to obtain CPU resources,
then DBMS has to check whether that task is in a state of deadlock or not. To
detect a deadlock a resource scheduler is used. A resource scheduler can detect
deadlock by keeping track of resources allocated to a specific transaction and
requested by another transaction.
• Wait-For Graph: This method of detecting deadlocks involves creating a graph
based on a transaction and its acquired lock (a lock is a way of preventing
multiple transactions from accessing any resource simultaneously). If the created
graph contains a cycle/loop, it means a deadlock exists.
Deadlock Prevention Algorithms:
• Wound wait:
In wound wait scheme, if the older transaction requests for a resource
which is held by the younger transaction, then older transaction forces
younger one to kill the transaction and release the resource. After the
minute delay, the younger transaction is restarted but with the same
timestamp.
• Wait die:
In this scheme, if a transaction requests for a resource which is already
held with a conflicting lock by another transaction then the DBMS simply
checks the timestamp of both transactions. It allows the older transaction
to wait until the resource is available for execution.
Deadlock Recovery Techniques:
• 1. Process Termination:
• To eliminate the deadlock, we can simply kill one or more processes. For this, we use two
methods:
• (a). Abort all the Deadlocked Processes
• (b). Abort one process at a time until deadlock is eliminated:
• 2. Resource Preemption:
• To eliminate deadlocks using resource preemption, we preempt some resources from
processes and give those resources to other processes. This method will raise three issues –
• (a). Selecting a victim:
• We must determine which resources and which processes are to be preempted and also the order to
minimize the cost.
• (b). Rollback:
• We must determine what should be done with the process from which resources are preempted. One
simple idea is total rollback. That means abort the process and restart it.
• (c). Starvation:
• In a system, it may happen that same process is always picked as a victim. As a result, that process will
never complete its designated task. This situation is called Starvation and must be avoided. One solution