Non-Deathmatch: Preempt v. Low-Latency Patch

LiquidPC writes: "In this whitepaper on Linux Scheduler Latency, Clark Williams of Red Hat compares the performance of two popular ways to improve kernel Linux preemption latency -- the preemption patch pioneered by MontaVista and the low-latency patch pioneered by Ingo Molnar -- and discovers that the best approach might be a combination of both."

Comments

co-op!

[FigBugDeux]

whats wrong with cooperative multitasking?

Re:co-op!

[lightfoot jim]

I hope you're kidding! In a co-op system, each program monopolizes all the resources of the machine until it voluntarily gives up control. If the instruction to return control to other processes is preceded by instructions which could result in an infinite loop or wait state, the machine is then inaccessible. Situations like this exist in preemptive systems as minor annoyances. For example, if you ssh from and openBSD machine to a sshd server and then pull the network cable from the sshd server, the tty on the openBSD machine will stop responding to input. Since the BSD kernel is preemptive, you can switch tty's and just kill the process of the frozen tty. In a coop setup, the key sequence to switch virtual consoles would be ignored and you'd have to reboot the machine.

Re:co-op!

[sharkey]

Hmm. Let me count the ways:

• Windows 3.0

• Windows 3.1

• Windows for Workgroups

• Windows 95

• Windows 98

• Windows 98SE

The list goes on...

The Linux kernel preemption project

[BrianGa]

Check out this
comprehensive guide to Linux Latency.

More serious player in the shadows

[CathedralRulz]

The article doesn't mention this, but something some folks aren't aware of is that MontaVista is a serious linux partner with IBM. If the technologies described in the white paper can be merged, then the real effect can have a more significant impact in the embedded application/ PowerPC products from the World's 9th largest corporation.

Oooooh

[NiftyNews]

Don't miss the thrilling link to the debate on whether it is PreemptAble or PreemptIble...

Re:Oooooh

[sharkey]

Well, let's just make it definitive. Run it through the "CmdrTaco Ofishul Spalchukkar" and let's see what we get:

• preumtailable

Well, there...you...go!

Re:Wow!, what an insightful conclusion.

[cs668]

I agree with you except there is a critical difference between assuming that this would be the case and demonstrating that the assumptions are true.

Clark Williams did a lot of work to prove that the assumptions you would have when looking at combining the two patches hold.

O(1) already integrated...

[Anonymous Coward]

Ingo Molnar's O(1) scheduler was integrated
into the development tree back around Linux 2.5.4
So it's already in there.

Preemption was integrated about the same time.

One good way to reduce kernel latency..

[thesupraman]

One thing not mentioned so far is that one of THE largest scheduler latency problems comes from the driver for a PS/2 mouse, a very common item to be found plugged into servers which have no need for it. By removing the PS/2 mouse (and driver..) a significant latency improvement can be gained!

It's a pity that most USB mice don't seem to provide quite the quality of use as the PS/2 items (although this is probably also a driver issue)

Loy latency can be an advantage, but it is important that the cost of the lower latency is not an increase in total load, as in reality the lower latency does not provide a large gain in performance for most desktop or server roles, but rather is a measure more often used in real time systems, which it can make the difference between a system working or not.

An example of this is in an ignition ECU for a V12 engine at 6000 RPM, a (pair of) plug is firing every 1/600th of a sceond (1.66ms), but the accuracy of the firing even must be in the order of 10us, which is not yet reachable be any 'standard' unix kernel, but quite easy to get on a much simpler ECU (I use an SH-2 at 24 MHz) than you would notmally find using a true real-time kernel.

With some developments is may be possibly for a form of linux to reach this level, which would be fantastic, as a LOT of time is spent in embedded development providing 'operating system' level functionality around the actual application code, and with embedded processors getting faster, and memory getting cheap, embedding *nix has become much more of a possibility.

Re:One good way to reduce kernel latency..

[clone304]

Honestly, I'm not trying to troll you here, but why would you WANT to run a *nix kernel on hardware that's responsible for engine timing? Especially when you apparently already have tech that works. Is the idea just to make vehicles that much harder for people to maintain? The day my mechanic keeps a sysadmin on duty so he patch my buggy Linux 4.5.3 ECU is the day I put a gun to my head and pull the trigger.

Aside from that. Way to inform the masses.

Re:One good way to reduce kernel latency..

[Jah-Wren Ryel]

Forget about mechanics. Just let us telnet into the engine and we can fix it ourselves.

Re:One good way to reduce kernel latency..

[iabervon]

The performance tests that various people have run with these patches seem to show improvements in throughput on servers. The guess is that this is because the machine will respond more quickly to the completion of I/O (which is, of course, is the slow step on most applications), so it essentially arranges tasks so that the next I/O operation can get started sooner.

Of course, you'd presumably get a higher load, since you're doing your task in less time, which means that the processor is busy more of the time.

Additionally, latency is important for interactive tasks on desktop machines, because it determines how responsive the system feels under load. The user's experience is determined more by how quickly the system responds to simple requests (moving the mouse cursor, drawing menus, etc) than by the milliseconds place on more complex tasks. Furthermore, the user will instantly notice if sound or video is not handled on time.

Re:One good way to reduce kernel latency..

[Junta]

Interesting what you say about USB mice, in my experience a USB mice provides smoother use than PS/2. I don't have PS/2 at all in my kernel anymore. With my Logitech MouseMan+, it came as USB with a PS/2 converter. I had to use it because I played with BeOS and BeOS didn't like it unless it was on the PS/2 port. In any case, when using a USB port instead of PS/2, the mouse can be polled much more frequently, allowing for more precise movement (particularly of interest in, say, first person shooters). Plus, the ability to plug and unplug, and plug my mouse into any USB port I feel like is nice.

Re:One good way to reduce kernel latency..

[Junta]

What you say about desktop responsiveness being more of an issue for these patches than server applications is accurate. And I agree that mouse and audio responsiveness is very noticable to user (if audio skips, very loud popping is usually heard). However, with video there is a little more wiggle room if the decoder handles things gracefully. Even if interrupted for 2/30s to even a tenth of a second as an isolated incident, you can probably get away with it. Certainly 1/30th of a second will almost certainly not be noticed (single frame drop), 2/30ths (2 frames) probably will slip under the radar. 3 frames dropped and then you start getting into a perceptible skip if there is a decent amount of movement in the scene. Of course, 1/30th of a second is much higher than most all latencies you see even under the unpatched kernel.

I personally haven't been able to tell between the pre-empt kernel and traditional, they both give the same 'feel' on the desktop level.

Re:One good way to reduce kernel latency..

[cduffy]

Having a Linux kernel doesn't mean having a Linux userland -- and almost all bugs that actually affect the end-user are userspace bugs, or kernel bugs that are only visible with a big userspace (ie. networking bugs -- if you don't need networking you don't compile it into your kernel, and so it never hits you). If you're doing a deeply enough embedded system, you don't need that userspace, so you don't *have* most of that userspace (heck, you can do without any of it if you like)... and there's only one application that the kernel runs (yours!) and only one set of hardware it runs on (yours!) and so it can be very thoroughly tested. Even when updates are needed, flashing a new kernel in (which happens to have an initrd with the one and only application it runs) isn't exactly rocket science, and certainly doesn't need a sysadmin.

Do you really think that companies doing their own proprietary kernels come up with something more reliable? For the most part, they don't -- but once a deeply embedded system is out the door, the rule is that it'll Just Work the way it did in the lab, because for that embedded system nothing (the hardware, the software, the input, the output, whatever) ever changes from what it was designed and tested on -- or if it does, you've got bigger problems.

That's less true for less deeply embedded systems... but those are where something like Linux is even more appropriate.

Re:One good way to reduce kernel latency..

[cduffy]

Under regular loads, yes.

Under high loads, when playing audio, the difference can be quite remarkable.

I'd be curious to know under what kinds of loads the tests documented here were run.

Re:One good way to reduce kernel latency..

[Junta]

I was just making blanket statements about visual percetption and how many frames can be dropped without being noticed. It's anecdotal, but I have seen some clips that can drop up to 40% of frames without much noticed (very low motion video). But if there is only enough of a glitch to interrupt a frame or two of video, then it will be smoothed over by the sensory system without it ever being missed, while with audio, any interruption will result in a waveform that has an undefined derivitave, a crack in the audio. Under very heavy loads, you'll drop more than 1-2 frames per second, you'll have probably up to 40-60% frame drop, and for almost any content that would indeed be noticable.

In any event, low latency is good, and my entire point is irrelevant except as a nitpick.

Re:One good way to reduce kernel latency..

[FlyingDragon]

The day my mechanic keeps a sysadmin on duty so he patch my buggy Linux 4.5.3 ECU is the day I put a gun to my head and pull the trigger.

If you use an early development kernel in a production engine, you deserve what you get.

Re:One good way to reduce kernel latency..

[ivan256]

I certainly hope that your USB mouse driver is interrupt driven. There shouldn't be any polling going on, as that would be an enormous waste of system resources. Similarly the origional post was dubious at best, since PS/2 ports can also generate interrupts. A still mouse should use *zero* system resources. USB does have higher throughput then PS/2, so theoretically the mouse could send updates much more frequently then the PS/2 equivalent, and that would account for smoothness.

Re:One good way to reduce kernel latency..

[iabervon]

That's interesting; I thought people would notice a dropped frame just because it would mean that one frame would be shown twice as long as any of the rest, so everything would stop for a moment and then jump forward to the right place. Of course, traditionally when a frame gets dropped, the person sees a blank frame or static or something unrelated to the scene; people don't notice these at all, because the brain is wired to ignore them (because you blink and so forth). But having a frame update dropped means you'll see the previous frame for twice as long, which appears as a change in the motions of objects, which the brain is tuned to see.

I'm not sure exactly how many frame updates you can miss without people noticing, but it's got to be a lot fewer than frames you can blank without anyone noticing, especially if it's not consistent.

Interrupt priorities

[ChaosDiscord]

Most RTOS's prioritize device interrupts so that important interrupts ("shut down the reactor NOW!") are serviced first and lower priority interrupts ("time to make the doughnuts") are serviced later.

Clearly, most RTOS designers have their priorities backwards.

Mmmm, donuts.

Re:I did better

[(outer-limits)]

The only real OS is MVS, aks OS/390 aka Z/OS. It is truly an operating system. It makes no concessions for mere mortals, it is made to run a machine. It hails from 1966. All bow down before it.

What's up with the degrading performance?

[A Commentor]

The low-latency patches had a maximum recorded latency of 1.3 milliseconds, while the preemption patches had a maximum latency of 45.2ms.

A 2.4.17 kernel patched with a combination of both preemption and low-latency patches yielded a maximum scheduler latency of 1.2 milliseconds, a slight improvement over the low-latency kernel. However, running the low-latency patched kernel for greater than twelve hours showed that there are still problem cases lurking, with a maximum latency value of 215.2ms recorded. Running the combined patch kernel for more than twelve hours showed a maximum latency value of 1.5ms.

So after only 12, the low-latency patch degraded by an ungodly amount (1.3 -> 215.2 ms)!! and even the combined patch had a 25% degraded performance(1.2 -> 1.5 ms)!

Embedded systems must have a very high uptime, it's not acceptable to reboot the machine every day to maintain performance. Many embedded systems require a downtime of less than 5 minutes per year. That doesn't give you much time to reboot the machine just for performance issues.

Re:What's up with the degrading performance?

[dmiller]

It has got nothing to do with how often the machine is rebooted and everything to do with the frequency of latency increasing events.

The event which caused the 215ms even probably only happens once or twice per day. Perhaps it was some weird code path that the LL patch didn't touch, or some unlikely combination of events occuring "simultaneously"

Re:What's up with the degrading performance?

[tempest303]

What's up with the degrading performance?

It's called a bug - they'll figure it out. ;)

it's not acceptable to reboot the machine every day to maintain performance

Hey, it worked for NT4 admins, why not for embedded developers? *rimshot*

Sorry. But seriously, anyone looking for hardcore low latency in Linux right now for systems that need that buzzword compliant "five 9's" should probably wait on using Linux until it's READY. Make no mistake, with as much interest and developer hours as are going into it, Linux WILL make it into this market, and it will succeed; it's merely a matter of time. (and hell, at this rate, it may not be long...)

Re:What's up with the degrading performance?

[Fluffy the Cat]

So after only 12, the low-latency patch degraded by an ungodly amount (1.3 -> 215.2 ms)!!

You're misinterpreting the figures. After a short benchmarking, the worst figure recorded was 1.3ms. After the machine had been left up for 12 hours (thereby allowing there to be much more time for something odd to crop up), the worst figure recorded was 215.2ms. That doesn't mean that the performance had degraded - it means that over the course of those 12 hours, something happened that caused latency to peak at 215.2ms. It might be something that happens once every 12 hours, for instance.

Re:What's up with the degrading performance?

[steveha]

Well, to be precise, the worst-case value "degraded". And I'm not sure "degraded" is the correct word. With a huge torture load put on the kernel, during a 15-hour interval, at least once the latency value was 215.2 msec. This could mean that there is a possible latency condition that happens under torture load approximately once every 15 hours. It could also mean that after 15 hours, your chance goes up so it could happen much more often than that, but we don't know that. It could even mean that there is a possible 215 msec latency condition that happens under torture load approximately once every 30 hours, and it happened to occur during the first 15 hours.

Embedded systems must have a very high uptime, it's not acceptable to reboot the machine every day to maintain performance.

True that. Which is why the author of that article made the point that combining the two patches is the best way to go, since he ran the torture test for 15 hours and it didn't go over 1.5 msec even once.

Note that for many purposes, a worst-case latency of 1.5 msec is ample. I don't think there is any version of Windows that goes that low; I don't even think BeOS (legendary for low latency) goes that low. As the author noted, if you are driving a chemical processing factory or something like that, you need hard realtime and you should use something other than Linux kernel 2.4.x!

steveha

Re:What's up with the degrading performance?

[SurfsUp]

It might even be something that happens just as often on with the combination patch as with the low-latency patch, except the combo got lucky.

If you'd actually read the article you'd know that this can't happen with the preempt patch + low-latency, not unless a spinlock gets jammed, then you have much worse problems. The preempt patch takes care of scheduling events that occur during normal kernel execution (and it does this much more reliably than the low latency patch) but since preemption isn't allowed while spinlocks are held, it can't do anything about latency due to spinlocks. This explains the apparently worse performance of the preempt patch - you're just seeing the spinlock latency there.

The low latency patch breaks up the spinlocks with explicit scheduling points, which is pretty much the only approach possible without really major kernel surgery. That's why the combination works so well. In fact, the parts of the low latency patch that aren't connected with breaking up spinlocks aren't doing anything useful and should be omitted. The worst-case performance won't change.

Re:The Right Reasons

[WNight]

If you want a database for a file system they've been out for decades.

However, it's debatable if this is a good thing. Providing transactions is good, but why write an SQL interface for the whole file system? And then have to massage files into specific data types, or a whole bunch of BLOBs which you can't perform any complex operations on...

If MS does come out with this filesystem, they won't make it a default. It'd rock for some uses and suck for others. Much like NTFS.

Measuring latencies?

[acordes]

Here's a question. How do you go about doing fine grained measurements of these latencies? Every time I've tried doing timings with Linux I've had problems being able to get accurate, fine grained results.

Custom Redhat RPM's

[nuintari]

Anyone know if Redhat is planning on offering lower latency kernel RPM's for those of us who are loath to patch and recompile a kernel JUST to try something new out to see if we like it. Its kind of nice if I can drop in a quick RPM, decide weather I like it, and THEN compile a trimmed kernel properly if need be.

I'm just lazy. :-)

la...

[nickynicky9doors]

...tency

A good paper, but...

[software_non_olet]

I'm missing on Clark Williams' paper how the patches influenced the OS overhead.

Re:QNX vs. Linux

[Anonymous Coward]

"Interrupt and process latency

All times given below are in microseconds (sec).

Processor_______Context____Interrupt Latency
Pentium/133_____1.95_______4.3
Pentium/1 00_____2.6________4.4
486DX4__________6.75_______ 7
386/33__________22.6_______15

With nested interrupts, these interrupt latencies represent the worst-case latency for the highest priority interrupt. Interrupt priority is user-definable and the interrupt latency for lower-priority interrupt sources is defined by the user's application-specific interrupt handlers. "

Interrupt latency in Windows CE 3.0

[jawahar]

Well, Windows CE 3.0 provides 50 ms latency response time running on a 166 MHz Pentium.

There was a fight?

[Anders]

I never realized there was competition between the two. I did hear the low-latency crowd claim that it was lower risk due to its less invasive nature. However, that hardly says anything about the performance of either approach - or that they should be mutually exclusive.

Two wrongs doesn't make a right, and vice-versa (but two Wrights make an airplane).

Low-latency and Preemptible on my Notebook

[hazzzard]

I am using a low-latency kernel on my notebook at the moment and I can report the following behavior:

• In X (KDE), I can move windows around, load programs, webpages etc. without my MP3-player ever beginning to skip.
• When doing massive file IO, the MP3-player begins to skip. tar cvzf file.tar.gz bla/ is still ok, but cp -R bla1 bla2 causes massive skipping.
• When I use the notebook as a samba server, things get worse. Still, massive skpping. Additionally, the samba becomes dog-slow and even the mouse falls asleep.
• Often times, after such phases of heavy load, the skipping and sound-distortion remains! So I have to reboot the machine from time to time to enjoy music again. Closing the player and opening it again is not enough. Somehow, under heavy load things get messed up enough to make a recovery impossible.

I did use the preemptive patch before, but performance under heavy load was even worse and the similar problems with rebooting occurred. I was using kernel 2.4.12 for preemptive and I am using kernel 2.4.17 currently. The machine is a Celeron 466 with 128 megs of ram. Still, the low-latency patch makes sense for machines that are primary for playing MP3s and reading emails (that's what my notebook is), but not for desktops with a wider variety of usage patterns. It's just not ready for primetime yet, but it's promising and fun!

Re:Low-latency and Preemptible on my Notebook

[Adnans]

Are you scheduling your MP3 player at a higher prioritary (*) than say, your cp command? It is very important that you do this. While this might not fix the massive skipping it could improve things a great deal. Given, there are still lots of problems with the disk I/O subsystem in Linux that neither the preempt or ll patches fix right now so the occasional skip under heavy load is guaranteed, especially since consumer grade audiocards are not really catering towards low latency.

<plug>

AlsaPlayer comes with a --realtime switch that enabled SCHED_FIFO scheduling for the audio thread, this eliminates skipping for most people, but requires the binary to be run as root (or be suid root)

</plug>

-adnans

(*) scheduling something at a higher prio usually requires running the program suid root, or calling renice(8) as root with the programs pid. A better method is to sudo the nice command for the given user so he/she can nice the app at the start

Re:Low-latency and Preemptible on my Notebook

[spencerogden]

Reports like these make me curious. I have a desktop with the exact same specs. Yet I have never experienced any skipping when using XMMS. Whether I am doing large file copies, compilation... nothing. This is under both Mandrake and Sorcerer. Is there a variable here which is being missed? I have never needed to renice anything.

Good article, good contribution

[mikera]

Some very thoughtful analysis clearly went into this. It's well written up with explanations that hit the right balance of having the key technical details but focusing on the big picture of how to make applications run better under Linux. As a casual follower of kernel development, I now understand far more of the trade-off than I used to.

I always think that tests and write-ups like this are a great way that people can contribute to Linux development without having to hack the kernel directly. There's no substitute for a thorough testing to help you improve your designs and theories.

Nice job!

No argument here, move along.

[Chops]

From the article:

Back in early November 2001, I started following a discussion between two factions of the Linux kernel community ... There were two main factions, the preemption patch faction and the low-latency patch faction. Both groups were very passionate (i.e. vocal) about the superiority of their solution.

Er... while some misinformed folks have in fact been arguing over "which approach is better," both Robert Love (preemption) and Andrew Morton (low latency), the authors of the patches, have agreed since before November that a hybrid approach is probably correct, and it seems to me (though I don't speak for them) that they're faintly embarassed at the number of True Believers who have stepped up to champion one or the other's side in this nondeathmatch. They're attacking different sections of the same problem.

Re:No argument here, move along.

[Alsee]

some misinformed folks have in fact been arguing over "which approach is better"

They are both wrong. The correct solution is to remodulate the preemption and vent the latency through the Bussard collectors.

-

Another article

[Onan The Librarian]

I wrote an article about low-latency for audio
applications under Linux, you can read it here if interested:

http://linux.oreillynet.com/pub/a/linux/2000/11/ 17 /low_latency.html

It's more of a hands-on article, tells you how
to do it yourself with Andrew Morton's patches.

My take on the results and the future

[sagei]

First, I wanted to give my view of the results - what they mean and what that means. Note there are multiple notions of latency performance. Average latency and worst-case latency, among others, but those are most important. This test measured worst-case latency. Both are important - for user experience average case is very important and for real-time applications worst-case is very important.

It is not a surprise the low-latency patches scored better, or that the ideal scenario was using both. The preemptive kernel patch is not capable of fixing most of the worst-case latencies. This is because, since we can not preempt while holding a lock, any long durations where locks are held now become our worst-case latencies. We have a tool, preempt-stats, that helps us find these. With the preempt-kernel, however, average case latency is incredibly low. Often measured around 0.5-1.5 ms. Worst-case depends on your workload, and varies under both patches.

Now, the results don't mention average case (which is fine), but keep in mind with preempt-kernel it is much lower. The good thing about these results are that it does indeed show that certain areas have long-held locks and the preempt-kernel does nothing about them. Thus a combination of both gives an excellent average latency while tackling some of the long-held locks. Note it is actually best to use my lock-break patch in lieu of low-latency in combination of with preempt-kernel, as they are designed and optimal for each other (lock-break is based on Andrew's low-latency).

So what is the future? preempt-kernel is now in 2.5 and, as has been mentioned, Andrew and I are working on the worst-case latencies that still exist. Despite what has been mentioned here, however, we are not going to adopt a low-latency/lock-break explicit schedule and lock-breaking approach. We are going to rewrite algorithms, improve lock semantics, etc. to lower lock-held times. That is the ease and cleanliness of the preemptive kernel approach: no more hackery and such to lower latency in problem areas. Now we can cleanly fix them and voila: preemption takes over and gives us perfect response. I did some lseek cleanup in 2.5 (removed the BKL from generic_file_llseek and pushed the responsibility for locking into the other lseek methods) and this reduced latency during lseek operations -- a good example.

So that is the plan ... it is going to be fun.

Re:My take on the results and the future

[Nick Barnes]

Now, the results don't mention average case (which is fine), but keep in mind with preempt-kernel it is much lower.

The results do mention the average latency. For the vanilla kernel it is 88.3 microseconds. For the low-latency patch it is 54.3 microseconds. For the preemption patch it is 52.9 microseconds. Is 52.9 much lower than 54.3?

Re:Wow!, what an insightful conclusion.

[by Linus Torvalds]

Well actually we have been discussing this recently on the kernel mailing lists. I am currently deciding whether this should be incorporated into the main tree, but am concerned that it may lower throughput.

Alan has suggested I include both patches into the next 2.5 release (though there is quite a lot going on there so it may not make it in until the next one after that) and it will be fun to see the effects on latency and throughput, especially with the new I/O subsystem, in widespread use on various architectures; Clark Williams only compared the patches on single processor machines for example, where we have to pay special attention to the various SMP archtectures out there.

But remember! Linux is not a RTOS and I have no intention of making it one, although there are forked kernels that do exactly that.

How much difference?

[Jeppe Salvesen]

Low latency, pre-emptive. All nice and good. However, what I really want is to get a super-fast connection between my database server and my application server. How much will the lower latency patches affect the throughput, given that I operate in multiple small queries? (No way around it, at the moment. So please don't flame (too hard))

Will Ethernet devices, TCP/IP stacks and the lot become more responsive? Will MySQL/PostgreSQL/SapDB/Oracle/DB2/Interbase be able to execute a small query even faster? How much?

Actually, I hope to measure this sometime not too far into the future!

I think the much bigger question is...

[OneFix]

When will this become stable enough for major distros to start using it?

I don't think anyone doubts that this is a good approach. But, both patches are still being worked on right now. And while the preempt patch has already been merged with the 2.5 kernel, the low-latency patch is still nowhere to be seen.

I certainly think that this would indeed have a great impact on Linux Multimedia, but not until a company like RedHat or SUSE is willing to include it at least as an optional kernel. The reason is, a vendor doesn't have to support patches until they include it in one of their pre-compiled kernels.

This might not mean much to home users, but a company will not rely on an unsupported feature.

Like it or not, business still drives the industry.

Re:Non-deathmatch, eh?

[be-fan]

They load fine. Been using a preempt+lock-break+XFS + nvidia system for several months now. Works great.