Page 9: Deadlock Handling

Prevention vs Detection

Like preventing car accidents vs having good insurance.

Deadlock Prevention

Method 1: Ordering

• Acquire all locks at once, OR

• Always request locks in same order (like tree protocol)

Method 2: Timestamps

Wait-Die (Non-preemptive):

• Older transaction waits for younger

• Younger dies if requests from older

• Example: T14 (TS=5) vs T15 (TS=10)

  • T14 requests from T15 → T14 waits

  • T15 requests from T14 → T15 dies

Wound-Wait (Preemptive):

• Older transaction wounds younger

• Younger waits for older

• Example: Same T14 vs T15

  • T14 requests from T15 → T15 gets wounded

  • T15 requests from T14 → T15 waits

Method 3: Timeout

Wait for lock up to X seconds, then rollback.

• ✅ Simple to implement

• ❌ Hard to choose right timeout value

Deadlock Detection

Wait-For Graph

Directed graph where Ti → Tj means Ti waits for Tj.

Example:

CopyT17 → T18
T17 → T19  
T19 → T18
T18 → T20
T20 → T19  (this creates cycle!)

Cycle Detection: T18 → T20 → T19 → T18 = DEADLOCK!

Recovery Steps

1. Victim Selection: Choose cheapest transaction to rollback

2. Rollback: Complete abort or partial rollback

3. Starvation Prevention: Don't always pick same victim