In a previous post I explained how mutexes work and the problem of race conditions.

In this post I introduce another common problem with mutexes, which is deadlocks. Deadlocks are situations when a program can’t make any progress because it is waiting for a mutex that will never be available. This might sound stupid, but it’s something that actually happens very often.

A naive example could be this:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <mutex>

std::mutex mutexA;
std::mutex mutexB;

void doSomething() {
std::lock_guard<std::mutex> gA(mutexA);
std::lock_guard<std::mutex> gB(mutexB);
}

void doSomethingElse() {
std::lock_guard<std::mutex> gB(mutexB);
std::lock_guard<std::mutex> gA(mutexA);
}

int main() {

t1.join();
t2.join();
}
``````

The example above will cause a deadlock. If you take a close look, you will find that two threads are being started:

### t1

• Locks mutexA
• Waits for 1 second
• Locks mutexB

### t2

• Locks mutexB
• Waits for 1 second
• Locks mutexA

The reason the program deadlocks is that after 1 second has passed, `t1` will try to grab `mutexB`, but won’t be able to do it, because it is being locked by `t2`. At the same time `t2` will try to grab `mutexA`, but will fail, because `t1` is holding that mutex. Both threads will wait forever for each other, so the program will never exit.

Although in this example, the problem is very obvious, when working on larger applications, it is not easy to spot problems like this.

## std::lock

One way to fix this problem is using `std::lock`:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <mutex>

std::mutex mutexA;
std::mutex mutexB;

void doSomething() {
std::lock(mutexA, mutexB);
}

void doSomethingElse() {
std::lock(mutexB, mutexA);
}

int main() {

t1.join();
t2.join();
}
``````

`std::lock` makes sure the mutexes are always locked in the same order (regardless of the order of the arguments), avoiding deadlocks this way. Even though we are using `std::lock` we still want to use `std::lock_guard` to make sure the mutexes are released at the end of the scope. The `std::adopt_lock` option allows us to use lock_guard on an already locked mutex.

This approach is very easy to implement when we are locking mutexes in the same function, but there are scenarios where this can’t be done. For example:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <mutex>

std::mutex mutexA;
std::mutex mutexB;

void doSomethingWithMutexA() {
std::lock_guard<std::mutex> gA(mutexA);
}

void doSomethingWithMutexB() {
std::lock_guard<std::mutex> gB(mutexB);
}

void doSomething() {
std::lock_guard<std::mutex> gA(mutexA);
doSomethingWithMutexB();
}

void doSomethingElse() {
std::lock_guard<std::mutex> gB(mutexB);
doSomethingWithMutexA();
}

int main() {

t1.join();
t2.join();
}
``````

In this case doSomething locks `mutexA` and then calls a function that needs to lock `mutexB`. Since the locking happens in two different functions, we can’t use `std::lock` in this scenario. Because there is another thread locking `mutexB` and then waiting for `mutexA`, the two threads block each other forever.

## Lock hierarchies

The issue shown above can, in some cases be mitigated by using lock hierarchies. A lock hierarchy consists of designing your application in a way that mutexes can only be locked in a specific order. This restriction might not be realistic for some applications, but in the cases where it applies, it helps us prevent deadlocks.

Before we start writing code, we can design a simple hierarchy for our application. In the example above, we have two mutexes. We can decide that we want `mutexA` to be lower in the hierarchy than `mutexB`.

The next step is to enforce this in code. The easiest way to do this is to create a mutex type that is aware of the hierarchy:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class HierarchicalMutex {
std::mutex theMutex;
int level;
int previousLevel;

// A thread_local variable is a global variable in the current thread

// Check if a mutex with a higher level has already been locked in this thread
void isLockValid() {
throw std::runtime_error("Higher level mutex already locked");
}
}

// When locking a mutex, update the global value on the thread and save the
// previousLevel, so we can restore it when the mutex in unlocked
void updateLevels() {
}

public:
// We use a explicit constructor, to force the user to set a level for the
// mutex
explicit HierarchicalMutex(int l) {
level = l;
previousLevel = 0;
}

// A user-defined mutex must implement `lock`, `unlock` and `try_lock`
void lock() {
isLockValid();
theMutex.lock();
updateLevels();
}

// Move thead level to the value of the mutex that was locked before
void unlock() {
theMutex.unlock();
}

// try_lock only locks the mutex if it is not currently locked. If it is locked
// it returns false. If it is not locked, it locks the mutex and returns true
bool try_lock() {
isLockValid();

if (!theMutex.try_lock()) {
return false
}

updateLevels();
return true;
}
}
``````

The class above will allow us to create a hierarchy of mutexes that will be enforced at runtime. To use it we have to define the levels in our hierarchy. We decided before, that we wanted `mutexA` to be lower than `mutexB`:

``````1
2
HierarchicalMutex mutexA(1000);
HierarchicalMutex mutexB(10000);
``````

The values `1000` and `10000` are arbitrary. It is usually a good idea to leave a gap between the mutex levels in case we want to add a mutex in the future, we don’t have to update the levels in all mutexes.

Let’s now rewrite our program using `HierarchicalMutex` and see what happens:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <mutex>

class HierarchicalMutex {
std::mutex theMutex;
int level;
int previousLevel;

// A thread_local variable is a global variable in the current thread

// Check if a mutex with a higher level has already been locked in this thread
void isLockValid() {
throw std::runtime_error("Higher level mutex already locked");
}
}

// When locking a mutex, update the global value on the thread and save the
// previousLevel, so we can restore it when the mutex in unlocked
void updateLevels() {
}

public:
// We use a explicit constructor, to force the user to set a level for the
// mutex
explicit HierarchicalMutex(int l) {
level = l;
previousLevel = 0;
}

// A user-defined mutex must implement `lock`, `unlock` and `try_lock`
void lock() {
isLockValid();
theMutex.lock();
updateLevels();
}

// Move thead level to the value of the mutex that was locked before
void unlock() {
theMutex.unlock();
}

// try_lock only locks the mutex if it is not currently locked. If it is locked
// it returns false. If it is not locked, it locks the mutex and returns true
bool try_lock() {
isLockValid();

if (!theMutex.try_lock()) {
return false;
}

updateLevels();
return true;
}
};

// Initialize thread level to 0

HierarchicalMutex mutexA(1000);
HierarchicalMutex mutexB(10000);

void doSomethingWithMutexA() {
std::lock_guard<HierarchicalMutex> gA(mutexA);
}

void doSomethingWithMutexB() {
std::lock_guard<HierarchicalMutex> gB(mutexB);
}

void doSomething() {
std::lock_guard<HierarchicalMutex> gA(mutexA);
doSomethingWithMutexB();
}

void doSomethingElse() {
std::lock_guard<HierarchicalMutex> gB(mutexB);
doSomethingWithMutexA();
}

int main() {

t1.join();
t2.join();
}
``````

The output of this program is:

``````1
2
3
terminate called after throwing an instance of 'std::runtime_error'
what():  Higher level mutex already locked
Aborted (core dumped)
``````

This time, instead of having the program stuck forever, the program will notice the violation of the lock hierarchy and quit. In a more complicated program you would probably want to take a look at the `core` generated from the crash to figure out what code let to it. To actually solve the deadlock, we would need to redesign the program, so it doesn’t violate the hierarchy.

## Conclusion

In this post I introduced two ways for avoiding deadlocks. There are many situations were these techniques won’t apply, but where it is possible, this might save you from some headaches. I’ll try to cover more concurrency techniques in future posts.