Deadlocks: wait-for graph, wait-die, wound-wait, starvation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which 2PL variant is deadlock-free? from Lesson 6.6.3
2. How do you test a directed graph for a cycle? from Lesson 6.4.1
3. When is a transaction's lock point? from Lesson 6.6.2

1 · The Hook

T1 holds A and waits for B; T2 holds B and waits for A. Neither will ever move: a deadlock. A DBMS either lets deadlocks happen and detects them (with a wait-for graph), or prevents them using transaction ages (wait-die, wound-wait). GATE gives timestamps and asks who waits and who is rolled back.

2 · Predict First

T1 (older, timestamp 5) requests an item held by T2 (younger, timestamp 10). Under wait-die, does T1 wait or die? Under wound-wait?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Wait-die: the older T1 waits. Wound-wait: the older T1 wounds T2 (T2 is rolled back) and takes the item.

Deadlock

A set of transactions is deadlocked if each waits for a lock held by another in the set. With 2PL (except conservative), deadlocks can occur.

Detection: wait-for graph

• Vertex per active transaction; edge Ti → Tj if Ti waits for a lock held by Tj.
• Deadlock ⇔ the wait-for graph has a cycle.
• The DBMS checks periodically, picks a victim in the cycle (e.g. the one with least work done, or youngest), aborts it, and frees its locks.

Prevention with timestamps

Each transaction gets a timestamp TS when it starts; smaller TS = older. When Ti requests an item held by Tj:

• In both, a rolled-back transaction is restarted with its original timestamp, so it eventually becomes the oldest and gets through: no starvation.
• In wait-die, only younger transactions wait for nothing; older ones wait for younger: waits go old → young. In wound-wait, waits go young → old. Either way, waits all point one direction in age, so no cycle can form.
• Wait-die may roll back the same young transaction several times; wound-wait tends to cause fewer rollbacks.

Other approaches

• Timeout: if a wait lasts too long, abort. Simple; may abort non-deadlocked transactions.
• No-waiting: if a lock is unavailable, abort immediately and restart later.
• Ordering of resources: all transactions lock items in a fixed global order (a form of prevention).

Starvation

A transaction waits indefinitely (or is repeatedly chosen as victim) while others proceed. Fixes: keep the original timestamp on restart, favour older transactions, FIFO lock queues.

4 · Visual

Wait-for graph: T1 → T2 → T3 → T1 is a deadlock; T4 waiting for T5 is not.

5 · Worked Examples

Example 1 Easy

TS(T1) = 3, TS(T2) = 7. T2 requests an item held by T1. Wait-die? Wound-wait?

Solution

T2 is younger. Wait-die: T2 dies. Wound-wait: T2 waits.

Example 2 Medium

Wait-for edges: T1 → T2, T2 → T4, T3 → T1, T4 → T3. Deadlock? Which transactions are involved?

Solution

T1 → T2 → T4 → T3 → T1: a cycle of all four.

Example 3 GATE

Wound-wait. TS(T1) = 10, TS(T2) = 20, TS(T3) = 30. T3 holds A, T2 holds B. T1 requests A; T3 requests B. What happens to each request?

Solution

T1 (older) requests A held by T3 (younger): T1 wounds T3 (T3 rolled back, releasing A). T3's request for B is gone (T3 was rolled back); had it been made first, T3 (younger) would wait for T2.

8 · Connect the Dots

Chapter 6.6 is complete: locks, 2PL and its variants, and deadlock handling. Next: the Chapters 6.5–6.6 Lock-in, then a lock-free approach: timestamp ordering, which can never deadlock.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Wait-die

Wait-die: an older transaction requests an item held by a younger one. It:

1. (A) waits
2. (B) dies
3. (C) takes the lock immediately
4. (D) wounds the younger

Q2 · MCQ · 1 mark(s) — Wound-wait

Wound-wait: a younger transaction requests an item held by an older one. It:

1. (A) dies
2. (B) is granted the lock
3. (C) waits
4. (D) wounds the older

Q3 · MCQ · 2 mark(s) — Detection

Wait-for edges: T1 → T2, T2 → T3, T3 → T4. Is there a deadlock?

1. (A) Yes, all four
2. (B) Yes, T1 and T2 only
3. (C) No
4. (D) Cannot tell

Q4 · MSQ · 2 mark(s) — Starvation

Which practices help avoid starvation in deadlock handling?

1. (A) FIFO lock queues
2. (B) Always choosing the oldest transaction as the victim
3. (C) Favouring older transactions
4. (D) Restarting a rolled-back transaction with its original timestamp

Q5 · NAT · 1 mark(s) — Timestamps

Under wait-die with TS(T1) = 4, TS(T2) = 9, TS(T3) = 2: T2 requests an item held by T3, and T1 requests an item held by T2. How many of these two requests lead to a rollback?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

deadlockwait-for graphvictim selectionwait-diewound-waittransaction timestamp (age)starvationtimeout