Slashdot Mirror
Preemptible Linux Kernel: Interviews and Info
An anonymous submitter sends: "MontaVista and Robert Love are developing a patch for the Linux kernel to make it fully preemptible. Lots of users are involved, and tests show huge reductions in latency. Robert's kernel patches are here. Finally, an interview with Robert, on preemption and more."
Does anyone think that this will ever make it into the kernel? It seems that Linus does not like this because it cures the symptons of latency in the kernel instead of the real problems.
If the kernel is preventing the same piece of code from running on more than one processor (by acquiring a spinlock), then it is also preventing the code from being preempted.
The interrupt handlers can't allow premption during the context switch of an interrupt because the registers are intransit. Basically, you can't have an interrupt while your in the process of any kind of context switch otherwise you're never sure what registers you were able to flush to and from the CPU to the stack.
Critical Sections (such as access to the IP stack or I/O queues) have to be protected. With the advent of multi-processor systems under the SMP scheme, there is already considerable locking within the kernel to synchronize access of critical resources between processors. Critical regions also need to be protected from interrupt concurrent access as well.
Bottom Half handlers generaly are fast track implementations to quickly deal with the interrupts. To avoid concurrency collisions of reasources used within the bottom half handlers, interrupts (for that particular handler) must be disabled during the handler's execution.
All in all, this is basic non-preemptive stuff. What I don't understand is that this strategy that he is defining is a textbook NON-premtive approach to kernel design. I'm not too sure where he gets off claiming that the kernel is fully-preemptive here.
Someone you trust is one of us.
If you're wondering what the heck a preemptive kernel entails, then here's some background.
Also, if you don't like Robert Love's implementation, then Andrew Morton maintains a patch with a similar low-latency goal.
- Linux Devices Article detailed, very nice, on this issue from Sept 6
- Kernel Hacking How-to Page on this again, very detailed.
- The Kernel SpinLock metering FAQ
All around useful stuff, enough to get you started destro^H^H^H^H^H^H hacking your own kernel"It is a greater offense to steal men's labor, than their clothes"
No, I think you're misunderstanding. It's not preempting the kernel, it's preemtping a lower-priority thread that happens to be in the kernel (ie. during a system call). If there is a runnable thread with a higher priority, it should be set running. But as things currently stand, if the low-priority thread is in the kernel it can't be preempted, and so the high priority thread has to wait. That is bad.
Higher Logics: where programming meets science.
I don't want to sound like I'm contradicting you, but did you happen to read this link from the article? It's specifically about realtime audio. Key paragraph:
*EXCITING* NEWS: things getting almost perfect ! Ingo's lowlatency-2.2.10-N6 patch with the shm.c part backed out and a modification of filemap.c (thanks to Roger Larsson) performs _REALLY_ well, using my usual latencytest parameters (4.3ms buffer), I got NO DROP-OUTS anymore, with sporadic maximum peaks of ONLY 2.9ms This is really exciting because it opens the doors to a whole new class of Realtime applications for Linux, simply using userspace processes scheduled SCHED_FIFO. I heard of comparable low-latencies only from BEOS, Windows can't simply guarantee these kind of latencies, not even using DirectX. Using a soft-synth on Win98 on my BOX I must use 15-20ms audio buffers to get _SOMEWHAT_ reliable audio. This is actually about more than 3-4times the buffer I used for testing under Linux ( 4.35ms).
I don't know much about the field, but the page seems to speak to several of the audio-related concerns mentioned above.
Kill, Tux, kill!
Love said that this patch even if added to the main tree would still be a config option.
pre-emptive is a form of multi-threading. the other form is co-operative.
Co-operative means that threads relinquish control on their own. This meant that a greedy thread could put a serious stranglehold on the OS and lock-up the system, forcing a reboot.
Co-operative was used in every Mac prior to and including OS-9, which made it very unstable should a thread crash.
Pre-empt means the OS decides when the thread loses control. A thread can still voluntarily relinquish control, but the final call still comes down to the OS.
OS-X is fully pre-empt, meaning a crashed thread doesnt crash the entire system, bettering the stability overall as that will usually only crash the program that thread belonged to, not the entire system.
I dont know what MS has for their threading model, they seem to have a very bad hybrid system. The threading in Windows 95/98 tends to cause a good number of BSODs. NT/2000 OTOH, had a better model and crash a lot less often, which is why they have traditionally been the more stable MS OS.
Task scheduling has to do with what thread gets control next. Priority and other factors decide that. Solaris threads have 2^31 possible levels of priority, Windows (all versions, IIRC) has 5 classes and then 5 sub-classes of priority for each (a REALLY screwed up and tough to understand and explain technique, iow not a clear-cut 25 levels), and Java has 10 levels for cross-platform threading. Each model has their plusses and minuses, but that's getting offtopic from preemptive vs. co-operative.
The One Rule Of Chess You'll Ever Need: Don't play someone who carries a kit in their bookbag.
Linux is fully preemptible, and has always been. This is about being preemptible while executing in the kernel. I have no idea if OSX allows this or not - it's BSD based, so probably no, but then Mach is involved someway or other, so maybe. It would be interesting to know.
/Janne
Trust the Computer. The Computer is your friend.
Ummm,
Sorry, just want to note that mutex and semaphore programming is not all that difficult if you do it much. True windows have a few kinks, but the concept is pretty basic. Basically I would have to disagree that mutex and thread programming makes programming hard. It's just programming once you understand it, it's pretty straight forward.
As for the windows problem use startthreadx instead of startthread (Yeah probably not the real api functions, but close enough haven't worked on windows for a while.)
Lando
/* TODO: Spawn child process, interest child in technology, have child write a new sig */
Wrong, dewd. You're thinking of a microkernel. They're two totally different architectures.
I originally felt I should stay out of any discussion here, but I want to answer some of these questions and clear some of this stuff up. To be honest, it is a little embarrassing having everyone read and comment on the interview. :)
Bottom Half handlers generaly are fast track implementations to quickly deal with the interrupts. To avoid concurrency collisions of reasources used within the bottom half handlers, interrupts (for that particular handler) must be disabled during the handler's execution.
Interrupts, even just the in question, are not disabled during a bottom half, at least in general. The reason we can't preempt bottom halves is that they are guaranteed to be serialized w.r.t CPUs (ie a given BH runs on only one CPU at a time). Because of this, the BHs are designed without a regard reentrancy. So we can't preempt them.
All in all, this is basic non-preemptive stuff. What I don't understand is that this strategy that he is defining is a textbook NON-premtive approach to kernel design. I'm not too sure where he gets off claiming that the kernel is fully-preemptive here.
Hardly. Would you say an SMP system is not SMP if it is non-concurrent inside critical sections? No, you wouldn't, and this is the same situation we have here with preemption. We can't preempt inside critical regions. We have concurrency and reentrancy concerns, just like SMP does. We also can't preempt inside interrupt handlers or bh's because they aren't designed to be preempted (nor would you want to interrupt the top half of an interrupt, anyhow).
The current kernel is not preemptive _anywhere_. The only way, in fact, kernel code ever yields execution is if it explicitly does so or returns. Since with the preempt-kernel patch we can now preempt in 90% of the kernel, I think its safe to say we have a preemptible kernel now.
This is about making the kernel preemptible, which means that a process can be preempted if it's in kernel space (i.e. making a system call) as well as when it's executing normal user code.
Without a preemptible kernel, a process can remain on the cpu during the several milliseconds that a system call can potentially take to return or sleep, even if a higher priority process becomes runnable during that time.
I thought the Slack 2.0 release had a 1.1 kernel.
It could of, I just seem to remember a 1.0 kernel.
Can anyone give a nice layman's description of what he is talking about here?
Basically I am explaining the modifications to the kernel we made in order to make it preemptible. To try to put it more for the layman, besides just allowing the kernel to preempt itself as needed, we had to prevent some certain situations from being preempted. This is the same situation with SMP. We use SMP's locks to disallow preemption, for concerns of concurrency and reentrancy. We can't preempt during interrupt or BH handling because those things are not designed for concurrency, either.
To sum it up, we have to prevent preemption in some situations. Those situations are: while locks are held, while handling interrupts and bottom halves, and while inside the scheduler itself.
Can someone fill me in... Hasn't Microsoft been claiming windows has been preemptive since win95??? Is this some other form of 'preemptiveness'?
You are thinking of forms of multitasking. One form is preemptive, in which tasks are given a specific period in which to run (timeslice) and then forcibly preempted by the next runnable task when that quanta ends. Win95, NT, all Unices, and anything decent fit in here
The other form is cooperative, in which tasks run until they yield execution. This is how Win 3.1 is. In 3.1, tasks ran until they finished processing their current Windows Message or called yield().
This article is about a preemptive kernel, where actually the same ideas apply. Inside the kernel, things are currently cooperative in the sense the kernel code runs until it completes or yields control. This patch makes it preemptive -- it will be preempted when something more important needs to happen.
Win95 does not have a preemptive kernel (it isn't even reentrant). NT might. Solaris does. Linux does with this patch.
Windows' "preemptiveness" refers, as explained somewhere else here, to the windows kernel being able to jump in and stop any user process executing to give the next one its term - so (in theory) no user-run program can hog all of the CPU and resources.
Linux has always done this - it's the standard way to write a unix kernel.
In relation to the audio discussion, preemptive in a linux kernel means (as far as I understand it) that the kernel attempts to guarantee a minimum time between an interrupt coming in on some device and control being handed to the driver for that device. It does this by preempting its own tasks in order to hand control over to the driver for the device needing the attention (the driver, of course, runs as a kernel process, also).
Typically, the goal is to get a maximum latency of 10ms or better (less) between the interrupt and the waking up of the driver.
In a professional audio situation, of course, the user can go a long way by stripping all the unnecessary hardware and tasks out of the configuration of the machine, which will mean that (if done properly) the only thing which can get in the way is linux' internal book-keeping. This is a different situation to playing with audio apps on a networked computer while you print out web pages..
Beyond this, there is real-time linux in which (as I recall) a hard maximum latency of 2ms or so is claimed. But the overheads introduced by all the timing and checking which guarantees this impact the performance to the extent that it's quite a different beast, for specialised applications.
Some audio programmers would like a low-latency patch (either the preemptive one or some other) which has a soft guarantee of "almost all" latencies below 5-10 ms to go into the standard kernel because they would like their userbase not to have to deal with the complexities of kernel recompilation and/or patching, but this is a pretty tall order because Linux will not like having basically ugly fiddly designs with lots of volatile little conditionals which have to be fiddled with everytime something changes going into the beautiful kernel.
Maybe vendors like mandrake should pick up the baton and provide a low-latency alternative kernel installable with their gui tools or at install time, which would keep everyone happy at the cost of not too much effort and space.
.sigs: Just Say No!
Not quite correct.
It's not preemptive vs. cooperative.
But preemptible vs. non-preemptible kernel.
"Pre-empt means the OS decides when the thread loses control."
Yes, that's preemption.
B,ut there is another preemption.
Should a process get a higher priority than the currently running process, then the current process gets preempted.
E.g.
You have a low priority CPU-bound process A(e.g. Seti@home) and you have a high priority I/O-bound process B (e.g. XMMS).
Usually, B does nothing but waiting for I/O (e.g. the soundcard and the harddisk). While waiting, the process is not in the run-queue.
Meanwhile, A hogs the CPU. Usually, when the I/O request is done, the CPU gets an interrupt request (IRQ) which causes the OS to switch in kernel mode and handle the request. B gets active again and has a higher priority than A, so A gets preempted. Usually that works fine, but now A wants to do some I/O (deliver a packet) and calls the kernel, which handles the request. Just this moment is the I/O for B ready. In Linux (as in most other OSs too) B has to wait until A gets its syscall done, since the kernel is not preemptible. This period of time until the B gets the CPU increases the latency.
Windows 95 is preemptive (at least according to A. Silberschatz) as is Linux.
The high amount of crashes of the whole system stem from the resource protection (direct hardware access), not the scheduling.
"Between strong and weak, between rich and poor [...], it is freedom which oppresses and the law which sets free"
I hope that Linus will look at whether these patches hurt the normal case. "normal" means things like kernel compilation, not just an arbitrary latency measure and dbench (one of the least realistic benchmarks possible!)
there are good reasons to be skeptical of all-out premptiveness: it will unavoidably lower throughput in easy-to-define cases. any intro OS text will talk about optimal scheduling, where 'optimal' requires a definition of throughput or some other metric. preemptive kernels will context switch more, and will probably interfere with the natural 'batching' that happens when a big job runs for a while. think about caches: you never want to switch unless you must. this is not an argument against low-latency! it's an arguement against lowest latency as an absolute; we need to set a target (5ms would be fine imo) and meet it. going beyond such a goal will hurt the normal case.
Whether this patch is added or not is surely just a question of whether it is stable enough or not.
As it says in the interview, the enablement of the patch is an option in the config... For those that want it (i.e. most desktop users I would expect) it's there. For those that don't, it can be disabled.
It seems that the patch works, as scientifically explored by his benchmarks. If there is a fault in the patch, I'm sure that half of slashdot will email the chap.
In summary, it works, is probably stable and can be enabled/disabled in config if needed. It already does, and probably can, benefit lots of people.
Put it in!
(At worst it can be removed and a new kernel released the day after... hehe)
-- Mike
http://www.linuxdevices.com/articles/AT4185744181. html
Goofed that up.
Nice discussion, from Sept 6, with related links
[sigh]
"It is a greater offense to steal men's labor, than their clothes"
As I understand it:
NT has 32 priority levels.
The split into idle (p=0), low, below-normal, normal, above-normal, high and realtime (p>=16) (which I assume is what you were referring to) is just a simple way to name different general priority levels. It's the 32 levels that matter.
Normal priority is 14.
Anything running at 16 or above ('realtime') will never get interupted by threads running at lower priorities. The OS will never change these priorities, though the user can.
Ready to run threads of priority =14 can be given a temporary priority boost to 15 (lasts for a double timeslice which is 40ms normally) if they have been ready to run for about three seconds. Anything at lower than priority 16 shares what time is available, with higher priorities being favored. At priorities lower than 16, no thread will ever be totally starved of CPU time.
Priority 0 is for things which should only run when nothing else needs CPU time, like RC5 or SETI@home (though some such apps actually set themselves to priority 4 and hence slow most things down. folding@home used to do this).
Disclaimer: It's my patch
:)
I think this is a good short-term solution for the latency problems but I personally wouldn't include it in the main kernel releases. I believe that it *might* be a good idea to fork the kernel releases (temorarily) in two groups: One for servers and one for workstations until the problems have been solved.
I tend to look at this more of a long-term solution, and I think people who see it has a short-term solution or hack are missing the point. First, this is a feature. We aren't kludging kernel code so that we can lower latency by stopping it when needed. We are effectively using the SMP code to multitask better within the kernel.
Second, forking the kernel over this is a terrible idea. Since it is a config setting, this is a non-issue anyhow, but I really don't want to see this thing forked off. In fact, I think the ideal situation is where we can get a preemptible kernel that benefits throughput so that server processes benefit from it as well.
I think that (for now) using this patch on workstations is a pretty good idea
Agreed
And I think there should be a better solution for the problem witch should THEN be something along the lines of kernel 3.0
There isn't a better solution that is not a hack. There is a reason Solaris, NT, and all RTOS are preemptible inside the kernel: it is the only way to achieve real-time response. You just _have_ to be able to respond to events when needed.
The "better" solutions in this case are "simpler" -- if we can hack some conditional schedules into places, perhaps simplify some algorithms, etc. then we can perhaps reduce latency without preemption. This is what Andrew Morton's low-latency patches do. But we need more. The point is not that preempt-kernel is a hack, but that it is a whole new high-tech feature, and some people want to find a simpler solution.
Personally, I don't think a simpler solution exists, and I believe the preemptive kernel satisfies other problems (and it also a neat feature:>). Thus I work on it.
HZ only comes into play when you have fully CPU bound tasks.
Bzzzt! Wrong. It is also determines the minimim timeout for poll() and sleep(). Please post only when you have something of value to say.
I thought that what (certain) kernel hackers really objected to is preemption while locks are held. The complications (eg priority inversion) they talked about seem only to arise in that case.
There are a few reasons other hackers complain, although I didn't know this was one of them. Since MontaVista's original preemptive kernel work, I believe, we have never preempted inside of locks. Note that you can, but then you reach the issues with deadlocks and thus the need for priority-inversion that you spoke of.
So, first, does "fully-preemtive" traditionally mean with or without locks? Are Solaris, NT, and RTOS preemtible when locks are held?
I would say it means sans locks. None of the mentioned OS's are preemptive while holding a lock. You always have to respect the lock. Now, you can preempt during the lock and go do other things. If you do this, you are assuming the lock is going to be held long (or else it is favorable to just spin for a cycle or two). In this situation you want to use semaphores, which we _do_ preempt during.
When a process hits a semaphore that is in use, it goes to sleep and something else continues. The process awakes when the resource is available. Now we reach the problem you wrote of above: priority inversion. What if task A holds resource Y and sleeps waiting for resource X and task B holds resource X and sleeps waiting for resource Y? You deadlock.
Thus we need to use a type of semaphore called a priority-inheriting mutex, which inverts the priority of the task holding a resource so it will always complete and release the lock. I know Solaris has these. However, I would consider any kernel that can preempt itself in general a preemptible kernel.
Second, observed results aside, what reason do you have to believe that preempting the lock-less parts of the kernel is "good enough". All else equal, one would expect the latency distribution to be similar with and without locks, so you would expect plenty of "worst cases" to occur with locks. Of course, there is already a pressure to reduce the time that critical locks are held, but I wouldn't be surprised to see non-contended locks (especially outside the kernel core) held for long times. So is there a good reason that the important "worst cases" are happen without locks?
First, before I cast results aside, let me mention that observations show we are already lowering latency a great amount. But, you are right, periods in which locks are held are a problem. This is why I mentioned in the interview the use of things like Andrew Morton's low-latency patch, the preempt-stats patch (for finding the locks), etc.
Some of the problems still occur while locks are held, but thankfully the point of a spinlock is that they are held for a VERY short time. A solution to this may be to replace the spinlocks held for a long time with a priority-inhereting mutex.
So, first, does "fully-preemtive" traditionally mean with or without locks? Are Solaris, NT, and RTOS preemtible when locks are held?
>>>>>
I don't know about those, but BeOS isn't preemptible during a spinlock either. BeOS requires you to disable local interrupts before acquiring a spinlock, which means that the scheduler never even gets to run on that CPU because it won't take the timer interrupt. I'd surmise that almost all preemptible kernels work like this. Judging from this doc it would appear QNX does it this way as well. This method shouldn't effect latency, because you are only supposed to hold a spinlock for a very short time.
A deep unwavering belief is a sure sign you're missing something...
Tried this patch before... it works great adds a nice option in the kernel config. But the problem is pcmcia-cs doesn't work with it. Says in the changelog it will be fixed on the next release of pcmcia-cs but I want it now!
It does work nicely... everything is a lot more responsive.
Great work!
After messing with it on several machines, here is what I have found.
* it doesn't work well on a shell server or anything which might have alot of disk activity. The changes seem to do everything at the expense of disk IO and network IO. I do see better speed on interactive stuff though. Its not worth the hit in IO.
* there is no option to turn it off while in operation. Means you have to run different kernels if you want to do some things with the preempt, and other stuff without.
Brielle
yeah the one I tried was with 2.4.10 didn't work. my card's driver isn't included with the kernel so I have to compile the pcmcia driver that comes with the pcmcia-cs package (why IS there 2 different drivers?). I checked the changelog on the pre-emptive kernel page and it mentions that they are pressing the maintainers to fix the code for pcmcia-cs for the next release which I hope is soon.
Anywhere that BeOS highlighted your race condition by causing unwanted behaviour is somewhere that you'd get "random" crash bugs from in another OS if you didn't fix the code.
Other OSes don't guarantee much about how long your timeslice is, or how often you'll get time, it's sort of haphazard. That randomness means that while those race conditions don't manifest as much, they're still there to bite you.
Think of it like memory leaks and dangling pointers. Ninety-nine times you can use an element of a linked list after delinking it, one time it will have already been written over. But you don't want to somehow make the bug come up one in a thousand times... you want it to come up EVERY time so that you fix the problem before release.
It might be a bit of a pain to put locks around everything, but after a while it becomes quick and natural and you still have the power of a fast kernel with a very small timeslice for when you need it.
I was surprised he said this. This isn't a big scary kludge that inserts a bunch of hacks all over the place in the kernel; this is a relatively small patch that simply leverages all the SMP work. It won't make the kernel uglier or harder to maintain, so IMHO it is very worth adding.
I am confident that Linus will get that prodding from the real world he is waiting for, because my own experiences with this patch are overwhelmingly positive. I'm using kernel 2.4.10 with the preemption patch on my desktop Linux boxes, and I love the snappy feel it gives my system. Playing back MP3 music never skips now, and my K6-III/450 system pops up web pages in Galeon so fast it feels like an Athlon system.
Kudos to Robert Love and anyone else who worked on this patch.
steveha
lf(1): it's like ls(1) but sorts filenames by extension, tersely