Slashdot Mirror
Significant Interactivity Boost in Linux Kernel
An anonymous reader writes "The Linux kernel team is at it again. Linux creator Linus Torvalds recently proposed a patch to offer interactive processes a boost, greatly benefiting the X desktop, as well as music and movie players. O(1) scheduler author Ingo Molnar merged Linus' patch into his own interactivity efforts, the end result nothing short of amazing... The upcoming 2.6 kernel is looking to be a desktop user's dream come true."
Absolute astounding. I am in complete and utter shock over this. Truly, truly the most amazing thing I've ever seen or heard.
Now what the hell is this article about?
At it again? At what again? That sorta makes it sound like a girls gone wild video or something. Kernel Dev's Gone Wild volume 3, where Ingo and Linus bare their breasts for beads at a Linux user conference in Tampa Bay - no, that's just too strange...
Oh, one more thing:
Hello, my name is Ingo Molnar. You killed my father: prepare to die.
Robots are everywhere, and they eat old people's medicine for fuel.
There's no reason not to implement both high-throughput scheduling for big servers and low-latency scheduling for desktops in the same kernel... just mark each process table entry with a bit saying whether this process is 'interactive' (favour fairness and low response times) or 'batch' (favour total throughput and bigger timeslices at the expense of fairness).
-- Ed Avis ed@membled.com
Something forms itself from the silent void of the empty mailing lists and the noisy chaos of the crowded mailing lists. It shapes and protects us, it entertains and challenges us, it aids us in our journey through the ether world of software. It is mysterious; it is at once source code and yet object code. I do not know the name, thus I will call it the Tao of Linux.
If the Tao is great, then the box is stable. If the box is stable, then the server is secure. If the server is secure, then the data is safe. If the data is safe, then the users are happy.
In the beginning there was chaos in Unix.
Tanenbaum gave birth to MINIX. MINIX did not have the Tao.
MINIX gave birth to Linux 0.1 and it had promise.
Linux gave birth to v1.3 and it was good.
v1.3 gave birth to v2.0 and it was better.
Linux has evolved greatly from its distant cousins of the old. Linux is embodied by the Tao.
The wise user is told about the Tao and contributes to it. The average user is told about the Tao and compiles it. The foolish user is told about the Tao and laughs and asks who needs it.
If it were not for laughter, there would be no Tao.
Wisdom leads to good code, but experience leads to good use of that code.
The master Cox once dreamed that he was a Kernel. When he awoke he exclaimed: "I don't know whether I am Cox dreaming that I am a Kernel, or a Kernel dreaming that I am Cox!"
The master Linus then said: "The Tao envelopes you. You shall create great code for Linux."
"On the contrary," said Cox, "The Tao has already created the code, I will only have to find it and write it down."
A master was explaining the nature of the Tao to one of his students:
"Is the Tao in the VM subsystem?" he asked. "Yes," replied the master.
"Is the Tao in the scheduler?" he queried again. "The Tao is in the scheduler."
"Is the Tao even in the modules?". "It is even in the modules," said the master.
"Is the Tao in the Low-Latency Patch?"
The master frowned and was silent for much time.
"You fail to understand the Tao. Go away."
The Tao is the yin and the yang. It is the good and the evil, it is everything and yet it is nothing, it is the beginning and the end.
The Tao was there at the kernel compile, and it will be there when the kernel panics.
A novice user once asked a master: "Why compile in C when C++ is more popular?"
"Why a monolythic kernel when Mach is more popular?"
"And why use ReiserFS when ext2 is more popular?"
The master sighed and replied: "Why run Unix when NT is more popular?"
The user was enlightened.
A frustrated user once asked a master: "My kernel has panicked, should I post to lkml?"
"No," replied the master, "You will only bother the Tao."
"Should I rm -rf?"
"No, you will have wasted the Tao's time."
"Well should I search the web?"
"You will search for all eternity," said the master.
"Perhaps I should try FreeBSD?"
"Then you will have disgraced the Tao."
"I suppose I could try gdb," said the user.
The master smiled and replied: "Then you will have made the Tao stronger."
A stubborn user once told a master: "I run version 2.2. I always have, and I always will."
The master replied: "You are foolish and do not understand the Tao. The Tao is dynamic and ever changing. Linux strives for the perfection that is the Tao. It flows from version to version with peace."
"So my Linux does not have the Tao, so what?" said the foolish user. "Oh your Linux is of the Tao," said the master. "However, the Tao of Linux follows the Tao of the C library. One day the C library will change, and your Linux will be left behind." The user was silent.
An angry user once yelled at a master:
"My Linux has panicked! What lousy software it is, I hate it so!"
"You are insulting the Tao," said the master. "The Tao is everywhere bringing order to hundreds of networks, aiding thousands of users, and fighting that of which we call the 'lame.' Do not disrespect the Tao; however, the Tao will forgive you."
"I apologize," said the user, "And I will be more forgiving the next time the Tao fails me."
"The Tao has not failed you, it is you that has failed the Tao," said the master. "The Tao is perfect."
The Tao decides if a kernel shall compile, or if it shall abort.
The Tao decides if a kernel shall boot, or if it shall freeze.
The Tao decides if a kernel shall run, or if it shall panic.
But, the Tao does not decide if a box will have no hardware failures. That is a mystery to everyone.
A young master once approached an old master: "I have a LUG for Linux help. But, I fail to answer my students' problems; they are above me."
The master replied: "Have you taught them of the Tao?" he asked. "How it brings together man and software, yet how it distances them apart; how if flows throughout Linux and transcends its essence?"
"No," exclaimed the apprentice, "These people cannot even get the source untarred."
"Oh, said the master, "In that case, tell them to RTFM."
A master watched as an ambitious user reconstructed his Linux.
"I shall make every bit encrypted," the user said. "I shall use 2048 bit keys, three different algorithms, and make multiple passes."
The master replied: "I think it is unwise."
"Why?" asked the user. "Will my encryption harm the mighty Tao, which gives Linux life and creates the balance between kernel and processes? The mighty Tao, which is the thread that binds the modules and links them with the core? The mighty Tao, which safely guides the TCP/IP packets to and from the network card?"
"No," said the master, "It will hog too much cpu."
The core is like the part of the mind that is static. It is programmed at a child's creation and cannot be changed unless a new child is made; unless a new kernel is compiled.
The modules are like the part of the mind that is dynamic. It is reprogrammed every time one learns new knowledge; every time one learns better code.
One is yin, the other yang. Each is nothing without the other.
A novice came to lkml and inquired to all the masters there: "I wish to become a master. Must I memorize the Linux header files?"
"No," replied a master.
"Must I submit code to Bitkeeper?"
"No," replied the master.
"Must I meditate daily and dedicate my life to Linux?"
"No," replied the master again.
"Must I go on a quest to ponder the meaning of the Tao?"
"No. A master is nothing more than a student who knows something of which he can teach to other students."
The novice understood.
And thus said the master:
"It is the way of the Tao."
A user came to a master who had great status in lkml. The user asked the master: "Which is easier: implementing new features to the kernel or documenting them?"
"Implementing new features," replied the master.
The confused user then exclaimed:
"Surely it is easier to write a few sentences in the man page than it is to write pages of code without error?"
"Not so," said the master. "When coding, the Tao of Linux opens my eyes wide and allows me to see beyond the code, to let the source flow from my fingers, to implement without flaw. When documenting, however, all I have to work with is a C in high school English."
He who compiles from the stable tree is stubborn
and unwilling to change, but is guaranteed reliability.
He who compiles from the current tree is wise but perhaps too conformist, but is guaranteed steadiness.
He who compiles from the unstable tree is adventurous and is guaranteed new innovations: some good, some bad.
He who compiles straight from Bitkeeper is brave but guaranteed turbulence.
They are all of the Tao. One shall respect the old, and debug the new; none shall argue over which is greatest.
There once was a user who scripted in Perl: "Look at what I have to work with here," he said to a master of core, "My code is interpreted dynamically, the syntax is unique and simple, I have sockets, strings, arrays, and everything I could ever need. Why don't you stop meddling in C and come join me?"
The C programmer described his reasoning to the scripter: "Scripting is to C as ebonics is to Latin. If the scripter does not grow beyond that of which he scripts, he will surely {die}. Besides, without C, how can there be script?"
The scripter was enlightened, and the two became close friends.
> Uh...check out Windows 2000 scheduling algos
Sure thing. What was the address of their anoncvs servers again? Oh wait, I forgot the "turn into a powerful government and sign a couple hundred non-disclosure agreements"-requirement.
It's:
My name is Ingo Molnar. You kill -9'd my parent process. Prepare to die()
Stop stealing that intellectual property from SCO already. Have you no shame? The gig is up: there's no way you could keep putting this stuff out without ripping off the hard working SCO programmers.
Fermat's other theorem: "I have a simple proof, but I can't write it down as I fear it's a DMCA violation to discuss it"
bashing linux/x/kde/whatever speed, I'm willing to bet you've never doen a full build (ala Gentoo) and actually optimized it for your system...have you? KDE 3.1 is as fast or faster than windows XP on my 1ghz box...it took a while to build, but it's well worth it.
Many people are not gonna compile their own kernel, especially those running something like Redhat in a corporate environment. It makes more sense to code it to work either way.
;-) That means a desktop edition could install a low-latency version and a server edition could install a high-throughput version.
How about this radical idea--
Let Red Hat, SuSE, etc. compile different kernels with different options and install them as needed
LedgerSMB: Open source Accounting/ERP
There was a time when idiots did not walk the earth.
Linux still screams, I have a single server with two gig's of ram in it that runs 100 desktops (KDE) simultaneously. Yes it indeed takes alot of ram to run all of the new software. But for a machine that runs 2200 processes that is a impressive feat. It is a dual processor box and I have yet to see it reach over 30% processor utilization, a testament to the efficency of the kernel.
Software today requires a ton of ram, this has nothing to do with efficency of the linux kernel.
Along with this goes the idiots that think there is something wrong with X. I run this stuff in a corporate environment and X windows is linux's biggest strength. Remove X Windows and I would have to eliminate our corporate use of Linux.
Got Code?
" As an avid Microsoft fan, one of my biggest beefs was the inferior performance of the Linux GUI and its components."
That would depend on exactly what you talking about. Those linux users running something like Blackbox would laugh at you for saying so. I'd also suggest as a user of both, KDE and XP have about the same interactive performance as well.
There's no doubt Windows still has more polish than Linux as a whole when it comes to the desktop. And while anything that improves any of LInux's many "gui's" is a welcome event, Linux's gui's are hardly inferior performance-wise across the board like your implying.
"Maybee this will finally blur the line between OS's enough to get more people to switch over."
Performance doesn't rate very high on why windows users aren't switching over. Lack of familiar apps and games, lack of widespread OEM bundling, and lack of millions in marketing are what's keeping people from switching over.
If you wanna get rich, you know that payback is a bitch
IANAKH (Kernel Hacker), but here's my understanding of it.
The kernel development team are experimenting with heuristics to determine what processes are "interactive" and to determine "how interactive" those processes are.
An interactive process is a process which spends a portion of it's time sleeping, waiting for some kind of event, and then needs cpu time quickly after the event happens.
In this case the events are user input and screen redraw requests.
So, the trick is that interactive processes don't need any more CPU time than other processes, they just need it very quickly in response to requests. Low latency.
The question is, how do you determine what processare are interactive, and how interactive they are.
They have developed a system whereby there are effectively "interactivity points" that can be given to and taken away from a process.
The act of being woken up from sleeping by an event awards you interactivity points. The act of completely using up lots of timeslices (acting like a CPU-bound process) takes away interactivity points.
With Linus's new patch, once you've reached a certain threshold of interactivity points, some of your points start going to the process that woke you up. So, if an "interactive" process is always waking up in response to an event from a certain other process, than that other process is also awarded interactivity points.
In the end, your interactivity points are taken into account when choosing which processes get the CPU.
So, with this new code, processes which are "interactive" like your X11 apps get more of the cycles they need when they need them, decreasing their latency, and making them appear to work "better."
Justin Dubs
Every new release of Windows wasn't vastly slower and more bloated then the release before it...
Oh wait. No there wasn't.
If you wanna get rich, you know that payback is a bitch
Its not just a UI issues; it does relate to the kernel in that the kernels job is to manipulate process priorities and give CPU cycles where they "should best be given". This is actually best done at the kernel level, and NOT the GUI level, because the GUI does not know about the other non-GUI processes is "competing with". I've felt for a long time that something like this should be done in both Windows AND Linux.
Windows is TERRIBLE at this. Consider the following scenario, which most here who here run Windows XP will be able to identify with. You boot up, you've just logged in. The task bar is there on the screen, the start button there, you click on it. And nothing happens. You wait. Still nothing happens. You wait some more. You start to get annoyed and click the start button a few more times. The hard disk is grinding away while Windows XP does all sorts of "invisible stuff" in the background. The computer is about as responsive as a brick. Then after anything from 20 seconds to a minute, the start menu suddenly opens and closes rapidly in quick succession a half dozen times.
THIS IS NOT HOW COMPUTERS SHOULD BEHAVE. Its pathetic. This is a perfect example of the necessity of this. The task bar process doesn't know about all those other background processes hogging CPU after you log in; there is no elegant way for it to magically know when to set its priority temporarily high, and for how long. But the kernel can say, OK, the user is trying to press a button, we must respond, and temporarily boost the start bar (explorer.exe) process and block the others.
On desktop machines (i.e. not servers), user input is the most important thing. If the user presses a button, something must happen. The kernel should be continually shifting priorities around to where the user is focusing his/her input.
The interactivity boost has been in linux from Linux 0.99. This is a new class of boost, increasing interactive proccess priority and helper proccess priority too.
Dropping X11 would be a HUGE mistake. X11 as a system is far more flexible than the gui system of windows, ofcourse this flexibility can introduce a performance hit, but theres many other things in modern os`s which sacrifice performance for features, ease of use, maintainability etc..
But even considering the larger and more featured system, X11 is as fast, or faster, than windows on all but one of my machines, the one where its slower is because the graphics card is very poorly supported by X.
What causes slowness more than X11 itself, is the programs running on top of it... KDE for instance, its hardly a speed demon compared to say, windowmaker.
You dont need a high end videocard to make X smoothe, you just need one that`s well supported... my PCI ATI Rage Pro works perfectly, as does my Elsa GLoria Synergy, both are oldish 8mb pci cards.
Any system will completely suck with poor drivers, try configuring windows to use generic vga or vesa drivers if you want a laugh.
X11 is FAR superior to any local-display-only gui system, i have several machines here, and 1 monitor for X, apps running from each machine and displayed here and interacting smoothly with each other and with locally running apps.
http://spamdecoy.net - free throwaway anonymous email - avoid spam!
There are various solutions to this problem. It sounds like the Linux kernel people are trying priority inheritance via the messaging system (local sockets). QNX has had that for over a decade. Because QNX does almost everything, including all I/O, by message passing, it has to do this right. In the UNIX world, message-passing was added quite late, in BSD, and X is one of the few interactive programs that uses socket communication on the local machine. Sockets are used mostly to talk across the network. So support for time-critical local sockets isn't very good. UNIX pipes were the original UNIX interprocess communication mechanism, and they were intended as batch-like devices. Sockets look, and work, a lot like pipes. This legacy is the real cause of the problem.
Of course, the reason Linux users actually want this feature is so that they can play their pirated MP3s in the background while using X-windows.
Not quite right. Every multi-tasking system since the first few in the 70s has had the concept of running interactive apps with a higher priority. It's a very obvious improvement.
The non-obvious improvements are things like making the applications that depend on, or are depended on, by the interactive app, run faster. There are also additional tweaks to this that that are being considered such as giving interactive programs a smaller time-slice, but more of them, so it'll do things like paint the windows properly in respose to your movements, but it won't bog the rest of the system down.
Technically, scheduling tweaks do add to code complexity, but only in such a tiny way. Linus's patch was five lines. And Linus is very concerned with making sure patches are self-contained and, when possible, aren't spread out, a few lines in many different areas. He's got a very good, very "correct" attitude about design. It comes from him being happy with Linux for years now, he's not rushing to any specific point so it becomes useful. He's willing to put the time in to do it right.
Anyways, this is to say that most kernel patches don't lead to complexity, most decrease the complexity of the code. Linus has often sent patches back to be done the "right way" instead of allowing a hack. This tweak is so small and self-contained that it can't really be said to add complexity to anything.
Err, these are competing philosophies. You can't have both types of scheduling going on. Think about it: you have an interactive process which wants to use all the CPU all day long, and you have 6 server processes that want to have balanced scheduling for the clients they are handling. No matter what the scheduler chooses, it is being unfaithful to your bit for each process.
Check out the Solaris 9 Resource Manager, which can do both types. It allows you specify at a high level how much of the system's resources each group of processes gets under which conditions. You could say for example, group A (interactive) gets up to 100% unless group B (batch) needs some, in which case allow B up to 30% during the day and up to 70% at night. You could do this sort of thing in VMS over a decade ago. Also, even if the underlying OS doesn't give you the capability, an Oracle server running batch and interactive tasks can do it too.
X is the most important example, since it doesn't help how much CPU your xterms or other X clients you run get if X doesn't get enough CPU time to service them, as if X doesn't get enough time the only thing extra CPU time will give your x clients is the ability to go back to sleep faster and more often.
Realtime scheduling is something else alltogether. Realtime scheduling is about predictability, not about CPU time allocated. With a realtime scheduler you can guarantee that task A get some time at least every 10ms, for instance, but if you're maxing out the CPU you still need a way of deciding which tasks have priority, or reduce their overall time slices.
The kernel patches in question attempts to decide which tasks to give priority automatically, instead of resorting to hacks like using nice on specific processes. It achieves that by making the assumption that if task A is interactive, and it frequently waits on B, then task B needs to get more CPU too.
Since a high load desktop scenario will likely have lots of clients waiting on X the result is that X will get more CPU even if X itself isn't an interactive task, and hence the machine will hopefully feel more responsive.
The way this is being accomplished is good because it doesn't special case - any non-interactive task that provides vital services to interactive tasks will get more CPU (though in this particular implementation, I believe only if they communicate using Unix domain sockets), without the user or developers having to guess which processes should get it.
Not at all. Indeed the lkml thread referenced was about getting good performance when there are some non-interactive processes such as gcc and some interactive ones such as MP3 players or the X server.
Suppose there are two CPU-bound processes marked as 'batch' and one process marked as 'interactive' which spends most of its time waiting for user input, but needs to respond quickly in short bursts when that input happens. The interactive process will get high priority and preempt the two batch processes when it needs to run; but when it goes back to sleep the two batch processes are scheduled with long timeslices.
-- Ed Avis ed@membled.com
This example perfectly illustrates what linus was having problems with when Ingo suggested that users just nice X up. It hides the problem, but doesn't actually fix it. Windows XP plays tricks on users to make them think that it's faster than Win2K or even NT. It loads the GUI earlier than the previous OSes, but there is still a lot of shit happening on the system in the background when you first get to the desktop (services starting, background apps loading, etc...). This is what causes the delay in response to clicking on the Start button. To prove this to a friend with Linux, I set X to start up a lot earlier and disabled a few of the non-critical services in the init scripts and compiled a custom kernel. Total APPARENT boot time from "Joe User's" perspective was about 30 seconds. I have to wonder if it would be a hell of a lot faster with this new patch. The thing is that these changes DON'T actually make the system faster at all. It's pretty much the same as before, but the end-user experience is that it APPEARS faster. That seems to be what a lot of people miss in this discussion.
Un-news
What's being described here is called a priority inversion, where a high-priority task makes a request of some service running at a lower priority and gets hung up behind it.
Which is wrong. Did you read the article?
Priority inversion is, as you explained yourself, about a high priority task effectively getting a low priority by being dependend and therefore waiting on a low priority task.
The article is about tasks at the same priority[1]. The task scheduler distinguishes between interactive and non-interactive tasks in order to improve latency where the user cares.
Beforehand, the behaviour failed on a slow, loaded system to recognize the X server as interactive, because then X looks like a CPU-hog[2]. That resulted in freezes of several seconds[3]. Simply speaking, the patch solves this by passing some interactivity points between processes.
You could have easily seen that this is not about priority inversion as one of the suggested work-arounds was to simply increase the niceness of the X process (which wouldn't help, if priority inversion had been the problem).
Regarding QNX: As good as it is as a RTOS, as bad it fails to do something sensible when you have too much processes at the same priority. Having a reasonably working system presumes that each task is assigned an appropriate priority. Of course, the people at QNX did a decent job on the default priorities.
[1] It may have an impact on tasks of different priority. I did not care to investigate that aspect, because that is of minor importance to what the patch is about.
[2] And for the scheduler, interactivity is determined by a process going to sleep often (by waiting for interaction).
[3] For non-interactive processes it is beneficial to do them in larger hunks, i.e. let 5 seconds other processes do their work, then work 5 seconds, instead of having 0.01 second slices and do the switching all the time.
Keep an eye on which arguments are silently dropped in replies. Not always, but often times it's very telling.
It doesn't. It goes through a UNIX socket. There is a significant difference.
I somehow doubt there was a single reason.
Concentrating on the UNIX socket is a mistake anyway. You need some form of client/server separation; otherwise you could never run more than one client. You also need some form of synchronisation between the clients and the server; otherwise you would have two clients accessing the hardware at the same time and most video hardware would simply lockup. The synchronisation method could be locks or mutexes or message passing or sockets; X11 chose a socket because that gives you UNIX sockets (local, high speed) and TCP/IP sockets (remote, flexible) without needing to code for special cases. Network transparency "for free".
Now the real question with X11 is "who should control the hardware". With X11 they decided a single process - the server - should control the hardware. This is perhaps the serious argument against X11. There are several reasons why this hurts performance but the serious problem - the one you inelegantly complain about - is that the client has to bundle all drawing requests up and send them to the server.
But stop. What's the real problem here. It's not that the bundling had to occur. No matter what model you chose there would have to be some data bundled up and sent between client and server. The real problem is the quantity of data. In Windows the quantity is a single message which is always quite small. In traditional X11 the "message" (aka request) grows without bound. If you're passing a huge bitmap then the request will be several kilobytes. Network transparency comes at a cost.
But stop again! Is this really a problem? The answer is no. X11 is extensible. All of the problem cases - bitmaps, video, 3D - can be special-cased with extensions. So on XFree86 we have Xvideo, MITSHM and DRI. In a traditional X11 model these guys would have stuffed the pipe to overflow and everything would have gone to shit. In modern XFree86 there is a second path that bypasses the pipe. You'll notice that DRI even allows the client to directly access the hardware! Network transparency is still there but can be bypassed on a needs basis. Perfect.
Now your argument shouldn't be "why do we need a client/server model" but "could we use something faster than sockets". The answer is no. There has already been work done by the XFree86 team where they tried a shm transport. It's no faster. Linux sockets are simply too quick. There's no reason to think that message passing would be any faster: effectively the X11 socket is a highly tuned message passing API. The platform independent nature of X11 means you'd need to use a platform independent message passing API. That probably means RPC or CORBA; X11 is going to be faster than either of those.
Anyway, my point from all of this is that the performance problems you complain about are being fixed. The developers are not idle and they are not stupid (far from it). If you wanted somebody to make your desktop faster then you could do no better than to put your trust in the current XFree86 developers team. They are a truly remarkable group of developers. They are not ignoring the performance problems. Give them some credit for understanding the depth of the issues rather than the superficial "why does XFree86 use TCP/IP?" misunderstanding that tries to pass for constructive criticism.