Synchronization and Task Scheduling in the Linux Kernel

Summary: The concept of synchronization has been fully interpreted in multithreading and multiprocess programming. Synchronization methods are simple to use for user applications, without having to think too much about the reasons they are generated (the only reason is that threads or processes are concurrent). However, the synchronization process in the kernel is much more complicated. The developer must know how the tasks in the kernel are scheduled to effectively control the synchronization in the kernel. So this article will combine kernel task scheduling, analyze the synchronization measures in the kernel, and combine an example to describe how to use various synchronization methods in the kernel.

Concurrency, Competition, and Synchronization: The concepts of concurrency, competition, and synchronization, we assume that everyone knows, and this article does not repeat. The focus of our discussion is on what happens when the kernel is concurrency? How to prevent kernel concurrency? What are the synchronization methods? And what are the characteristics of these methods and how do they use them?

The following paragraph describes the general relationship between the above concepts, which is also applicable in the kernel.

For multi-threaded developers, multi-threaded access to shared data is often used to avoid cumbersome interprocess communication. However, multi-threaded concurrent access to shared data is likely to cause competition, making the data in an inconsistent state, so some synchronization methods are needed to protect the shared data. Multithreaded concurrent execution is due to thread preemptive scheduling —— one thread is interrupted by the scheduler during shared data access (not yet completed), put another thread into operation —— if newly scheduled Threads also have to access this shared data, which will create competition. In order to avoid competition, it is necessary to make the thread serially access the shared data, that is, the access needs to be synchronized —— after one party has finished accessing the data, the other party can access the same data.

Core Concurrency Causes The above situation is a common cause of user space concurrency. For the kernel, the reasons for concurrency are similar, but the situation is more diverse and more complicated.

The situation is relatively simple for a single processing machine. Prior to the 2.6 kernel, the Linux kernel was non-preemptive —— it could not be interrupted until the kernel task was executed. In this case, the concurrent execution of the program in the kernel is rare. There are only two possibilities: Br>

One: Interrupts occur because interrupt execution is asynchronous, and interrupts are the only way to interrupt the current running kernel code in a non-preemptive kernel, so interrupts can obviously be executed concurrently with other kernel code. So if the interrupt operation and the interrupted kernel code access the same kernel data, then competition will occur.

Two: sleep and re-schedule, the kernel task in the process context (described below) can sleep (sleep means giving up the processor), then the scheduler will schedule other programs to execute (first execute the scheduled task) Kernel tasks in the queue, then perform soft interrupts, etc., and finally select a high-priority user process from the run queue to run). Obviously, this will also cause concurrent access by the kernel. When the sleeping kernel task and the newly launched kernel task access the same shared data, competition occurs. See Resources 1

The 2.6 kernel becomes a preemptive kernel —— the kernel may preempt the running kernel code at any time. So the situation of concurrent execution in the kernel has greatly increased. Kernel preemption has become another possibility for kernel program concurrency, so you need to be wary of preemption competition when developing preemptive kernel code.

Concurrency on a single processor is a logical pseudo-concurrency. In fact, the so-called concurrent kernel program actually uses the processor in an interleaved manner. True concurrent execution programs must rely on symmetric multiprocessors. But whether it is logical concurrency or true concurrency, there will be competition, and their processing is the same. But for symmetric multiprocessors, since two or more processors can execute code at the same time, it is inevitable to bring concurrency to the kernel, if the kernel code executed on different processors simultaneously access the same Sharing data, competition is created. Therefore, it goes without saying that symmetric multiprocessing is another possibility of kernel concurrency. Please refer to the reference 2

. As the Linux kernel continues to evolve, the kernel supports the system more comprehensively, and the task scheduling is more efficient. At the same time, it also brings more concurrency to the kernel. Easy to cause competition. The various concurrency situations mentioned above must be effectively handled in the kernel to ensure high stability of the kernel.

Concurrent concurrency due to interrupts or concurrency caused by sleep, or concurrency caused by kernel preemption, in order to be well avoided in kernel development, you must understand their concurrency reasons in essence. Only after mastering the scheduling mechanism of the kernel task can you truly achieve the possible prediction of concurrency, and then you can adopt the appropriate synchronization method ——lock—— to avoid concurrency.

We will discuss the task scheduling below. Contrast the conditions generated by the concurrency, analyze the conditions under which the scheduling in the kernel occurs.

Task scheduling in the kernel: The task scheduling we are talking about here is different from the process scheduling that is often said. Process scheduling is: The scheduler in the kernel selects the appropriate (high priority) process execution in the process run queue. What we mean by kernel task scheduling means that tasks in the kernel get execution opportunities. For kernel concurrency, the relationship between kernel tasks is especially important.

First, let's take a look at the tasks that the kernel has, and what are the characteristics of each.

Core Task Type Hard Interrupt Operation:

A hard interrupt is an interrupt generated by a peripheral other than the processor. These interrupts are received by the processor and passed to the interrupt handler in the kernel. deal with. It should be noted that: First, the hard interrupt is generated asynchronously, and the interrupt is processed immediately after the interrupt occurs, that is, the interrupt operation can preempt the running code in the kernel. This point is very important. Second, interrupt operations occur in the context of interrupts (so-called interrupt contexts refer to contexts that are independent of any process). In the interrupt context, process-related resources cannot be used and cannot be scheduled. See Reference 2

Soft Interrupt Operation:

Soft Interrupt is a post-push execution mechanism in Linux that performs some hard interrupt operations beyond the time it is completed. Because interrupts during hard interrupt operations are discarded, hard interrupts run at unsafe times. Unsafe time should be as short as possible, so soft interrupts are used to perform most tasks. It pushes time-consuming tasks that can't be completed by hard interrupts to safe time execution (the interrupt signal is not discarded during soft interrupts).

A soft interrupt can be executed at any time, like a hard interrupt. In general, a soft interrupt will be processed before returning to the user-level program after the kernel processing task has been processed. Specifically, there are three times when it will be executed (do_softirq()): after the hardware interrupt operation is completed; in the kernel scheduler; when the system call returns, (the other kernel thread ksoftirqd cycle executes the soft interrupt). It should be noted that the execution of the soft interrupt is also in the interrupt context, so the interrupt context limits it to be the same as the hard interrupt.

Tasklet and bottom half

Tasklet and bottom half are two kinds of delay mechanisms built on soft interrupts, the specific difference is that soft interrupts are statically allocated, and similar soft interrupts can be Concurrently running on several CPUs; Tasklets can be dynamically allocated, and different kinds of Tasklets can run on several CPUs concurrently, but similar tasklets can't; bottom half can only be statically allocated, essentially the lower half is one. High-priority tasklets that execute concurrently with the other lower half, even if they are of different types and run on different CPUs.