• Synchronization mode between threads
    • The introduction
    • The mutex
      • Explore the bottom layer and implement a lock
        • Test and lock (TAS)
        • Compare and exchange (CAS)
        • Another problem, too much spin?
      • Back to the mutex
    • A semaphore
      • Named semaphore
      • Unknown semaphore
      • conclusion
    • Condition variables,
      • What is a conditional variable?
      • Correlation function
        • 1. Initialization
        • 2. Wait for conditions
        • 3. Notification conditions
      • Usage and Thinking
    • Practice – Reader locks

This article has been included in my repository: Java Learning Notes and free book sharing

Synchronization mode between threads

The introduction

Access to critical resources between different threads can cause common concurrency problems. We want threads to execute a series of instructions atomically, but because of interrupts on a single processor, we have to find other ways to synchronize threads. This article describes some ways to synchronize threads.

The mutex

A mutex (also known as a mutex) is a resource access mutex. When a thread occupies a resource, it cannot be accessed by another thread until it unlock the resource.

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
Copy the code

Note that the trylock function is different from the normal lock function, which blocks the resource while it is locked until the lock is released.

The trylock function is non-blocking, which means that if the mutex is not locked, the trylock function locks the mutex and gains access to the shared resource. If the mutex is locked, the trylock function will not block the wait but return EBUSY, indicating that the shared resource is busy, thus avoiding extreme situations such as deadlock or starvation.

Explore the bottom layer and implement a lock

Implementing a lock requires hardware support, because we must ensure that the lock is also concurrency safe, which requires hardware support to ensure that the lock is implemented atomically inside.

It is easy to think of maintaining a global flag variable that, when 0, allows threads to lock and sets flag to 1. Otherwise, the thread must hang and wait until flag is 0.

typedef struct lock_t {
    int flag;
}lock_t;

void init(lock_t &mutex) {
    mutex->flag = 0;
}

void lock(lock_t &mutex) {
    while (mutex->flag == 1) {; }// Spin waits for a variable of 0 to enter
    mutex->flag = 1;
}

void unlock(lock_t &mutex) {
    mutex->flag = 0;
}
Copy the code

This is a preliminary software-based implementation, initializing the variable to 0 and waiting for the thread spin variable to be 0 before entering. This may not seem like a problem, but if you think about it, it is:

When the thread is interrupted by the while judgment, the flag is not set to 1, and another thread intrudes into the critical area. When the thread is judged by the while, the thread is interrupted and returns to the original thread, which continues to execute and also enters the critical area. This causes synchronization problems.

In the while loop, it’s not enough to just set mutex->flag == 1. Even though it’s a primitive, we have to have more code, and when we introduce more code, we have to make sure it’s atomic, which means we need hardware support.

So why did the code fail? The reason is that when exiting the while loop, the flag is still zero at that point, giving another thread the opportunity to steal the critical section.

The solution is also straightforward — use hardware support to ensure that flag is set to 1 when exiting the while.

Test and lock (TAS)

We write the following function:

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}
Copy the code

Also reset the while loop:

void lock(lock_t &mutex) {
    while(TestAndSet (mutex - > flag,1) = =1) {; }// Spin waits for a variable of 0 to enter
    mutex->flag = 1;
}
Copy the code

Here, we use hardware to ensure that the TestAndSet function is executed atomically, and now the lock can be used correctly. When flag is 0, we have already set flag to 1 during the while test, and no other thread can enter the critical section.

Compare and exchange (CAS)

We write the following function:

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected) {
        *ptr = new;
    }
    return actual;
}
Copy the code

Similarly, hardware should also support CAS primitives to ensure that CAS is also secure inside. Now reset while:

void lock(lock_t &mutex) {
    while(CompareAndSwap (mutex - > flag,0.1) = =1) {; }// Spin waits for a variable of 0 to enter
    mutex->flag = 1;
}
Copy the code

Now the lock works correctly. When flag is 0, we set flag to 1 during the while test, and no other thread can enter the critical section.

In addition, you may find that CAS requires more registers, which you’ll find nice when you study synchronozation in the future.

Another problem, too much spin?

You might find that even though a thread failed to acquire the lock, it continues to use CPU resources in a while loop. One way to do this is if the thread fails to acquire the lock, it goes to sleep to release CPU resources (condition variables), and when a thread releases the lock, it wakes up a sleeping thread. It also takes time to go into sleep and wake up a lock. When a thread can release the lock quickly, waiting is a better option than falling into sleep.

In Linux, a two-stage lock is used. In the first stage, the thread spins for a certain time or number of times to wait for the lock to be released. When the time or number reaches a certain period, the thread enters the second stage and enters sleep.

Back to the mutex

Mutex provides a basic guarantee of concurrency security. Mutex is used to guarantee safe access to a critical section resource, but when a mutex needs to access a resource is not a matter for the mutex. It may be a matter for condition variables.

If the thread is locked and unlocked frequently, it is very inefficient, and this is a point we must take into account.

A semaphore

It is important to understand that the semaphore is not used to transmit resources, but to protect shared resources. The representation of the semaphore S is the maximum number of threads allowed to access resources at the same time. It is a global variable.

Semaphores can also be used in processes, and are understood in the same way as in threads, to protect resources. For more information on semaphores, see JavaLearningNotes/ Interprocess Communication.

Consider the simple example above: two threads modify at the same time and cause an error. We do not consider the reader but only the writer process. In this example, sharing resources allows at most one thread to modify resources, so we initialize s to 1.

At the beginning, A writes resources first. At this time, A calls P(s) and subtracts S by one. At this time, S = 0, A enters the shared area to work.

At this point, thread B also wants to enter the shared area to modify resources. It calls P(s) and finds that s is 0, so it suspends the thread and joins the waiting queue.

When A is done, V(s) is called. It finds that S is 0 and detects that the wait queue is not empty, so it wakes up A random wait thread and increases S by 1, which wakes up B.

B wakes up and continues to perform P. At this time, S is not 0. B successfully sets S to 0 and enters the workspace.

At this point C wants to enter the workspace……

You can see that only one thread can access a shared resource at any time. This is what the semaphore does. It controls the maximum number of processes that can enter the shared area, depending on the value of initialization s. After that, the P operation is called before entering the shared area, and the V operation is called after exiting the shared area. This is the idea of semaphore.

Named semaphore

Named semaphores exist in the form of files that can be accessed even by threads between different processes, so they can be used for mutual exclusion and synchronization between multiple threads between different processes.

Create an open named semaphore

sem_t *sem_open(const char *name, int oflag);
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
// Successfully return semaphore pointer; If SEM_FAILED is returned on failure, set errno
Copy the code

Name is the file pathname and value is set to the initial value of the semaphore.

Close the semaphore, which is called when the process terminates

int sem_close(sem_t *sem);	// Returns 0 on success; On failure, return -1 and set errno
Copy the code

To delete a semaphore, delete the semaphore name immediately and destroy it when all other processes have closed it

int sem_unlink(const char *name);
Copy the code

Wait for the semaphore, tests the value of the semaphore and waits (blocks) if its value is less than or equal to zero; As soon as its value becomes greater than 0, it is subtracted by 1 and returned

int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
// Returns 0 on success; On failure, return -1 and set errno
Copy the code

When the semaphore value is 0, sem_trywait immediately returns with errno set to EAGAIN. If interrupted by a signal, sem_wait returns prematurely, setting errno to EINTR

Emits a semaphore, increments its value by one, and then wakes up the process or thread that is waiting on the semaphore

int sem_post(sem_t *sem);
Copy the code

Returns 0 on success; Error returns -1 without changing its value. Set errno. This function is asynchronous signal-safe and can be called in a signal handler

Unknown semaphore

Nameless semaphores exist in virtual space within a process and are not visible to other processes. Therefore, nameless semaphores are used for mutual exclusion and synchronization between threads within a process, using the following API:

(1) Sem_init function: used to create a semaphore and initialize the value of the semaphore. Function prototype:

int sem_init (sem_t* sem, int pshared, unsigned int value);
Copy the code

The function passed in values: sem: semaphore. Pshared: Determines whether a semaphore can be shared among several processes. Since LINUX does not currently share information between processes, this value can only be 0.

(2) Other functions

int sem_wait       (sem_t* sem);
int sem_trywait   (sem_t* sem);
int sem_post       (sem_t* sem);
int sem_getvalue (sem_t* sem);
int sem_destroy   (sem_t* sem);
Copy the code

Function:

Sem_wait and sem_trywait are equivalent to P operations in that they both reduce the semaphore value by one. The difference is that sem_wait blocks if the semaphore value is less than zero, while sem_trywait returns immediately.

Sem_post is equivalent to the V operation, which increments the semaphore value by one and sends a wake up signal to the waiting thread.

Sem_getvalue gets the semaphore value.

Sem_destroy Destroys the semaphore.

If a memory-based semaphore is synchronized between different processes, the semaphore must reside in a shared memory area as long as the shared memory area exists.

conclusion

Nameless semaphores live in memory, and named semaphores live on disk, so nameless semaphores are faster, but only for individual threads within a single process. Named semaphores can be slow but can synchronize threads between different processes through shared memory, which is a means of communication between processes.

As you may have noticed, when the semaphore value s is 1, the effect of the semaphore on the mutex is the same. The mutex allows only one thread to enter the critical region, while the semaphore allows more threads to enter the critical region, depending on the semaphore value.

Condition variables,

What is a conditional variable?

In a mutex, the thread waits for flag 0 to enter the critical section; P operations in the semaphore also wait for s not to be 0…… In multithreading, it is common for a thread to wait for a condition. In the section on mutex implementation, is there a more specialized and efficient way to wait for a condition using spin?

It’s the conditional variable! Condition variable is a mechanism to synchronize global variables shared between threads. It mainly includes two actions: one thread suspends itself until a condition is true; The other thread sets the condition to true and tells the waiting thread to continue.

Because a condition is a global variable, condition variables are often protected by a mutex (this is mandatory and mandatory).

Condition variables, when used with mutex, allow threads to wait in an uncontested manner for a particular condition to occur.

Threads can use condition variable to wait for a condition is true, pay attention to understand and not waiting on the condition variable is true, condition variables (cond) is in a multithreaded program to implement “wait — > wake up” the in common use method of logic, to maintain a condition () with the concept of condition variables is different, is not to say that waiting on the condition variable is true or false. The condition variable is an explicit queue. When the condition is not met, the thread adds itself to the queue and releases the mutex it holds. When a thread changes a condition, it can wake up one or more waiting threads (note that the condition may not be true).

There are two basic operations on conditional variables:

  • Wait: A thread sleeps in a wait queue, does not occupy the mutex, and, when awakened, reobtains the mutex (possibly in contention with multiple threads) and reobtains the mutex.
  • Signal /notify: When a condition changes, another thread sends a notification to wake up the thread in the waiting queue.

Correlation function

1. Initialization

The condition variable takes the data type pthread_cond_t, and must be initialized before it can be used. This can be done in two ways:

Static: Directly set the condition variable cond to the constant PTHREAD_COND_INITIALIZER.

Dynamic: the pthread_cond_init function cleans up a dynamic condition variable with pthread_cond_destroy before freeing its memory.

int pthread_cond_init(pthread_cond_t *restrict cond, pthread_condattr_t *restrict attr);
int pthread_cond_destroy(pthread_cond_t *cond);
// Return 0 on success, error number on error.
Copy the code

Note: The space occupied by the condition variable is not freed.

Cond: condition variable to initialize; Attr: The value is usually NULL.

2. Wait for conditions

int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restric mutex);
int pthread_cond_timedwait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex, const struct timespec *restrict timeout);
// Return 0 on success, error number on error.
Copy the code

These two functions are respectively blocking wait and timeout wait, blocking until entering the wait queue sleep until the condition is modified to wake up; Timeout wait Automatically wakes up after a certain period of sleep.

The thread releases the mutex when it enters the wait, and regains the lock when it wakes up.

3. Notification conditions

int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);
// Return 0 on success, error number on error.
Copy the code

These two functions are used to notify the thread that the condition has been modified, and they are called to send signals to the thread or condition.

Usage and Thinking

Conditional variable usage template:

pthread_cond_t cond;  // Condition variable
mutex_t mutex;	/ / the mutex
int flag; / / conditions

/ / A thread
void threadA(a) {
    Pthread_mutex_lock(&mutex);  // Protect critical resources because threads modify the global condition flag
    while (flag == 1) // Wait for a condition to be true
        Pthread_cond_wait(&cond, &mutex);  // If no, join the queue for sleep and release the lock. dosomthing .... change flag// The condition is modified
    Pthread_cond_signal(&cond); // Send signal notification condition changed
    Pthread_mutex_unlock(&mutex); Release the lock as quickly as possible after the signal is released, since the awakened thread will try to acquire the lock
}


/ / thread B
void threadB(a) {
    Pthread_mutex_lock(&mutex);  // Protect critical resources
    while (flag == 0) // Wait for a condition to be true
        Pthread_cond_wait(&cond, &mutex);  // If no, join the queue for sleep and release the lock. dosomthing .... change flag// The condition is modified
    Pthread_cond_signal(&cond); Release the lock as quickly as possible after the signal is released, since the awakened thread will try to acquire the lock
    Pthread_mutex_unlock(&mutex);
}
Copy the code

The difference between a condition variable and a condition should be understood from the example above. A condition variable is logic, it is not a bool statement in a while loop. I believe many beginners have the misconception that a condition variable is a condition that a thread has to wait for. A condition is a condition, and a thread waits for a condition instead of waiting for a condition variable, and a condition variable makes a thread more efficient for waiting conditions, which is a set of wait-wake logic.

Note that you still have to use the while loop to wait for the condition, and you might think that the lock is already locked and that no other thread can force in. When thread A into dormancy release the lock, and when the awakened, will try to get the lock, and are its trying to get the lock, another thread B now try to get the lock, and rob to lock into the critical region, and then modify the conditions, make the thread A condition was established, no longer thread B returns, the thread A finally gets the lock, and into the critical region, But thread A’s condition is no longer valid, it should not enter the critical section!

In addition, being awakened does not mean that the condition is established. For example, the code thread B changes flag = 3 and wakes up thread A, where the condition of thread A does not meet at all, so the condition must be repeated. The example of mutex and condition variables tells us that when waiting for a condition, always use while instead of if!

It also makes sense that a dormant thread must release the lock, because without releasing the lock, no other thread can modify the condition at all, and the dormant thread never wakes up!

Practice – Reader locks

Read lock — share; Write lock — exclusive. That is, the reader thread can add more than one, while the writer thread can have only one, and the reader and writer cannot work at the same time.

In this case, since it is efficient to allow multiple readers to share the critical section, let’s consider the implementation problem: if only one writer is allowed to work, a mutex or binary semaphore must be maintained, which we call the writer lock; Due to the reader and the writer can’t work at the same time, must try to get the first readers to write locks, and once the reader number greater than 1, the subsequent readers do not need to try to get to write locks and can directly enter, noticed that there is a global readership variables, so the reader is also need a lock to safeguard global readership, the last exit lock must be responsible for releasing readers.

Know the principle, go and implement a reader lock yourself!

Linux through the pthread_rwlock function family implementation.