How to solve deadlock in multiple mutexes

Question

I have a code that required to lock multiple mutexes.

void AttackAoeRequest(Player* attacker, int range)
{
    std::lock_guard<std::mutex> lk_attacker(attacker->mtx);

    if (attacker->isInVehicle)
    {
        return;
    }

    //there are a lot of code that need to check before the loop, and these code need to access attacker properties.

    //s_map is the global map class that contains all player in the map.
    for (Player* defender : s_map.GetAllPlayers())
    {
        if (attacker == defender) continue;
        std::lock_guard<std::mutex> lk_defender(defender->mtx);
        if (GetDistance(attacker->position, defender->position) <= 5)
        {
            printf("%d attack %d damage : %d\n", attacker->id, defender->id
                , attacker->attackUpgrade - defender->defenseUpgrade);
        }
    }
}

There is a deadlock occured when the attacker is the defender as the same time. e.g.

//playerA and playerB are in the global map class.
std::thread threadA = std::thread(AttackAoeRequest, &playerA, 5);
std::thread threadB = std::thread(AttackAoeRequest, &playerB, 5);

UPDATE

Actually the threadA, threadB illustrate which situation the cause the deadlock. AttackAoeRequest is calling from a multithread networking. The networking is going to handle messages from client and call AttackAoeRequest. There are might be a situation that clientA(playerA) and clientB(playerB) attack each others.

As the code described. There is a situation the player might be the attacker and defender in the same times, and this cause the deadlock. I had searched about std::lock to lock multiple mutexes in same time, but in this case the mutex aren't lock in the same time.

Answer 1

Presumably who is "attacker" and who is "defender" is very fluid, and so you are getting opposite locking order issues.

One defense against deadlocks is to write the code so that it avoids holding multiple locks at the same time. Or, going the other way, make the locking more coarse-grained so that a single lock covers all the objects.

If you have to lock an attacker and defender, you could have the code do it always in the same order. For instance, by address. The object with the lower address in memory is locked first, then the higher one. Acquire both locks this way, and then execute the all the code that has to work with both of them.

You could have some scoped lock for this which takes two objects. Make a template class supporting lock_double_guard<std::mutex> dbl_lk(attacker->mtx, defender->mtx); which puts the two objects in sorted order, and locks them in that order.

In C and C++, pointer to distinct objects may not be compared other than for exact equality, but being able to do ptrObj1 < ptrObj2 is a common extension. If that makes you nervous, you could just assign an unsigned integer serial number to each object which is incremented whenever a new object is made. The object with a lower serial number is locked first.

Answer 2

There is no universal answer to your question. You will have to evaluate what makes most sense in your design and possibly redesign your code. Here are a few avenues to explore:

• Avoid locking in the first place. Use atomics and lock-free techniques to work with player structures. This is not always easy or even possible to do, but may provide good performance.

• Make locking more coarse grained. For example, don't lock individual players, instead lock all players with a single lock. This, obviously, limits parallelism, but this may not be an issue in your code at a large scale.

• Avoid locking multiple players at the same time. For example, complete all you need to do with attacker in AttackAoeRequest, release lk_attacker and then proceed to iterate over defenders. Copy/cache the necessary data from attacker if you have to to avoid having to access attacker during iteration. Your design should allow that some of the cached data will become stale during iteration, if another thread modifies attacker while you're iterating.

• Introduce asynchronicity or retries. For example, try locking the defender opportunistically, using try_lock. If it fails, postpone processing that player and go on with the rest. After you've completed the iteration, release all locks and retry the whole operation on the leftover defenders a bit later. Hopefully, by that time other threads will have completed their work with the defenders and released their locks. You may need to redo some work on the attacker on the second retry, or reuse the previously cached data.

• Separate players processing to different threads. Or, more generally make sure that a given player is never accessed by multiple threads concurrently. Use message passing between threads to implement interaction between players. The message passing mechanism does not need to lock any players, and in fact, locking the players should not be necessary at all. This will also introduce some asynchronicity in the sense that the effects of AttackAoeRequest may be applied to defenders with a delay - when the corresponding thread processes damage notifications from the attacker.

I'm sure there are other ideas as well.