Preemptive Kernel

by Danny Kalev

November 2, 2001 —

Preemption 101
"Preemption" basically means that a running task can be suspended while
another task takes its place as the currently running process. Once a
task has consumed its allotted quantum, or CPU time slice, the
scheduler will suspend it and run the next task in the queue. In
practice, the scheduling algorithm is more complicated because of
different process priorities.

User vs. Kernel Preemption
You might get the impression that the scheduler can preempt a running
process at any given time. That's not entirely correct. Linux supports
only user-level preemption, which allows the scheduler to suspend a
process as long it's running in user mode. It will not suspend a
running process that is in kernel mode, though (read more on kernel
mode vs. user mode here: http://www.itworld.com/nl/lnx_tip/06082001).

Kernel Preemption Pros and Cons
By contrast, a preemptive kernel may suspend a running task even if
it's in kernel mode. This is necessary in hard-core, real-time
applications that must meet very rigid time constraints. Under the user
preemption model, syscalls present a challenge in this regard. Although
their execution time is very short, it isn't constant. For instance,
the time needed to complete a malloc() call depends on heap
fragmentation, the size of the requested memory block, and the system's
load. Thus, one call may take 10 milliseconds to complete whereas
another might take 50. A task that must terminate within 40
milliseconds might not finish on time if another process calls malloc()
in between.

By contrast, the scheduler could preempt the malloc() call and enable
the real-time task to always finish on time under a preemptive kernel.
Kernel preemption can also improve the responsiveness of some notorious
applications that cause the system to freeze up for a short while
during certain activities.

Kernel preemption exacts a price, though. Many applications aren't
ready to deal with the possibility of a preempted syscall. Preemption
also will require a kernel overhaul and complicate the kernel's code.
Is it really worth the trouble? For most everyday uses, the answer
is "no". That said, with Linux becoming the OS of choice in embedded
and real-time environments, the demand to add kernel preemption is
constantly increasing. Presently, several preemptive kernel patches are
available such as Robert Love's patch: http://www.tech9.net/rml/linux/
For benchmark results, visit the Linux kernel preemption project:
http://kpreempt.sourceforge.net/

ITworld