Deadlock by lock ordering: the guarantee Rust does not give you

Settle a batch of account-to-account transfers in parallel and return the final balances.

pub fn settle_transfers(
    balances: Vec<i64>,
    transfers: Vec<(usize, usize, i64)>,
    workers: usize,
) -> Vec<i64>

Accounts are a Vec<Mutex<i64>> inside an Arc — one lock per account, not one lock for the ledger. Each transfer (from, to, amount) must hold both accounts’ locks while it moves the money, because a half-applied transfer is exactly the invariant violation locks exist to prevent.

Split the transfers across workers threads. Balances may go negative; overdrafts are allowed. Treat workers == 0 as 1. The grader passes tens of thousands of transfers in some cases.

This problem will hang before it works. That is the curriculum.

Rust eliminates data races. It does not eliminate deadlocks.

This is the honest centre of “fearless concurrency”. The Send/Sync system makes data races — two unsynchronised accesses, one of them a write — impossible in safe code, completely, at compile time. That is a genuine and rare achievement.

Deadlock is a different failure. Every individual access here is perfectly synchronised. Every lock is released correctly by its guard. Nothing is racing. The program is simply waiting, forever, and no type system in any production language catches it.

Watch it happen

The starter locks from, then to. Now run two threads:

thread A: transfer 0 -> 1     thread B: transfer 1 -> 0
  lock(account 0)   OK          lock(account 1)   OK
  lock(account 1)   ...waits     lock(account 0)   ...waits

A holds 0 and wants 1. B holds 1 and wants 0. Neither will ever release what it has, because releasing happens after acquiring. This is the textbook circular wait, and with 10,000 crossing transfers it happens within milliseconds.

The fix: a global lock order

Deadlock needs a cycle in the “who waits for whom” graph. Remove the possibility of a cycle and you remove deadlock — and the way to do that is to impose a total order on the locks and require that every thread acquires them in that order.

Here the accounts are indexed, so the order is free: always lock the lower index first.

let (low, high) = if from < to { (from, to) } else { (to, from) };
let mut lo = accounts[low].lock()?;
let mut hi = accounts[high].lock()?;

Both threads in the example now try lock(0) first. One wins, does its work, releases; the other proceeds. No cycle is constructible, because “waits for” now always points from a lower index to a higher one and a cycle would have to come back down.

Then be careful applying the amount: low is not necessarily from. Which guard gets debited depends on the original direction, not on the lock order.

The sting in the tail

There is a hidden test with from == to.

A correctly-ordered solution self-deadlocks on it, because low == high and the thread locks the same mutex twice. std::sync::Mutex is not reentrant — the docs say the behaviour is unspecified, and in practice the thread waits for a lock it is already holding, forever.

A self-transfer is a no-op, so skip it. But notice what happened: you fixed the deadlock in general and introduced a new one in a degenerate case that a quick test would never cover. That is very much what real concurrency debugging is like.

No lint catches any of this

Nothing in rustc or clippy has an opinion about lock ordering. There is no analysis, no warning, no #[lock_order] attribute. This problem’s starter compiles clean and passes clippy -D warnings, and then hangs.

Nor is it a std limitation you can buy your way out of. parking_lot and crossbeam do not fix lock ordering either — parking_lot ships an optional deadlock_detection feature that will tell you after the fact, which is genuinely useful and is still not prevention. This is a class of bug where tooling does not help you and discipline does. Track 15 closes with an honest inventory of what this grader can and cannot see; this problem is the first entry.

If your submission times out

It is wedged. Ask: do two of my threads ever want the same two locks in opposite orders? And: can one thread ever ask for the same lock twice?