Semaphore
Semaphore (Semaphore) is the most typical method used for synchronization and mutual exclusion in the operating system. The value of the semaphore can be 0, 1 or n.
The semaphore corresponds to the classic concept PV operation in the operating system.
+ P(S): ① Decrease the value of the semaphore S by 1, that is, S=S-1; ②If S≥0, the process continues to execute; otherwise, the process is placed in a waiting state and placed in the waiting queue . + V(S): ①Add 1 to the value of the semaphore S, that is, S=S + 1; ②If S>0, wake up the process waiting for the semaphore in the queue. The operations related to semaphores in Linux mainly include the following types.
- 1. Define the semaphore
The following code defines a semaphore named sem:
struct semaphore sem;
- 2. Initialize the semaphore
void sema_init(struct semaphore *sem, int val);
This function initializes the semaphore and sets the value of the semaphore sem to val.
- 3. Get the semaphore
void down(struct semaphore * sem);
This function is used to obtain the semaphore sem, which will cause sleep, so it cannot be used in interrupt context.
int down_interruptible(struct semaphore * sem);
The function of this function is similar to down, the difference is that the process that enters the sleep state because of down() cannot be interrupted by the signal, but the process that enters the sleep state because of down_interruptible() can be interrupted by the signal, and the signal will also cause The function returns, and the return value of the function is not 0 at this time.
int down_trylock(struct semaphore * sem);
This function tries to obtain the semaphore sem, if it can be obtained immediately, it obtains the semaphore and returns 0, otherwise, returns a non-zero value. It does not cause the caller to sleep and can be used in interrupt context.
When using down_interruptible() to obtain a semaphore, the return value is generally checked. If it is not 0, it usually returns -ERESTARTSYS immediately, such as:
if (down_interruptible( & amp;sem))
return -ERESTARTSYS;
- 4. Release the semaphore
void up(struct semaphore * sem);
This function releases the semaphore sem and wakes up the waiter. As a possible means of mutual exclusion, the ** semaphore can protect the critical section, and it is used in a similar way to a spin lock. **Same as spin lock, Only the process that gets the semaphore can execute the critical section code. However, unlike the spin lock, when the semaphore cannot be obtained, the process will not spin in place but will enter a dormant waiting state. When used as a mutex, a semaphore is generally used like this:
Because the new Linux kernel tends to use mutex directly as a means of mutual exclusion, semaphores are no longer recommended for mutual exclusion.
Semaphores can also be used for synchronization. A process A executes down() to wait for the semaphore, and another process B executes up() to release the semaphore, so that process A waits for process B synchronously. The process is similar to:
In addition, for producer/consumer problems that care about specific values, using semaphores is more appropriate. Because the producer/consumer problem is also a kind of synchronization problem.
Mutex
Although the semaphore can already realize the function of mutual exclusion, the “authentic” mutex still exists in the Linux kernel.
The following code defines a mutex named my_mutex and initializes it:
struct mutex my_mutex; mutex_init( & my_mutex);
The following two functions are used to acquire a mutex:
void mutex_lock(struct mutex *lock); int mutex_lock_interruptible(struct mutex *lock); int mutex_trylock(struct mutex *lock);
The difference between mutex_lock() and mutex_lock_interruptible() is exactly the same as the difference between down() and down_trylock(). The sleep caused by the former cannot be interrupted by signals, while the latter can.
mutex_trylock() is used to try to obtain the mutex, and will not cause the process to sleep when the mutex is not obtained.
The following functions are used to release a mutex:
void mutex_unlock(struct mutex *lock);
The use of mutex is exactly the same as that of semaphore for mutual exclusion:
struct mutex my_mutex; /* define mutex */ mutex_init( & amp;my_mutex); /* initialize mutex */ mutex_lock( & amp;my_mutex); /* get mutex */ ... /* critical resources */ mutex_unlock( & amp;my_mutex); /* release mutex */
Spin locks and mutexes are the basic means to solve the mutual exclusion problem. Facing a specific situation, how should we choose between these two means? The choice is based on the nature of the critical section and the characteristics of the system.
Strictly speaking, mutexes and spin locks belong to different levels of mutual exclusion means, and the implementation of the former depends on the latter.
In the implementation of the mutex itself, in order to ensure the atomicity of the mutex structure access, a spin lock is required for mutual exclusion. So the spin lock is a lower-level means.
Mutexes are process-level and are used for mutual exclusion of resources between multiple processes. Although they are also in the kernel, the execution path of the kernel is to compete for resources on behalf of the process as a process of. If the race fails, a process context switch occurs, the current process goes to sleep, and the CPU runs other processes. In view of the high overhead of process context switching, it is a better choice to use a mutex only when the process occupies resources for a long time.
When the access time of the critical section to be protected is relatively short, it is very convenient to use a spin lock, because it can save the time of context switching. But if the CPU does not get the spin lock, it will idle there until other execution units are unlocked, so it is required that the lock cannot stay in the critical section for a long time, otherwise the efficiency of the system will be reduced.
From this, three principles for the selection of spin locks and mutexes can be summarized.
- 1) When the lock cannot be acquired, the cost of using the mutex is the process context switching time, and the cost of using the spin lock is waiting to acquire the spin lock (determined by the execution time of the critical section). If the critical area is relatively small, you should use a spin lock. If the critical area is large, you should use a mutex.
- 2) The critical section protected by the mutex can contain code that may cause blocking, and the spin lock must absolutely avoid being used to protect the critical section containing such code. Because blocking means switching processes, if another process tries to acquire the spin lock after the process is switched out, deadlock will occur.
- 3) The mutex exists in the process context, Therefore, if the protected shared resource needs to be used in the case of interrupt or soft interrupt, you can only choose between the mutex and the spin lock twist lock. Of course, if you must use a mutex, you can only do it through mutex_trylock(), and if you can’t get it, return immediately to avoid blocking. (Prevent interrupt signal from continuously sleeping and causing deadlock)
Completion
Linux provides the amount of completion (Completion, there is no good translation for this term so far, the author translates it as “the amount of completion”), It is used for one execution unit to wait for another execution unit to finish executing something.
There are mainly four types of operations related to the amount of completion in Linux.
- 1. Define Quantity Done
The following code defines a completion named my_completion:
struct completion my_completion;
- 2. The amount of initialization completed
The following code initializes or reinitializes the value of my_completion to 0 (that is, there is no completed state):
init_completion( &my_completion); reinit_completion( & my_completion)
- 3. Waiting for completion
The following functions are used to wait for a completion to be woken up:
void wait_for_completion(struct completion *c);
- 4. Amount of wake-up completion
The following two functions are used to wake up completions:
void complete(struct completion *c); void complete_all(struct completion *c);
The former only wakes up one waiting execution unit, and the latter releases all execution units waiting for the same completion amount.
The process for completing the synchronization is generally as follows:
