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
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.
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.
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
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.
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));
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
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
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.