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.
After watching traffic about this almost every day for several months, I can say that I agree with this inclusion and hopefully some of the Low - Latency patches will make it in as well.
$home =~ s/work/play/gi; nice -20 run $home;
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
I am interested to know if this will make the response time on X86free faster. So far from what I have noticed, comparing the way MS-Windows works where the GUI is running within the kernal, and how X runs non natively. I have seen significant lag between mouse clicks and on-screen response.
Example. Running XMMS and pushing play on an MP3 the video display and the sound are not synched. I am running a reasonable video card and sound card (Geforce 256 and a SB-Live) and I expect the video to work on the same scale and rate as the audio, like MS-Windows.
BTW, this has been one of the biggest complaints I have had against X86free and why I haven't completely made the transition to Linux yet. If this patch does in fact improve the response time of X86free, then I would be more likely to use it more often than I use XP.
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
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.
I know this is somewhat offtopic, however to make Linux more responsive, we need to improve X somehow. I am not saying that X sucks...I think it is a fantastic system
Anybody who uses X and Windows regularly knows the difference in responsiveness. X Windows does what it was for designed extremely well-- a client/server display system. However, due to the marshalling and de-marshalling of X calls, even if completely local, it will always be less responsive than other methods (winblows).
But I have an idea. Develop a system that implements the exact same interface as X but does no marshalling/demarshalling. Pixels can be written directly to the framebuffer. So you are thinking, "Yeah, but I want to use X apps without recompiling". Ok, use library interposition. This also allows you to use a "local" and "global" X library to maintain client/server capabilities. For those who aren't familar which library interpositioning, it essentially takes advantage of dynamic linking (set LD_LIBRARY_PATH on Unix). If you want to run a X program that directly writes to the framebuffer, then switch your LD_LIBRARY_PATH to a different directory before the program is executed. This could get annoying, but a Window Manager like Gnome could take care of this automatically.
Granted that our existing X server would have to be retrofitted to allow 2 different types of X libraries to update the same display to that we can run standard client/server X apps with the new "directXfree86" (no pun intended) apps.
However library interpositioning can be used to make X programs more responsive without sacrificing client/server capabilities and compatibility with existing applications (except those statically linked of course).
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 !
I compiled this into 2.4.17 with the preempt-kernel-rml-2.4.17-1 patch. When i booted i got PPP module errors, and when i tried to install the NVIDIA (2314/2313) drivers it gave me more errors. So i went back and disabled it...
Im looking foward to trying this patch out again when 2.4.18 comes out and i hope it works better.
-phinn
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
I know that I shouldn't ask this because there has already been enough changes and troubles in 2.4 - but I've got some Karma to burn:
Wasn't this patch long enough available on 2.4 so that it should be stable enough?
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
Perhaps you're thinking of 'pre-emptive multitasking'? Here's some general multi-tasking info.
As I understand it, the pre-emptible kernel patch allows user processes to pre-empt the kernel itself. Apparently the NT I/O subsystem is pre-emptible.
Yours Sincerely, Michael.
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!
Not pre-emptive, pre-emptible. The first describes a mode of multi-tasking. The second refers to user processes being able to pre-empt the kernel.
Yours Sincerely, Michael.
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
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
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));
Doesn't this patch just add a bunch of extra schedualling points in stategic places? That's not technically "preemptible". Or perhaps I'm thinking of one of the other "preemptible" kernel patches :~)
Well, even if the NT kernel is preemtible, the implementation sucks. Overloading or crashing drivers can and will lock up every other process on the machine, while with 2k a hung kernel process doesn't kill the entire machine. Of course, it may just be a better-behaved shell, I haven't done any real testing, just my observations.
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));
"damn it, I am a preemptible patch, not a miracle!"
sic transit gloria mundi
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.
While the preemptible kernel is a more elegant solution to scheduling latency than peppering the kernel with rescheduling checks, Andrew Morton's "Low Latency" patches give better performance. I'm doing 24-bit/96-kHz audio and with the LL kernel I get vastly more stable performance than the PE kernel. Note that you aren't going to see a spit of difference with either kernel unless the process is running at realtime priority (i.e. SCHED_FIFO or SCHED_RR).
burris
Preemptive multitasking - the kernel and high-priority user tasks can preempt userspace tasks, and force them to give up control of the CPU. Linux and MacOSX are too)
FYI, MacOSX also has a preemtible kernel (Mach 3.0)
As others have pointed out, DRI, DGA, etc all exist. Another thing to point out is the performance of Windows in VMWare. It feels responsive. Why? Simply because the VMWare video driver is smart. It knows how to turn Win32 calls, boil them down into vectors, and send them off to the X11 video driver very quickly. This is why DGA fullscreen Win98 is as fast on my machine as it is navite for video updates (but I've not run Windows natively on my workstation for over a year).
If you want more responsiveness, fix your toolkits. This is happening in GTK+ v2. Look at the changelogs and code. IF you treat a video card like a framebuffer, you lose out bigtime. If you do everything as a vector op, you save bigtime ! This is (on of the) reason(s) why OpenGL is popular -- it's a vector API for 3D graphics.
--
Internet Explorer (n): Another bug -- that is, a feature that can't be turned off -- in Windows.
QNX stands as a rebuke to those who say a microkernel OS has to be slow.
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
X just destroys Windows as a windowing system.
One of the sad, unintended consequences of Linux's popularity is that there is a young generation of geeks out there who think that X-windows is something other than a comedy of errors.
The toolkit, the inefficiencies in communication, the lack of intelligent control at the terminal side, and the list goes on and on...
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.
The linker definitly needs some work on linux. Program startup can be painfully slow especialy when using KDE (C++). This really gives the feeling of a slow system, even though when the programs are finally started, they run rather snappy.
Redhat 7.2 has a prelinker utility on the cdrom although it is unsupported. I tried it out. Installed it, and ran the prelinker on all binaries in the default path (it appears to include most libraries and binaries). The improvement was negligible if even there.
Any Ideas on how this could be improved in the future. I have two ideas that I can think of to improve the linking performance, or at least improve the feel of the linking.
1. Memory pages that are linked, but not dirty(Havent been updated since) could be marked as part of a link cache. For instance the same program starting up could just ajust it's page table to point to the already linked page, and update the page count. The page would then be copy on write. These pages would be usable until the reference count is zero, and the system needs the page for other purposes. This would impove load speed as long as the program was previously used, and it's pages haven't been used for other purposes. This would be great for multiple use systems like a terminal server. I don't know if this is possible, or already been done, and I'm behind the times.
2. Simple start up tricks. For instance the window manager opens a frame where the program is going to start up. The frame would contain a throbber, status bar, etc. The frame would resize once the program connects to the Xserver to surround the first window of the application.
I hope these posts aren't too off topic.
Thanks.
Adam
Pre-emptive multitasking is ment for tasks that run ON TOP of the kernel, since the kernel does the scheduling :) That works for ages in all kinds of OS-es, also Linux.
Now, what about tasks that are part of the kernel? Are these run in a pre-emptive multitasking environment? Some OS-es don't and some do. Most OS-es have a different kind of scheduling of tasks within a kernel, so a kernel can predict when a kerneltasks is finished and can prevent kerneltasks from stalling the overall systemperformance. What is done here, is that by this patch, Linux got a pre-emptive scheduler for kerneltasks, so these are scheduled on a different way than before, resulting in better overall performance.
Your gzip-X problem has nothing to do with it: if 1 program hogs the cpu, another can't fully use it.
Never underestimate the relief of true separation of Religion and State.
Win9x doesn't run entirely in kernelmode. It runs 32bit processes in usermode and it's own modules in kernelmode.
The NT kernel is partly pre-emptive because it's build up by a very small core that only does scheduling and very low level stuff. All other kernelprocesses are tasks on top of that small core. So you can implement the scheduling between these parts as a pre-emptive scheduler. BECAUSE it's pre-emptive it's so fast. The NT kernel isn't eating more performance than needed, it's more faster than comparable kernels. This has been tuned in win2k and in XP. In XP f.e. the locking mechanism which is holding back NT's kernel has been greatly enhanced. Locks are the nail on the pre-emptive-kernel-coffin.
Linux has a big kernel, it's not implemented as a small core that simply does very very low level stuff and scheduling, it does a lot more.
Never underestimate the relief of true separation of Religion and State.
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....
In 1991, OS/2 2.0 had pre-emptive multi-tasking AND multi-threading in the kernel. Windows NT 3.1 had it too but what a slow pig that was.
I don't think *nix's got multi-threading til the mid 90's (Solaris first?). But then again, creating process's on *nix's was faster than creating a thread on Windows. On OS/2 that was questionable ( IBM knows how to make a kernel ).
This is a very good move and putting it into the 2.5.x kernel so early will help test the heck out of it. Good move. IMHO
LoB
"Anyone who stands out in the middle of a road looks like roadkill to me." --Linus