Deadlock handling in databases in DBMS Theory - Full Explanation

Introduction

Imagine two people trying to pass through a narrow hallway from opposite ends, but each waits for the other to move first. In databases, a similar problem happens when two or more transactions wait forever for resources locked by each other. Deadlock handling solves this problem to keep the database running smoothly.

Explanation

What is a Deadlock

A deadlock occurs when two or more transactions hold locks on resources and each waits for the other to release their lock. This creates a cycle of waiting with no transaction able to proceed. The database must detect and resolve this to avoid freezing.

Deadlock is a cycle of transactions waiting on each other’s locked resources, causing a standstill.

Deadlock Detection

The database regularly checks for cycles in the waiting transactions, often using a wait-for graph. If a cycle is found, it means a deadlock exists. Detection helps the system know when to intervene and break the deadlock.

Deadlock detection finds cycles of waiting transactions to identify deadlocks.

Deadlock Resolution

Once detected, the database chooses one transaction as a victim to roll back or abort. This frees the locked resources and allows other transactions to continue. The choice is usually based on factors like transaction age or cost to roll back.

Deadlock resolution breaks the cycle by aborting one transaction to free resources.

Deadlock Prevention

Some systems prevent deadlocks by ordering resource requests or using timeouts. For example, transactions may request all needed locks at once or wait only a limited time before aborting. Prevention aims to avoid deadlocks before they happen.

Deadlock prevention avoids cycles by controlling how and when locks are requested.

Real World Analogy

Two drivers meet on a narrow bridge from opposite sides. Each waits for the other to back up first, so neither moves. A traffic officer arrives and asks one driver to reverse, letting the other pass and clearing the blockage.

Deadlock → Two drivers stuck waiting for each other on a narrow bridge

Deadlock Detection → Traffic officer noticing the blockage and identifying who is stuck

Deadlock Resolution → Traffic officer asking one driver to reverse to clear the bridge

Deadlock Prevention → Traffic rules that prevent two cars entering the bridge at the same time

Diagram

Diagram

┌───────────────┐       waits for       ┌───────────────┐
│ Transaction A │ ────────────────▶ │ Transaction B │
└───────────────┘                   └───────────────┘
       ▲                                   │
       │                                   ▼
┌───────────────┐       waits for       ┌───────────────┐
│ Transaction C │ ◀─────────────── │ Transaction D │
└───────────────┘                   └───────────────┘

Cycle detected: Transactions waiting in a loop causing deadlock.

This diagram shows transactions waiting on each other in a cycle, illustrating a deadlock situation.

Key Facts

Deadlock → A situation where transactions wait indefinitely for resources locked by each other.

Wait-for Graph → A graph representing transactions as nodes and waiting relationships as edges.

Deadlock Detection → The process of finding cycles in the wait-for graph to identify deadlocks.

Deadlock Resolution → Breaking a deadlock by aborting one or more transactions to free resources.

Deadlock Prevention → Techniques to avoid deadlocks by controlling lock acquisition order or timing.

Code Example

DBMS Theory

import sqlite3
import threading
import time

conn = sqlite3.connect(':memory:', check_same_thread=False)
cur = conn.cursor()
cur.execute('CREATE TABLE accounts (id INTEGER PRIMARY KEY, balance INTEGER)')
cur.execute('INSERT INTO accounts VALUES (1, 100)')
cur.execute('INSERT INTO accounts VALUES (2, 100)')
conn.commit()

lock = threading.Lock()

def transfer_a_to_b():
    with lock:
        cur.execute('BEGIN EXCLUSIVE')
        cur.execute('SELECT balance FROM accounts WHERE id=1')
        balance_a = cur.fetchone()[0]
        time.sleep(1)  # Simulate delay
        cur.execute('SELECT balance FROM accounts WHERE id=2')
        balance_b = cur.fetchone()[0]
        if balance_a >= 10:
            cur.execute('UPDATE accounts SET balance = balance - 10 WHERE id=1')
            cur.execute('UPDATE accounts SET balance = balance + 10 WHERE id=2')
        conn.commit()


def transfer_b_to_a():
    with lock:
        cur.execute('BEGIN EXCLUSIVE')
        cur.execute('SELECT balance FROM accounts WHERE id=2')
        balance_b = cur.fetchone()[0]
        time.sleep(1)  # Simulate delay
        cur.execute('SELECT balance FROM accounts WHERE id=1')
        balance_a = cur.fetchone()[0]
        if balance_b >= 10:
            cur.execute('UPDATE accounts SET balance = balance - 10 WHERE id=2')
            cur.execute('UPDATE accounts SET balance = balance + 10 WHERE id=1')
        conn.commit()

thread1 = threading.Thread(target=transfer_a_to_b)
thread2 = threading.Thread(target=transfer_b_to_a)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

cur.execute('SELECT * FROM accounts')
print(cur.fetchall())

Common Confusions

Deadlock is the same as a simple lock wait.

Deadlock is the same as a simple lock wait. Deadlock involves a cycle of waiting transactions, while a simple lock wait is just one transaction waiting for a resource.

Deadlock detection always happens instantly.

Deadlock detection always happens instantly. Deadlock detection runs periodically or when certain conditions occur; it is not continuous or instantaneous.

Aborting any transaction will resolve deadlocks equally well.

Aborting any transaction will resolve deadlocks equally well. Databases choose victims carefully based on cost or priority to minimize impact when resolving deadlocks.

Summary

Deadlocks happen when transactions wait forever for each other's locked resources, causing a standstill.

Databases detect deadlocks by finding cycles in waiting transactions and resolve them by aborting one transaction.

Prevention techniques control how locks are requested to avoid deadlocks before they occur.

Practice

1. What is a deadlock in a database system?

easy

A. A situation where two or more transactions wait indefinitely for each other to release locks

B. A method to speed up database queries

C. A backup process for database recovery

D. A type of database index

Solution

1. Step 1: Understand the concept of deadlock

   A deadlock occurs when transactions wait for resources locked by each other, causing a cycle of waiting.

2. Step 2: Identify the correct description

   Only a situation where two or more transactions wait indefinitely for each other to release locks describes this waiting cycle causing indefinite blocking.

3. Final Answer:

   A situation where two or more transactions wait indefinitely for each other to release locks -> Option A

4. Quick Check:

   Deadlock = indefinite waiting cycle [OK]

Hint: Deadlock means transactions stuck waiting on each other [OK]

Common Mistakes:

• Confusing deadlock with query optimization
• Thinking deadlock is a backup process
• Mixing deadlock with indexing

2. Which of the following is a common method to handle deadlocks in databases?

easy

A. Ignoring the deadlock and letting transactions wait

B. Deadlock detection and transaction rollback

C. Increasing the database size

D. Using more indexes

Solution

1. Step 1: Review deadlock handling methods

   Deadlock handling usually involves detecting the deadlock and aborting one transaction to break the cycle.

2. Step 2: Match the correct method

   Deadlock detection and transaction rollback correctly states deadlock detection and rollback, which is standard practice.

3. Final Answer:

   Deadlock detection and transaction rollback -> Option B

4. Quick Check:

   Deadlock handling = detect and rollback [OK]

Hint: Deadlocks are handled by detection and rollback [OK]

Common Mistakes:

• Thinking deadlocks can be ignored
• Believing increasing size fixes deadlocks
• Confusing indexing with deadlock handling

3. Consider two transactions T1 and T2. T1 holds a lock on resource A and waits for resource B. T2 holds a lock on resource B and waits for resource A. What will happen if the database uses deadlock detection?

medium

A. Both transactions will complete successfully without waiting

B. The transactions will wait forever causing a system crash

C. The database will automatically grant both resources to both transactions

D. The database will detect the deadlock and abort one transaction

Solution

1. Step 1: Analyze the resource waiting scenario

   T1 and T2 each hold one resource and wait for the other, creating a circular wait (deadlock).

2. Step 2: Understand deadlock detection response

   The database detects this cycle and aborts one transaction to break the deadlock.

3. Final Answer:

   The database will detect the deadlock and abort one transaction -> Option D

4. Quick Check:

   Deadlock detection aborts one transaction [OK]

Hint: Deadlock detection aborts one waiting transaction [OK]

Common Mistakes:

• Assuming both transactions finish without waiting
• Thinking system crashes always occur
• Believing resources are shared automatically

4. A database system uses timeout to handle deadlocks. A transaction waits for a lock for 10 seconds before aborting. What is the problem if the timeout is set too low?

medium

A. Transactions may abort unnecessarily even if no deadlock exists

B. Deadlocks will never be detected

C. The database will run out of memory

D. All transactions will complete faster

Solution

1. Step 1: Understand timeout-based deadlock handling

   Timeout aborts transactions waiting too long for locks, assuming deadlock.

2. Step 2: Analyze low timeout effect

   If timeout is too low, transactions may abort even when just waiting normally, causing unnecessary rollbacks.

3. Final Answer:

   Transactions may abort unnecessarily even if no deadlock exists -> Option A

4. Quick Check:

   Low timeout causes false aborts [OK]

Hint: Too low timeout causes false deadlock aborts [OK]

Common Mistakes:

• Thinking deadlocks won't be detected at all
• Assuming database memory is affected
• Believing all transactions speed up

5. In a database with multiple transactions, which strategy best reduces the chance of deadlocks?

hard

A. Allowing transactions to lock resources randomly

B. Increasing the number of concurrent transactions

C. Ensuring all transactions lock resources in the same order

D. Disabling deadlock detection

Solution

1. Step 1: Understand deadlock cause

   Deadlocks happen when transactions lock resources in different orders, causing circular waits.

2. Step 2: Identify prevention strategy

   Forcing all transactions to lock resources in the same order prevents cycles, reducing deadlocks.

3. Final Answer:

   Ensuring all transactions lock resources in the same order -> Option C

4. Quick Check:

   Same lock order prevents deadlocks [OK]

Hint: Lock resources in same order to avoid deadlocks [OK]

Common Mistakes:

• Thinking random locking reduces deadlocks
• Believing more transactions help
• Disabling detection solves deadlocks