Order matters

Deadlocks can be notoriously difficult to track down because they can be very timing-dependent, making them hard to reproduce on demand. The most common cause of these types of deadlocks is when more than one thread tries to grab more than one mutex at the same time.

Consider the following function which locks the src account and then later locks the dst account.

transfer_status transfer(Account& src, Account& dst, unsigned amount) {
    std::lock_guard lsrc(src.mtx);
    if (amount <= src.balance) {
        std::lock_guard ldst(dst.mtx);
        src.balance -= amount;
        dst.balance += amount;
        return transfer_status::complete;
     } else {
        return transfer_status::failed;
    }
}

This function might work for decades before you run into a situation where different threads are simultaneously attempting to transfer money in opposite directions.

    Account alice;
    Account bob;

    std::thread t1([] {
        transfer(alice, bob, 100);
    });
    std::thread t2([] {
        transfer(bob, alice, 5);
    });

If thread t1 happens to be checking Alice's balance at the same time that thread t2 is checking Bob's balance, this will deadlock. The thread t1 will be waiting for t2 to release bob.mtx while, at the same time, t2 will be waiting for t1 to release alice.mtx. They will each be waiting for the other.

The same scenario can even happen across more than two threads:

    std::thread t1([] { transfer(rock,     paper,    10); });
    std::thread t2([] { transfer(paper,    scissors, 10); });
    std::thread t3([] { transfer(scissors, rock,     10); });

The most straightforward fix is to have transfer acquire both locks simultaneously using scoped_lock(...):

transfer_status transfer(Account& src, Account& dst, unsigned amount) {
    std::scoped_lock lboth(src.mtx, dst.mtx);
    if (amount <= src.balance) {
        src.balance -= amount;
        dst.balance += amount;
        return transfer_status::complete;
    } else {
        return transfer_status::failed;
    }
}

The cost, here, is that now the dst object is locked for slightly longer. In the above code, it is not much longer.

If the computation required to check the src account's balance is more substantial, it may be beneficial to keep dst unlocked while that happens. In that case, one would have to rework the function to ensure that only one object is locked at a time.

transfer_status transfer(Account& src, Account& dst, unsigned amount) {
    { // scope for holding src.mtx
        std::lock_guard lsrc(src.mtx);
        if (amount <= src.calculate_balance_in_complicated_manner()) {
            src.balance -= amount;
        } else {
            return transfer_status::failed;
        }
    } // release src.mtx

    std::lock_guard ldst(src.mtx);
    dst.balance += amount;
    return transfer_status::complete;
}

It's not just mutexes that cause these kinds of deadlocks. You can do the same with almost any "stop and wait for something else to happen" action.

Packages like lock_align from Eigenstate Solutions can help you find errors like this that might otherwise lurk in your code for years waiting to pounce.