Deadlock: Explanation, Prevention, Detection, and Starvation

1. What is Deadlock?

Deadlock is a condition in a database system (or operating system) where no process proceeds for execution and each process waits for resources that have been acquired by other processes. In other words, a set of transactions are permanently blocked, each waiting for another to release a lock, and none can proceed.

"Deadlock is a condition where no process proceeds for execution and each waits for resources that have been acquired by the other processes."

Example of Deadlock

Consider two transactions T1 and T2, and two data items X and Y:

• T1 holds X and waits for Y.
• T2 holds Y and waits for X.
• Neither can proceed. This is a deadlock.

2. Deadlock Prevention Protocols

Deadlock prevention protocols ensure that the system never enters a deadlock state. Several schemes have been proposed, many using the concept of transaction timestamps.

"A transaction timestamp is a unique identifier assigned to each transaction."

a) Wait-Die Scheme (Non-Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older (smaller timestamp) than Tj, Ti is allowed to wait.
  • If Ti is younger (larger timestamp) than Tj, Ti dies (is rolled back and restarted).
• Older transactions wait; younger transactions are aborted.

Rule: Wait or Die

If TS(Ti) < TS(Tj)  --> Ti waits
If TS(Ti) > TS(Tj)  --> Ti dies (aborts)

b) Wound-Wait Scheme (Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older than Tj, Ti wounds (preempts/aborts) Tj.
  • If Ti is younger than Tj, Ti waits.
• Older transactions preempt younger ones; younger transactions wait.

Rule: Wound or Wait

If TS(Ti) < TS(Tj)  --> Ti wounds Tj (Tj aborts)
If TS(Ti) > TS(Tj)  --> Ti waits

c) Timeout-Based Scheme

"If a transaction waits for a period longer than a system-defined timeout period, the system assumes that the transaction may be deadlocked and aborts it -- regardless of whether a deadlock actually exists."

• Simple and practical due to low overhead.
• A transaction waiting beyond the timeout limit is automatically aborted and restarted.
• Limitation: May abort transactions that are not actually deadlocked (false positives).

Comparison Table

3. Deadlock Detection

"An alternative approach to deal with deadlock is deadlock detection, where the system checks if a state of deadlock actually exists."

When deadlock prevention is not used, the system must detect and recover from deadlocks.

How Deadlock Detection Works

The system maintains a Wait-For Graph (WFG):

• Nodes represent transactions.
• A directed edge Ti --> Tj means Ti is waiting for a resource held by Tj.
• A deadlock exists if and only if there is a cycle in the Wait-For Graph.

Example:

T1 --> T2 --> T3 --> T1   (Cycle detected = Deadlock!)

Detection Algorithm Steps

1. Build the Wait-For Graph from current lock and wait information.
2. Periodically invoke a cycle-detection algorithm.
3. If a cycle is found, select a victim transaction (usually the youngest or least-cost transaction).
4. Abort (rollback) the victim transaction to break the cycle.
5. Release all locks held by the victim and restart it later.

When to Invoke Detection

• After every lock request (high overhead, fast detection).
• Periodically at fixed time intervals (lower overhead, delayed detection).

"This solution is attractive if different transactions will rarely access the same items at the same time."

4. Starvation

"Starvation is a condition where process with higher priorities continuously uses the resources preventing low priority process to acquire the resources."

Starvation occurs when a transaction is indefinitely delayed because other transactions (usually of higher priority) continuously acquire the resources it needs. Unlike deadlock, in starvation some processes do proceed -- just not the starved one.

Difference Between Deadlock and Starvation

How Starvation Occurs in Deadlock Recovery

When the system repeatedly selects the same transaction as victim during deadlock recovery, that transaction is continuously rolled back and never completes -- this is starvation.

Prevention of Starvation

• Aging: Gradually increase the priority of a waiting transaction over time so it eventually

Data Independence and Three-Schema Architecture

Data Independence

Data independence is the capacity to change the schema at one level of a database system without having to change the schema at the next higher level.

There are two types of data independence:

1. Logical Data Independence

It is the capacity to change the conceptual schema without having to change the external schemas or application programs. For example, we may add new entity types, change constraints, or reduce the database. Only the view definition and mappings need to be updated; the external/user views remain unaffected.

2. Physical Data Independence

It is the capacity to change the internal schema without having to change the conceptual schema (and hence the external schemas also need not change). Changes to the internal schema may be needed because physical files were reorganized or storage structures were modified. As long as the same data remains in the database, the conceptual schema should not need to change.

Three-Schema Architecture

The goal of the three-schema architecture is to separate user applications from the physical database, thereby achieving data independence and data abstraction.

The three schemas are only descriptions of data; the actual data is stored at the physical level only. Requests and results are transformed between levels through a process called mappings.

External Users
      |
  [External Level]  -- External Views (View 1, View 2, ...)
      |
  External/Conceptual Mapping
      |
  [Conceptual Level] -- Conceptual Schema
      |
  Conceptual/Internal Mapping
      |
  [Internal Level]  -- Internal Schema
      |
  Stored Database

Level 1: External Level (View Level)

• The highest level of abstraction.
• Describes the part of the database that a particular user group is interested in.
• Each user group has its own external view (also called a subschema).
• Hides the rest of the database from that user group.
• Defined using View Definition Language (VDL).

Level 2: Conceptual Level

• Describes what data is stored in the database and the relationships among the data for the entire organization.
• Hides the details of physical storage structures.
• Represents the logical structure of the whole database (entities, attributes, constraints, relationships).
• Defined using Data Definition Language (DDL).

Level 3: Internal Level (Physical Level)

• The lowest level of abstraction.
• Describes how data is physically stored on storage media (file organization, indexing, access paths, record formats, etc.).
• Defined using Storage Definition Language (SDL).

Summary Table

Note: Most DBMSs do not completely and explicitly separate the three levels, but they support the three-schema architecture to some extent.