Subject: Re: Hard realtime scheduling
To: None <>
From: Joerg Sonnenberger <>
List: tech-kern
Date: 04/13/2005 09:06:37
On Mon, Apr 11, 2005 at 03:56:09PM -0700, Jonathan Stone wrote:
> In message <>,
> Joerg Sonnenberger writes:
> >Making the kernel preemption and supporting hard RT are not the same thing
> >at all. They are not even similiar. E.g. you can do hard RT in a coroutine
> >like kernel setting without having any preemption at all.
> Nope. To oversimplify, with apologies in advance to others in the
> audienc with a more sophisiticated exposure to the issues:
> A coroutine-style approach can "guarantee" deadlines only for those
> points where the coroutine-style check for approaching hard-real-time
> deadlines is explicitly added to the kernel. And you can only add such
> coroutine-style calls at points where it's *known* to be safe to do so.

Acutally you have to ensure it anyway, otherwise you can completely
use data structure integrity, just as you have a set of contraints
for fine grained locking.

> The 4BSD kernel (and all descendants which haven't yet added explicit
> fine-grained SMP locking to all datastructures), implicitly rely on
> the fact that the kernel is non-preemptive.  Because the kernel is
> non-preemptive, even spl0()-level code can issue series of operations
> which are _required_ to be atomic as seen by userspace, without any
> explicit locking. The userspace atomicity is guaranteed by the fact
> that the kernel is non-preemptive.

This is not completely true. All descendants of 4BSD, which allow
kernel threads, have a certain level of preemptivity already.
The mechamism used to decide when preemption in kernel space is allowed
_could_ be extended to cover userland preemption as well, but I agree
that it is mostly not implemented. Still the point remains, that
the current schedulers don't return to userland if there is any other
kernel thread runnable and that's a safe preemption point.

> Even operations at raised SPL rely on the fact that any other
> (correct) operation on data-structures which are synchronized at that
> SPL level must *raise* SPL to the desired level.  Those operations are
> therefore guaranteed atomic w.r.t. all processes which *raise* SPL to
> that level.  One notable exception is that calls to {{l,}t,}sleep()
> will implicilty lower SPL: correct code must therefore not rely on
> state being atomically carried across the {l,}tsleep() boundary.
> [[To (again) oversimplify to the point of being flat wrong: you can
> almost think of the NetBSD codpaths which *do* use lockmgr locks, as
> being just those codepaths which *do* need to synchronize state across
> a {l,}tsleep() boundary: e.g., VM or filesystem code which needs to
> sleep() on a buffer waiting for I/O to complete, but which also needs
> to maintain state across that sleep. But that's just an analogy; don't
> push it too far.]]

SPL and mutex models are similiar, you have to get hold of a mutex
to guranty the atomicy. It would the job of scheduler in combination
with splXXX to ensure that a preempting thread is pushed backed if it
tries to get the same SPL level as the preempted thread. This completely
ignores dead lock issues, but it would be possible.

> If you want real hard real-time guarantees, then to a first
> approximation, you *have* to make the kernel pre-emptable. And, quite
> possibly, also insert "are we nearly overdue on a real-time deadline?"
> coroutine-like calls, to explicitly (coroutine-style) pre-empt away
> from long-running elevated-priority code paths.  But pre-emptibility
> is a must-have. And to achieve pre-emptibility, one basically *must*
> first implement fine-grained SMP locking, *everywhere*.

While preemption allows one set of hard RT guaranties, full coroutine
allows a different. If your kernel is entirely consisting of coroutines,
you can actually allow more complex operations with RT contraints, using
resource contention techniques (forget the name of the algorithm).

But to not stray from the path, if the original intend of the question
was userland RT e.g. for sound applications, it becomes a very interesting
question what a kernel can offer at all. Any kind of disk IO can normally
be considered unbound, what remains is stuff like RT mixing. At least
soft RT in the area of ms can be achieved with a good scheduler.