~/problems / Locks / Deadlock and lock ordering

Deadlock-free bank transfers

easy ~15 min

Implement a thread-safe Bank:

bank = Bank([100, 50, 0])      # balances of accounts 0, 1, 2
bank.transfer(0, 2, 30)        # True: moved 30 from account 0 to 2
bank.transfer(1, 0, 80)        # False: account 1 only has 50, nothing changes
bank.balance(2)                # 30

Rules:

  • transfer(src, dst, amount) returns False (and changes nothing) if src == dst, if amount <= 0, or if src has less than amount.
  • Use one lock per account, not one global lock. Transfers between unrelated accounts must be able to run at the same time.
  • It must never deadlock, even when a → b and b → a transfers run concurrently.
  • Bank(balances, work=None): if work is given, call work() while holding both locks during a successful transfer. The tests use it to simulate slow operations.

Constraints: src, dst and the account passed to balance are always valid account indices; balances and amounts are non-negative integers.

Show hint

A deadlock needs two transfers that each hold one lock and wait for the other's. If every transfer took its two locks in the same agreed order, could that happen?

Topic: Deadlock and lock ordering. The four conditions and how to break one.

0:00
Ctrl ' run · Ctrl ↵ submit
esc