Deadlock Illustrated: Two Programmers Stuck Over a Meeting Room

Story Introduction

Two programmers, Xiao Ming and Xiao Gang, each occupy one meeting room (A and B) on Monday morning and both need the other room, leading to a standstill where neither releases their current room.

What Is a Deadlock?

A deadlock occurs when two or more processes/threads hold resources the others need and wait indefinitely for each other, forming a circular wait.

Four Necessary Conditions

1. Mutual Exclusion

Only one process can use a resource at a time (e.g., a meeting room).

2. Hold and Wait

A process holds one resource while requesting another (Xiao Ming holds A and wants B).

3. No Preemption

Allocated resources cannot be forcibly taken away until the holding process releases them.

4. Circular Wait

Processes form a cycle of waiting (A waits for B, B waits for A).

Real‑World Analogies

Four‑way traffic jam: each direction waits for the next.

Couple refusing to apologize first, leading to a prolonged cold war.

ABO blood‑type matching can create a circular wait in extreme cases.

Code Example of a Deadlock

import threading
import time

# Two locks
lock_a = threading.Lock()
lock_b = threading.Lock()

def task1():
    print("Task1: trying to acquire lock A...")
    lock_a.acquire()
    print("Task1: acquired lock A!")
    time.sleep(0.1)
    print("Task1: trying to acquire lock B...")
    lock_b.acquire()  # blocks here
    print("Task1: acquired lock B!")
    lock_b.release()
    lock_a.release()

def task2():
    print("Task2: trying to acquire lock B...")
    lock_b.acquire()
    print("Task2: acquired lock B!")
    time.sleep(0.1)
    print("Task2: trying to acquire lock A...")
    lock_a.acquire()  # blocks here
    print("Task2: acquired lock A!")
    lock_a.release()
    lock_b.release()

# Start two threads – will deadlock
threading.Thread(target=task1).start()
threading.Thread(target=task2).start()

Deadlock Handling Strategies

Strategy 1 – Prevention (break a condition)

Acquire all required locks atomically so that either all are obtained or none.

def task():
    # acquire both locks together
    with lock_a:
        with lock_b:
            pass  # work

Strategy 2 – Avoidance (banker’s algorithm)

Before granting resources, simulate the allocation to ensure it will not lead to a circular wait; reject the request if it would.

Strategy 3 – Detection & Recovery

Periodically examine the resource‑allocation graph for cycles; if a cycle is found, forcibly release a lock, roll back a transaction, or kill a process.

Strategy 4 – Ignoring (ostrich algorithm)

If deadlocks are rare and recovery is costly, simply restart the system, which resolves most cases.

Classic Dining‑Philosophers Example

Five philosophers sit at a round table with a chopstick between each pair. If every philosopher picks up the left chopstick first, they all wait for the right one, causing deadlock.

Limit the number of concurrent eaters to four.

Enforce a global ordering (e.g., always pick the lower‑indexed chopstick first).

Odd‑even strategy: odd philosophers pick left then right, even philosophers pick right then left.

def philosopher(i):
    if i % 2 == 0:  # even – left then right
        left = chopsticks[i]
        right = chopsticks[(i + 1) % 5]
    else:           # odd – right then left
        right = chopsticks[i]
        left = chopsticks[(i + 1) % 5]
    with left:
        with right:
            eat()

Best Practices to Avoid Deadlock

Maintain a consistent lock acquisition order across the codebase.

Acquire all needed locks in a single step when possible.

Limit the number of locks held simultaneously.

Use lock time‑outs and handle failures gracefully.

Key Takeaways

Deadlock = mutual exclusion + hold‑and‑wait + no preemption + circular wait.

Breaking any one condition prevents deadlock.

In practice, combine fixed lock ordering with time‑outs.

Regularly monitor resource graphs and be prepared to intervene.