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 have been waiting for this for a long time. I was not even sure whether Linus will ever accept it one day. This is a major achievement for Linux and open a lot of new opportunities in Desktop and Real time applications.
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 thought other UNIX's and Windows and OSX already did this.
In fact, I'm surprised that Linux doesn't do it.
This isn't meant to be flame-bait, I'm a newbie in regards to the kernel. But isn't this common technology everywhere else?
this is not a sig
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
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
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
The new scheduler and the preemptible patch should work together well. The new scheduler is designed to make interactive tasks seems snappier, so 2.5/2.6 should be a lot faster on interactive stuff.
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.
This is a (good) sign that Linux is more interested in the Desktop than before. Adding this feature probably will slow down Linux servers since there is more overhead, but will make desktop machines appear faster. I am glad to see that desktops are taking priority over servers.
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 :~)
I hate the fake word "clueful". It's a stupid, obnoxious word.
Please don't let it catch on.
~jeff
I hate the fake phrase "catch on". It's a stupid, obnoxious phrase.
Please don't let it become popular.
Yours Sincerely, Michael.
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));
from the first article:
"I tend to disregard any technical comments when there is bias."
https://www.accountkiller.com/removal-requested
Go take a look at the Berlin Consortium. Berlin could eventually replace X. It could have an X compatibility layer, it is speedier, gives a consistent look on all apps. However, it needs much more development.
Berlin is a windowing system derived from Fresco, a powerful structured graphics toolkit originally based on InterViews. Berlin extends Fresco to the status of a full windowing system, in command of the video hardware (via GGI, SDL, DirectFB or GLUT) and processing user input directly rather than peering with a host windowing system. Additionally, Berlin's extensions include a rich drawing interface with multiple backends, an upgrade to modern CORBA standards, a new Unicode-capable text system, dynamic module loading, and many communication abstractions for connecting other processes to the server. It is developed entirely by volunteers on the internet, using free software, and released under the GNU Library General Public License.
Berlin FAQ
Berlin vs X
--Metrollica
But will it mean that Star Office 5.2 on my 166 with 128M RAM will actually run at a decent speed?
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
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.
Currently the pre-emptive kernel is unavailable under make menuconfig on an alpha cpu
http://spamdecoy.net - free throwaway anonymous email - avoid spam!
On the Alpha the HZ is already 1024, and has been as long as i`ve been using it.
http://spamdecoy.net - free throwaway anonymous email - avoid spam!
Infrastructure, not interface. And that's used solely for 3D acceleration at the moment.
The main problem I see with the current UDS based X implementation is not the slowness of the transport, but the sheer amount of protocol data there is to send. With a higher-level tooklit running in the server's address space, we probably wouldn't be having this discussion.
I was always under the impression that the Great 32-bitOS of the Future is, indeed, a preemptive multitasking OS.
Are you telling me that it was the same as the friggin' Win 3.1 (albeit with memory protection and 32 bits)??
The sad thing is, when I would point out ot Linux zealots that gzip would slow down X, I would get attacked from right and left with "you don't know how to configure Linux".
Sigged!
Is it possible that most of the big distros like RH and Mandrake will compile this into their prerolled kernels? It's probably gonna be a while before the distros sold at retail outlets start using 2.5 (RH and Mandrake are still using kernels earlier than 2.4.10 due to the VM system), but would there be enough of an advantage in desktop responsivness for them to use this by default?
I guess I reasoned that I would always have a sort of love/hate relationship with UNIX and its clones. Then when RTAI and RTLinux came along, that solved that, but it did so (I ASSUME) by philosophically thumbing its nose at UNIX tradition. Ok. So Linus decided to keep the default behavior not preemptable, which makes sense, but--given that the "Linus blessed" Linux version numbers have an optional preemption behavior built in--doesn't that mean a significant parting of company between the Linux kernel and UNIX as people know UNIX to be?
no kidding. what i though would be even nicer would be a way to dynamically udate hz.. during idle hours, or when one big process is running, hz low would slightly (negligibly probably) increase thru-put, while in busy times, hz==1024 would help responsiveness/reduce latency.
implimenting this is difficult though (in the middle of it, little to show for it). everything has the right to change the pit (x86, maybe mips) and there seems to be no way to read what was written. pit shold have been made a device from the start.
QNX stands as a rebuke to those who say a microkernel OS has to be slow.
Oh, yeah, X blows Windows away, except for the standard printing architecture, the single widget toolkit (argue for choice all you like, but as far as I'm concerned having up to 5 competing toolkits all visible on my desktop is horrible), the raw speed of the windowing environment (Windows is a whole lot more responsive than X on Linux on my machine, although I would much prefer if the reverse were true), a single sound API (Linux has oss, esound and a variety of other more or less workalikes), even simple things like ABILITY TO CHANGE COLOUR DEPTH ON THE FLY. I love Linux and use it exclusively, but compared with Windows, X is a dog.
Yeah, it'd just be nice if DRI worked better. :) DRI with my Radeon was so flaky, any speed benefits of it over my crusty ol' GeForce 2 MX were lost. Crashes, hang-ups, graphical glitches...
DRI is an excellent idea, but its implementation at the moment leaves quite a bit to be desired. If I had the coding talent, I would try to help contribute and improve it... Alas, I cannot.
Mozilla's a nice operating system, but it needs a better browser.
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...
I'll try not to boast, but I for one have a state of the art (circa-never) Cyrix 300 (running at ~216MHz), 128mb of RAM, and an ATI XPert 98. When I'm using Windows 2000 I get a fairly responsive system - IE is quick, loading in about 3 secs, Word doesn't seam too slow, also loading in 3 secs. Editplus, WMP6 and WinAmp load in roughly a second each. Windows/Mozilla appeared in on 12 seconds.
When on Linux/X/KDE2 the system was far from snappy, and close to being unusable. X/Mozilla loaded in about 25 seconds, XEmacs in about 8, Konquerer in about 10, XMMS in about 6. I tried Gnome at one point, and it was a little faster, but still far slower. But it wasn't just boot times; XFree86 couldn't resize in realtime in any sense. Resizing a slashdot window in Windows/IE is no problem, and at a very rough estimate about 10fps, and even Windows/Mozilla at a usable 5. For me it's a completely different story under XFree86: Mozilla and Konquerer both resized at about 1fps, which is unusable. I will be honest with you - I've probably spent less than half an hour reading XFree86 docs. But does that mean I can't critique it? Does that mean that when I'm using it that it's of an acceptable speed? Does it fluck.
tlhf
Notes to the possible responses:
Yes, I have used [Gnome|TWM]. Yes, I will accept it's faster than KDE2. No, it's still not as fast. No, I'm not astro-turfing, in fact I prefer BeOS. If only BeOS had multi-user support and memory protection. Long live Glass Elevator! The system those times are off was Mandrake 8.0. I've also run DemoLinux 3 on my PC, and FreeBSD. XFree86 was still slow. Yes, all those times are fairly rough estimates, and probably upto 75% off each. No, this doesn't make my point wrong. Any idiot with a slow PC will tell you XFree86 is s l o w. Yes, all those tests were done on a first run, no caching. I'm not thick. Except maybe IE, which manages to have itself constantly cached due to half being in the OS. Yes, the memory usage was about the same on both (roughly 80mb after a boot). Yes, I know parts of the Win2k GUI are at a lower level than X. And yet I don't care, for my desktop PC
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.
Very recently I started evaluating the different approaches to realtime in Linux. As i gather in the Preemption Enhancement "Linux kernel code is modified to reduce the amount of time that the kernel spends in non-preemptible sections of code..."
... that there are certain context switch latencies involved when a process is switched into in user space (due to MMU processing overhead, cache line flushes, and other things), that will inherently yield more jitter, and thus worse case guaranteed task switch latencies.
As pointed out this approach has problems:
* increased complexity and hard-to-maintain code.
* extra context switches can be counter-productive
* who will track the code-path?
* This approach places an onus on the kernel developers to put together pre-emptible algorithms which is definetly not easier than developing non-preemptible algorithms. (Logically this woulld cripple the development rate of kernel enhancement and debugging!! )
On the other hand there is "Interrupt Manager", or the "Micro-Kernel" approach. Its a neat trick by veteran RTLinux hacker Victor Yodaiken. Read more here
I quote from this source "...entire kernel is made preemptible by having a separate hardware-handling layer intercept and manage the actual hardware interrupts on a system. This hardware abstraction layer has complete control over the hardware interrupts, and simulates the interrupts up to the Linux kernel in a way that allows the kernel to run unmodified on the real-time scheduler. linux kernel remains largely untouched"
If you want "hard guarantees" you make Linux kernel loadable modules software modules(just like device drivers etc.) otherwise make regular threads in the user space.
There are arguments against this approach as well-.. "its not linux" , "unique programming model" etc. The most important is
taking into account the pros and cons of both approaches it seems that balance tilts in favour of "Interrupt Abstraction" approach as from my point of view it should put lesser burden on kernel developers. Can somebody point out to me what was the reason for going otherwise?
Voltaire: God is dead.
God: Voltaire is dead!
Hey I'm not an expert on Amiga OS internals but IIRC it had pre-emptive *multi-tasking* which is very different from a preemptible kernel.
The difference is in what gets preempted - in pre-emptive multitasking it is just user-mode programs that get interrupted, wheras with the pre-emptible kernel high priority tasks can interrupt the kernel itself.
So did the Amiga have a pre-emptible kernel, or was it just preemptive multi-tasking?
Or was it just a low-latency kernel, which gets you most of the benefits of kernel preemption from the point of view of multimedia apps?
If it was just multi-tasking/low latency, that's not exactly a big deal as most OSes have had that for years.....
not a kernel problem.
But the GCC people are working on it.
-- "As a human being I claim the right to be widely inconsistent", John Peel
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....
I've tried the patch under various kernel versions under heavy desktop/X11 load, and it only makes the problem worse - instead of slowing down the system immediately, the system gets slower on a delay, and disk I/O is done in chunks instead of when it's supposed to be done. All in all, this patch just makes the kernel respond even slower than without the patch. Things like unRARing files or apt-get upgrade-ing the system will slow down X11 to almost an unusable state with this patch, while it is bearable without the patch.
i think you have no idea what you are talking about.
:)), but any application could get supervisor mode if she wanted to) and just look at all the places in exec that simply did
the amiga had no kernel at all. there was no difference between kernel space and user space. (ok, some few things had to be done in supervisor mode (eg stop #$xxxx
move.w #7fff, $dff01e (ie stop interupts!)
OK, so it's kind of "preemptible everything".
Never knew that - thanks for the info!