In our last couple of articles we've tired to go through the fundamentals of concurrency in C++ using Standard Template Library. We've gone through basics of thread management and how to safely share data amongst threads using mutex. In this article we'll try to understand what is deadlock, how it impact multi threaded application and how to avoid deadlocks.
What is Deadlock?
Imagine that you have a toy that comes into two parts, and you need both parts to play with it. For example, the toy is drum and drumstick. Now imaging that you've two children, both of whom like to playing with it. Kids being kids, if one of them gets both the drum and the drumstick then that child will continue to play until the child get tired. Now imaging drum and drumstick are kept separately in toy box, and both of your children decided to play with them at the same time. So they quickly try to grab the toy and one of them finds drum and other one drumstick. Now they're stuck; unless one decides to be nice and let other play. But in reality each kid hold on to it's part of toy and neither gets to play.
Above example is simplified version of deadlock which is common problem in multi threaded programs.
A deadlock in C++ is a situation where a process or thread is waiting for a resource that is being held by another waiting process. This can cause the program to behave strangely, or even appear to lock up.
Types and Cause of Deadlock
Below are some types additional information wrt deadlocks in C++.
Types of Deadlock
There are two types of deadlocks:
Potential Deadlock
Actual Deadlock
A potential deadlock may not occur in every run, but could happen depending on the timing of lock requests and thread scheduling.
Causes of Deadlock
Deadlocks can be caused by below four conditions.
Mutual exclusion
A resource is held in a non-sharable mode, so other processes must wait to use it.
Hold and wait
A process is holding a resource and waiting for another resource that's currently held by another process.
No preemption
Once a process has a resource, it can't be taken away until the process releases it voluntarily.
Circular-wait
A set of processes exist where each process is waiting for the next process in the set to release a resource.
Prevention Methods
One way to prevent deadlocks is to ensure that all mutexes are locked in the same order. Another way is to use RAII-based locks, such as lock_guard, to help ensure that locks are released.
Lets try to understand deadlock using simple example. Below example launches two threads and using two global mutexes inside each thread to perform some task and print details.
// Example 2: Demonstrating Deadlock
#include <iostream>
#include <mutex>
#include <thread>
#include <string>
void print(std::string str) {
std::cout<< str<<"\n";
}
int main() {
std::mutex m1;
std::mutex m2;
std::thread t1([&m1, &m2] {
print("1. Acquiring m1.");
m1.lock();
std::this_thread::sleep_for(std::chrono::milliseconds(10));
print("1. Acquiring m2");
m2.lock();
// Critical Section
m1.unlock();
m2.unlock();
});
std::thread t2([&m1, &m2] {
print("2. Acquiring m2");
m2.lock();
std::this_thread::sleep_for(std::chrono::milliseconds(10));
print("2. Acquiring m1");
m1.lock();
// Critical Section
m2.unlock();
m1.unlock();
});
t1.join();
t2.join();
}Output
1. Acquiring m1.
2. Acquiring m2
2. Acquiring m1
1. Acquiring m2
// Program does not terminates due to deadlockRunning above program results in deadlock and threads continue to wait for mutex, and hence program does not terminate.
Avoiding Deadlock?
Continuing with the earlier toy example, we can avoid deadlock by ensuring kid should get both the drum and the drumstick before starting to play. If kid has only one part of the toy then that kid should not keep half part of the toy, potentially unblocking other kid.
In the realm of programming, we can avoid the deadlock over resources held by threads using mutexes, using simple principle, each thread need to lock both pair of mutexes before starting execution of critical section.
One way to prevent deadlocks is to ensure that all mutexes are locked in the same order. Another way is to use RAII-based locks, such as lock_guard, to help ensure that locks are released.
The common advice for avoiding deadlock is to always lock two mutexes in the same order: if you always lock mutex A before mutex B, then you'll never deadlock
Avoiding Deadlock with Std::lock
The C++ Standard Library provide std::lock a function that can lock two or more mutexes at once without risk of deadlock. Lets try to understand C++ STL function std::lock with with simple example:
Consider simple example of swap() function which performs swap of user defined object's data. Custom objects contain mutex locks and using std::lock() we first try to acquire locks on both the objects inside swap() function. If any one of the mutex of not lockable then std::lock() does not lock any mutex of the object. Once both mutex are available in lockable condition then only std::lock locks the mutexes.
Next step is now to create std::lock_guard object on both mutexes with std::adopt_lock as second parameter to the std::lock_guard constructor, indicating std::lock_guard objec that the mutexes are already locked and they should adapt the ownership of existing lock onto the mutex, rather than attempt to lock the mutex in constructor. Once both std::lock_guard object are created, swap() function can now successfully
// Example 2: Avoiding deadlock using std::lock
#include <mutex>
using namespace std;
class MyBigObjectClass {};
void swap(MyBigObjectClass& lhs,MyBigObjectClass& rhs);
class X
{
private:
MyBigObjectClass myObj;
std::mutex m;
public:
X(MyBigObjectClass const& obj):myObj(obj){}
friend void swap(X& lhs, X& rhs)
{
// The arguments are checked to ensure they
// are different instances,
// because attempting to acquire a lock on a std::mutex
// when we already hold it is undefined behavior.
if(&lhs == &rhs ) return;
// The call to std::lock() locks the two mutexes
std::lock(lhs.m,rhs.m);
// Two std::lock_guard instances are constructed
// one for each mutex...
std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock);
std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock);
swap(lhs.myObj, rhs.myObj);
}
};std::lock provides all-or-nothing semantics with regards to locking the supplied mutex. C++17 provides additional support for this scenario, in the form of a new RAII template, std::scoped_lock<>. This is exactly equivalent to std::lock_guard<>, except that it is a variadic template, accepting a list of mutex types as template parameters, and a list of mutexes as constructor arguments.
Now lets re-write example 1 with std::lock and std::lock_guard:
// Example 3: Avoiding deadlock using std::lock
#include <iostream>
#include <mutex>
#include <thread>
#include <string>
void print(std::string str) {
std::cout<< str<<"\n";
}
int main() {
std::mutex m1;
std::mutex m2;
std::thread t1([&m1, &m2] {
std::lock(m1, m2);
std::lock_guard<std::mutex> lock_a(m1,std::adopt_lock);
print("1. Acquiring m1.");
std::lock_guard<std::mutex> lock_b(m2,std::adopt_lock);
print("1. Acquiring m2");
std::this_thread::sleep_for(std::chrono::milliseconds(10));
});
std::thread t2([&m1, &m2] {
std::lock(m1, m2);
std::lock_guard<std::mutex> lock_a(m1,std::adopt_lock);
print("2. Acquiring m1.");
std::lock_guard<std::mutex> lock_b(m2,std::adopt_lock);
print("2. Acquiring m2");
std::this_thread::sleep_for(std::chrono::milliseconds(10));
});
t1.join();
t2.join();
}Output
// First run gives below output and program terminates
2. Acquiring m1.
2. Acquiring m2
1. Acquiring m1.
1. Acquiring m2
// Second run gives below output and program terminates
1. Acquiring m1.
1. Acquiring m2
2. Acquiring m1.
2. Acquiring m2
Running above program ensure thread having both locks only execute and after release locks by one thread, other thread acquires the lock to complete its task. Note, we could have simply followed One way to prevent deadlocks is to ensure that all mutexes are locked in the same order to avoid deadlock, however in practice with multiple developer working on different part of program, std::lock approach ensure deadlock is avoided.
Additional Guidelines For Avoiding Deadlock
Deadlock doesn't only occur with locks, although that's the most common cause of deadlock. You can create deadlock with two threads and no locks by having each thread call join() on the std::thread object by the other.
Below are few additional guidelines to avoid
Avoid nested lock
Avoid calling user-supplied code while holding a lock
Acquire locks in a fixed order
Conclusion
The general guideline for avoiding deadlock boils down to one idea:
Don't wait for another thread if there's a chance it's waiting for you...
Reference:
A Tour of C++ - Bjarne Stroustrup
C++ Concurrency In Action - Anthony Williams
Comments