[Linux] Thread Mutual Exclusion | Deadlock | Process Synchronization

? Author: @阿亮joy.
Column:“Learning Linux”
Motto: Every outstanding person has a silent time, that time is a day when a lot of hard work but no results can be obtained, we call it rooted

Table of Contents

    • Thread mutual exclusion
      • Mutual exclusion related concepts
      • mutex
      • Implementation principle of mutual exclusion lock
    • Reentrant and thread safe
      • concept
      • Common Thread Unsafe Situations
      • Common Thread Safety Situations
      • Common non-reentrancy cases
      • Common reentrant cases
      • The link between reentrancy and thread safety
    • Deadlock
      • concept
      • Four necessary conditions for deadlock
      • avoid deadlock
      • deadlock avoidance algorithm
    • Thread Synchronization
      • concept
      • condition variable
    • Summarize

Thread mutual exclusion

Mutual exclusion related concepts

  • Critical resources: resources that are shared by multi-threaded execution streams and can only be accessed by one execution stream at a time are called critical resources
  • Critical section: The code that accesses critical resources inside each thread is the critical section
  • Mutual exclusion: At any time, mutual exclusion guarantees that there is only one execution flow entering the critical section to access critical resources, which usually protects critical resources
  • Atomicity: Atomicity means that an operation is either completed or not done, and there is no intermediate state
#include <iostream>
#include <unistd.h>
#include <cstdio>
#include <pthread.h>

using namespace std;

// Multiple threads access the same global variable and perform data calculations on it, and multiple threads will affect each other
// During concurrent access, data inconsistency occurs due to scheduling timing issues
int tickets = 10000;

// The getTickets function will be flushed by multiple execution streams, and the getTickets function is a flushing function
void* getTickets(void* args)
{<!-- -->
    (void) args;
    while(true)
    {<!-- -->
        if(tickets > 0) // The essence of judgment is also calculation
        {<!-- -->
            usleep(1000);
            printf("%p: %d\\
", pthread_self(), tickets--);
        }
        else
            break;
    }
    return nullptr;
}


int main()
{<!-- -->
    // Multi-thread grabbing tickets
    pthread_t t1, t2, t3;
    pthread_create( &t1, nullptr, getTickets, nullptr);
    pthread_create( &t2, nullptr, getTickets, nullptr);
    pthread_create( &t3, nullptr, getTickets, nullptr);

    pthread_join(t1, nullptr);
    pthread_join(t2, nullptr);
    pthread_join(t3, nullptr);

    return 0;
}


The above code is to simulate the scenario of multi-threaded ticket grabbing, but we will find that the number of tickets actually grabs -1, which is not allowed to exist. So why is this happening? In fact, when multiple threads access the same global variable and calculate it, if it is not protected, the threads will affect each other.

The reason for the problem: tickets > 0 The essence of the judgment is calculation, and the calculation needs to read the data in the memory into the register of the CPU, and the essence of reading the data into the register of the CPU is Read data into the context of the current execution flow. In this way, it is possible for multiple execution streams to judge that none of them is less than 0 and meet the judgment conditions, and then multiple execution streams perform subtraction operations to reduce the tickets to a negative number, and then there will be a negative number of tickets. In addition to this reason, there will also be problems with different data due to scheduling timing problems!



So how to solve this problem? In order to solve this problem, we need lock protection!

Mutex

To solve the above problems, three things need to be done:

  • The code must have mutual exclusion behavior: when the code enters the execution of the critical section, other threads are not allowed to enter the critical section.
  • If multiple threads request the execution of the code in the critical section at the same time, and no thread is executing in the critical section, only one thread is allowed to enter the critical section.
  • If a thread is not executing in a critical section, that thread cannot prevent other threads from entering the critical section.

To achieve these three points, a lock is essentially needed, and the lock provided by the Linux system is called a mutex.



When destroying a mutex, you need to pay attention to:

  • Mutexes initialized with PTHREAD_ MUTEX_ INITIALIZER do not need to be destroyed
  • Do not destroy a locked mutex
  • For the mutex that has been destroyed, make sure that no thread will try to lock it later

When calling pthread_mutex_lock, the following conditions may be encountered:

  • If the mutex is unlocked, this function will lock the mutex and return success at the same time.
  • When the function call is initiated, other threads have locked the mutex, or there are other threads applying for the mutex at the same time, but the mutex is not competed, then the pthread_mutex_lock call will be blocked (the execution flow is suspended), waiting for the mutex to be unlocked .

Note: When pthread_mutex_trylock applies for a lock, if the application is successful, it will return 0; if the application fails, it will return an error code immediately, and will not block waiting for the lock to be released.

Global mutex

#include <iostream>
#include <unistd.h>
#include <cstdio>
#include <pthread.h>

using namespace std;

// pthread_mutex_t is the data type provided by the native thread library
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER; // global mutex
int tickets = 10000; // critical resource

void* getTickets(void* args)
{<!-- -->
    (void) args;
    while(true)
    {<!-- -->
        // Only the thread that has acquired the lock can execute to enter the critical section and access critical resources
        pthread_mutex_lock( & amp;mtx); // lock protection
        // The code between locking and unlocking is the critical section
        if(tickets > 0)
        {<!-- -->
            usleep(1000);
            printf("%p: %d\\
", pthread_self(), tickets--);
            pthread_mutex_unlock( & amp;mtx); // unlock (release lock)
        }
        else
        {<!-- -->
            pthread_mutex_unlock( & amp;mtx); // unlock (release lock)
            break;
        }
        // cannot be unlocked here, because tickets is less than 0, it will jump out of the while loop
        // Unable to execute here, resulting in the lock not being released, and the rest of the threads cannot be acquired
        // Get the lock and block waiting

// After grabbing the tickets, follow-up actions are required
    }
    return nullptr;
}


int main()
{<!-- -->
    // Multi-thread grabbing tickets
    pthread_t t1, t2, t3;
    pthread_create( &t1, nullptr, getTickets, nullptr);
    pthread_create( &t2, nullptr, getTickets, nullptr);
    pthread_create( &t3, nullptr, getTickets, nullptr);

    pthread_join(t1, nullptr);
    pthread_join(t2, nullptr);
    pthread_join(t3, nullptr);

    return 0;
}

If all tickets are grabbed by one thread, you can increase the number of tickets or randomize the sleep time so that each thread can grab tickets.


Locking will lead to serial access (mutually exclusive access) of critical section code, so that the efficiency of code execution will be reduced. Therefore, when locking, ensure that the granularity of locking is as small as possible, and do not lock code that does not access critical section resources.

Local mutex

#include <iostream>
#include <unistd.h>
#include <cstdio>
#include <cassert>
#include <pthread.h>
#include <string>
#include <ctime>

using namespace std;

#define THREAD_NUM 5 // number of threads

class ThreadData
{<!-- -->
public:
    ThreadData(const string & tname, pthread_mutex_t* pmtx)
        : _tname(tname)
        , _pmtx(pmtx)
    {<!-- -->}

    string _tname;
    pthread_mutex_t* _pmtx;
};

int tickets = 10000; // critical resource

void* getTickets(void* args)
{<!-- -->
    ThreadData* td = (ThreadData*)args;
    while(true)
    {<!-- -->
        // Only the thread that has acquired the lock can execute to enter the critical section and access critical resources
        int n = pthread_mutex_lock(td->_pmtx); // lock
        assert(n == 0);
        (void)n;
        // The code between locking and unlocking is the critical section
        if(tickets > 0)
        {<!-- -->
            usleep(rand() % 2000);
            printf("%s: %d\\
", td->_tname.c_str(), tickets--);
            pthread_mutex_unlock(td->_pmtx); // unlock
        }
        else
        {<!-- -->
            pthread_mutex_unlock(td->_pmtx);
            break;
        }

        //Other logic after grabbing the ticket
        usleep(rand() % 2000);
    }

    delete td; // Release ThreadData when the number of votes is 0
    return nullptr;
}

int main()
{<!-- -->
    int begin = time(nullptr);
    pthread_mutex_t mtx;
    // The second parameter is the attribute of the lock, set it to nullptr to indicate that you don't care
    pthread_mutex_init( & amp;mtx, nullptr); // Initialize the lock

    pthread_t t[THREAD_NUM];
    for(int i = 0; i <thREAD_NUM; + + i)
    {<!-- -->
        string name = "thread";
        name + = to_string(i + 1);
        ThreadData* td = new ThreadData(name, &mtx);
        pthread_create(t + i, nullptr, getTickets, (void*)td);
    }

    for(int i = 0; i <thREAD_NUM; + + i)
    {<!-- -->
        pthread_join(t[i], nullptr);
    }

    
    pthread_mutex_destroy( & amp;mtx); // Destroy the lock
    int end = time(nullptr);
    // Output the time consumed by grabbing tickets
    cout << "time: " << end-begin << endl;
}


time returns the time at the second level, if you want to get the time at the microsecond level, you can use the gettimeofday function. Note: It does not mean that the more threads, the faster the ticket grabbing, because thread scheduling will also consume.

Further understanding of mutex

  • After adding the lock, the thread will also be switched in the critical section, but this will not be a problem. Because threads carry out thread switching with locks, other threads cannot apply for locks, and cannot enter the critical section to access critical resources.
  • Wrong coding method: the thread directly accesses the critical section resources without applying for a lock. In this case, even if other threads hold the lock, the thread can also enter the critical section.
  • From the perspective of a thread that does not hold a lock, there are only two situations that make the most sense for the thread: 1. Thread 1 does not hold the lock (do nothing), 2. Thread 1 releases the lock (done), and this When I can apply for a lock. Then while thread 1 holds the lock, all operations done are atomic to other threads!
  • After locking, the code executing the critical section must be executed serially!
  • To access critical resources, each thread must first apply for a lock, then each thread must first see the same lock and access it, so the lock itself is also a shared resource. Then the lock must also be protected. In order to protect the security of the lock, the operation of applying for and releasing the lock must be atomic!

How to ensure that the operation of applying and releasing the lock is atomic, in order to answer this question, we need to know how the lock is implemented!

Principle of mutual exclusion

If there is only one assembly instruction for an operation, then we can make the operation atomic! In order to realize the operation of the mutex, most architectures provide the swap or exchange instruction, which is used to exchange the data in the memory and the register in the CPU in the form of an assembly instruction. Since there is only one assembly instruction, the atomicity of applying for locks and releasing locks is guaranteed!

Reentrant and thread-safe

Concept

  • Thread safety: When multiple threads concurrently execute the same piece of code, different results will not appear. This problem occurs when global variables or static variables are commonly operated and there is no lock protection.
  • Reentrancy: The same function is called by different execution flows. Before the current process is executed, other execution flows enter again. We call it reentrance. A function is called a reentrant function if there is no difference in the running result or any problems in the case of reentrancy; otherwise, it is a non-reentrant function.

Common thread unsafe situations

  • Functions that do not protect shared variables
  • A function whose state changes as it is called
  • function returning a pointer to a static variable
  • Functions that call thread-unsafe functions

Common thread-safe situations

  • Each thread has only read access to global variables or static variables, but no write access. Generally speaking, these threads are safe
  • Classes or interfaces are atomic operations for threads
  • Switching between multiple threads will not cause ambiguity in the execution results of this interface

Common non-reentrant situations

  • The malloc / free function is called, because the malloc function uses a global linked list to manage the heap
  • calls to standard I/O library functions, many implementations of the standard I/O library use global data structures in a non-reentrant manner
  • Static data structures are used in reentrant function bodies

Common reentrant situations

  • Do not use global or static variables
  • Do not use the space created by malloc or new
  • Non-reentrant functions are not called
  • Does not return static or global data, all data is provided by the caller of the function
  • Use local data, or protect global data by making a local copy of global data

The relationship between reentrancy and thread safety

  • A function is reentrant, that is, thread-safe; a thread-safe function is not necessarily a reentrant function
  • The function is not reentrant, so it cannot be used by multiple threads, which may cause thread safety issues (for example: the printf function is not reentrant, and when multiple threads print data to the display, the data may stick together)
  • If a function has global variables, then the function is neither thread-safe nor reentrant

Deadlock

Concept

Deadlock refers to a kind of permanent waiting in which each process (thread) in a group of processes (threads) occupies resources that will not be released, but each other applies for resources that are occupied by other processes (threads) and will not be released. state.


Note: Two or more locks may cause a deadlock problem, but a single lock can also cause a deadlock problem (in special cases), as shown in the figure below:

Four necessary conditions for deadlock

  • Mutually exclusive conditions: a resource can only be used by one execution flow at a time
  • Request and Hold Conditions: When an execution flow is blocked by requesting resources, hold on to the obtained resources
  • Non-deprivation condition: the resource obtained by an execution flow cannot be forcibly deprived before it is used up
  • Circular waiting condition: A head-to-tail cyclic waiting resource relationship is formed between several execution flows

Avoid deadlock

  • Four necessary conditions for destroying deadlocks (destroying request and holding conditions: when using pthread_mutex_trylock to apply for locks for many times fails, release your own locks. Destroying non-deprivation conditions: according to certain conditions (priority, etc.) requirements Non-eligible threads release locks they own.)
  • The order of locking is the same
  • Avoid the scene where the lock is not released (release the lock immediately when the lock is used up, and reduce the scene where multiple threads hold the lock)
  • One-time allocation of resources

Deadlock avoidance algorithm

  • Deadlock detection algorithm (understand)
  • Banker’s Algorithm (understand)

Thread synchronization

Concept

Mutex locks have two unreasonable situations: 1. One thread frequently applies for locks, and others cannot apply for locks, which causes others to starve; 2. If we add a situation to multi-threaded ticketing, When the number of votes is 0, it will not exit immediately, but wait for the number of votes to increase. In the process of waiting for the number of votes to increase, threads will frequently apply for locks and release locks, which is too wasteful of resources and does not create any value. Both cases are not wrong, but they are not reasonable.

In order to solve the problem of rationality of accessing critical resources, the concept of synchronization is introduced! Race condition: When the program is abnormal due to timing problems, we call it a race condition. Thread synchronization: On the premise of ensuring data security, allowing threads to access critical resources in a specific order, thereby effectively avoiding starvation problems, is called synchronization. In order to complete thread synchronization, condition variables are needed.

Before we apply for critical resources, we must first check whether the critical resources exist. The essence of the detection is to access critical resources. Then the detection of critical resources must also be between locking and unlocking. The conventional method of detecting whether critical resources are ready means that we must frequently apply for and release locks.

Condition variable

In order to solve the problem of frequent application and release of locks, the following two points need to be done:

  • Don’t let the thread frequently check whether the resource is ready, but let the thread wait when the resource is not ready.
  • When the resource is ready, notify the threads waiting for the resource, and let these threads apply for and access the resource.

What can do the above two points is the condition variable. The condition variable can make up for the lack of the mutex by allowing the thread to block and wait for another thread to send a signal, so the mutex and the condition variable are usually used together.

Condition variable initialization and destruction


Wait for conditions to be met


Wake up waiting

#include <iostream>
#include <pthread.h>
#include <string>
#include <unistd.h>
#include <string>

#define THREAD_NUM 3
typedef void (*func_t)(const std::string &name, pthread_mutex_t *pmtx, pthread_cond_t *pcond);
volatile bool quit = false;

// pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
// pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

using namespace std;

class ThreadData
{<!-- -->
public:
    ThreadData(const string & amp; name, func_t func, pthread_mutex_t* pmtx, pthread_cond_t* pcon)
        : _name(name)
        , _func(func)
        , _pmtx(pmtx)
        , _pcon(pcon)
    {<!-- -->}

    string_name;
    func_t_func;
    pthread_mutex_t* _pmtx;
    pthread_cond_t* _pcon;
};

void func1(const string & name, pthread_mutex_t* pmtx, pthread_cond_t* pcon)
{<!-- -->
    while(!quit)
    {<!-- -->
        // Detect whether the critical resource is ready, it needs to be detected between locking and unlocking
        // wait must be done between locking and unlocking
        pthread_mutex_lock(pmtx);
        // if(critical resource is ready - no) pthread_cond_wait(pcon, pmtx);
        // The wait code is executed, the current thread will be blocked immediately, that is, the state of the thread becomes S, and it is put into the waiting queue
        // When the thread is woken up, there will be a certain wake-up sequence
        pthread_cond_wait(pcon, pmtx); // Don't need to care about pmtx now, it will be explained later
        cout << name << " running --- execute download task " << endl;
        pthread_mutex_unlock(pmtx);
    }
}

void func2(const string & name, pthread_mutex_t* pmtx, pthread_cond_t* pcon)
{<!-- -->
    while(!quit)
    {<!-- -->
        // wait must be done between locking and unlocking
        pthread_mutex_lock(pmtx);
        // wait code is executed, the current thread will be blocked immediately
        pthread_cond_wait(pcon, pmtx);
        cout << name << " running --- execute playback task " << endl;
        pthread_mutex_unlock(pmtx);
    }
}

void func3(const string & name, pthread_mutex_t* pmtx, pthread_cond_t* pcon)
{<!-- -->
    while(!quit)
    {<!-- -->
        // wait must be done between locking and unlocking
        pthread_mutex_lock(pmtx);
        // wait code is executed, the current thread will be blocked immediately
        pthread_cond_wait(pcon, pmtx);
        cout << name << " running --- execute refresh task " << endl;
        pthread_mutex_unlock(pmtx);
    }
}

void* Entry(void* args)
{<!-- -->
    ThreadData* td = (ThreadData*)args; // td is saved in the independent stack space of each thread
    td->_func(td->_name, td->_pmtx, td->_pcon); // it is a function, it will return after the call
    delete td; // release ThreadData
    return nullptr;
}

int main()
{<!-- -->
    pthread_mutex_t mtx;
    pthread_cond_t cond;
    pthread_mutex_init( &mtx, nullptr);
    pthread_cond_init( & amp; cond, nullptr);

    pthread_t tids[THREAD_NUM];
    func_t funcs[THREAD_NUM] = {<!-- -->func1, func2, func3};
    for(int i = 0; i <thREAD_NUM; + + i)
    {<!-- -->
        string name = "Thread";
        name + = to_string(i + 1);
        ThreadData* td = new ThreadData(name, funcs[i], & amp;mtx, & amp;cond);
        pthread_create(tids + i, nullptr, Entry, (void*)td);
    }
    
    sleep(5); // Sleep for 5 seconds, observe the phenomenon of waiting conditions
    int count = 10;
    while(count)
    {<!-- -->
        cout << "Wake up thread " << count-- << endl;
        pthread_cond_signal( & amp;cond); // wake up a process waiting on this condition
        // pthread_cond_broadcast( & amp;cond); // wake up all threads waiting on the condition
        sleep(1);
    }

    quit = true;
    pthread_cond_broadcast( & amp;cond); // finally need to wake up again

    // wait thread
    for(int i = 0; i <thREAD_NUM; + + i)
    {<!-- -->
        pthread_join(tids[i], nullptr);
        cout << "thread: " << tids[i] << " quit!" << endl;
    }
\t
// Destroy the lock and condition variable
    pthread_mutex_destroy( &mtx);
    pthread_cond_destroy( & amp;cond);

    return 0;
}

Summary

This blog mainly explains thread mutual exclusion, reentrancy and thread safety, deadlock and thread synchronization. So the above is the whole content of this blog. If you feel that you have gained something, you can support it by clicking three links! thank you all!