Experiments and implementations · Intermediate

Reproducing deadlocks through lock ordering

Construct circular waiting with opposite lock orders, bound the demonstration with acquisition timeouts, and compare it with a consistent lock order.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Demonstrate the cycle without leaving a permanent hang
  2. Synchronize after each first acquisition
  3. A shared order removes this particular cycle
  4. A timeout does not roll back partial updates
  5. Report the scope of the successful order
  6. Ask Logeia about this articleCheck your understanding

Demonstrate the cycle without leaving a permanent hang

Two participants can each hold one lock while waiting for the other participant’s lock, creating a circular wait. A barrier aligns the stage at which both first locks are already held. The experiment then attempts the second acquisition with a short timeout rather than blocking forever. It therefore demonstrates an ownership pattern that would deadlock under unbounded acquisition, and the timeout that breaks that cycle in this particular run. Do not manipulate production locks or another process. Use Python threading with two experiment-owned threads and two locks only. An outer runner timeout remains useful for handling unexpected failures, but the program’s intended path already has bounded waits.

Synchronize after each first acquisition

Worker A takes left and worker B takes right before meeting at the barrier. Each retains its first lock while attempting the other. They cannot both immediately succeed. When at least one second acquisition times out and releases its first lock, the other may subsequently succeed. Do not require both workers to time out; the valid outcomes depend on scheduling after the first timeout. Assert at least one failed second acquisition. Release a successfully acquired second lock and always release the first lock in a finally block. Capture unexpected worker exceptions separately so broken coordination does not masquerade as the intended circular-wait result.

python
import threading
left, right = threading.Lock(), threading.Lock()
barrier = threading.Barrier(2, timeout=3)
results, errors = [], []
def reversed_order(first, second):
    try:
        with first:
            barrier.wait()
            acquired = second.acquire(timeout=0.2)
            results.append(acquired)
            if acquired:
                second.release()
    except BaseException as error:
        errors.append(repr(error))
workers = [threading.Thread(target=reversed_order, args=pair, daemon=True)
           for pair in ((left, right), (right, left))]
for t in workers: t.start()
for t in workers: t.join(3)
assert not errors and all(not t.is_alive() for t in workers)
assert len(results) == 2 and not all(results)
print('opposite order acquisition results', results)
completed = []
def ordered():
    with left:
        with right:
            completed.append(True)
workers = [threading.Thread(target=ordered, daemon=True) for _ in range(2)]
for t in workers: t.start()
for t in workers: t.join(3)
assert len(completed) == 2 and all(not t.is_alive() for t in workers)
print('consistent order completed', len(completed))

A shared order removes this particular cycle

In the second phase, both workers acquire left and then right. While one worker holds left, the other waits before acquiring any right lock. It cannot hold right while waiting for left, so this two-lock reversed-order cycle cannot form. The argument depends on every access path following the same order, including calls through helpers and callbacks. A function that looks locally correct can still participate in a larger cycle if it calls external code while holding a lock and that code acquires resources in a conflicting order. State the ordering rule over the relevant resource set and inspect all paths that can cross that ownership boundary.

A timeout does not roll back partial updates

Ending a wait does not automatically undo changes made while holding the first lock. If a real operation mutates shared state before the second acquisition, its failure path must preserve the relevant invariant. Releasing and immediately retrying can also lead to repeated collisions or livelock; catching an error and spinning through the same sequence is not a complete recovery design. This example deliberately modifies no application state before acquiring both resources, so releasing locks is sufficient cleanup. Revisit that boundary before adding business updates. A bounded demonstration of acquisition failure is different from a transaction mechanism that restores arbitrary effects after a timeout.

Report the scope of the successful order

A consistent order prevents the reversed two-lock cycle shown here, but does not guarantee fairness or a small waiting time. Long work inside a critical section can still delay the other participant. Stalled external I/O, cycles involving additional resources and cancellation behavior are outside this two-lock argument. Record the first phase’s acquisition outcomes and the second phase’s completion count. Do not demand two timeouts in the first phase, and do not conclude that every possible program deadlock has vanished because one ordered run succeeded. The strongest conclusion combines a stated ordering invariant with evidence that the tested paths followed it, while retaining the limits of the resource set being analyzed.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 18

Understand the systems behind the web · STEP 15

Choose a learning path