C++ Deadlocks

Introduction

In concurrent computing, a deadlock is a state in which each member of a group is waiting for another member, including itself, to take action, such as sending a message or more commonly releasing a lock. A lock is required when a concurrent application
will modify the shared memory, and a deadlock will likely happen if there are more than one lock in one situation, the situation was not treated carefully. The phenomenon of deadlock will be the program hangs forever and it is often very difficult to troubleshoot.

Since I have hardly implemented many C++ concurrent programs, I was bored and implemented a deadlock myself. In this blog post, I would like to show how a typical concurrent C++ program that modifies shared objects will cause program error, and how to use mutual exclusion and lock to modify shared objects in a thread-safe way.

Multithread Swap Implementation

Swap is commonly implemented to take the references or pointers to two objects and swap the information stored in them. The swap function is usually easy to implement and in a single thread program swap will not likely go wrong.

However, if there are multiple threads that run swap function and might swap the same two objects, a race condition raises. We would have to use mutual exclusion and lock to make sure that the swaps were done without competitions.

Source Code

The program is extremely simple. We have a swap function that swaps the information of two people. We have two guys, Michael and Howard, and we would like to swap their information four times. In a single thread program, after swap four times, we expect Michael remains Michael and Howard remains Howard. In a multi-thread concurrent program, after swap four times, we would also expect Michael remains Michael and Howard remains Howard.

dead_lock.cpp
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
// g++ -std=c++14 dead_lock.cpp -lpthread -o dead_lock
#include <cstdlib>
#include <functional>
#include <iostream>
#include <mutex>
#include <string>
#include <thread>

/**
* @brief Thread safe sleep function.
* Randomly sleep 0 to 5 nano seconds.
*/
void random_sleep()
{
std::chrono::nanoseconds random_duration{std::rand() % 5};
std::this_thread::sleep_for(random_duration);
}

/**
* @brief A Dummy class for personal information.
*/
class Guy
{
public:
Guy();
Guy(std::string name, unsigned int age, std::string id)
: mName{name}, mAge{age}, mId{id} {};
void setName(const std::string name)
{
random_sleep();
this->mName = name;
}
void setAge(const unsigned int age)
{
random_sleep();
this->mAge = age;
}
void setId(const std::string id)
{
random_sleep();
this->mId = id;
}
std::string getName() const
{
random_sleep();
return this->mName;
}
unsigned int getAge() const
{
random_sleep();
return this->mAge;
}
std::string getId() const
{
random_sleep();
return this->mId;
}

private:
std::string mName;
unsigned int mAge;
std::string mId;
};

/**
* @brief Swap the information of two Guy objects.
* This swap function is thread-unsafe.
*/
void swap(Guy& lhs, Guy& rhs)
{
if (&lhs == &rhs)
{
return;
}
std::string tmpName = lhs.getName();
unsigned int tmpAge = lhs.getAge();
std::string tmpId = lhs.getId();
lhs.setName(rhs.getName());
lhs.setAge(rhs.getAge());
lhs.setId(rhs.getId());
rhs.setName(tmpName);
rhs.setAge(tmpAge);
rhs.setId(tmpId);
}

/**
* @brief A Guy wrapper that has an additional std::mutex.
*/
class GuyWrapper
{
public:
GuyWrapper(Guy& guy) : mGuy{guy} {};
std::mutex mMutex;
Guy& mGuy;
};

/**
* @brief A swap function that uses mutex but will cause deadlock.
* Even if we are always locking the first GuyWrapper first and the second
* GuyWrapper second, The user could switch the order of these two objects and
* cause dead lock.
*/
void swapDeadLock(GuyWrapper& lhs, GuyWrapper& rhs)
{
if (&lhs == &rhs)
{
return;
}
std::lock_guard<std::mutex> lock_lhs(lhs.mMutex);
std::lock_guard<std::mutex> lock_rhs(rhs.mMutex);
swap(lhs.mGuy, rhs.mGuy);
}

/**
* @brief A thread-safe swap function.
* Locking two std::mutex simultaneously prevented deadlock.
* @param lhs
* @param rhs
*/
void swapSafe(GuyWrapper& lhs, GuyWrapper& rhs)
{
if (&lhs == &rhs)
{
return;
}
std::lock(lhs.mMutex, rhs.mMutex);
// std::adopt_lock indicates that the std::mutex object might be already
// locked. In stead of lock the std::mutex object in the constructor Use the
// locked state from the std::mutex object
std::lock_guard<std::mutex> lock_lhs(lhs.mMutex, std::adopt_lock);
std::lock_guard<std::mutex> lock_rhs(rhs.mMutex, std::adopt_lock);
swap(lhs.mGuy, rhs.mGuy);
}

/**
* @brief Verify Guy object's information.
*/
bool verifyGuy(const Guy& guy, const std::string name, const unsigned int age,
const std::string id)
{
if ((guy.getName() == name) && (guy.getAge() == age) && (guy.getId() == id))
{
return true;
}
else
{
return false;
}
}

/**
* @brief A thread-unsafe swap demo.
* After even number of swap, we expect the information of Michael and Howard
* remain unchanged. However, because of race conditions, sometimes, the
* information of Michael and Howard are incorrect.
*/
void unsafeDemo()
{
const std::string michaelName{"Michael"};
const unsigned int michaelAge{28};
const std::string michaelId{"X0001"};

const std::string howardName{"Howard"};
const unsigned int howardAge{35};
const std::string howardId{"Y9999"};

Guy michael{michaelName, michaelAge, michaelId};
Guy howard{howardName, howardAge, howardId};

bool pass = true;

for (int i = 0; i < 1000; i++)
{
std::thread thread0{swap, std::ref(michael), std::ref(howard)};
std::thread thread1{swap, std::ref(howard), std::ref(michael)};
std::thread thread2{swap, std::ref(michael), std::ref(howard)};
std::thread thread3{swap, std::ref(howard), std::ref(michael)};
thread0.join();
thread1.join();
thread2.join();
thread3.join();
if (!verifyGuy(michael, michaelName, michaelAge, michaelId))
{
std::cout << "Expected Michael: " << michaelName << " "
<< michaelAge << " " << michaelId << " " << std::endl;
std::cout << "Got Michael: " << michael.getName() << " "
<< michael.getAge() << " " << michael.getId() << " "
<< std::endl;
pass = false;
break;
}
if (!verifyGuy(howard, howardName, howardAge, howardId))
{
std::cout << "Expected Howard: " << howardName << " " << howardAge
<< " " << howardId << " " << std::endl;
std::cout << "Got Howard: " << howard.getName() << " "
<< howard.getAge() << " " << howard.getId() << " "
<< std::endl;
pass = false;
break;
}
}

if (pass)
{
std::cout << "Thread Lock Test Passed!" << std::endl;
}
else
{
std::cout << "Thread Lock Test Failed!" << std::endl;
}
}

/**
* @brief A thread-safe swap demo.
* After even number of swap, the information of Michael and Howard remain
* unchanged.
*/
void safeDemo()
{
const std::string michaelName{"Michael"};
const unsigned int michaelAge{28};
const std::string michaelId{"X0001"};

const std::string howardName{"Howard"};
const unsigned int howardAge{35};
const std::string howardId{"Y9999"};

Guy michael{michaelName, michaelAge, michaelId};
Guy howard{howardName, howardAge, howardId};

GuyWrapper michaelWrapped{michael};
GuyWrapper howardWrapped{howard};

bool pass = true;

for (int i = 0; i < 1000; i++)
{
std::thread thread0{swapSafe, std::ref(michaelWrapped),
std::ref(howardWrapped)};
std::thread thread1{swapSafe, std::ref(howardWrapped),
std::ref(michaelWrapped)};
std::thread thread2{swapSafe, std::ref(michaelWrapped),
std::ref(howardWrapped)};
std::thread thread3{swapSafe, std::ref(howardWrapped),
std::ref(michaelWrapped)};
thread0.join();
thread1.join();
thread2.join();
thread3.join();
if (!verifyGuy(michael, michaelName, michaelAge, michaelId))
{
std::cout << "Expected Michael: " << michaelName << " "
<< michaelAge << " " << michaelId << " " << std::endl;
std::cout << "Got Michael: " << michael.getName() << " "
<< michael.getAge() << " " << michael.getId() << " "
<< std::endl;
pass = false;
break;
}
if (!verifyGuy(howard, howardName, howardAge, howardId))
{
std::cout << "Expected Howard: " << howardName << " " << howardAge
<< " " << howardId << " " << std::endl;
std::cout << "Got Howard: " << howard.getName() << " "
<< howard.getAge() << " " << howard.getId() << " "
<< std::endl;
pass = false;
break;
}
}

if (pass)
{
std::cout << "Thread Lock Test Passed!" << std::endl;
}
else
{
std::cout << "Thread Lock Test Failed!" << std::endl;
}
}

/**
* @brief A thread-safe swap demo that will cause deadlock.
* This function will run forever due to deadlock.
*/
void deadLockDemo()
{
const std::string michaelName{"Michael"};
const unsigned int michaelAge{28};
const std::string michaelId{"X0001"};

const std::string howardName{"Howard"};
const unsigned int howardAge{35};
const std::string howardId{"Y9999"};

Guy michael{michaelName, michaelAge, michaelId};
Guy howard{howardName, howardAge, howardId};

GuyWrapper michaelWrapped{michael};
GuyWrapper howardWrapped{howard};

bool pass = true;

for (int i = 0; i < 1000; i++)
{
std::thread thread0{swapDeadLock, std::ref(michaelWrapped),
std::ref(howardWrapped)};
std::thread thread1{swapDeadLock, std::ref(howardWrapped),
std::ref(michaelWrapped)};
std::thread thread2{swapDeadLock, std::ref(michaelWrapped),
std::ref(howardWrapped)};
std::thread thread3{swapDeadLock, std::ref(howardWrapped),
std::ref(michaelWrapped)};
thread0.join();
thread1.join();
thread2.join();
thread3.join();
if (!verifyGuy(michael, michaelName, michaelAge, michaelId))
{
std::cout << "Expected Michael: " << michaelName << " "
<< michaelAge << " " << michaelId << " " << std::endl;
std::cout << "Got Michael: " << michael.getName() << " "
<< michael.getAge() << " " << michael.getId() << " "
<< std::endl;
pass = false;
break;
}
if (!verifyGuy(howard, howardName, howardAge, howardId))
{
std::cout << "Expected Howard: " << howardName << " " << howardAge
<< " " << howardId << " " << std::endl;
std::cout << "Got Howard: " << howard.getName() << " "
<< howard.getAge() << " " << howard.getId() << " "
<< std::endl;
pass = false;
break;
}
}

if (pass)
{
std::cout << "Thread Lock Test Passed!" << std::endl;
}
else
{
std::cout << "Thread Lock Test Failed!" << std::endl;
}
}

int main()
{
unsafeDemo();
safeDemo();
deadLockDemo();
}

To build the program, please run the following command in the terminal.

1
$ g++ -std=c++14 dead_lock.cpp -lpthread -o dead_lock

To run the program, we would likely see the following outputs. However, the program will hang forever due to the deadlock.

1
2
3
4
5
6
$ ./dead_lock
Expected Michael: Michael 28 X0001
Got Michael: Howard 35 Y9999
Thread Lock Test Failed!
Thread Lock Test Passed!

Essentially, using the conventional swap in the concurrent program is not thread-safe, using two locks for locking the mutexes of two objects sequentially in swapDeadLock will cause deadlock, and only using two locks for locking the mutexes of two objects simultaneously in swapSafe is thread safe.

Lock and Mutex Implementation

We cannot use a global lock or a specialized lock for swap, because we would possibly use the swap function to swap different pairs of objects concurrently. Only when swapping the same pair of the objects simultaneously, we want the swap to happen in an ordered way. For example, we could have implemented a swap function like the one below.

1
2
3
4
5
6
7
8
9
void swapNonConcurrent(Guy& lhs, Guy& rhs, std::mutex& mtx)
{
if (&lhs == &rhs)
{
return;
}
std::lock_guard<std::mutex> lock_lhs(mtx);
swap(lhs, rhs);
}

It is thread-safe, however, there would be no concurrency for swap from such implementation either. Even if we want to swap two pair of the guys, Michael and Howard, Jack and Tom, we could not do it concurrently with one std::mutex object to lock.

One of the correct implementations is to add a std::mutex object to each of the Guy object. We did this by creating a wrapper GuyWrapper that has a member referencing to the Guy object. An additional std::mutex was created specifically.

1
2
3
4
5
6
7
class GuyWrapper
{
public:
GuyWrapper(Guy& guy) : mGuy{guy} {};
std::mutex mMutex;
Guy& mGuy;
};

Then we could lock the modification to each Guy specifically. If we swap different pairs of Guy objects simultaneously, we could do them concurrently. And if there are two threads calling swapDeadLock(michaelWrapped, howardWrapped) simultaneously, one of the thread will wait until the other one is done because the lock for Michael will not be freed until one swap is done in one thread. These are the correct behaviors we are expecting.

1
2
3
4
5
6
7
8
9
10
void swapDeadLock(GuyWrapper& lhs, GuyWrapper& rhs)
{
if (&lhs == &rhs)
{
return;
}
std::lock_guard<std::mutex> lock_lhs(lhs.mMutex);
std::lock_guard<std::mutex> lock_rhs(rhs.mMutex);
swap(lhs.mGuy, rhs.mGuy);
}

However, we might have missed something. What if one thread is calling swapDeadLock(michaelWrapped, howardWrapped) and the other thread is calling swapDeadLock(howardWrapped, michaelWrapped)? It is possible that the swapDeadLock(michaelWrapped, howardWrapped) locked Michael and swapDeadLock(howardWrapped, michaelWrapped) locked Howard. When swapDeadLock(michaelWrapped, howardWrapped) wants to further lock Howard, it waits because Howard was already locked. Similarly, when swapDeadLock(howardWrapped, michaelWrapped) wants to further lock Michael, it also waits because Michael was already locked. Therefore, this is a race condition. The swapDeadLock calls in both threads are waiting, and the process will hang forever.

To overcome this, the best possible solution might be locking the two GuyWrapper objects simultaneously. If the two GuyWrapper objects are locked simultaneously, other threads that is trying to lock the same pair of the GuyWrapper objects will have to wait, which is thread-safe.

Fortunately, C++11 has provided us an implementation std::lock for simultaneous locking multiple std::mutex objects.

1
2
3
4
5
6
7
8
9
10
11
void swapSafe(GuyWrapper& lhs, GuyWrapper& rhs)
{
if (&lhs == &rhs)
{
return;
}
std::lock(lhs.mMutex, rhs.mMutex);
std::lock_guard<std::mutex> lock_lhs(lhs.mMutex, std::adopt_lock);
std::lock_guard<std::mutex> lock_rhs(rhs.mMutex, std::adopt_lock);
swap(lhs.mGuy, rhs.mGuy);
}

Problem solved.

Conclusions

We always have to be careful when we implement concurrent applications that tries to modify the same object. Deadlock could happen anywhere.

Author

Lei Mao

Posted on

08-23-2020

Updated on

08-23-2020

Licensed under


Comments