Concept of deadlock

What is deadlock?

The program flow cannot continue to advance to a stuck state

Deadlock generation condition

1. Mutually exclusive condition: when I accept the lock, others cannot lock it

2. Inalienable condition: I have locked it, and only I can solve it

3. Request and hold conditions: lock A is added and lock B is requested. If lock B is not requested, lock A will not be released

4. Loop waiting conditions: thread 1 takes lock A and requests lock B, while thread 2 takes lock B and requests lock A

 

Deadlock prevention: necessary conditions for destruction
                  1. Damage condition 4, ensure the same sequence of adding and unlocking
                  2. Use non blocking locking: A lock request is taken, and B lock request fails to release A lock

• Four necessary conditions for breaking deadlock
• The locking sequence is consistent
• Avoid scenarios where the lock is not released
• One time allocation of resources

Deadlock avoidance: banker algorithm( Banker algorithm and code implementation )Deadlock detection algorithm

 

Analysis and solution of deadlock problem

Examples

Simulate the deadlock problem: thread 1 has acquired lock 1 and thread 2 has acquired lock 2. At this time, thread 1 needs to obtain lock 2 to continue running, while thread 2 needs to obtain lock 1 to continue running. At this time, the program will enter the deadlock state, and the code is as follows: (programming with thread class and mutex provided by c++11)

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
using namespace std;

mutex m1;
mutex m2;

//Thread 1 acquires lock 1
void thread1()
{
    //Acquire lock 1
    m1.lock();

    //The thread sleeps for 1 second and acquires lock 2 to ensure that thread 2 can acquire lock 2 first
    this_thread::sleep_for(chrono::seconds(3));
    cout << "thread1 Got it mutex1" << endl;

    m2.lock();

    cout << "thread1 Got it mutex1 And mutex2" << endl;

    m2.unlock();
    m1.unlock();
}

//Thread 2 acquires lock 2
void thread2()
{
    //When the thread sleeps for 1 second and acquires lock 1, ensure that thread 1 can acquire lock 1 first
    this_thread::sleep_for(chrono::seconds(1));
    //Acquire lock 2
    m2.lock();
    cout << "thread2 Got it mutex2" << endl;
    //Acquire lock 1
    m1.lock();

    cout << "thread2 Got it mutex1 And mutex2" << endl;

    m1.unlock();
    m2.unlock();
}

int main()
{
    thread t1(thread1), t2(thread2);

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

    return 0;
}

At this time, after the two threads obtain a lock respectively, the program stops, does not continue to execute, and has been waiting here. So how to analyze what caused it?

The program has been waiting for possible situations: dead loop, waiting for input (cin, scanf), deadlock, etc

1. First, let's check the status of the process

You can see that it is in the Sl + state. Baidu knows that it is in the sleep state, multi-threaded and background process, that is, the multi-threaded program enters the blocking state.

2. Now let's take a look at the operation of threads in the process: top -Hp PID

You can see that all threads are in the blocking state and the CPU utilization is 0, so the case of dead loop is excluded.

3. Take another look at the stack call information of the thread

Conduct remote gdb debugging of the running program, gdb attach PID enters gdb command line, and ＾ view the stack information of each thread of the process ＾ thread apply all bt

You can see that thread1 and thread2 finally stop at lock_wait here, that is, both threads are waiting to obtain a lock. Combined with source code analysis, thread1 and thread2 want to obtain the lock in each other's hand, but they can't get it, so they have been waiting here and blocked.

 

Locating problems from source code

1. Compile the debug version

2. Run the program and conduct remote gdb debugging

3. View all current thread information

At this time, at thread 1, that is, the main thread, switch threads first

4. Switch the thread to thread2 or thread3 and print the stack information

5. View the frame 4 information of thread 2

You can see that the source code stops at line 20.

 

Code modification

According to several methods of deadlock prevention mentioned above, the loop waiting condition that destroys the deadlock is OK. We use the above to ensure that the sequence of adding and unlocking is consistent.

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
using namespace std;

mutex m1;
mutex m2;

//Thread 1 acquires lock 1
void thread1()
{
    //Acquire lock 1
    m1.lock();
    cout << "thread1 Got it mutex1" << endl;
    //Acquire lock 2
    m2.lock();
    cout << "thread1 Got it mutex2" << endl;

    //Release lock
    m2.unlock();
    m1.unlock();
    cout << "thread1 Got it mutex1 And mutex2" << endl;
}

//Thread 2 acquires lock 2
void thread2()
{
    //Acquire lock 1
    m1.lock();
    cout << "thread2 Got it mutex1" << endl;
    //Acquire lock 2
    m2.lock();
    cout << "thread2 Got it mutex2" << endl;

    //Release lock
    m1.unlock();
    m2.unlock();
    cout << "thread2 Got it mutex1 And mutex2" << endl;
}

int main()
{
    thread t1(thread1), t2(thread2);

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

    return 0;
}