In this interview, Linux Journal chats with Robert Love, the principal maintainer of an increasingly popular kernel-preemption patch that improves the real-time responsiveness of the Linux kernel. Robert describes his role in the project, explains why the preemption enhancement is important to a broad range of Linux applications beyond just embedded/real-time (including end-users' desktops) and shares his vision of the future of Linux in the embedded and desktop markets.
Rick You have been becoming well known as the maintainer of a preemptible kernel patch for the Linux kernel. How did that situation come about?
Robert I am interested in innovative ideas, and the preemptible kernel is a very neat concept. The idea was first talked about during 2.3 (we finally had a kernel that had fine-grained enough locking that it was doable)--Linus actually outlined the first design. MontaVista released a patch in this time frame and worked on it through the early days of 2.4.
About this time I tried the patch, rediffed it to the newest kernel and starting making changes. I eventually posted them. People started trying it, and use of the patch took off. I've been working hard since.
Rick What is different between what you have done and what was (or is) being done by MontaVista Software with their preemptible kernel patch? Are you now collaborating with them, and if so, how closely?
Robert The patch I am maintaining now is MontaVista's. They still put time into the patch, and I work closely with a couple of their engineers. Obviously it has evolved a lot since I got involved, but it's still their work. I believe they are using the latest release in their product.
Rick As I understand it, your interest in the preemptible kernel is for reasons that would tend to be of interest to a broader range of Linux applications such as streaming of audio/video, etc., as opposed to the embedded/real-time system focus of MontaVista. Is this accurate? Can you give some examples of the sorts of applications that your patch can noticeably improve the performance of?
Robert This is correct. I see a preemptible kernel as a means to an overall better system. Besides the traditional markets for low latency (audio/video, specialized embedded/real-time, etc.), a preemptive kernel can benefit any interactive task. The result is hopefully a smoother, more responsive desktop.
Rick With the preemptible kernel patch added, does Linux outperform what the latest versions of MS Windows can offer to desktop, enterprise and embedded users?
Robert I've got no idea how we perform compared to Windows. I'd certainly say even earlier versions of Linux were superior to Windows 9x. How we compare to Windows NT (i.e., 2000 and XP) for desktop performance is hard to measure.
The latency of the kernel certainly can be measured—scheduling latency, jitter, etc., are quantitative—but the quality of the desktop only begins with the kernel. That means X and everything on top of it factors in, too.
Rick When Red Hat announced that they were going to use RTLinux to provide real-time capabilities to their customers, both Mike Tiemann (CTO of Red Hat) and Alan Cox went on record to say that real time doesn't belong in the kernel. Would you care to comment on that?
Robert Red Hat has an agenda here, and I tend to disregard any technical comments when there is bias. There are benefits to the hard real-time interrupt-driven approach, I don't deny, but that solution is not Linux. I think Linux can become a contender in the embedded/real-time market without giving up on itself, while still being a UNIX and having the standard Linux API. In fact, I think a lot of the technologies that achieve this could live right in the official kernel. Kernel preemption is one such innovation, and it's an innovation that does not benefit solely real-time applications.
Rick Have you seen any indication from Linus or other key kernel maintainers that your patch (or the MontaVista patch) is being seriously considered for the 2.5 kernel? What do you think the chances are that it will get incorporated into 2.5 or 2.6?
Robert Linus said at ALS [Annual Linux Showcase] this year  that he was interested in the preemptible kernel patch. That doesn't mean anything to me until we are in, but it is a good sign. There is opposition. There are various issues that need to be dealt with. I believe it is a sane move for 2.5. The patch has seen a lot of testing, and we have a lot of users. I do not want to predict whether it will be merged for 2.5. Time will tell. [Subsequent to this interview, the announcement was made that Linus has merged the patch into the main Linux development-kernel tree, beginning with version 2.5.4-pre6.]
Rick Please summarize the advantages in general, not just for embedded real-time applications, of having the preemptible kernel enhancement included in the kernel. What about any disadvantages?
Robert I'll start with a quick explanation of how the patch works. Right now, the kernel is not preemptible. This means that code running in the kernel runs until completion, which is the source of our latency. Although kernel code is well written and regulated, the net result is that we effectively have an unbounded limit on how long we spend in the kernel. Time spent in kernel mode can grow to many hundreds of milliseconds. With some tasks demanding sub-5ms latencies, this non-preemptibility is a problem.
The preemptible kernel patch changes all this. It makes the kernel preemptible, just like user space. If a higher-priority task becomes runnable, the preempt patch will allow it to run. Wherever it is. We can preempt anywhere, subject to SMP- [symmetric multiprocessing] locking constraints. That is, we use spin locks as markers for regions of preemptibility. Of course, on UP [uni-processing] they aren't actually spin locks, just markers.
The improvement to response is clear: a high-priority task can run as soon as it needs to. This is a requisite of real-time computing, where you need your real-time task to run the moment it becomes runnable. But the same effect applies to normal interactive tasks: as soon as an event occurs (such as the user clicking the mouse) that marks it runnable, it can run (subject to the non-preemptible regions, of course).
There are some counter arguments. The first is that the preemptible kernel lowers throughput because it introduces complexity. Testing has showed, however, that it improves throughput in nearly all situations. My hypothesis is that the same quicker response to events that helps interactivity helps throughput. When I/O data becomes available and a task can be removed from a wait queue and continue doing I/O, the preemptible kernel allows it to happen immediately—as soon as the interrupt that set need_resched returns, in fact. This means better multitasking.
There are other issues, too. We have to take care of per-CPU variables, now. In an SMP kernel, per-CPU variables are implicitly locked—they don't have explicit locks, but because they are unique to each CPU, a task on another CPU can't touch them. Preemption makes it an issue because a preempted task can trample on the variables without locks.
Overall, I think the issues can be addressed, and we can have a preemptible kernel as a proper solution to latency in the kernel.
Rick From your brief explanation of how the preemptible kernel does its business, I get the impression that nothing new needs be done on a user's system other than installing the modified kernel in order to gain benefits. Specifically, if I were to install the patched kernel on my desktop system, would I immediately begin noticing performance improvements during my work (and play) on the system, such as doing work during downloads or burning CDs while listening to streaming audio or watching streaming video? Or, do I need to have applications that can take advantage of the kernel's preemption capability? Would it be necessary to alter the priority of the apps I run, or make any other adjustments?
Robert You don't have to do anything. The preemptible kernel patch requires no change in user applications, environment or API. The change (from switching to a preemptible kernel) should be immediate. Your normal programs and your normal benchmarks will show latency improvements. Renicing your programs would help, just because they would be able to reap the benefits of preemption more readily (anything they need to do could cause a preemption).
This is why I see elegance in this solution; Linux can be made more RT without abandoning itself.
Rick Please describe yourself, what you do and what your interests are. Also, what is your background relative to Linux and your philosophy with respect to open-source software?
Robert I am a student at the University of Florida studying mathematics and computer science, originally from South Florida. I first used Linux six or seven years ago with an early Slackware release. I've run nothing but Linux for the past couple years.
Outside of computing I'm really into rock music, good food and the military-industrial complex.
My philosophy with respect to open source is that of a pragmatist. While I enjoy the freedom of the code and certainly appreciate the rights gained from free software, I see the biggest benefit in merely having open code. I can see it; I can fix it; I can play with it. With enough momentum, open source creates amazing software. I am very proud of our kernel.
Rick Approximately how much time per week do you spend working on your kernel patch for Linux?
Robert My girlfriend would probably say too much. Anywhere from a couple hours a week to many hours a day.
Rick What is your vision of the future of Linux in the embedded market and in the home and business desktop computer market?
Robert Linux is going far in the embedded market. I'm sure you as much as anyone can see the vast potential there. Linux offers key benefits—particularly available source and a highly configurable system—that should appeal to the embedded space. It is light, so it embeds well. It has a simple API. A lot of user-space solutions exist, and it is easy to create entirely new ones.
I certainly think Linux is an excellent desktop system (both GNOME and KDE are quite mature), but I don't see huge strides here in the coming year. Market share will certainly increase, perhaps significantly, but we will not be overtaking any evil monopolies this year.
Rick Is there anything else you'd like to add?
Robert The latest version of all this fun stuff is available for FTP download at ftp.kernel.org/pub/linux/kernel/people/rml or at your favorite mirror.
Rick Thanks very much!
Editor's note: Look for an article by Robert on his preemptive work in next month's issue.