Reproduce and Diagnose Deadlock; Fix Using Lock Ordering

Circular Waits

Deadlock needs four conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait. In practice you diagnose it by finding a cycle in the wait-for graph: A waits for B's lock, B waits for C, C waits for A.

Lock Ordering Prevention

Impose a global order on mutex acquisition:

• Assign each lock an integer rank
• A thread may only acquire higher ranks while holding lower ones
• Never lock L2 then L1 if rank(L1) < rank(L2)

For example, threads locking account_mutex before log_mutex never deadlock with threads following the same order, even when transferring funds and logging.

Why This Matters in Production

The dining philosophers deadlock Dijkstra formalized in 1965 has a very real modern descendant: database engines like MySQL's InnoDB detect exactly this kind of lock-ordering cycle at runtime and kill one transaction to break it, because the alternative is an indefinite hang. The global lock-ordering fix you implement here is the same discipline the Linux kernel's lockdep validator enforces to catch AB-BA deadlocks before they ship.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will reproduce a two-thread deadlock, capture stack traces or logs, then fix it with ordered locking. The task asks you to document the cycle before and after the fix so the prevention strategy is explicit.