[Linux] thread mutual exclusion

Article directory

    • Ticket grabbing system
    • mutex
    • Mutex interface function
      • Initialize the mutex: pthread_mutex_init
      • Destroy the mutex: pthread_mutex_destroy
      • Mutex lock – pthread_mutex_lock
      • Mutex unlock – pthread_mutex_unlock
    • Locked version ticket grabbing system
      • Precautions
  • Exploration of Mutex Realization Principle
    • Precautions:

remember

  • Critical resources: The resources shared by multi-threaded execution flows are called critical resources
  • Critical section: Inside each thread, the code that accesses critical resources is called a critical section
  • Mutual exclusion: At any time, mutual exclusion guarantees that only one execution flow enters the critical area, accesses critical resources, and usually protects critical resources
  • Atomicity: An operation that will not be interrupted by any scheduling mechanism. This operation has only two states, either completed or not completed

Example: Critical Resources and Critical Sections

If we want to communicate between processes, we need to create a third-party resource first, so that different processes can see the same resource. This third-party resource can be provided by different modules in the operating system, so there are many ways to communicate between processes

The third-party resources in inter-process communication are called critical resources, and the code that accesses third-party resources is called critical section

Because most of the resources of multi-threading are shared, communication between threads does not require so much effort to create third-party resources

  • Example: We define a global variable count, the new thread executes the count ++ operation every 1s, and the main thread gets the value of the count variable every 1s for printing
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
int count = 0;
void* Routine(void* arg)
{<!-- -->
while (1)
    {<!-- -->
count + + ;
sleep(1);
}
}
int main()
{<!-- -->
pthread_t tid;
pthread_create( &tid, NULL, Routine, NULL);
while (1)
    {<!-- -->
printf("count: %d\\
", count);
sleep(1);
}
pthread_join(tid, NULL);
return 0;
}

At this point, we are equivalent to realizing the communication between the main thread and the new thread, where the global variable count is called a critical resource, because it is shared by multiple execution streams

The location of accessing the critical resource count is the critical area: printf in the main thread and count ++ in the new thread are called critical areas

image-20220826095404805

About Mutex and Atomicity

1) In the case of multi-threading, if these multiple execution streams operate on critical resources on their own, then data inconsistency may occur at this time. The solution to this problem is called mutual exclusion, the role of mutual exclusion is to ensure that at any time, only one execution flow enters the critical section to access critical resources

2) Atomicity refers to an indivisible operation that will not be interrupted by any scheduling mechanism. The operation has only two states, either completed or not completed

Ticket Grabbing System

We simulate and implement a ticket grabbing system: define a class Ticket, the main thread creates 5 threads to grab tickets, and these 5 threads automatically exit when the tickets are robbed

class Ticket
{<!-- -->
public:
    Ticket():tickets(1000){<!-- -->}
    ~Ticket(){<!-- -->}
    
    bool GetTicket()
    {<!-- -->
        bool res = true;
        if(tickets>0)
        {<!-- -->
            usleep(1000); //1s == 1000ms 1ms = 1000us
            std::cout << "I am [" << pthread_self() << "] The ticket I want to grab is: " << tickets << std::endl;
            tickets--;
            printf("");
        }
        else
        {<!-- -->
            printf("The ticket has been sold out\\
");
            res = false;
        }
        return res;
    }
private:
    int tickets;
};

void* ThreadRun(void* args)
{<!-- -->
    Ticket* t = (Ticket*)args;
    while(1)
    {<!-- -->
        if(!t->GetTicket())
        {<!-- -->
            break;//There is no ticket to exit
        }
    }
}
int main()
{<!-- -->
    Ticket *t = new Ticket();

    pthread_t tid[5];
    //Create 5 threads
    for(int i = 0; i < 5; i ++ )
    {<!-- -->
        int *id = new int(i);
        pthread_create(tid + i, nullptr, ThreadRun, (void*)t);
    }
    // thread waiting
    for(int i = 0 ; i < 5; i ++ )
    {<!-- -->
        pthread_join(tid[i], nullptr);
    }
    return 0;
}

The result of the operation obviously did not meet our expectations, because there was a situation where the remaining votes were negative

image-20220826101647283

At this time, the tickets variable is a critical resource, because it is accessed by multiple execution flows at the same time, and the codes to judge whether tickets are greater than 0, print the remaining tickets and --tickets are critical areas, because these codes are critical resource was accessed

Reasons for negative numbers:

  • After the if statement judges the condition to be true, the code can switch to other threads concurrently, and then there is no break

  • usleep is used to simulate a long business process. In this long business process, many threads may enter the code segment

  • --ticket(ticket--) operation itself is not an atomic operation

Q: Why is --ticket(ticket--) not atomic?

To perform -- on a variable, the following three steps are actually required

  • load : Load the shared variable ticket from memory into the register
  • update : Update the value in the register, and then perform -1 operation
  • store: Write the new value from the register back to the memory address of the shared variable ticket

image-20220826102856002

The corresponding assembly code:

image-20220826103015972

Because the process needs 3 steps to complete, the following situations will exist:

1) When thread1 has just read the value of tickets into the CPU, it is cut off, that is, it is stripped off from the CPU, assuming that the value read by thread1 is 1000 at this time, and when thread1 is cut off, 1000 in the register is called The context information of thread1, so it needs to be saved, and then thread1 is suspended

2) Assuming that thread2 is scheduled at this time, since thread1 only performs the first step of the -- operation, thread2 sees that the value of tickets is still 1000 at this time, and the time slice given by the system to thread2 may be Many, causing thread2 to execute 100 times -- at one time before being cut off, and finally the tickets were reduced from 1000 to 900

3) At this time, the system restores thread1 again. The essence of the restoration is to continue to execute the code of thread1, and to restore the hardware context information of thread1. At this time, the value in the register is restored to 1000, and then thread1 continues to execute-- The second and third steps of the operation, and finally write 999 back to the memory

image-20220826104828263

In the above process, thread1 grabbed 1 ticket, thread2 grabbed 100 tickets, and the remaining number of tickets at this time is 999, which is equivalent to 100 more tickets

Therefore, the -- operation on a variable is not atomic. Although --tickets seems to be one line of code, this line of code is essentially three lines of code after being compiled by the compiler. On the contrary, performing + + on a variable also requires corresponding three steps, that is, the + + operation is not an atomic operation

mutex mutex

  • In most cases, the data used by the thread is a local variable, and the address space of the variable is in the thread stack space. In this case, the variable belongs to a single thread (in the thread’s own stack structure), and other threads cannot obtain this variable.

    • So ask: Is the above bool variable res shared by all threads?

      • no! , although each thread will execute the GetTicket function, but res is a local variable, which is opened on the stack! -> Privately owned by the thread in the thread’s own thread stack

  • But sometimes, many variables need to be shared between threads. Such variables become shared variables, and the interaction between threads can be completed through data sharing.

  • Multiple threads concurrently operate shared variables, which will cause some problems

To solve the above problems of the ticket grabbing system, three things need to be done:

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

To achieve these three points, you need a lock in essence. The lock provided on Linux is called a mutex

Specific process:

image-20220826141209485

Mutex interface function

Initialize the mutex: pthread_mutex_init

The function to initialize the mutex is: pthread_mutex_init

#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);

Parameter Description

The first parameter: the mutex that needs to be initialized

The second parameter: initialize the properties of the mutex, generally set to empty

Return value description

Returns 0 if the initialization succeeds, returns an error code if it fails

Note: Calling the pthread_mutex_init function to initialize a mutex is called dynamic allocation. We can also use the following static allocation to initialize a mutex

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

Destroy the mutex: pthread_mutex_destroy

The function to destroy the mutex is called pthread_mutex_destroy

#include <pthread.h>
int pthread_mutex_destroy(pthread_mutex_t *mutex);

Parameter Description

mutex: the mutex that needs to be destroyed

Return value description

If the mutex is destroyed successfully, it returns 0, and if it fails, it returns an error code.

Precautions:

  • 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

Mutex lock-pthread_mutex_lock

The function of mutex locking is called pthread_mutex_lock

#include <pthread.h>
int pthread_mutex_lock(pthread_mutex_t *mutex);

Parameter Description

mutex: the mutex that needs to be locked

Return value description

Mutex lock successfully returns 0, failure returns an error code

Note: When calling pthread_mutex_lock, you may encounter the following situations

1) The mutex is in an unlocked state, this function will lock the mutex and return successfully

2) 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 blocked pending), waiting for the mutex to be unlocked

Mutex unlock-pthread_mutex_unlock

The function to unlock the mutex is called pthread_mutex_unlock

#include<pthread.h>
int pthread_mutex_unlock(pthread_mutex_t *mutex);

Parameter Description

mutex: the address of the mutex that needs to be unlocked

Return value description

If the unlock is successful, it will return 0, and if it fails, it will return an error code.

Locked version ticket grabbing system

We introduce a mutex into the above-mentioned ticket grabbing system. Each thread must apply for a lock before entering the critical section. Only the thread that has applied for the lock can enter the critical section to access critical resources. When the lock needs to be released, so that the rest of the threads to enter the critical section continue to compete for the lock

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

class Ticket
{<!-- -->
public:
    Ticket(): tickets(1000)
    {<!-- -->
        pthread_mutex_init( & amp;mtx, nullptr);//Initialize the mutex
    }
    ~Ticket()
    {<!-- -->
        pthread_mutex_destroy( & amp;mtx);//Destroy the mutex
    }
    
    bool GetTicket()
    {<!-- -->
        bool res = true;
        pthread_mutex_lock( & amp;mtx); // lock
        //Access critical resource tickets
        if(tickets>0)
        {<!-- -->
            usleep(1000); //1s == 1000ms 1ms = 1000us
            std::cout << "I am [" << pthread_self() << "] The ticket I want to grab is: " << tickets << std::endl;
            tickets--;
            printf("");
        }
        else
        {<!-- -->
            printf("The ticket has been sold out\\
");
            res = false;
        }

        pthread_mutex_unlock( & amp;mtx);//unlock
        return res;
    }
private:
    int tickets;
    pthread_mutex_t mtx;//mutex lock
};

void* ThreadRun(void* args)
{<!-- -->
    Ticket* t = (Ticket*)args;
    while(1)
    {<!-- -->
        if(!t->GetTicket())
        {<!-- -->
            break;//There is no ticket to exit
        }
    }
}
int main()
{<!-- -->
    Ticket *t = new Ticket();

    pthread_t tid[5];
    //Create 5 threads
    for(int i = 0; i < 5; i ++ )
    {<!-- -->
        int *id = new int(i);
        pthread_create(tid + i, nullptr, ThreadRun, (void*)t);
    }
    // thread waiting
    for(int i = 0 ; i < 5; i ++ )
    {<!-- -->
        pthread_join(tid[i], nullptr);
    }
    return 0;
}

At this time, in the process of grabbing tickets, there will be no situation where the remaining number of votes is negative

image-20220826145026355

We can also use C++ built-in library functions to lock and unlock: import: #include

class Ticket
{<!-- -->
public:
    Ticket():tickets(1000){<!-- -->}
    ~Ticket(){<!-- -->}
    
    bool GetTicket()
    {<!-- -->
        bool res = true;
        mymtx.lock();//lock

        //Access critical resource tickets
        if(tickets>0)
        {<!-- -->
            usleep(1000); //1s == 1000ms 1ms = 1000us
            std::cout << "I am [" << pthread_self() << "] The ticket I want to grab is: " << tickets << std::endl;
            tickets--;
            printf("");
        }
        else
        {<!-- -->
            printf("The ticket has been sold out\\
");
            res = false;
        }
        mymtx.unlock();//unlock
        return res;
    }
private:
    int tickets;
    std::mutex mymtx;//language-level mutex
};

void* ThreadRun(void* args)
{<!-- -->
    Ticket* t = (Ticket*)args;
    while(1)
    {<!-- -->
        if(!t->GetTicket())
        {<!-- -->
            break;//There is no ticket to exit
        }
    }
}
int main()
{<!-- -->
    Ticket *t = new Ticket();

    pthread_t tid[5];
    //Create 5 threads
    for(int i = 0; i < 5; i ++ )
    {<!-- -->
        int *id = new int(i);
        pthread_create(tid + i, nullptr, ThreadRun, (void*)t);
    }
    // thread waiting
    for(int i = 0 ; i < 5; i ++ )
    {<!-- -->
        pthread_join(tid[i], nullptr);
    }
    return 0;
}

Comparison of mutexes in native thread library and C++ language-level mutexes:

pthread_mutex_t vs std::mutex
    
pthread_mutex_t mtx; //Native thread library, system level
std::mutex mymtx; //C++ language level

The bottom layer of the language level must encapsulate the system level

Notes

  • In most cases, locking itself is detrimental to performance. It changes the multi-execution flow from parallel execution to serial execution, which is almost inevitable.
  • We should lock and unlock in the right place, so as to reduce the performance overhead cost of locking as much as possible
  • The protection of critical resources is a standard that all execution flows should abide by. At this time, programmers need to pay attention when coding

Discussion on the Principle of Mutex Implementation

Where is the atomicity after locking?

After the mutex is introduced, when a thread applies for a lock and enters the critical section, it appears to other threads that the thread has only two states.Either the lock has not been applied for, or the lock has been released, because only these two states are Other threads are meaningful

For example: when thread 1 enters the critical section, from the perspective of threads 2~5, thread 1 either does not apply for a lock, or thread 1 has released the lock, because only these two states are meaningful to threads 2~5 , when threads 2~5 detect other states, they are blocked

At this time, for threads 2~5, they think that the entire operation process of thread 1 is atomic

image-20220826150411315

Question 2: Is it possible for threads in the critical section to switch threads?

It is entirely possible for threads in the critical section to switch threads, but even if the thread is switched away, other threads cannot enter the critical section for resource access

Because the thread is cut off with the lock at this time, if the lock is not released, it means that other threads cannot apply for the lock, and cannot enter the critical section for resource access

Other threads that want to enter the critical area for resource access must wait for the thread to execute the code in the critical area and release the lock before applying for the lock, and then entering the critical area after applying for the lock

Whether the lock needs to be protected

Locks are also essentially critical resources

  • A resource shared by multiple execution streams is called a critical resource, and code that accesses a critical resource is called a critical section
  • Threads must compete to apply for locks before entering the critical section, so locks are also resources shared by multiple execution flows, so locks themselves are critical resources

Since the lock is a critical resource, the lock must be protected, but the lock itself is used to protect the critical resource, so who will protect the lock?

The lock actually protects itself, we only need the process of locking and unlocking to be atomic, then the lock is safe

How to ensure that locking and unlocking are atomic

  • We have explained above that -- and + + operations are not atomic operations, which may cause data inconsistency
  • In order to achieve mutual exclusion lock operation, most architectures provide swap or exchange instruction, the function of this instruction is to exchange the data of register and memory unit
  • Since there is only one instruction, the atomicity is guaranteed ** (one line of code is atomic: –> only one line of assembly code) ** Even on a multi-processor platform, the bus cycles for accessing memory are sequential, and the exchange on a processor While the instruction is executing, the exchange instruction from the other processor can only wait for the bus cycle

Pseudocode about lock and unlock:

image-20220826150934255

When a thread applies for a lock, it needs to perform the following steps: (Assume that the initial value of the current mutex is 1, al is a register)

  1. First clear the value in the al register to 0
    • This action can be executed by multiple threads at the same time, because each thread has its own set of registers (save context information), and executing this action is essentially clearing its al register to 0
  2. Then exchange the values in the al register and mutex, (xchgb is an exchange instruction provided by the architecture, which can complete the exchange of data between registers and memory units)
  3. Finally, determine whether the value in the al register is greater than 0
    • If it is greater than 0, the lock application is successful, and you can enter the critical area to access the corresponding critical resources
    • Otherwise, if the application lock fails, it needs to be suspended and wait until the lock is released and then compete for the application lock again

For example: At this time, the value of mutex in the memory is 1. When the thread applies for a lock, first clear the value in the al register to 0, and then exchange the value in the al register with the value of mutex in the memory.

image-20220826152450300

After the exchange is completed, it is detected that the value of the al register of the thread is 1, and the thread applies for the lock successfully, and can enter the critical area to access critical resources

If the following thread applies for the lock again, the value obtained by exchanging with the mutex in the memory is 0. At this time, the thread fails to apply for the lock and will be suspended and wait until the lock is released and then compete to apply for the lock again

image-20220826152605194

When the thread releases the lock:

  1. Set the mutex in memory back to 1
    • So that the next thread that applies for the lock can get 1 after executing the exchange instruction, which is to say “put the key of the lock back”
  2. Wake up the thread waiting for mutex
    • Wake up these threads that are suspended due to failure to apply for locks, and let them continue to compete for locks

Notes:

  • When applying for a lock, it is essentially which thread executes the exchange instruction first, then the thread applies for the lock successfully, because the value in the al register of the thread is 1 at this time
    • The exchange instruction is just an assembly instruction -> it is atomic. A thread either executes the exchange instruction or does not execute the exchange instruction, so the process of applying for the lock is atomic
  • When the thread releases the lock, the value in the al register of the current thread is not cleared to 0, which will not affect
    • Because every time a thread applies for a lock, it will first clear the value in its al register to 0, and then execute the exchange instruction
  • **The registers in the CPU are not shared by all threads,**Each thread has its own set of registers
    • But the data in the memory is shared by each thread
    • Applying for a lock is actually to atomically swap the mutex in the memory to its own al register through the swap instruction