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.
/** * @brief Swap the information of two Guy objects. * This swap function is thread-unsafe. */ voidswap(Guy& lhs, Guy& rhs) { if (&lhs == &rhs) { return; } std::string tmpName = lhs.getName(); unsignedint 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. */ classGuyWrapper { 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. */ voidswapDeadLock(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 */ voidswapSafe(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 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. */ voidunsafeDemo() { const std::string michaelName{"Michael"}; constunsignedint michaelAge{28}; const std::string michaelId{"X0001"};
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. */ voidsafeDemo() { const std::string michaelName{"Michael"}; constunsignedint michaelAge{28}; const std::string michaelId{"X0001"};
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. */ voiddeadLockDemo() { const std::string michaelName{"Michael"}; constunsignedint michaelAge{28}; const std::string michaelId{"X0001"};
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.
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.
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.
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.