Lei Mao bio photo

Lei Mao

Machine Learning, Artificial Intelligence, Computer Science.

Twitter Facebook LinkedIn GitHub   G. Scholar E-Mail RSS

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
// 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.

$ 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.

$ ./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 people 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.

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.

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.

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.

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.