Hands-On Multithreading with C++ 03—Deadlock

Complete code: https://github.com/yu-cheng-kuo-28/multithreading-cpp

Hands-On Multithreading with C++ 02—Synchronization

Hands-On Multithreading with C++ 04 — Producer-Consumer Problem

You may refer to the technical article below for theoretical knowledge:

OS Walkthrough 05 — Deadlock

Figures: Illustrations of deadlock [1][2]

There’re 2 main ways to solve a deadlock: the banker’s algorithm & resource ordering. Since the banker’s algorithm is a bit complicated solution, we’re gonna leverage resource ordering to solve the deadlocks in this article from simple examples to complex instances.

Outline
(1) Deadlock 01: A typical deadlock (2 resources & 2 threads)
(2) Deadlock 02: A solution to Deadlock 01 (lock both resources)
(3) Deadlock 03: Another solution to Deadlock 01 (resource ordering)
(4) Deadlock 04: A more complicated case
(5) Deadlock 05: A more complex case (3 resources & 3 threads) solved by resource ordering
(6) Deadlock 06: A more real-world case (3 resources [each with 2 units] & 3 threads)
(7) Conclusion
(8) References

(1) Deadlock 01: A typical deadlock (2 resources & 2 threads)

// 10_deadlock_01 
#include <iostream>
#include <thread>
#include <mutex>

std::mutex resource1;
std::mutex resource2;

void threadFunction1() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2); // This will wait for resource2

    std::cout << "Thread 1 has both mutexes" << std::endl;
}

void threadFunction2() {
    std::lock_guard<std::mutex> lock2(resource2);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock1(resource1); // This will wait for resource1

    std::cout << "Thread 2 has both mutexes" << std::endl;
}

int main() {
    std::thread t1(threadFunction1);
    std::thread t2(threadFunction2);

    t1.join();
    t2.join();

    return 0;
}

The output:

The program just never ended. This was exactly a deadlock.

(2) Deadlock 02: A solution to Deadlock 01 (lock both resources)

// 11_deadlock_02
#include <iostream>
#include <thread>
#include <mutex>
#include <utility>

std::mutex resource1;
std::mutex resource2;

void threadFunction1() {
    std::lock(resource1, resource2); // Lock both mutexes without deadlock
    std::lock_guard<std::mutex> lock1(resource1, std::adopt_lock);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2, std::adopt_lock);

    std::cout << "Thread 1 has both mutexes" << std::endl;
}

void threadFunction2() {
    std::lock(resource1, resource2); // Lock both mutexes without deadlock
    std::lock_guard<std::mutex> lock2(resource2, std::adopt_lock);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock1(resource1, std::adopt_lock);

    std::cout << "Thread 2 has both mutexes" << std::endl;
}

int main() {
    std::thread t1(threadFunction1);
    std::thread t2(threadFunction2);

    t1.join();
    t2.join();

    return 0;
}

Output:

Utilizing an extra lock to lock the orignial 2 mutexes.

ChatGPT-4: std::lock uses a combination of advanced locking strategies and atomic operations to ensure that multiple mutexes are locked simultaneously in a safe and deadlock-free manner. The exact implementation details may vary, but the behavior and guarantees are consistent across different C++ standard library implementations.

(3) Deadlock 03: Another solution to Deadlock 01 (resource ordering)

// 12_deadlock_03
#include <iostream>
#include <thread>
#include <mutex>

std::mutex resource1;
std::mutex resource2;

// Function to be executed by thread 1
void threadFunction1() {
    // Locks are acquired in the order: resource1, then resource2
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2);

    std::cout << "Thread 1 has both resources" << std::endl;
}

// Function to be executed by thread 2
void threadFunction2() {
    // Locks are acquired in the same order: resource1, then resource2
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2);

    std::cout << "Thread 2 has both resources" << std::endl;
}

int main() {
    std::thread t1(threadFunction1);
    std::thread t2(threadFunction2);

    t1.join();
    t2.join();

    return 0;
}

Output:

Successfully solved the deadlock by resource ordering.

(4) Deadlock 04: A more complicated case

// 13_deadlock_04 
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>

std::mutex resource1;
std::mutex resource2;
std::mutex resource3;

// Function to be executed by thread 1
void threadFunction1() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2);

    std::cout << "Thread 1 has locked resource1 and resource2" << std::endl;
}

// Function to be executed by thread 2
void threadFunction2() {
    std::lock_guard<std::mutex> lock1(resource2);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource3);

    std::cout << "Thread 2 has locked resource2 and resource3" << std::endl;
}

// Function to be executed by thread 3
void threadFunction3() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource3);

    std::cout << "Thread 3 has locked resource1 and resource3" << std::endl;
}

int main() {
    std::thread t1(threadFunction1);
    std::thread t2(threadFunction2);
    std::thread t3(threadFunction3);

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

Output:

(5) Deadlock 05: A more complex case (3 resources & 3 threads) solved by resource ordering

// 14_deadlock_05.cpp
#include <iostream>
#include <thread>
#include <mutex>

std::mutex resource1;
std::mutex resource2;
std::mutex resource3;

void threadFunction1() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    std::lock_guard<std::mutex> lock2(resource2);
    std::lock_guard<std::mutex> lock3(resource3);  // Attempt to lock resource3 as well

    std::cout << "Thread 1 has locked resource1, resource2, and resource3" << std::endl;
}

void threadFunction2() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    std::lock_guard<std::mutex> lock2(resource2);
    std::lock_guard<std::mutex> lock3(resource3);

    std::cout << "Thread 2 has locked resource1, resource2, and resource3" << std::endl;
}

void threadFunction3() {
    std::lock_guard<std::mutex> lock1(resource1);
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    std::lock_guard<std::mutex> lock2(resource2);
    std::lock_guard<std::mutex> lock3(resource3);

    std::cout << "Thread 3 has locked resource1, resource2, and resource3" << std::endl;
}

int main() {
    std::thread t1(threadFunction1);
    std::thread t2(threadFunction2);
    std::thread t3(threadFunction3);

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

Output:

Again we solve this more complex case with resource ordering.

(6) Deadlock 06: A more real-world case (3 resources [each with 2 units] & 3 threads)

// 15_deadlock_06.cpp
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

class Resource {
private:
    std::mutex mtx;
    std::condition_variable cv;
    int available_units;

public:
    Resource(int units) : available_units(units) {}

    void acquire() {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, [&]{ return available_units > 0; });
        available_units--;
    }

    void release() {
        std::unique_lock<std::mutex> lock(mtx);
        available_units++;
        cv.notify_one();
    }
};

Resource resource1(2);
Resource resource2(2);
Resource resource3(2);

void acquireResources() {
    resource1.acquire();
    resource2.acquire();
    resource3.acquire();
}

void releaseResources() {
    resource1.release();
    resource2.release();
    resource3.release();
}

void threadFunction(int id) {
    acquireResources();
    std::cout << "Thread " << id << " has acquired all resources" << std::endl;
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // Simulating work
    releaseResources();
    std::cout << "Thread " << id << " has released all resources" << std::endl;
}

int main() {
    std::thread t1(threadFunction, 1);
    std::thread t2(threadFunction, 2);
    std::thread t3(threadFunction, 3);

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

Output:

We then move on to a more practical case with 3 resources (and 2 units for each resources) & 3 threads. Also, since every resource has 2 units, we have to adopt semaphore, which corresponds to the condition variable along with the functions wait() and notify_one().

• A std::condition_variable is used for blocking a thread or multiple threads until a particular condition is met.wait() and notify_one() are essential for condition-based synchronization in multithreaded applications, allowing threads to sleep and wake up at appropriate times to efficiently manage shared resources.

Let’s see how ChatGPT-4 broke down this code snippet:

(ChatGPT-4) In your provided C++ code, std::condition_variable, wait(), and notify_one() are used to synchronize access to a shared resource. These are key components in concurrent programming to avoid busy-waiting and efficiently manage resource access among multiple threads. Let's break down their usage and roles:

std::condition_variable

• Role: A std::condition_variable is used for blocking a thread or multiple threads until a particular condition is met. It's often used in conjunction with a std::mutex to synchronize threads.
• Purpose in Code: In your code, cv (a std::condition_variable) is used to block a thread when it tries to acquire a resource that is not available. It waits until the resource becomes available.

wait()

• Role: The wait() function is used to block the current thread until the condition variable is notified and the provided condition is met.
• Usage in Code:
• cv.wait(lock, [&]{ return available_units > 0; });
• This line tells the thread to wait on the condition variable cv.
• lock is a std::unique_lock<std::mutex> that provides exclusive access to the shared resource.
• The lambda function &]{ return available_units > 0; } is the condition. The thread will be blocked until available_units is greater than 0.
• When wait() is called, it atomically releases the lock and suspends the execution of the thread. When the thread is unblocked (notified and the condition is true), it automatically re-acquires the lock.

notify_one()

• Role: This function is used to unblock one of the threads waiting on the condition variable.
• Usage in Code:
• cv.notify_one();
• After a thread releases a resource (available_units++), it calls notify_one() on the condition variable.
• This wakes up one of the waiting threads (if any are waiting).
• The awakened thread then re-acquires the lock and checks the condition. If the condition is satisfied (i.e., available_units > 0), it proceeds with its execution.

(7) Conclusion

As we went through all the cases of deadlock from simple instances to complex examples, you might have gained some insights into how to solve a deadlock by leverage resource ordering.

Check “(6) Deadlock 06: A more real-world case (3 resources [each with 2 units] & 3 threads)” especially for a more real-world case dealing with std::condition_variableand related functions like wait()&notify_one().

(8) References

[1] Florida State University | Deadlock
https://www.cs.fsu.edu/~baker/cop5611.S03/deadlock.html
[2] Deadlock
https://hackmd.io/@ExcitedMail/Hy6Ot7s7Y
[3] ChatGPT-4