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."
I thought that the preempt patch was quite a way from being part of the linus tree. On the other hand, early in a development kernel is probably the right place to integrate it, so that all those device drivers with problems with the preempt stuff (like NE2000, I think) can get fixed.
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
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
You don't get anything for free. What is the tradeoff that occurs when you integrate this patch?
*Condense fact from the vapor of nuance*
What effect would a pre-emptible kernal have on the scalability of Linux?
As far as I can tell, a particularly responsive kernal wouldn't scale very well, since there wouldn't any guarantees as how much "time" as being spent on a thread/process by the CPU.
Think of a large, multi-user environment based on Linux. Do you really want any user to pre-empt the processing in the kernal by CPU to the detriment of other users? A more logical answer to this is to have set guarantees as how much processing time is given to each user. It shouldn't matter if it's one user or 2,000 users, the speed of applications for each user should stay the same as much as possible.
Maybe I'm describing Solaris, or some other operating system like this.
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.
Has anyone tried this patch on non-x86 hardware?
I've got a Powermac 7200 I'm playing with YDL on right now...
(Note: I am not a programmer. Should this be something patently obvious to anyone with the most casual knowledge of OS programming, I still don't know. So don't flame me.)
--saint
Writing pixels directly to a frame-buffer is slow. You lose all of the acceleration features of your video card. Keeping as much of the protocol at a high level as possible is good. The only things that benefit from direct frame-buffer access are programs that do all their own rendering. (Think video decoders.)
Still, if you think about it, the basic gist of your idea is to get rid of the network channel from the communication protocol, and instead have the app talk directly to the X server, say, in shared memory. If so, then how does your idea compare to MITSHM and Shared-Memory Transport? Or the Direct Rendering Interface for that matter? And for 2-D stuff, let's not forget the Direct Graphics Architecture extension. Nothing stops GTK, Qt and friends from using any one of these technologies if they'd improve performance and latency.
--JoeProgram Intellivision!
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
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
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.