Subject: Re: Hard realtime scheduling
To: Joerg Sonnenberger <joerg@britannica.bec.de>
From: Jonathan Stone <jonathan@dsg.stanford.edu>
List: tech-kern
Date: 04/11/2005 15:56:09
In message <20050404132519.GC35537@britannica.bec.de>,
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.

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.


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


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

Corrections welcome, particularly where I'm oversimplifying in the
interests of brevity.