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."

Comments

Wow.

[1010011010]

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.

Re:Wow.

[digitalunity]

It's really good that it was put in now instead of later. In fact, I really think the new VM should have waited for 2.5 as well. I just couldn't figure out why you'd change such a fundamental piece in the middle of a stable tree! But hey, I don't wear the Linus nametag; not my job.

This will be a good first step in reducing latency and increasing response time in X and other programs.

Re:Wow.

[Chromium_One]

Yes. It all sucks. As has been said in the past though, there is a certain range of problems for which *nix sucks twice as fast and ten times more reliably than Windows.

Re:Wow.

[WNight]

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.

Nice work

[ekrout]

But many folks may have no idea what effect preemptability actually has upon a user who uses GNU/Linux. Here's the good news:

[] 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 :: A Weblog On Crack

Re:Nice work

[jsse]

Aye, it's sure a great news for *cough* gamers. In the past when we'd like to have a smoother 'mouse' we must change the HZ value in include/asm/param.h from 100 to a higher value(progressive increase the value and recompile kernel until it breaks. ^_^)

Other archs like alpha use values higher than 100 e.g.

include/asm-alpha/param.h:# define HZ 1024

include/asm-ia64/param.h:# define HZ 1024

You may try it if you aren't going to go to 2.5.x in the near future, but hell, if you don't mind twisting and breaking the kernel by altering the HZ value, why not 2.5.x! :D

Note: I notice that whenever I talk about changing kernel values the post will be modded redundant. I know a lot of you guys know about kernel insdide out so this might bore you - but come on! I'm sure so many other would be interested in it.

Re:Nice work

[rhekman]

Just to avoid confusion... a few notes about this approach.

First, for those that didn't get it from the parent post, HZ is a system wide timing value. It has nothing directly to do with the mouse.

What it does deal with is how many times a second the system's interrupt timer fires. The problem with increasing the interrupt timer frequency is that you waste more time servicing interrupts than doing real work. It may improve interactive "feel" because the timer interrupt will trigger higher priority tasks to be rescheduled more often, but at the price of higher system time and lower "throughput".

Compared to the preemptible kernel patch, increasing HZ is actually harder on throughput, especially on slower systems. Much work has been done on finding and killing long held locks not covered by the preempt patch (thanks to Andrew Morton and RML), an approach which has been shown to be quite effective. Increasing timer interrupt frequency means you're creating more pointless interrupt load, which goes against the approach and advances of the other low-latency patches.

There is an interesting discussion of the HZ value and how it effects Linux in a VM at Linux Weekly News and for more arcana check out the high resolution timers project.

Regards

Will this apply to X Windows?

[BlueJay465]

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.

Re:Will this apply to X Windows?

[Anonymous Coward]

myself I just type xm

I've also got some aliases for volume if I type 50,60,65,70,75,80,85 or 90 they alias to mixer 50:50, mixer 60:60 etc.

Wow. Welcome to 1973. What's it like back there, caveman? Are you "grooving" to those "funky" "disco beats"?

Tradeoffs?

[chuckw]

You don't get anything for free. What is the tradeoff that occurs when you integrate this patch?

Re:Tradeoffs?

[keeg]

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.

Re:Tradeoffs?

[megabeck42]

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.

Re:Tradeoffs?

[sydb]

Aside from the technicalities of this particular patch, your assumption that you're going to lose something when you apply a beneficial patch because 'you don't get anything for free' is, despite appearing mature and clueful, way off mark.

The cost doesn't have to be borne by the end user. The cost can be developer time / clues. In the Free Software world, you do get that for free.

Re:Tradeoffs?

[B1ood]

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.

Re:Tradeoffs?

[sasami]

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.

Re:Tradeoffs?

[RelliK]

Aside from the technicalities of this particular patch, your assumption that you're going to lose something when you apply a beneficial patch because 'you don't get anything for free' is, despite appearing mature and clueful, way off mark.

False. There *is* a tradeoff. And you probably want to take an Operating Systems course before spewing "there is no tradeoff with Free Software" nonsense. (BTW, I wanted to ask the same question).

Anyway, here is how it works: a ready, higher-priority process can kick off a running, lower priority process before the running process's time slice expires. This does indeed improve responsiveness so that your machine "feels" (*)faster, but in reality it actually runs slower. The cost of pre-emptible kernel is that it does more process switching than a non-preemptible one (see above, it can (and does) interrupt a process before its time slice is finished). More process switching requires more CPU time, concequently, less CPU time is spent on actually doing work. So yes, the good thing is that it decreases latency (hence better responsiveness). But the bad thing is that it decreases throughput (the amount of work actually done) because of the increased process switching overhead.

(*) The reason your machine "feels" faster is that the GUI becomes more responsive. But that is pure illusion! Your machine actually does less work. Thus, the pre-emptible kernel patch would probably be useful for workstations, but you definitely don't want to use it on a server.

So the question becomes: what is the throughput/latency tradeoff with the current implementation of the preemptible kernel?

Re:Tradeoffs?

[psamuels]

You don't get anything for free.

Not quite true - some Linux patches give unilateral improvement. But I do see your point.

What is the tradeoff that occurs when you integrate this patch?

None of the other responses to this thread (that I've noticed) addressed one tradeoff: complexity and bugs. Ever since Linux started to support SMP systems, SMP kernels have been somewhat buggier than UP kernels. This is because there are a lot of potential mistakes to be made - getting and releasing spinlocks and semaphores at the right places is not trivial stuff. Of course bugs have been fixed over the past several years, and SMP is now considered a standard Linux feature (in 2.0 it was "experimental"), but there are still no doubt lots of SMP bugs in some of the more obscure device drivers.

The problem with the preempt patch is that it introduces all these potential bugs into a standard non-SMP kernel, since preempt uses much the same basic mechanism as SMP. Most people only have one CPU, but now these people will be exposed to the same "increased level of risk" as SMP systems.

In a way, that could be considered a benefit - this may serve to flush out some of those last remaining SMP bugs. The SMP code paths will be exercised by a lot of people now.

Re:Tradeoffs?

[BlowCat]

In fact, you just demonstrated that the processor does more work with the preemptible kernel. Perhaps you were assuming that all 100% of CPU time is utilized and that faster GUI is not really useful, so the processor does less "useful work".

This is not true in case of workstations, whose primary purpose is to provide smooth and fast environment for people to work, not to crunch numbers.

Neither does your assumption hold for embedded systems - their function is often to provide fast responce to external signals, which they can do much better now. Most embedded systems don't utilize 100% of the processor power either.

It is only in the case of servers with heavy I/O that your reasoning makes sence. But the solution is in the hardware - use bigger blocks of data, and the processor won't be interrupted too much.

Re:Tradeoffs?

[Ami Ganguli]

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.

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.

Re:Disadvantages

[Metrollica]

Also look here

Scalability of a pre-emptible kernal?

[Maddog_Delphi97]

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.

Re:Scalability of a pre-emptible kernal?

[restive]

If you don't like it, treat it the same way as SMP...turn it off!

The fact that this is built into the kernel means that we don't always have to go out and download patches to change this. I would assume that vendors using the Linux kernel would make decisions on how to compile the kernel to suit their environment.

There are lots of people that are frustrated by the current need to go and get patches to change this. Incorporating it into the main kernel should be very positive, IMHO.

Re:Scalability of a pre-emptible kernal?

[be-fan]

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.

Re:Scalability of a pre-emptible kernal?

[Fjord]

"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."

Actually, I would think it would be the opposite. Being able to preempt within the kernel can pretect you against a DOS attack where a process repeatedly makes long running kernel calls. That would give that process more than it's fair share of time, and other processes couldn't respond to interrupts as well. Without a fully preemptable kernel, you can't guarantee how long a process can run, because it is impossible to preempt them while they are in a kernel call.

Re:Scalability of a pre-emptible kernal?

[iabervon]

Consider, however, the case where the reason a task is preempted in the kernel is that it has used all of its timeslice. Without the preemptable kernel patch, the task cannot be interrupted to schedule another task. In order to make guarantees about how much time will be given to each process, it needs to be possible to stop a process when its time is up essentially no matter what the process is doing.

The issues you raise are a matter of scheduling policy, not of whether the kernel is preemptible. Furthermore, for most interactive tasks, the correct behavior is to react quickly, because those tasks haven't used up their timeslices, since they blocked waiting for input. In this case, interactive processes give up the CPU to wait for input, and then get their time back as soon as they have a use for it.

Of course, this all also applies to tasks which "interact" with the network or the hard drives, which is any task when you have swap space. Processes which are waiting on input want to run as soon as their input is ready, and don't care about time before that. Processes which are not waiting on input want to run as much as possible, and don't care exactly when. Having the scheduler's instructions followed as closely as possible benefits both kinds.

This and O(1) scheduling by Ingo Molnar _rock_

[sydb]

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.

Re:This and O(1) scheduling by Ingo Molnar _rock_

[Lac]

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.

Sounds awesome. Quick question: does Ingo's patch make all of userland O(1), or just the kernel? I'm curious.

(1/5 wink)

Re:This and O(1) scheduling by Ingo Molnar _rock_

[doug363]

The fact that the scheduler is O(1) is largely irrelevant, although that's how it was announced on the Kernel mailing list so that's what it's called. The patch includes rewrites for other critical scheduler functions which improve performance under common conditions, especially interactive performance. In particular, it gives priority boosts for processes that have low average load requirements when they need the CPU.

Here is the bitkeeper log

[Khalid]

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 !

Re:Doesn't everyone else already do this?

[Max Threshold]

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.

Other arches?

[saintlupus]

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

Re:Other arches?

[hysterion]

I wondered too (I also have a 7200), and found this answer in the changelog:

<rml@tech9.net>:
[PATCH] Re: [PATCH] Preemptible Kernel for 2.5

On Sat, 2002-02-09...<snip>

Again, this is a minimal i386-only patch. I have other arches, documentation, etc. Patch against 2.5.4-pre5. Enjoy,

Robert Love

And what about 2.4?

[rseuhs]

I thought that the preempt patch was quite a way from being part of the linus tree.

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?

Re:And what about 2.4?

[evil_one]

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.

Agree, here is the excerpt from the config file

[Khalid]

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

Can you say "Re-inventing the wheel?"

[Mr Z]

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.

--Joe

Re:Can you say "Re-inventing the wheel?"

[Junta]

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

Re:Can you say "Re-inventing the wheel?"

[kevinank]

The main slowdown for X doesn't come from Marshalling data. The marshallers are quite fast, and run at CPU speed. The latency mostly grows in the interaction between the X server and the display hardware. Since the X server is running in user mode it doesn't have access to Hardware interrupts. As a result the server ends up polling the hardware registers until the operation is complete, which wastes huge amounts of time. Still a lot faster than blitting video memory in the CPU, but not nearly as fast as Windows can manage.

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.

Re:Great Feature

[sydb]

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.

Re:Ingo?

[sydb]

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

and it won't

[Ranger Rick]

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.

Now for the entropy pool.

[augustz]

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.

http://www.kernel.org/pub/linux/kernel/people/rml/ netdev-random/README-netdev-random

describes what it is all about

[PATCH] To fix compile error on UP systems

[worldwideweber]

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

Re:Doesn't everyone else already do this?

[Fjord]

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.

Re:Disadvantages

[dougmc]

Another disadvantage ...

It crashes my machine occasionally. Dual p3/700 (so it's SMP -- which complicates matters.) Without the preempt patch, the box stays up for months at a time. With it, it seems to lock up hard after a few days.

So far, at least two crashes happened while burning a CD. I wonder if that's a coincidence ..

Re:Doesn't everyone else already do this?

[Cid Highwind]

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

Maybe you could call it Direct Rendering Interface

[lkaos]

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

Technical Overview

[lkaos]

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.

Re:Star Office 5.2

[glwtta]

"damn it, I am a preemptible patch, not a miracle!"

Re:won't help X too much

[nathanh]

But I have an idea. Develop a system that implements the exact same interface as X but does no marshalling/demarshalling.

Impossible. The X11 protocol is incompatible with this idea.

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.

This has been tried. See the D11 paper by Kilgard.

http://citeseer.nj.nec.com/125132.html

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.

Recompile the drivers, they will work.

[leereyno]

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.

Whatchew talkin' bout?

[clump]

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

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 .avi being created with no apparent latency with the preempt patch. Without the patch, previewing the avi is not at all realistic. Hats off to RML and Linus.

This is due to a restrictive locking system

[Otis_INF]

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.

Re:Ingo?

[mikera]

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.

Re:Ingo?

[p3d0]

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

Actually, that's not a convention. It's the definition of the big-O notation. See here.