Robert Love, Preemptible Kernel Maintainer Interviewed

Tom F writes: "LinuxDevices did an interesting interview with Robert Love, the maintainer of the Linux preemptible kernel along with MontaVista. It is an exciting read and has Robert's usual wit and insight."

Comments

this one gets my vote

[spongman]

I've been running this patch since the early -ac days on a machine that doubles as a development desktop and a medium-load server and I've had absolutely no problems. I don't have any numbers but X/Gnome seems much more responsive even when other procs are busy. I see no reason why this isn't in the main tree, especially since it's a kbuild-time option.

a quick nice -n -5 /usr/bin/X11/X helps, too.

Re:Preemptive kernel looks good

[Lozzer]

I think you'll find that Linux has premptive multitasking too. What it can't do (without the preempt patch) is prempt a task that is currently running kernel code (e.g. through a syscall). I've no idea whether the Amiga's "kernel" (exec?) was preemptible in this sense or not.

Crash-course in preemtivity

[slashdot.org]

For those that don't really understand the importance of preemptive multitasking (and from reading some comments, there are a few of you out there :-O), let's explain this through an example.

Consider application (a) that wants to read 128MB of data from the disk and application (b) that wants to read 1KB of data.

Let's say that the disk transfers @ 1MB/sec and let's assume application (a) issues the read 1 second before application (b) is started.

The sequence of calls for each app will look something like this:
1) program calls read
2) read is handled by the top level file system and is handed down to the proper file system
3) the file system calls the block device
4) the block device driver breaks up the request into the maximum block size the device can handle per request (for example 256 sectors for IDE)
5) for every request, the block device sends request to physical drive
6) drive transfers data to host
7) drive indicates 'done'
8) goto 5 until done
9) file system returns
10) read returns

It's important to know that there may be limitations on the number of requests any stage can handle simultaneously. For example, an IDE drive can only handle one request at a time. Some Operating Systems however introduce even tighter restrictions, because for example the block device driver was written, assuming only one request at a time would be allowed.

Take for example an OS where the kernel assures that no more that one request is pending between step 3) and 9).

This would have the following effect on our apps: app (a) is allowed to call step 4) because it is the first request. One second later, app (b) arrives at step 3) and is blocked. It is not allowed to enter step 4) until app (a) is done and passes step 9). Effectively this means that app (b) has to wait for 127 seconds before it gets access to step 4).

Now consider an OS where the file system and drivers can handle multiple requests. It still has to assure that the physical drive receives only one request though, so it permits only access of one app between step 5) and 7). App (a) arrives at step 5) first, so it gets to start sending requests to the drive. One second later, app (b) arrives at step 5) and has to wait for app (a) to finish it's current request to the drive. As soon as this request is done though, app (a) gets to step 8). Now we have both app (a) and app (b) wanting to have access to step 5). Depending on the scheduler either one will be granted access. There's a good change that app (b) will get access, and thus it only had to wait the time it took for app (a) to finish it's outstanding request, which takes max 1/8th of a second (256 sectors = 128KB) in this example.

Btw. you may notice though that there's more likely to be an (expensive) seek introduced by allowing app (b) to interrupt the transfer of app (a)

You can see how moving the 'lock' deeper in to the OS improves responsiveness. I'm not going to start a flame war about which OS is better, all I will say is that MY OS locks steps 5) through 7) :-)

Re:Crash-course in preemtivity

[nevets]

This is fine except the way the linux kernel works (as well as most others). When app(a) calls the IDE to get the data, it goes to sleep (calls schedule) and won't wake up until it gets the received data. When schedule is called, it can go back to user land. app(b) will now do its call and it will be queued up and blocked until app(a) gets its data. Then app(b) will get a turn and this goes on and app(b) will not be affected by the big read of app(a). Your situation would happen if the kernel didn't call schedule while waiting for data. Thus that would really hurt the performance of the kernel.

The real problem is if you have a periodic program that needs to make a deadline. What a non preemptive kernel does is place in too many varients. You can't guarentee that the program will make its deadlines when you have other lower priority tasks running.

Say you have a period of 10 ms and your task needs 3 ms to do its job, and it must be done within the first 5 ms. So your app starts and gets priority, and you do what needs to be done in the first 3 ms and easily makes your 5 ms deadline. Now you may run other task for the next 7 ms. Come the next period, you start your 3 ms task and repeat.

But lets say you have a system call that takes 4 ms, and one of your non priority tasks calls it at the 9 ms time. With out being able to preempt it, your priority task will start at the 3 ms time and it won't finish until the 6 ms time and thus you missed your deadline.

The reason you have preemtive kernels is so that priority tasks are not affected by lower prioriy tasks. Not the reason you gave above.

Re:Pre-Emptable Kernel & MicroKernels

[be-fan]

(Aside from the fact that all of the Linux kernel, drivers, etc. is in 'kernel' mode, and a MicroKernel has only the message-passing and task-scheduling in 'kernel' mode, and everything else (drivers, etc.) run in 'user' mode.)
>>>>>>>>>>.
That's basically everything that distinguishes a microkernel from a monolithic kernel :) The preemptive bit is orthagonal to micro/macro kernel. There are non-preemptible microkernels (like MINIX, I think) and preemptible monolithic kernels (Solaris).