Nearly full tickless operation in Linux 3.10

http://lwn.net/SubscriberLink/549580/82983789866b5fad/

by fintler • 13 years ago

287 75 13 years ago

phaemon• 13 years ago

This is one of the reasons I prefer to use Linux over systems such as Windows or OSX. I love the public discussion over the direction of technical details; the to-and-fro on the benefits of esoteric technologies.

The whole openness of the culture.

mrb2• 13 years ago

There is not much discussion about Windows internals, not only because they are not shared, but also because quite frankly the Windows kernel evolves slower than the Linux kernel in terms of new algorithms implemented. For example it is almost certain that Microsoft never tested I/O schedulers, process schedulers, filesystem optimizations, TCP/IP stack tweaks for wireless networks, etc, as much as the Linux community did. One can tell just by seeing the sheer amount of intense competition and interest amongst Linux kernel developers to research all these areas.

The net result of that is a generally acknowledged fact that Windows is slower than Linux when running complex workloads that push network/disk/cpu scheduling to its limit: https://news.ycombinator.com/item?id=3368771 A really concrete and technical example is the network throughput in Windows Vista which is degraded when playing audio! http://blogs.technet.com/b/markrussinovich/archive/2007/08/2...

Note: my post may sound I am freely bashing Windows, but I am not. This is the cold hard truth. Countless of multi-platform developers will attest to this, me included. I can't even remember the number of times I have written a multi-platform program in C or Java that always runs slower on Windows than on Linux, across dozens of different versions of Windows and Linux. The last time I troubleshooted a Windows performance issue, I found out it was the MFT of an NTFS filesystem was being fragmented; this to say I am generally regarded as the one guy in the company who can troubleshoot any issue, yet I acknowledge I can almost never get Windows to perform as good as, or better than Linux, when there is a performance discrepancy in the first place.

chinpokomon• 13 years ago

Well Mark's post was interesting, but this is also old news now, is it not? Microsoft has had two OS updates since then and hot fixes and service packs. The biggest difference I see is that the Linux Kernel can be tweaked to specific performance characteristics at build time, whereas Windows can only be altered by runtime configuration. depending on what you might want to change, you may not have that capability. Going back to the article about network latency while playing media, the breakdown seems to show that this was a bug, and bugs happen. To Linux's credit, those bugs are probably patched more quickly and even if it hasn't been promoted to release, if someone has made a patch, you can incorporate your own fix. If not, the landscape doesn't look any different for Linux vs. Windows in that regard.

redstripe• 13 years ago

That deleted post from the MSFTer is pretty damning, but is the difference one that really matters?

Take a look at these benchmarks that were posted here recently: https://news.ycombinator.com/item?id=5644880

There isn't a single comment in that whole thread about how outrageously bad EC2 performance is. Meanwhile I'd bet that most HN startups run on EC2, heroku or other virtualized cloud platforms. And how many are using dog slow interpreted languages like python or ruby? It looks to me like people around here are quite willing to take very large performance hits for the sake of convenience.

I find Windows to be a small performance hit for the sake of convenience.

ksk6• 13 years ago

Sorry, I have never noticed Windows being slower than Linux. And usually when people complain, they usually have an incomplete understanding of what they're doing (nothing personal!).

The links that you posted in support of your claim are irrelevant IMO.

Compiling has nothing whatsoever to do with windows internals. You're comparing Visual Studio a full fledged IDE with dozens of extra threads running source indexing, source code completion/help indexing and dozens of other things that gcc does not do. To make a fair comparison you will have to just compare cl.exe with gcc with a bunch of makefiles (yes you can have makefiles on windows too).

Then your "real concrete and technical" example is actually a bug in windows vista which was fixed around 6 years ago.

And your claim about MFT fragmentation kind of sounds bizzare to be honest. Since Vista the OS internally runs a scheduled task to run a partial-defrag that takes care of it. I'm not sure what went wrong in your case.

I'm not saying you imagined the slowness, I believe you experienced what you said. So lets test your theory. Since you can write code runs slower only on Windows - give us some C code that runs horribly on Windows.

asdqwezxc• 13 years ago

http://pastebin.com/KXpg5wgz

Anon_Cow3• 13 years ago

ChuckMcM2• 13 years ago

One wonders if you can go to a full 'subscribe' model which a bunch of pre-emptive OSes use, which says "I need to run in 'x' nS" or "I need to run when interrupt 'y' fires." and then they don't get any cycles at all until they need them, and at that time they are arbitrated.

The challenge of course is priority inversion, which is to say that low priority thread A gets started on an otherwise idle processor and then higher priority thread B wants to run, except there isn't a 'tick' where the processor periodically checks to see that the highest priority thread is running. Now your low priority thread is running in preference to the high priority thread.

You can finesse some of that by interrupting on thread state change (which has its own issues since sometimes threads have to run to know they want to change their state) but you're still stuck somewhere between ticks when threads are sleeping and full tickless. Not surprisingly its kind of like building asynchronous hardware in hardware description languages.

I'm glad to see the experiments continue.

DigitalJack2• 13 years ago

So how would context switching occur if not initiated by an interrupt?

wmf3• 13 years ago

Most context switches are actually triggered by a thread blocking. In a completely tickless OS you'd also set a one-shot preemption timer whenever a thread starts running (this used to be expensive, but Intel recently added the TSC deadline timer).

mwcampbell• 13 years ago

I wonder if any general-purpose OS kernel is ahead of Linux in this area.

gizmo6863• 13 years ago

I doubt it. Being the most popular (and open source) kernel means that anyone looking to experiment or improve in this area will almost definitively go to Linux. Combine that with the fact that Linux has major corporate support, and many of those sponsors have an interest in the kernel being good, it is not surprising that Linux is doing well in this area.

However, this also means that the kernel is (in some ways) optimized for more server/super computer type stuff which prefers throughput over latency, at the expense of desktop/smartphone use, which prefers low latency over throughput.

Of course, in many cases there is an option between approaches (either at compile or run time). In the case of the scheduler however, they decided not to support multiple implementations in the mainline. This leaves us with the highly complicated implementation suitable for high end computer, and not the simpler Brain Fuck Scheduler (BFS) that shows minor improvements in desktop use.

Of course, using BFS is only a patch away, and several desktop distributions do use it.

cokernel_hacker2• 13 years ago

Do you consider xnu to be general purpose? OS X/iOS have been tickless for a long, long time.

prirun• 13 years ago

I wrote an emulator for a Prime minicomputer (1975-1992 era). The Prime had built-in instructions for process coordination via semaphores. So when a process issued a WAIT instruction to wait on an event (semaphore), the microcode scheduler looked through the ready list to find the next eligible process to run. At the end of the ready list is the "backstop" process, the lowest priority process; it is always ready to run. The backstop process would look through other scheduling queues (just a semaphore with a list of processes waiting on it) for processes that had exhausted their timeslice, give them a new timeslice, and execute the NFYE instruction to put the process on the ready list. The NFYE instruction would actually switch to the new process, because that process had a higher priority than the backstop process.

There was a periodic timer process on the Prime, that ran at the highest priority. It was used for things like waking up driver processes periodically, in case an IO device was hung and didn't interrupt like it should have, and for waking up processes that were sleeping until a certain time passed (sleep call).

I think it was advanced for its time. If you want to read more about it, here's a link to the Prime System Architecture Guide:

http://bitsavers.trailing-edge.com/pdf/prime/doc/DOC9473-2LA...

to3m3• 13 years ago

I suspect you can infer a subscription when a thread goes to sleep. It's probably waiting on some kind of synchronization primitive (and I guess I/O would count), or has explicitly slept for a period.

You still need a timer, I think, but it doesn't have to be a fixed frequency. It gets set to the time slice period when each new thread is scheduled, and if it fires before the thread has given up its time slice then a new thread is selected. (Ideally this behaviour should be relatively rare.)

zokier• 13 years ago

The advantages of full tickless elude me somewhat. Single percent performance gain does not seem worth the effort, so what else? For real-time operation tickless may make sense, but on the other hand idk how much ticking interferes currently RT processes on linux.

IgorPartola• 13 years ago

I was under the impression that tickless operation would translate to better power savings, but I may be wrong on this.

acallan• 13 years ago

Precisely. The latency of some of the more aggressive power states exceeds the resolution of most OS tick timers, so they are often aborted for no good reason. So, as I'm typing this reply, in-between keystrokes, voltage to the CPU can be killed (not just clock-gated).

mjg59• 13 years ago

Being tickless when idle provides significant power savings. Being tickless when active doesn't. The benefit here is to avoid trapping into the kernel an additional HZ times a second when you have a single CPU bound task bound to a CPU that nothing else wants to run on.

tyree732• 13 years ago

A single percent performance gain for all Linux using systems sounds massively worth it to me.

numbsafari• 13 years ago

It's interesting, when you think about it from that perspective.

On my system, maybe that 1% improvement doesn't mean very much.

But when you add up all the systems in the world that are running Linux, and think about how much electricity is used by them or how many personal experiences they are mediating, it really adds up into something worthwhile.

The curious question is: at what point does it become not worthwhile? 1% is maybe worthwhile. But .01%? .5%?

krenoten• 13 years ago

For mobile devices and laptops, the ability to turn off ticks on certain cores translates to huge power savings. I almost doubled my battery life on a quad core laptop when I switched from a full-tick to a dynamic-tick kernel.

lallysingh3• 13 years ago

Posting a subscriber link to HN is a bit abusive, no? Quoting:

  The "subscriber link" mechanism allows an LWN.net subscriber to generate a 
  special URL for a subscription-only article. That URL can then be given to 
  others, who will be able to access the article regardless of whether they 
  are subscribed. This feature is made available as a service to LWN 
  subscribers, and in the hope that they will use it to spread the word about 
  their favorite LWN articles.

  If this feature is abused, it will hurt LWN's subscription revenues and 
  defeat the whole point. Subscriber links may go away if that comes about.

bmm6o• 13 years ago

> This feature is made available [...] in the hope that they will use it to spread the word about their favorite LWN articles

Emphasis mine. Can you make a case for it being "abusive" in the context of the full text? I take it to mean generating an excessive number of links, not posting one link to a wide audience.

lallysingh3• 13 years ago

I took it as sending the occasional article to people you know. Not as a way to poke a hole through the paywall and send (via HN) it to thousands and thousands of people.

stcredzero2• 13 years ago

How is 1 process per CPU not a "real load?" How about a server or a VM on that processor?

claudius• 13 years ago

You will always have more than one process running, if only for the kernel threads handling filesystems, networking etc., so you can only get that if you have at the very least two CPUs. And even then you usually have more processes than CPUs and the ‘application’ split up in various processes that in turn require scheduling by the kernel.

stcredzero2• 13 years ago

Yes, but specialized server installations where multi-core CPUs have one process sitting on one core are still "real" loads. They're just specialized and not the common case.

dchichkov• 13 years ago

Kudos to Frederic. It was quite an effort: https://lkml.org/lkml/2012/8/18/77

And! Yes! Finally. Our 'isolated' cores are finally ours. Bare metal. No more jitter. Thank you for everyone who put that together. Your efforts are really appreciated!

swah• 13 years ago

Anyone knows if the paid OSes have this?

gizmo6863• 13 years ago

Well, if your RedHat and are paying someone to work on this feature in Linux, then yes. [1] Irrespective of my disclaimer, many companies are investing many smart people in making Linux work well.

Anyway, I've heard rumors that Windows 8 has this, but I can't find a good source on that (admittedly, I'm spoiled with GNU/Linux where it does not take much work to find this stuff).

[1] I just pieced this together, so take it with a grain of salt. Following the e-mail at [2], I guessed that Frederic Weisbecker was running this project. Googling him brought me to his github profile [3] which indicates he is with RedHat. Anyone who actually knows what is going on please confirm or correct this.

[2] http://lwn.net/Articles/549592/ [3] https://github.com/fweisbec

dantle2• 13 years ago

Windows 8 pushes out the tick. See "Idle Hygiene" here:

http://blogs.msdn.com/b/b8/archive/2011/11/08/building-a-pow...

blinkingled• 13 years ago

You sure about that? I read that section and it seems to be about idle duration whereas this is about turning off the timer interrupt on non-idle CPUs.

Nearly full tickless operation in Linux 3.10

Related Stories