Linux kernel design and implementation - kernel synchronization

Kernel Synchronization

Introduction to Synchronization

Concept of Synchronization

Critical section: Also known as a critical section, it is a code segment that accesses and manipulates shared data.

Competitive conditions: When two or more threads are executed simultaneously in a critical section, they constitute a race condition.

Synchronization prevents the formation of competitive conditions in critical sections.

If there is an atomic operation in the critical section (that is, it will not be interrupted before the entire operation is completed), then there will naturally be no competition conditions. However, in practical applications, the code in the critical section is often not so simple, so in order to maintain synchronization, the lock mechanism is introduced. But there will be some problems with locks.

Deadlock-generated condition: There must be one or more execution threads and one or more resources, each of which is waiting for one of the resources, but all resources are already occupied. So threads wait for each other, but they never release resources that they already have. So any thread can't continue, and a deadlock occurs.

Self-dead lock: If an execution thread tries to acquire a lock that it already holds, it has to wait for the lock to be released. But because it is busy waiting for this lock, it will never have a chance to release the lock, and a deadlock will occur.

Starvation is a phenomenon in which a thread cannot get the resources it needs for a long time and cannot execute it.

Causes of Concurrency

Interrupt —— Interrupts can happen asynchronously at any time, that is, you can interrupt the currently running code at any time.

Soft Interrupts and Tasklets —— The kernel can wake up or schedule interrupts and tasklets at any time, interrupting the code currently executing.

Kernel Preemption —— Because the kernel is preemptive, tasks in the kernel may be preempted by another task.

Synchronization of sleep and user space —— The process executing in the kernel may sleep, which wakes up the scheduler and causes a new user process to be scheduled for execution.

Symmetric Multiprocessing —— Two or more processors can execute code at the same time.

Simple rules to avoid deadlocks

The order of locking is the key. When using nested locks, you must ensure that locks are acquired in the same order, which prevents deadlocks of the deadly hug type. It is best to record the order of the locks so that others can use them in this order.

Prevent hunger from happening. Determine if the execution of this code will end. If A does not happen, does B have to wait all the time?

Do not request the same lock repeatedly.

The more complex the locking scheme, the more likely it is to cause a deadlock. --- Design stress should be simple.

The granularity of the lock

The granularity of the lock is used to describe the size of the data protected by the lock. An overly thick lock protects large blocks of data, such as all data structures of a subsystem; an overly thin lock protects small pieces of data, such as an element in a big data structure.

When locking, not only to avoid deadlocks, but also to consider the granularity of locking.

The granularity of the lock has a great impact on the scalability of the system. When locking, consider whether the lock will be frequently used by multiple threads.

If the lock is likely to be frequently contending, you need to refine the granularity of the lock.

The refinement of the lock will improve performance in the case of multiprocessors.

Synchronization Methods

Atomic Operations

Atomic operations refer to operations that are not interrupted by other code paths during execution. Kernel code can safely call them. Without being interrupted.

Atomic operations are divided into integer atomic operations and bit atomic operations.

spinlock spin lock

The characteristic of a spin lock is that when a thread acquires a lock, other threads trying to acquire the lock are waiting in a loop to acquire the lock until the lock is available again.

Since the thread actually loops to acquire this lock, it will cause a waste of CPU processing time, so it is best to use the spin lock for the critical section that can be processed quickly.

There are 2 points to note when using spin locks:

1. Spin locks are not recursive, and recursive requests with the same spin lock will lock themselves.

2. Before the thread acquires the spin lock, it is necessary to disable the interrupt on the current processor. (Preventing the thread and interrupt that acquires the lock to form a race condition) For example, after the current thread acquires the spin lock, it is interrupted by the interrupt handler in the critical section, and the interrupt handler just needs to acquire the lock, so the interrupt handler will wait for the current The thread releases the lock, and the current thread is also waiting for the execution of the interrupt before executing the critical section and releasing the lock code.

The use of spin locks in the lower half of interrupt handling requires special care:

1. When the lower half processes and the process context shares data, the lower half of the processing can preempt the process. The code of the context, so the process context must prohibit the execution of the lower half before locking the shared data, and then allow the execution of the lower half when unlocking.

2. When the interrupt handler (top half) and the lower half process shared data, the interrupt processing (upper half) can preempt the execution of the lower half, and the lower half is added to the shared data. Interrupt processing (upper half) is prohibited before the lock, and interrupt execution is allowed when unlocking.

3. The same tasklet cannot run at the same time, so the shared data in the same tasklet does not need to be protected.

4. When sharing data in different class tasklets, one of the tasklets does not need to prohibit the execution of other tasklets after the lock is acquired, because there will be no tasklet preemption on the same processor

5. Soft interrupts of the same type or different types do not need to disable the lower half when sharing data, because there will be no soft interrupts preempting each other on the same processor

Read-write spin lock

If the data protected by the critical section is readable and writable, then concurrent operations can be supported for reading as long as there is no write operation. For this requirement that only write operations are mutually exclusive, if you still use a spin lock, you obviously cannot meet this requirement (it is too wasteful for read operations). For this purpose, the kernel provides another lock-read-and-write spin lock. The read spin lock is also called a shared spin lock. The write spin lock is also called an exclusive spin lock.

Read-write spin lock is a lock mechanism that is smaller than the spin lock granularity. It retains the concept of "spin", but in writing, there can only be at most one write process. In terms of read operations, there can be multiple read execution units at the same time. Of course, read and write cannot be performed simultaneously.

Spin locks provide a quick and easy way to achieve this. If the lock time is not long and the code does not sleep, using a spin lock is the best choice. If the lock time can be long or the code is likely to sleep while holding the lock, it is best to use the semaphore to complete the lock function.

Semaphores

A semaphore in Linux is a type of sleep lock. If a task attempts to acquire an already occupied semaphore, the semaphore pushes it into a wait queue. Then let it sleep, then the processor can regain freedom to execute other code, and when the semaphore process releases the semaphore, which task in the waiting queue is woken up and gets the semaphore.

1) Since the process of contention semaphore sleeps while waiting for the lock to become available again, the semaphore applies when the lock is held for a long time; on the contrary, when the lock is held for a short time The use of semaphores is not very suitable. The cost of sleeping, maintaining the wait queue, and waking up may be longer than the total time the lock is occupied.

2) Since the execution thread sleeps when the lock is contending, the semaphore lock can only be obtained in the process context because it cannot be scheduled in the interrupt context. 3) You can go to sleep while holding a semaphore, because when other processes try to get the same semaphore, they won't be deadlocked (because the process just goes to sleep and will continue to execute).

4) You can't take up spin locks while you're taking up semaphores. Because you may sleep while waiting for a semaphore, and you are not allowed to sleep while holding a spin lock.

5) The semaphore allows for any number of lock holders at the same time, while the spin lock allows up to one task to hold it at a time. The reason is that the semaphore has a count value, for example, the count value is 5, which means that 5 threads can access the critical section at the same time. If the initial value of the semaphore starts at 1, this semaphore is the mutual semaphore (MUTEX). For non-zero value semaphores greater than 1, it can also be referred to as counting semaphore. The semaphores used by general drivers are mutually exclusive semaphores.

The semaphore supports two atomic operations: P/V primitive operations (also called down and up operations):

P: If the semaphore value is greater than 0, the semaphore is decremented The value of the program continues to execute, otherwise, the sleep wait semaphore is greater than zero.

V: The value of the increment semaphore. If the value of the incremented semaphore is greater than 0, the waiting process is woken up.

There are two versions of the down operation, which are interruptible for sleep and sleep uninterrupted.

Read-Write Semaphore

The relationship between read-write semaphores and semaphores is similar to the relationship between read-write spin locks and ordinary spin locks.