Chapter 4

Concurrency Control
Techniques

Lecture 4

Compiled by Chala.M
 Concurrent Transaction
What is concurrency?
 is a unique characteristic enabling two or more users to work on the
database at the same time without affecting data integrity.
 is the execution of a set of multiple instruction sequences at the same
time.
 Process of managing simultaneous operations on the database without
having them interfere with one another is called Concurrency Control
 Concurrency control is needed in Multiuser Database Management
Systems (DBMS) where multiple users or processes access and
manipulate the database simultaneously.

2
 Single-User vs. Multiuser Database Management Systems

Single-User System:

• At most one user at a time can use the database management system.

E.g. Personal computer system

Multiuser System:

• Many users can access the DBMS concurrently.

• System are operated by many users who submit transaction concurrently to

the system

• This is achieved by multiprogramming, which allows the computer to

execute multiple programs/processes at the same time.

E.g. Air line reservation, Bank

3
 Problems of Concurrent Transaction

• The main objective in developing database system is to allow many

concurrent user to access the database.
• But concurrent access of database rise following the problem if not
controlled and managed.
1. Lost Update problem (Write-Write Conflict)
2. Dirty Reads or Uncommitted dependency or Inconsistent read
problem(Write-Read Conflict)
3. Unrepeatable Reads Problem or Incorrect summary or
Inconsistent Analysis (read-write confict)

4
 Write-Write Conflict (Lost Update Problem)
 Occurs when two or more transactions simultaneously try to write to the same data item, and
one transaction overwrites the other's changes.
Example:
• Transaction T1: Writes a new value to a data item.
• Transaction T2: Simultaneously writes another value to the same data item.
• One write operation is "lost" because the last write overwrites the previous one.

 T1 reads Stock = 50 and updates it to 70.

 T2 simultaneously reads the same Stock = 50 and updates it to 40.
 T2’s update overwrites T1’s, leading to the loss of T1’s update (70), leaving the final value as 40.
5
 Write-Read Conflict (Dirty Reads Problem)
• Occurs when a transaction reads data written by another transaction that has not yet been
committed. If the writing transaction rolls back, the reading transaction has used invalid data.
• Example:
• Transaction T1: Writes a new value to a data item but hasn’t committed.
• Transaction T2: Reads the uncommitted value.
• If T1 rolls back, the value read by T2 becomes invalid.

• T1 writes a new value (5000) but hasn’t committed the transaction.

• T2 reads the uncommitted value.
• T1 then rolls back, reverting the value to 4000.
• T2 has already used the incorrect value (5000), causing dirty read issues.
6
 Read-Write Conflict (Unrepeatable Reads Problem)
• Occurs when a transaction reads the same data item multiple times but gets different
values due to modifications by other concurrent transactions.
• Example:
• Transaction T1: Reads a data item (e.g., balance = 100).
• Transaction T2: Updates the same data item (e.g., balance = 200) and commits.
• Transaction T1: Reads the same data item again and sees the updated value (200),
resulting in inconsistency.

 T1 reads the Balance as 100 initially. After T2 updates it to 200, T1 reads it again and sees
a different value, resulting in inconsistent analysis.
7
 Purpose of concurrency control

 Enforcing Isolation Among Transactions:

 Ensures that each transaction is executed independently, as if no other
transactions are running simultaneously.
 Preserving Database Consistency:
 Ensures that the database remains in a consistent state before and after
the execution of transactions.
 Resolving Read-Write and Write-Read Conflicts:
Manages conflicts that arise:
 A transaction reads data that another is writing (read-write conflict).
 A transaction writes data that another is reading (write-read conflict).
 Multiple transactions write to the same data (write-write conflict).

8
 Concurrency control techniques

Basic concurrency control techniques:

– Locking,
– Time stamping
– Optimistic methods
The First two are conservative approaches
– delay transactions in case they conflict with other transactions.
– Optimistic methods assume conflict is rare and only check for conflicts
at commit.

9
 Locking Technique

Locking
 A lock is a variable associate with a data item in the database.

 It describes the status of that data item with respect to possible

operations that can be applied to the item.
 Transaction uses locks to deny access to other transactions and so
prevent incorrect updates.
 Transaction must claim a shared lock(read) or exclusive lock(write) on
data item before read or write
 Lock prevents transaction T2 from modifying item x or reading item x
in the case that item x has a write lock by T1.

10
 Cont.….

• Locking is an operation which secures

 Permission to Read
 Permission to Write a data item for a transaction.
Example:
• Lock (X). Data item X is locked in behalf of the requesting
transaction.
– Unlocking is an operation which removes these permissions from the
data item.
• Unlock (X): Data item X is made available to all other
transactions.
– Lock and Unlock are Atomic operations.

11
 Cont.…..

Binary locks
 A binary lock can have two states or values 1 and 0.
 If the value of the lock on X is 1, item X is locked and cannot be accessed
by a database operation that requests the item.
 If the value of the lock on X is 0, item X is unlocked, and it can be
accessed when requested.
 A transaction requests access to an item X by allocating a lock(X)
operation.
 If LOCK(X) = 1, the transaction is forced to wait; otherwise, the
transaction sets LOCK(X) := 1 (locks the item) and allows access.
 If LOCK(X) := 0 (unlocks the item) so that X may be accessed by other
transactions.

12
 Cont.….
Two locks modes:
– Shared (read)
– Exclusive (write).
Shared mode: Shared lock (X)
– More than one transaction can apply share lock on X for reading its
value.
– But no write lock can be applied on X by any other transaction.
Exclusive mode: Write lock (X)
– Only one write lock on X can exist at any time No shared lock can be
applied by any other transaction on X.
Conflict matrix

13
 Cont…

Locking - Basic Rules

14
 Cont.….
 If a DBMS wishes to read an item, then a shared (S) lock is placed on
that item.
 If a transaction has a shared lock on a database item, it can read the item
but not update it.
 If a DBMS wishes to write (update) an item, then an exclusive (X) lock is
placed on that item.
 If a transaction has an exclusive lock on an item, it can both read and
update it.
 To prevent interference from other transactions, only one transaction can
hold an exclusive lock on an item at any given time.
 A read-locked item is also called share-locked, because other transactions
are allowed to read access that item.
 A write-locked item is called exclusive-locked, because a single transaction
exclusively holds the lock on the item.
15
 Cont.….

 If a transaction TA holds a shared lock on item X, then a request from

another transaction TB for an exclusive lock on X will cause TB to go
into a wait state (and B will wait until TA lock is released).

 A request from transaction TB for a shared lock on X will be granted

(that is, TB will now also hold a shared lock on X).

 Reads cannot conflict, so more than one transaction can hold shared locks
simultaneously on same item.

 If transaction TA holds an exclusive lock on record X, then a request from

transaction TB for a lock of either type on X will cause TB to go into a
wait state (and TB will wait until TA lock is released).
16
 Cont….
Two-Phase Locking (2PL)

17
 Cont.….

18
 Problem/challenges of Locking Techniques

 Deadlocks
 Starvation
 Lock Contention

19
 Deadlock
 Is occur when two (or more) transactions are each waiting for locks held
by the other to be released or occurs when each of two transactions is
waiting for the other to release the lock on an item.

 Deadlocks occur when two or more transactions are blocked indefinitely

(unable to proceed with a task or process without a specified resolution or
release) each waiting for the other to release a lock.

 It's a situation where a set of processes is effectively preventing each

other from progressing because each is waiting for the other to release a
lock.

20
 Deadlock

 At time step 5, it is not possible for T1 to acquire an exclusive lock on X as there is

already a shared lock on X held by T2 so, T1 has to wait.
 Transaction T2 at time step 6 tries to get an exclusive lock on Y, because T1 has a
shared lock on Y already so, T2 is put in waiting too.
 Therefore, both transactions wait fruitlessly for the other to release a lock. This
situation is known as a deadly embrace or deadlock.
 The above schedule would terminate in a deadlock.
21
 Deadlock
 Techniques for handling deadlock:
 Timeout
 Deadlock prevention.
 Deadlock detection and recovery.

22
 Deadlock
Timeout
 Transaction that requests lock will only wait for a system-defined period
of time.
 If lock has not been granted within this period, lock request times out.
 If a transaction cannot obtain the required locks within the specified time,
it is aborted or restarted.
 In this case, DBMS assumes transaction may be deadlocked, even though
it may not be, and it aborts and automatically restarts the transaction.

23
 Deadlock
Deadlock Prevention

24
 Deadlock

25
 Deadlock
 Timestamp to prevent deadlock has two method wait-die and wound-
wait.
 Wait-Die - only an older transaction wait for younger one,(an older
transaction is allowed to wait on a younger transaction) otherwise
transaction is aborted (dies) and restarted with the same timestamp.
 if TS(Ti)<TS(Tj) (Ti is older than Tj) then Ti is allowed to wait, otherwise
abort Ti (Ti dies) and restart it later with the same timestamp.
 Prefers younger transaction

26
 Deadlock
 Wound-Wait - a younger transaction wait for an older one.
• If older transaction requests lock held by younger one, younger one is
aborted (wounded).
• “Wound”: The younger transaction rolls back (if it cannot finish in
small interval of time) and gives lock to the older one
• if TS(Ti)<TS(Tj) (Ti is older than Tj) then Tj is allowed to wait,
otherwise abort Tj (Tj wounded) and restart it later with the same
timestamp.
• Prefers Older Transaction

27
 Deadlock
Deadlock detection and recovery
Deadlock Detection:
 By Resource Allocation Graph (RAG):
 constructing a resource allocation graph (RAG) that represents the
relationships between processes and resources.
 nodes in the graph represent processes and resources, and edges
represent resource requests and allocations.
 By wait-for-graph (WFG)
 construction of wait-for-graph (WFG) showing transaction
dependencies
 Deadlock exists if and only if WFG contains cycle.
 If a cycle is present in the graph, it indicates that a set of processes is
waiting for resources held by each other, forming a circular wait
condition, a characteristic of deadlocks.

28
 Deadlock
Resource Allocation Graph
(RAG) or wait-for-graph (WFG)
Graph (a) has no deadlock
Graph (b) has deadlock since
T1wait T2 wait T3 wait T1

Deadlock Recovery:
 Abort and Rollback:
 Once a deadlock is detected, one or more transactions involved in the deadlock
can be aborted to break the circular wait condition.
 Aborted transactions are rolled back to their previous consistent state, and their
locks are released, allowing other transactions to proceed.
 Choosing which transaction to abort is known as victim selection.
 The algorithm for victim selection should generally avoid selecting transactions
that have been running for a long time and that have performed many updates.
29
 Starvation
 happens when a transaction is unable to acquire the required locks and is
repeatedly delayed.
 The transaction is consistently delayed or unable to make progress due to
being repeatedly avoided by other transactions.
 may arise due to unfair scheduling policies, improper prioritization of
processes.
 result in unfair resource allocation, where certain processes continually
access resources while others are consistently delayed or abort.
 Solution-use
– priority-based scheduling(FIFO)
– allow for transaction that wait for a longer time and
– give high priority for transaction that have been abort for many time.

30
 Time stamping protocol
 A unique identifier created by DBMS that indicates relative
starting time of a transaction.
 Can be generated by using system clock at time transaction
started, or by incrementing a logical counter every time a new
transaction starts.
 Every transaction has a timestamp associated with it, and the
ordering is determined by the age of the transaction.
 A transaction created at 0002 clock time would be older than
all other transactions that come after it.
 Eg. transaction 'y' entering the system at 0004 is two seconds younger and the priority
would be given to the older one.

31
 Time stamping protocol
 Transactions ordered globally so that older transactions, transactions with
smaller timestamps, get priority in the event of conflict.
 Conflict is resolved by rolling back and restarting transaction.
 No locks so no deadlock.
 Read/write proceeds only if last update on that data item was carried out by
an older transaction.
 Otherwise, transaction requesting read/write is restarted and given a new
timestamp.

32
 Time stamping protocol
Advantages of Timestamp Ordering:
High Concurrency:
 Allows for a high degree of concurrency as transactions with non-
conflicting operations can proceed simultaneously.
Determination of Serializability:
 The protocol guarantees that the execution of transactions is
equivalent to some serial order, ensuring serializability.
No Deadlocks:
 Timestamp Ordering eliminates the possibility of deadlocks because
transactions are strictly ordered based on timestamps.

33
 Multi-version Concurrency Control Techniques
 is a technique used in database management systems to handle concurrent
operations without conflicts, using multiple versions of a data item.
 Instead of locking the items for write operations (which can reduce concurrency
and lead to bottlenecks or deadlocks), MVCC will create a separate version of the
data item being modified.

34
 Cont.….
Breakdown of the Multi version concurrency control (MVCC)

 Multiple Versions: When a transaction modifies a data item, instead of

changing the item in place, it creates a new version of that item. This means that
multiple versions of a database object can exist simultaneously.
 Reads aren’t Blocked: One of the significant advantages of MVCC is that read
operations don’t get blocked by write operations.
• When a transaction reads a data item, it sees a version of that item
consistent with the last time it began a transaction or issued a read,
even if other transactions are currently modifying that item.
 Timestamps or Transaction IDs: Each version of a data item is tagged
with a unique identifier, typically a timestamp or a transaction ID.
• This identifier determines which version of the data item a
transaction sees when it accesses that item.

35
 Cont.…

 Garbage Collection: As transactions create newer versions of data

items, older versions can become obsolete.
• There’s typically a background process that cleans up these old versions, a
procedure often referred to as “garbage collection.”
 Conflict Resolution: If two transactions try to modify the same data
item concurrently, the system will need a way to resolve this.
• the first transaction to commit will succeed, and the other transaction will
be rolled back or will need to resolve the conflict before proceeding.

36
 Cont.…

Explanation:
 Both transactions T1 and T2 were able to proceed concurrently without blocking
each other.
 Each transaction created a new version of the data it modified, indicated by the
unique timestamp associated with that version.
 The database now contains multiple versions of each account, allowing the system
to maintain a consistent state and support concurrent transactions.
37
 Validation (Optimistic) Concurrency Control Technique
 validation concurrency control allows transactions to work on private copies of
database items and validates the transactions only at the time of commit.

 Optimistic Concurrency Control (OCC) is a technique used in database management

systems to control access to shared resources and maintain data consistency in a
multi-user environment.

 Unlike pessimistic concurrency control mechanisms which acquire locks to control

access, OCC adopts an optimistic approach.

 In optimistic concurrency control is that conflicts between transactions are rare, and
it’s better to let transactions run to completion and only check for conflicts at
commit time.
 It allows transactions to proceed without acquiring locks initially, and conflicts are
detected and resolved at the time of transaction commitment.
38
 Cont.…
Phase of VCC
 Read Phase: The transaction reads values from the database and makes
changes to its private copy without affecting the actual database.

 Validation Phase: Before committing, the transaction checks if the changes

made to its private copy can be safely written to the database without causing
any conflicts.

 Write Phase: If validation succeeds, the transaction updates the actual

database with the changes made to its private copy.

39
 Cont.…

– If during validation, T finds that another transaction has modified a

data item that T read, a conflict is detected.
– Conflicts may arise if two transactions attempt to modify the same
data concurrently.
– If a conflict is detected, the system must resolve it before allowing T
to commit.
– Common conflict resolution strategies include aborting one of the
conflicting transactions or prompting the application to resolve the
conflict.
– If no conflicts are detected during validation, transaction T can commit
its changes to the database.
– The changes are applied to the shared database, making them visible to
other transactions.

40
 Cont.….

Advantages of Validation (Optimistic) Concurrency Control:

• Reduced Lock Contention:
– Since transactions do not acquire locks during the read phase, there is
less contention for locks, leading to increased concurrency.
– There is lower overhead associated with acquiring and releasing locks
compared to pessimistic concurrency control mechanisms.
• Higher Throughput(high rate to complete process):
– Optimistic concurrency control allows transactions to proceed
independently during the read and write phases, leading to potentially
higher throughput in scenarios with low conflict rates.

41
 Cont.…
Disadvantages and Considerations:
• Potential for Conflicts:
– The optimistic approach can lead to conflicts, especially in scenarios with high
contention for the same data items.
• Abort and Retry Overhead:
– Transactions that encounter conflicts may need to be aborted and retried, leading
to additional processing overhead.
• Application Logic for Conflict Resolution:
– The application must implement logic for conflict resolution, and developers
need to handle conflicts appropriately.

42
 Multiple Granularity Locking
 Multiple Granularity Locking (MGL) is a concurrency control technique
used in database management systems to address the locking needs at
different levels of granularity within a hierarchical data structure.

43
 Multiple Granularity Locking
Granularity hierarchy

44
 Multiple Granularity Locking
Let's consider an example of Multiple Granularity Locking (MGL) in the
context of a relational database with different levels of granularity: database-
level, table-level, page-level, and record-level locks.
Database Schema:
• Suppose we have a simple relational database with two tables: Customers
and Orders

45
 Multiple Granularity Locking
 Let's consider four transactions: T1, T2, T3, and T4, each performing
different operations on the database.
Transaction T1:
– Operation: T1 wants to perform a global operation that involves updating the
balance of all customers.
– Acquires a database-level lock to ensure exclusive access to the entire database.
Transaction T2:
– Operation: T2 wants to update the balance of a specific customer (record-level
operation).
– Acquires a table-level lock on the Customers table to ensure exclusive access to
the table.
– Acquires a record-level lock on the specific customer (e.g., CustomerID = 101).

46
 Multiple Granularity Locking
Transaction T3:
– Operation: T3 wants to add a new order for a specific customer (record-level
operation).
– Acquires a table-level lock on the Orders table to ensure exclusive access to the
table.
– Acquires a record-level lock on the specific customer for whom the order is
being added (e.g., CustomerID = 102).
Transaction T4:
– Operation: T4 wants to perform an operation that involves updating multiple
records on a specific page (page-level operation).
– Acquires a table-level lock on the Customers table to ensure exclusive access to
the table.
– Acquires a page-level lock for the page containing records of customers (e.g., a
block of records).

47
 End

End of chapter four

Thankyou !!

48