Concurrency Control

Concurrency Control

Published by: Sareena Kumari Basnet

Published date: 28 Jul 2024

Concurrency Control

Concurrency Control

Definition

Concurrency control is a database management system (DBMS) concept that is used to address the problem of concurrent access to the database by multiple transactions. It ensures that database transactions are performed concurrently without violating the integrity of the data.

Lock-Based Protocols

Lock-based protocols manage concurrent access to the database by requiring transactions to obtain a lock on the data before accessing it.

Locks:

  • Exclusive (X) lock: Data item can be both read and written. X-lock is requested using lock-X instruction.
  • Shared (S) lock: Data item can only be read. S-lock is requested using lock-S instruction.

Lock Compatibility Matrix:

  • A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions.
  • Any number of transactions can hold shared locks on an item, but if any transaction holds an exclusive lock on the item, no other transaction may hold any lock on the item.

Example:

 

In this example, transaction T2 locks data items A and B in shared mode to read them and then unlocks them. This simple protocol can lead to incorrect results if A and B are updated by another transaction between reads.

A locking protocol is a set of rules followed by all transactions while requesting and releasing locks. Locking protocols restrict the set of possible schedules.

Deadlock

Deadlock in DBMS is a situation where two or more transactions are unable to proceed because each is waiting for the other to release a lock on a resource, creating a cycle of dependencies.

Methods for Deadlock Handling

Deadlock Avoidance

Ensure that the system never enters a deadlock state by dynamically examining the resource-allocation state.

Methods:

  • Resource Allocation Graph (RAG): Detects cycles in a graph of transactions and resources.
  • Banker’s Algorithm: A safety algorithm that checks whether resources can be safely allocated without entering a deadlock.

Deadlock Prevention

Ensure that the system never enters a deadlock state by careful resource allocation.

Methods:

  • Wait-Die Scheme: Older transactions can wait for younger ones, but younger transactions must restart if they need resources held by older ones.
  • Wound-Wait Scheme: Older transactions can preempt younger ones, forcing them to restart.

Deadlock Detection

  • Allow the system to enter a deadlock state, detect it, and recover.

Methods:

  • Wait-for Graph: Construct a graph where transactions are nodes and edges represent waiting for resources. A cycle in this graph indicates a deadlock.

Deadlock Recovery

After detection, the system needs to recover from deadlock.

Methods:

  • Transaction Rollback: Rollback one or more transactions to break the deadlock.
  •  Abort Transactions: Abort one or more transactions to release resources.

Starvation

Starvation occurs when a transaction is perpetually delayed from accessing necessary resources because other transactions continually take precedence.

Example:

A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item. The same transaction is repeatedly rolled back due to deadlocks.

Concurrency control manager can be designed to prevent starvation.

Two-Phase Locking Protocol

The Two-Phase Locking Protocol ensures conflict-serializable schedules by dividing the process into two phases.

Phases:

1. Growing Phase:

  •  Transactions may obtain locks.
  • Transactions may not release locks. 

2. Shrinking Phase:

  • Transactions may release locks.
  • Transactions may not obtain locks

Key Points:

  • Ensures serializability: Transactions can be serialized in the order of their lock points (the point where a transaction acquired its final lock).
  • Two-phase locking does not ensure freedom from deadlocks.
  • Cascading roll-back is possible. To avoid this, use the Strict Two-Phase
  • Locking protocol, where transactions must hold all exclusive locks until they commit or abort.
  • Rigorous Two-Phase Locking is even stricter: all locks are held until commit or abort, allowing transactions to be serialized in the order they commit.

Lock Conversions

First Phase: (Growing Phase)

  • Can acquire a Shared Lock (lock-S) on an item.
  • Can acquire an Exclusive Lock (lock-X) on an item.
  • Can convert a Shared Lock (lock-S) to an Exclusive Lock (lock-X) (Upgrade).

Second Phase: (Shrinking Phase)

  • Can release a Shared Lock (lock-S).
  • Can release an Exclusive Lock (lock-X).
  • Can convert an Exclusive Lock (lock-X) to a Shared Lock (lock-S) (Downgrade)

Lock Manager

  • Role: A separate process managing lock and unlock requests from transactions.
  • Function: Sends lock grant messages or requests a transaction to roll back if deadlocked.
  • Waiting: Transactions wait until their lock request is answered.
  • Lock Table: A data structure maintained by the lock manager, recording granted locks and pending requests.
  • In-Memory Hash Table: Usually used for the lock table, indexed by the name of the data item being locked.

Graph- based Protocol

Tree Protocol:

  • Only exclusive locks are allowed.
  • Data items may be unlocked at any time.

Benefits

  • Ensures conflict serializability.
  •  No deadlocks.
  • Early unlocking:
    • Shorter waits.
    • More concurrency.
    • No rollbacks needed (but cascading rollbacks can happen).

Drawbacks

  • May lock unused items:
    • More locking overhead.
    • More waiting time.
    • Less concurrency.

Schedules Compatibility

  • Some schedules not possible under two-phase locking are possible under tree protocol and vice versa.

Timestamp Based Protocol

Definition

The Timestamp Ordering Protocol is used to order transactions based on their timestamps. Transactions are processed in the order they are created, which is in ascending order of their timestamps.

Basic Timestamp ordering protocol works as follows:

1. Check the following condition whenever a transaction Ti issues a Read (X) operation:

  • If W_TS(X) >TS(Ti) then the operation is rejected.
  • If W_TS(X) <= TS(Ti) then the operation is executed.
  • Timestamps of all the data items are updated.

2. Check the following condition whenever a transaction Ti issues a Write(X) operation:

  • If TS(Ti) < R_TS(X) then the operation is rejected.
  • If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled back otherwise the operation is executed.

Where,

TS(TI) denotes the timestamp of the transaction Ti.

R_TS(X) denotes the Read time-stamp of data-item X.

W_TS(X) denotes the Write time-stamp of data-item X.

Validation Based Protocol

Overview

  • Used in DBMS to avoid concurrency issues in transactions.
  • Called optimistic due to the assumption of minimal interference among transactions.
  • No concurrency checking during transaction execution; checks are done at the end.

Phases of the Protocol

Read Phase:

  • Transaction reads values of committed data items.
  • Updates are applied to local copies, not directly to the database.

Validation Phase:

  • At the end of the transaction, checks ensure updates do not violate serializability.
  • If no violation, the transaction is committed; otherwise, it is restarted.

Write Phase:

  • If validation is successful, updates are applied to the database.
  • If validation fails, updates are discarded, and the transaction is slowed down or restarted.

Time-Stamps for Validation

  • Start(Ti): When Ti starts execution.
  • Validation(Ti): When Ti finishes the read phase and starts the validation phase.
  • Finish(Ti): When Ti completes all write operations in the write phase.

Validation Conditions

For Ti to pass validation, one of the following conditions must hold for all Tj:

  1. Finish(Tj) < Start(Ti): Tj completes write phase before Ti starts execution.
  2. Write Phase After: Ti's write phase begins after Tj completes, and Ti's read_set is disjoint with Tj's write_set.
  3. Read Phase Complete: Tj completes its read phase before Ti, and both read_set and write_set of Ti are disjoint with the write_set of Tj

Schedule Produced by Validation

FAQs About Topic
Concurrency control is a database management system (DBMS) concept that is used to address the problem of concurrent access to the database by multiple transactions.
The main types of locks are: Shared lock (s-lock): Allows many transactions to read a data item without modifying it. Exclusive Lock (X-Lock): Allows a transaction to read and modify a data element. No other transaction can access the data item while it is exclusively locked.
A deadlock occurs when two or more transactions wait for each other to release locks, creating a cycle of interdependence in which none of the transactions can advance. Deadlocks can block the execution of the transactions indefinitely.