Lowering Latency in Linux: Introducing a Preemptible Kernel

Whether you seek higher scores in Quake, are an audio enthusiast or want a smoother desktop, lowering latency in the kernel is an important goal.
The Results

Thus, with the preemptive kernel patch, we can reschedule tasks as soon as they need to be run, not only when they are in user space. What are the results of this?

Process-level response is improved twentyfold in some cases. (See Figure 1, a standard kernel, vs. Figure 2, a preemptible kernel.) These graphs are the output of Benno Senoner's useful latencytest tool, which simulates the buffering of an audio sample under load. The red line in the graphs represents the amount of latency beyond which audio dropouts are perceptible to humans. Notice the multiple spikes in the graph in Figure 1 compared to the smooth low graph in Figure 2.

Figure 1. Result of a Latency Test Benchmark on a Standard Kernel

Figure 2. Result of a Latency Test Benchmark on a Preemptible Kernel

The improvement in latencytest corresponds to a reduction in both worst-case and average latency. Further tests show that the average system latency over a range of workloads is now in the 1-2ms range.

A common complaint against the preemptible kernel centers on the added complexity. Complexity, opponents argue, decreases throughput. Fortunately, the preemptive kernel patch improves throughput in many cases (see Table 1). The theory is that when I/O data becomes available, a preemptive kernel can wake an I/O-bound process more quickly. The result is higher throughput, a nice bonus. The net result is a smoother desktop, less audio dropout under load, better application response and improved fairness to high-priority tasks.

Table 1. Throughput Test: dbech Runs

Changes to Programming Semantics

Kernel hackers are probably thinking, “How does this affect my code?” As discussed above, the preemptible kernel leverages existing SMP support. This makes the preemptible kernel patch relatively simple and the impact to coding practices relatively minor. One change, however, is required. Currently, per-CPU data (data structures unique to each CPU) do not require locking. Because they are unique to each CPU, a task on another CPU cannot mangle the first CPU's data. With preemption, however, a process on the same CPU can find itself preempted, and a second process can then trample on the data of the first. While this normally is protected by the existing SMP locks, per-CPU data does not require locks. Data that does not have a lock, because it is protected by its nature, is considered to be “implicitly locked”. Implicitly locked data and preemption do not get along. The solution, thankfully, is simple: disable preemption around access to the data. For example:

int catface[NR_CPUS];
catface[smp_processor_id()] = 1;  /* index catface
                                     by CPU number */
/* operate on catface */

The current preemption patch provides protection for the existing implicitly locked data in the kernel. Thankfully, it is relatively infrequent. New kernel code, however, will require protection if used in a preemptible kernel.

Work for the Future

We still have work to do. Once the kernel is preemptible, work can begin on reducing the duration of long-held locks. Because the kernel is nonpreemptible when a lock is held, the duration locks are held corresponding to the system's worst-case latency. The same work that benefits SMP scalability (finer-grained locking) will lower latency. We can rewrite algorithms and locking rules to minimize lock held time. Eradicating the BKL will help too.

Identifying the long-held locks can be as difficult as rewriting them. Fortunately, there is the preempt-stats patch that measures nonpreemptibility times and reports their cause. This tool is useful for pinpointing the cause of latency for a specific workload (e.g., a game of Quake).

What is needed is a goal. Kernel developers need to consider any lock duration that extends over a certain threshold, a bug for example, 5ms on a reasonably modern system. With that goal in mind, we can pinpoint and ultimately eliminate the areas of high latency and lock contention.



Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

AH! I get it now.

Wo_Dao's picture

Hmm, this explains why some distros are slow or fast. Lunar Linux allows a Preemptiblle kernel. And it's just lightning fast without any bloat. Hmm, put this option with other distros...and perhaps...*ZOOM ZOOM ZOOM*

Just a rambling thought...anyways, this article comes in handy while deciding on kernel configuration in the unix console.. :p Keep it around!!


Manjunath MB's picture

Thanks Robert,
nicely explained...

spinlocks in preemptible kernel

San's picture


The information here is very helpful. thanks.

I have one question.

What is the effect of having kmalloc calls in the code that is protected with spinlock in a preemptible kernel.

kernel preemption

Anonymous's picture

Excellent article, explains well. So that's where all kernel preemption stuff in 2.6 come from!

One question I always had was when the process is in kernel execution path (system call execution), doesn't scheduler_tick decrement its timeslice, and if it does when the timeslice is over, doesn't the scheduler preempts the current process, even though it might be in the middle of the kernel exec path?

Re: Lowering Latency in Linux: Introducing a Preemptible Kernel

Anonymous's picture

It's helpful for me to understand the preemptive kernel.


Seminar on your topic

Pavan Boob's picture

I am studying in final year of computer engg at MIT .
I read your extract and you will be glad to know that I have taken the same topic for a technical seminar at our college.I thereby request you to please send me some more technical details and direct me to some inportant links
waiting for your positive reply.