1. Linux Concurrency Features
Linux, as a typical multi-user, multi-task, and preemptive kernel scheduling operating system, requires special mechanisms to ensure task correctness and system stability in both the kernel and user layers to improve parallel processing capabilities.
At the kernel level, it involves various software and hardware interrupts, thread sleeping, preemptive kernel scheduling, and multi-processor SMP architecture, so the kernel is constantly dealing with resource contention conflicts while completing its work.
At the user level, processes, although Linux operates in virtual address mode and allocates independent virtual address space for each process, pseudo-solely owning resources, still face many scenarios where multiple processes need to share resources to complete inter-process communication.
At the thread level, threads, as part of a process, have only their own independent stack and a small amount of structure, while most resources are shared among threads, making resource occupation conflicts in multi-threading more pronounced, so thread safety in multi-threaded programming is a difficult point.
In summary, whether in the kernel or user space, there must be mechanisms to solve resource sharing problems, and these mechanisms are what will be discussed next: synchronization and mutual exclusion.
2. Synchronization and Mutual Exclusion Mechanisms in Linux
Synchronization and mutual exclusion mechanisms are used to control the access strategy of multiple tasks to specific resources; synchronization controls multiple tasks to access shared resources in a certain order or rule; mutual exclusion controls shared resources to only allow a specified number of tasks to access at any given time.
To understand synchronization and mutual exclusion well, it is necessary to clarify several important terms:
Race hazard or race condition
The earliest encounter with this term was in the course of analog and digital electronics, where gate circuits appeared with race conditions, causing incorrect results. In computers, it refers to multiple users operating on shared variables simultaneously, causing uncertain results.Critical section
The critical section is the part of the code that multiple users may operate on simultaneously, such as increment and decrement operations. When multiple threads process it, they need to protect the increment and decrement operations, and this code segment is the critical section.
3. Commonly Used Locks in Linux
Mutex Mutual Exclusion Lock
When using a mutex, the user must perform a locking operation before accessing shared resources and an unlocking operation after accessing is complete. The entity that locks must also be the one to unlock, and other users do not have the permission to unlock. After locking, any other thread that attempts to lock again will be blocked until the current process unlocks. Unlike spinlocks, mutexes will block and sleep when unable to acquire a lock, requiring the system to wake them up. However, in reality, this is not always the case, as many business logic systems are unaware of this and still require business threads to execute while loops to poll whether they can re-lock. Consider a situation where multiple threads are blocked when unlocking, so all threads on that lock are set to a ready state. The first thread to become ready will then perform a locking operation, causing other threads to enter a waiting state again. From the perspective of other threads, this is a false wake-up. In this way, only one thread can access the resource protected by the mutex.Spinlock
The main characteristic of a spinlock is that when a user wants to acquire execution permission for a critical section, if the critical section is already locked, the spinlock will not block and sleep, waiting for the system to wake it up. Instead, it will busy-wait in place, polling whether the resource has been unlocked. The name "spinlock" is quite intuitive. Spinlocks have their advantages, such as avoiding system wake-ups and executing polls themselves. If the code for the resources in the critical section is very short and atomic, using spinlocks is very convenient, avoiding various context switches with very small overhead. Therefore, spinlocks are widely used in some data structures in the kernel.Semaphore
Whether it's a mutex or a spinlock, they both limit the number of threads that can acquire critical section resources to one at any given time. However, in some scenarios, critical section resources can be accessed simultaneously by multiple threads, which is where semaphores come in.
In Linux, the definition of a semaphore is very similar to that of a mutex, both containing a spinlock that protects the structure and a wait queue "wait_list".
struct semaphore {
raw_spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};
A semaphore is without an "owner", it only needs an identifier to indicate the number of shared resources, hence it is also known as a counting semaphore.
As long as the value of the "count" corresponding to the semaphore is greater than 0, the thread can successfully obtain the semaphore, but it will decrease the number of threads that can enter the critical section (corresponding to the "count" value minus 1), so its function name is down(). Based on the existing problem with mutex_lock() (cannot be interrupted by a signal), down_interruptible() is actually used more often. If the value of "count" is less than or equal to 0, it means that the number of threads that can enter the critical section is already full, so new threads can only join the "wait_list" waiting queue and enter a dormant state.
If the waiting queue is empty, releasing the semaphore will increase the number of threads that can enter the critical section (corresponding to the "count" value plus 1). Otherwise, it needs to wake up the first waiter thread in the waiting queue. When a thread tries to obtain a semaphore, it may enter sleep due to insufficient resources, but releasing a semaphore will not, so up() can be used, and there is no need for functions like "up_interruptible()".
Mutex and Semaphore: In a sense, a mutex can be seen as a special semaphore with a "count" value that can only be 0 or 1, that is, a binary semaphore. However, strictly speaking, there are some differences between mutex and binary semaphore.
A semaphore can no longer be considered a lock. For a true lock like a mutex, the principle of "who locks, who unlocks" must be followed. This limits the use of mutex to some extent, such as interactions between the kernel and user space, but it is also less prone to errors.
rwlock Read-Write Lock
Read-write locks are also called shared mutexes: read mode is shared, and write mode is mutually exclusive. This is very reasonable, because as long as the data is not being written, multiple readers do not need to lock. Read-write locks have three states: read-locked, write-locked, and unlocked. When a read-write lock is in write-locked mode, any thread that tries to lock it will be blocked until the write process unlocks it.
Read-Priority Read-Write Lock: The default read-write lockrwlockis also read-priority, that is, when the read-write lock is in read-locked mode, any thread can perform a read lock operation, but all threads that try to perform a write lock operation will be blocked until all read threads are unlocked. Therefore, read-write locks are very suitable for situations where the number of reads is much larger than the number of writes. This situation needs to consider the problem of writer starvation, that is, a large number of reads always precede writes, so a fair read-write strategy needs to be set.RCU Lock
Read Copy Update Lock, read-copy-update lock, is an extension of the read-write lock. Simply put, it supports multiple reads and multiple writes to lock simultaneously. Multiple reads are not a problem, but for multiple writes to lock simultaneously, there are still some technical challenges. Copy: when the writer accesses the critical section, the writer first copies a copy of the critical section, and then modifies the copy; Update: the RCU mechanism will use a callback function to redirect the pointer to the original critical section to the new modified critical section at an appropriate time. Update timing: after no CPU is operating on this RCU-protected critical section, this critical section can be recycled, and the callback function is called at this time. From the implementation logic, the RCU lock has a relatively large synchronization overhead between multiple writers, involving multiple data copies and callback functions. Therefore, the use of this lock mechanism is relatively narrow, suitable for situations where reads are much more frequent than writes, such as querying and updating network routing tables, updating device status tables, etc. It is not used much in business development.Conditional Variable
A conditional variable is used to wait for a thread rather than locking. It is usually used with a mutex. A obvious feature of a mutex is that in some business scenarios, it cannot rely on the system to wake up, and the business code still needs to usewhileto judge, which is relatively inefficient. The conditional variable makes up for the deficiency of the mutex by allowing threads to block and wait for another thread to send a signal. Therefore, mutexes and conditional variables are usually used together to allow conditional variables to asynchronously wake up blocked threads.
The typical use of conditional variables and mutexes is the producer-consumer model, which is a very classic model and is often asked in interviews. Example code:
#include <stdio.h>
#include <pthread.h>
#define MAX 5
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t notfull = PTHREAD_COND_INITIALIZER; //是否队满
pthread_cond_t notempty = PTHREAD_COND_INITIALIZER; //是否队空
int top = 0;
int bottom = 0;
void* produce(void* arg)
{
int i;
for ( i = 0; i < MAX*2; i++)
{
pthread_mutex_lock(&mutex);
while ((top+1)%MAX == bottom)
{
printf("full! producer is waiting
");
//等待队不满
pthread_cond_wait(notfull, &mutex);
}
top = (top+1) % MAX;
//发出队非空的消息
pthread_cond_signal(notempty);
pthread_mutex_unlock(&mutex);
}
return (void*)1;
}
void* consume(void* arg)
{
int i;
for ( i = 0; i < MAX*2; i++)
{
pthread_mutex_lock(&mutex);
while ( top%MAX == bottom)
{
printf("empty! consumer is waiting
");
//等待队不空
pthread_cond_wait(notempty, &mutex);
}
bottom = (bottom+1) % MAX;
//发出队不满的消息
pthread_cond_signal(notfull);
pthread_mutex_unlock(&mutex);
}
return (void*)2;
}
int main(int argc, char *argv[])
{
pthread_t thid1;
pthread_t thid2;
pthread_t thid3;
pthread_t thid4;
int ret1;
int ret2;
int ret3;
int ret4;
pthread_create(&thid1, NULL, produce, NULL);
pthread_create(&thid2, NULL, consume, NULL);
pthread_create(&thid3, NULL, produce, NULL);
pthread_create(&thid4, NULL, consume, NULL);
pthread_join(thid1, (void**)&ret1);
pthread_join(thid2, (void**)&ret2);
pthread_join(thid3, (void**)&ret3);
pthread_join(thid4, (void**)&ret4);
return 0;
}
The use of pthread_cond_wait is a point that needs attention: pthread_cond_wait() first unlocks the mutex and then blocks until a signal is sent by pthread_signal(), after which pthread_cond_wait() locks the mutex again before exiting.
若无法加载请检查网络环境。
若无法加载请检查网络环境，或切回 Disqus 稍后再试。