Concurrency Control Protocols and Deadlocks

In the previous articles, we studied:

  • Concurrency problems
  • Serializability
  • Precedence graphs

Now we will learn how a DBMS actually prevents concurrency problems.

The mechanisms used to ensure safe concurrent execution are called Concurrency Control Protocols.

1. What is a Concurrency Control Protocol?

A concurrency control protocol is a set of rules that transactions must follow while accessing shared data.

Its objectives are:

  • Ensure serializable schedules
  • Maintain isolation
  • Prevent anomalies
  • Preserve database consistency

There are several concurrency control protocols:

  • Lock-based protocols
  • Timestamp-based protocols
  • Graph-based protocol
  • Multiversion protocols

The most widely used approach is a lock-based protocol.

2. Lock-Based Protocol

In a lock-based protocol, a transaction must obtain a lock on a data item before accessing it.

If another transaction already holds a conflicting lock, the requesting transaction must wait.

2.1 Types of Locks

Shared Lock (S)

  • Used for read operations.
  • Multiple transactions can hold shared locks on the same data item.

Example:
If T1 and T2 only read A, both can acquire shared locks.

Exclusive Lock (X)

  • Used for write operations.
  • Only one transaction can hold an exclusive lock.
  • No other transaction can read or write the item.

2.2 Lock Compatibility

Current Lock

Shared Request

Exclusive Request

Shared

Allowed

Not Allowed

Exclusive

Not Allowed

Not Allowed

This compatibility ensures safe concurrent access.

3. Two-Phase Locking (2PL)

Two-Phase Locking is a protocol that guarantees conflict serializability.

It has two phases:

3.1 Growing Phase

  • A transaction can acquire locks.
  • It cannot release any lock.

3.2 Shrinking Phase

  • A transaction can release locks.
  • It cannot acquire new locks.

Once a transaction releases its first lock, it enters the shrinking phase.

2PL ensures serializable schedules.

However, it may still cause cascading rollbacks.

4. Strict Two-Phase Locking (Strict 2PL)

Strict 2PL improves basic 2PL.

Rule:

  • All exclusive locks are held until the transaction commits or aborts.

Advantages:

  • Prevents cascading rollback
  • Ensures recoverability
  • Used in most real DBMS

Strict 2PL is more practical than basic 2PL.

5. Timestamp-Based Protocol

Instead of locks, this protocol assigns each transaction a unique timestamp.

Transactions execute in timestamp order.

Rules:

  • If an operation violates timestamp order, the transaction is rolled back.
  • Older transactions are given priority.

Advantages:

  • No deadlock
  • Simple ordering mechanism

Disadvantages:

  • May cause frequent rollbacks

6. Multiple Granularity Locking

Databases are organized hierarchically:

  • Database
  • Table
  • Page
  • Record

Instead of locking only at one level, DBMS allows locking at multiple levels.

This is called Multiple Granularity Locking.

6.1 Intention Locks

To support hierarchical locking, a DBMS uses intention locks:

  • Intention Shared (IS)
  • Intention Exclusive (IX)

These locks indicate that a transaction intends to acquire locks at lower levels.

Rule:

A transaction must acquire an intention lock at a higher level before locking lower-level objects.

This improves performance while maintaining safety.

7. Graph-Based Protocol (Brief Idea)

In the graph-based protocol:

  • Data items are organized as a directed acyclic graph.
  • Transactions must follow a predefined partial order when accessing data.

If transactions follow the graph order, serializability is guaranteed.

This protocol prevents cycles and ensures safe execution.

8. Deadlock in DBMS

Deadlock occurs when two or more transactions wait indefinitely for each other.

Example:

T1 holds a lock on A and waits for B.
T2 holds a lock on B and waits for A.

Neither can proceed.

8.1 Wait-For Graph

Deadlock detection uses a Wait-For Graph.

  • Nodes represent transactions.
  • Edge Ti → Tj means Ti is waiting for Tj.

If the graph contains a cycle, a deadlock exists.

8.2 Deadlock Handling Techniques

1. Deadlock Prevention

Prevent circular wait by controlling resource allocation.

2. Deadlock Avoidance

Allow resource allocation only if the system remains in a safe state.

3. Deadlock Detection and Recovery

  • Detect a cycle using the wait-for graph.
  • Abort one transaction to break the cycle.

Summary

In this article, we studied:

  • Lock-based protocol
  • Shared and exclusive locks
  • Two-Phase Locking (2PL)
  • Strict 2PL
  • Timestamp-based protocol
  • Multiple Granularity Locking
  • Graph-based protocol
  • Deadlock and its handling