Slashdot Mirror
Preemptible Kernel Patch Accepted
An Anonymous Coward writes: "The preemptible Linux kernel patch that was originally introduced by MontaVista Software and more recently championed by Robert Love has been merged by Linus Torvalds into the main linux development-kernel tree, beginning version v2.5.4-pre6. This adds a far greater degree of real-time responsiveness to the standard Linux kernel, by reducing
interrupt latencies while kernel functions are executing. The story at LinuxDevices.com includes comments by Robert Love, and there is also a recent interview with Robert Love about the preemptable kernel here and a whitepaper about the technology by MontaVista here."
But many folks may have no idea what effect preemptability actually has upon a user who uses GNU/Linux. Here's the good news:
:: A Weblog On Crack
[] Smoother video
[] Smoother user interface
[] A seemingly more responsive computer
[] Overall smoothness in operation
(reply to this if you'd like to add to my list)
Congrats to Linus for getting this ready so soon, and to those who helped develop it.
EricKrout.com
If you celebrate Xmas, befriend me (538
RL: Please summarize the advantages in general, not just for embedded real-time apps, of having the preemptible kernel enhancement included in the kernel. What about any disadvantages?
Love: 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 userspace. 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 multi-processing) locking constraints. That is, we use spinlocks as markers for regions of preemptibility. Of course, on UP (uni-processing) they aren't actually spinlocks, 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 RT 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 counterarguments. The first is that the preemptible kernel lowers throughput since 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 since they are unique to each CPU, a task on another CPU can't touch them. Preemption makes it an issue since 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.
--Metrollica
I completely agree. This is one of the biggest annoyances I have with Linux: that there is a percievable delay between clicking, say, the "File" menu in a GTK-based app and the contents of the File menu showing up.
However, I doubt that it's XFree86's fault, as the port of X-Chat (which was built with GTK) to Windows shows the same menu behavior as its Linux counterpart. On Linux, however, IceWM exhibits no menu delay whatsoever.
Then, of course, you have to take into account if you're running a theme that uses pixmaps. If you're running bubbles-gradient, for example, you're more than likely wasting a horrendous amount of CPU cycles just to highlight a button. Even with fast themes like thinice, the delay is still there.
It's this kind of clunkiness that makes me wonder how people can use themes like this
http://www.linuxdevices.com/articles/AT5152980814. html
The average throughput drops. In other words, it's not something you use on a server, but it's very useful for embedded devices, where latency is important. It's also very nice for desktops, been using it for ~2 months now. YMMV, but my desktop is a _lot_ smoother.
With this patch the kernel becomes preemptible - meaning, other kernel tasks can stop the current one from executing, execute, finish, and allow the stopped tasks to finish.
Net effect - expensive operations can be suspended for user interactiveness. Can this impact performance, Yes. Noticeably? No.
If you're running a big-ass server, it's probably head-less, anyways - and you won't have any large, interactive processes preempting the kernel for smoothness.
If you're running a workstation, this means that X won't bog down as much when you're running those huge simulations, compiles, etc.
If you're on an embedded device, you can use this to try and get real-time responsiveness. (perhaps not ideal, but, in an embedded situation you have enough control that if you need a better real-time guarantee, you have other options (e.g. rtlinux).)
If you're on a modest, consumer PC - X won't suck as much.
All in all, this is a good idea. In theory, you lose some efficiency making several thousand context switches/second, but that's the price you pay for multi-tasking. Yeah, certain kernel operations may take longer, but, you get a better responsiveness, which - for most people, is a good thing. Most interactive individuals are seldomly pegging their processor at 100% utilization for any worthwhile period of time. (Games are an exception.)
This is good stuff.
fnord.
Quake 3 has never been smoother on my machine. 2.4.18-pre7 with Robert Love's Pre-emptible Kernel patch and Ingo's O(1) patch. Get it.
Yours Sincerely, Michael.
http://linux.bkbits.net:8088/linux-2.5/ChangeSet@- 1d?nav=index.html
:)
It's just 3 hours old
A very nice way to follow the fresher kernel !
It shouldn't have ANY effect on scalability. First, scalability really refers to how well the kernel handles multiple processors*, which isn't what you're talking about. Second, a process doesn't preempt another process unless it has a lower priority. As long as each of the 2000 users' apps have the same priority level, they'll all get the same response times. The only time preemptibility comes into effect is when the priorities are diffrent. In that case, a higher priority process can preempt a lower priority one, even if the lower priority process is running in the kernel, just like it should be. Big name UNIXs like Solaris are fully preemptible, and there is little question about how well they scale to thousands of users.
*Not technically, but that's the most common usage.
A deep unwavering belief is a sure sign you're missing something...
Linux user-space processes have always been preemptible. The kernel itself was not. WinNT/2K is fully preemptible (kernel and user); other flavors of Windows are not. Preemptive multi-tasking means that a process can be forced to give up its control of the CPU. This is opposed to cooperative multi-tasking, which means each process must voluntarily give up control before others can proceed. In general, preemptive multi-tasking is a good thing because it means one process cannot hog the CPU.
Taken from the Bitkeeper diff
--- 1.3/arch/i386/Config.help Tue Jan 29 06:32:09 2002
+++ 1.4/arch/i386/Config.help Sat Feb 9 11:11:32 2002
@@ -25,6 +25,16 @@
If you don't know what to do here, say N.
+CONFIG_PREEMPT
+ This option reduces the latency of the kernel when reacting to
+ real-time or interactive events by allowing a low priority process to
+ be preempted even if it is in kernel mode executing a system call.
+ This allows applications to run more reliably even when the system is
+ under load.
+
+ Say Y here if you are building a kernel for a desktop, embedded
+ or real-time system. Say N if you are unsure.
+
CONFIG_X86
This is Linux's home port. Linux was originally native to the Intel
386, and runs on all the later x86 processors including the Intel
The patch makes scheduling occur in O(1) time... i.e. very good scaling as number of processes grow, I believe.
O(1) is constant time regardless of input size. O(n) means time grows linearly with input size. There's others but I don't know that much about it...
Yours Sincerely, Michael.
I expect it won't be any better.
NVIDIA drivers have to be rebuilt when you build a new kernel. As for PPP, you were probably just missing a driver when you configured.
WWJD? JWRTFM!!!
Robert Love has another patch that I'm hoping to see make it into the kernel. For systems in headless situations with large entropy reqs, this is pretty much make or break.
/ netdev-random/README-netdev-random
http://www.kernel.org/pub/linux/kernel/people/rml
describes what it is all about
This is an option in the kernel. if you aren't compiling a kernel for a desktop box, chances are you won't want to enable this in the first place. therefore your net loss is zero.
Note to self: pasty-skinned programmers ought not stand in the Mojave desert for multiple hours. -- John Carmack
Folks:
It should be noted that this will lead to a compile error if you enable preemption but disable SMP. To make this build, you need to add this patch:
diff -urN linux-2.5.4-pre6/include/asm-i386/smplock.h linux/include/asm-i386/smplock.h
--- linux-2.5.4-pre6/include/asm-i386/smplock.h Sun Feb 10 15:35:55 2002
+++ linux/include/asm-i386/smplock.h Sun Feb 10 18:15:55 2002
@@ -15,6 +15,7 @@
#else
#ifdef CONFIG_PREEMPT
#define kernel_locked() preempt_get_count()
+#define global_irq_holder 0
#else
#define kernel_locked() 1
#endif
w o r l d w i d e w e b e r
You are probably thinking of preemtive multitasking. Most modern operating systems use preemtive multitasking, where the kernel enforces when a process gets on the CPU, instead of cooperative multitasking, where a process (in a cooperative way) tells the kernel that it's okay to interrupt it (directly or indirectly) and then kernel makes a decision to give another process the CPU. Cooperative multitasking is bad because a process can decide not to cooperate and effectively take over the system.
This is a refinement on preemptive multitasking, which linux had before. Before having a preemptive kernel, the kernel could only preempt the process if it wasn't in a kernel call (okay, there are some kernel calls like writes to disk that it can preempt but most it can't). So, if an interrupt happens while my process is in the middle of a kernel call, the process that handles the interrupt will just have to wait until the call is completed.
With this patch, my process will be preempted for the handling process, allowing it to respond in a very timely fashion. Thus, this is considered to be a prerequisite for real time operating systems.
According to this Windows NT does have a preemptive kernel, but I doubt 9x/ME do. I'm not even sure that page is right, since I couldn't find any primary sources for this and other pages imply it doesn't (by listing a fully preemptive kernel as a feature under one operative system, but not listing it under windows NT).
Windows CE definitly has a fully preemptive kernel.
-no broken link
Pretty good response, though I would note that even for video decoders writing to a raw framebuffer isn't desired... Writing directly to an allocated overlay in a colorspace natural to the decoding is better (that way, X provides a surface to write to that takes care of both colorspace conversion and scaling in hardware, two *Very* expensive video rendering tasks.). There are very few applications in which direct, unmediated framebuffer access is that beneficial... For example some apps support all sorts of targets from standard Xlib, to XShm, to DGA, to GL. The DGA is probably the closes to direct access, and, no surprise, it isn't that impressive....
Of course, I think the poster didn't really mean direct framebuffer access, but rather trimming Xlib where possible to not do things that increase latency locally, which, as many have pointed out Xshm does that very thing..
XML is like violence. If it doesn't solve the problem, use more.
There are different level of multitaksing.
Cooperative multitasking - each process has to willingly give up the CPU, thus one program can bog down the whole machine. Older MacOS incarnations are like this
Preemptive multitasking - the kernel and high-priority user tasks can preempt userspace tasks, and force them to give up control of the CPU. Linux < 2.5.3 is like this (I believe Win9x and MacOSX are too)
Preemptable kernel - High priority user tasks can preempt the kernel as well as each other. Net result - lower latency I/O, possible reduced throughput due to more CPU overhead. QNX, some other commercial Unices, and WinNT/2k are here
0 1 - just my two bits
Preemptiveness give the kernel the possibility to change direction in the middle of a leap, and later get back to that point to finalize the leap, what ever system call that is. It will of course not do this for no reason, only if an important event has happened that has a higher priority than the current running event. A little like 'nice' but much more powerful. Can't be bad, can it?
The next thing to have is predicatability in kernel space, then we can calculate the exact max latency to expect between the important event and the systems respons to it... belive it or not. Check out with Monta Vista for this feature, I am sure they are thinking about it.
Oh wait, that name's already taken as it's been a part of XFree86 by default since the 4.0 release!
/.
Man, people piss me off sometimes... I wish people would actually read something about X before bitching about it on
I don't know why people think X is so horrible. X just destroys Windows as a windowing system. The only plus Windows has it that it has better hardware support. Other than that, X blows Windows away.
And this got mod'd up to 4... Sheeesh
int func(int a);
func((b += 3, b));
Four keys terms to know:
1) Pre-emptive
The operating system can interrupt the currently running process to allow another process to run
2) Co-operative multi-tasking
A task gives control back to the operating system in order to let more programs run.
3) User Mode
On most platforms, an execution state with limited hardware and memory access.
4) Kernel Mode
On most platforms, an execution state with direct access to all system resources including page tables and hardware.
Win3.1 runs entirely in Kernel Mode and uses co-operative multi-tasking.
Win9x runs entirely in Kernel Mode and uses pre-emptive multi-tasking.
WinNT based systems (including Win2k) uses pre-emptive multi-tasking and supports both user mode and kernel mode.
Linux uses pre-emptive multi-tasking and supports both user mode and kernel mode.
Now, a system that has pre-emptive multi-tasking can either only allow pre-emption to occur in user mode, or in both user mode and kernel mode.
Theoritically, something should not be in kernel mode for a very long period of time and what's being done in kernel mode tends to be very important.
So, Linus never really was very concerned about kernel mode pre-emptiveness because it's not terribly useful unless you have a horribly inefficent kernel or you require absolute real-time operations. Instead, he wanted to focus on making sure the kernel was as efficent as possible.
This patch allows one to enable kernel pre-emption, but be forewarned, that it will only increase the total time spent in kernel mode (doing the necessary checks) and it will not have a noticable effect unless you are running very real-time applications. That is why it's disabled by default.
It's a good thing to have for a kernel, but it's not very useful for the average user. That's why it's a configuration option. The big performance increase people are referring to is because of the new scheduler... That's a different thread though.
The fact that WinNT has a pre-emptive kernel is not necessarily a good thing. They are undoubtly taking a performance hit for it and since one can't disable it, there is no way to not have it if one doesn't need it.
I think Linus made a good decision about letting it into the kernel mainline, but I think he also made a good decision about keeping it as a configuration option and not integrating by default.
int func(int a);
func((b += 3, b));
Not that I'm an expert on Video hardware or anything, but that is paraphrased from an explanation given by X-inside for their X server.
LibBT: BitTorrent for C - small - fast - clean (Now Versio
You're confusing preemption with mutual exclusion. Being preemptible only means you can be suspended. It does not mean the task that someone gets to break your locks.
If a low-priority task locks a resource, it can still be preempted by a high-priority task... but if the high-priority task also wants that resource, it's going to have to get in line just like everyone else. This is also what leads to the possibility of priority inversion.
Nothing changes if you substitute "kernel task" for "task" in the preceding paragraph.
--
I like canned peaches.
Freedom is not the license to do what we like, it is the power to do what we ought.
Impossible. The X11 protocol is incompatible with this idea.
This has been tried. See the D11 paper by Kilgard.
The idea is called Direct Rendering and it is not a significant performance win for most graphics ops. The obvious exception is high bandwidth graphics such as OpenGL and streaming video. You'll notice that XFree86 already has direct rendering for OpenGL and streaming video.
Summary: X11 is not the bottleneck on your desktop.
The GLX portion of th nvidia drivers doesn't seem to care what kernel revision you're running on. The kernel module portion does however. I've been running the preempt patch for some time now with several revisions of Nvidia's drivers. Just get the SRPMS and recompile them. Or get the TGZ versions if you're running a non-RPM distribution (slackware, debian, etc).
I don't know what problems others have or have not had, but I've never had a bit of trouble with the preempt patch.
Muslim community leaders warn of backlash from tomorrow morning's terrorist attack.
On one hand, the preempt patch makes heavy use of SMP spinlocks, and the stability of preempt in parts of the kernel that arn't SMP capable (which are few and far between at this point) and on SMP systems is questionable.
On the other hand, an awful lot of users have been testing and reporting back to lkml, and Robert Love has been persuing the bugs with the dedication of a first love. I'm sure that scores points with the power(s) that be on LK.
Desperation is a stinky cologne
I wondered too (I also have a 7200), and found this answer in the changelog:
Timeo idiotikOS et dona ferentes
Well, since none of us seemed to have even remotely complete answers, I decided to do a bit of research. Actually it doesn't really deserve the term 'research' as all I did was take a glance at the appropriate README in RML's directory on kernel.org.
;-)
The patch supports x86, ARM, and SH. Comments the author (Robert Love) has made lead me to believe that the same techniques will work with more architectures. And, now that the patch is mainline, it probably won't be long before this is the case.
If nothing else, all us PPC-heads (or fans of other architectures...) have something to look forward to for a few weeks, eh?
Take it easy,
- John
"where the GUI is running within the kernal" the gui is explorer and it doesn't run in the kernel.
"and how X runs non natively" huh? you mean in user space. The graphics in windows 2k/xp run in the kernel which is what you actually mean by all this.
"pushing play on an MP3 the video display and the sound are not synched" This has to do with the sound being buffered in xmms, the video is rendered from samples as they are placed into the sound buffer instead of when you actually hear them. This has nothing to do with anything but xmms.
Hrm... I am running that exact setup, and due to ISP/CLEC madness, I am also using PPP for connectivity. In fact, I am writing this dialed in with a 2.4.17-preempt kernel. No issues with all of the above plus a GeForce3 with the newest NVidia drivers.
So far, I have to say I am very impressed with the performance. I do notice a difference because I have taken to creating Divx;-) movies which proves to be a loborious task. I can rip a DVD and preview the
Actually Distro's are using 2.4 because it is the latest stable kernel. 2.5 is a developement kernel not intended for everydays use.
Snoozer.
But you will have IO-bound processes coming alive faster once their data is available, often improving throughput. There have been benchmarks floating around that indicate that a lot of typical server workloads benefit from this patch too.
It appears that this is generally a good thing. The only downside is the added complexity.
It is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail. - Abraham Maslow
The locking system in the NT kernel is very conservative. However even hanging kernelprocesses in NT don't bring down the entire machine, it's just that the kernel can't re-grab locked resources that easily. The introduction of spin-locks in XP removed this problem completely, after the enhanced kernelmode locking mechanism in Win2k's kernel. Locking can bring down any pre-emptive kernelscheduler. So in this light, you might say: ok, the idea is good, but the locking mechanism should have been better. The analysis they've done on the win2k kernel which resulted in the implementation of spinlocks in XP's kernel (and which makes it really fly on SMP systems) could have been done earlier, f.e. on the NT kernel, true.
Never underestimate the relief of true separation of Religion and State.
You can have O(f(n)) where f(n) is pretty much any function of n.
:-)
Classifying algorithms this way is *extremely* useful for working out what will give good real-world performance.
In general, you want to stick to O(1) or O(log n) to have performance that scales in a reasonably effective way.
Quite a lot of algorithms are O(n) which is OK for small values of n but can get nasty when n becomes large. Inserting a value into a linked list is a typical O(n) algorithm - OK for small lists, bad for long ones as you have to run down the list to find the correct insertion point. (Tchnically you only have to go halfway down the list on average, which would make it O(0.5n), but by convention and for practicality purposes the notation drops and constant factors).
A large proportion of processor bottlenecks are due to getting stuck in O(n^2) or O(n.log n) tasks. Sorting algorithms tend to fall into this category, which explains why they are often slow and/or processor hungry.
Higher polynomial orders such as O(n^4) etc are possible, but generally less common. Sometimes writing a sort algorithm really badly will get you into this territory however
Then there are the *really evil* algorithms that behave like O(2^n) or O(n!). These rapidly become intractable as n grows. Good examples would be the exhastive search of soloutions for the travelling salesman problem, or an exhaustive search of the tree of moves for a game like chess. When faced with this kind of problem, you are basically forced to either limit yourself to small values of n or choose an "approximate" algorithm, such as accepting the best solution found after a timeout period.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
This is actually a problem with the word "stable".
The even numbered (2.2, 2.4, etc) builds are API stable.
API stable means that a program you wrote for 2.4.0 would run without change on 2.4.99 because the libraries and system APIs are identical.
Now, ideally they'd be stable as in not crashing, but that's never going to happen. New testing releases often have problems.
"But, it's not testing, they released it," you say.
Did you get a buggy kernel from Redhat, or Debian, or any other distro? Or did you go download it seperately and install it? If so, it's not released for end users.
This doesn't mean that those kernels weren't buggy, just that they weren't guaranteed not to be.
Stable is like free, a word with many connotations. In this case is means unchanging, not crash-free. If you want crash-free, simply wait a week and see what people have to say. (You never need a new kernel so badly you can't wait.)
Anyways, the new VM was a big change, but if the original VM wasn't cutting it, I think Linus did the only thing he could. He wanted 2.4 to be usable (if not perfect) so he swapped out a potentially better VM for a simpler VM that would work now. Otherwise 2.4 would still be unusable for many applications and people who needed it would have to use 2.2.x or wait for 2.6 which is likely quite a ways off.
Don't forget that changing the VM doesn't change the APIs. A program written for Rik's VM works fine with the AA VM and vice versa.