Re: On hierarchy

[Udo A. Steinberg]

On Fri, 21 Oct 2005 10:43:33 -0400 Jonathan S. Shapiro (JSS) wrote:

JSS> Requirements:
JSS> 
JSS> I assume that we want a microkernel that is capable of supporting
JSS> real-time activity, and that we can secure with confidence. This creates
JSS> several requirements:
JSS> 
JSS> 1. System calls are only preemptable between well-defined "units of
JSS>    operation".

In order to use compatible terminology, please write "preemptible" ;)

JSS> 2. Because they are non-preemptable, units of operation must complete in
JSS>    a small *constant* number of steps.
JSS> 
JSS>   => In my *opinion*, the L4 string bound is too large to satisfy
JSS>      this requirement, but this is definitely a matter of opinion
JSS>      and preference. In effect, I want a smaller constant bound.

Note that there exist at least one fully preemptible L4 microkernel, namely
Fiasco, where your concern is a non-issue.

JSS> 4. Locks may not be held across preemptions. This is necessary to avoid
JSS> priority inversion.

Not quite. Priority inversion can also be avoided by using helping mechanisms
such that higher-priority threads help a low-priority lock holder out of its
critical section. There's a whole set of formulas for such things in common
real-time literature.

JSS> 2. The UNMAP operation requires an "all children" visit. The question
JSS> is: can this operation be divided successfully into constant-bounded
JSS> units of operation? The answer appears to me to be "no". 

You can descend down the mapping tree starting at the root node, marking each
node "unmapped" as you come across it. Such marked nodes don't allow creation
of any subnodes underneath them, which ensures the mapping tree does not grow
in such branches. For each leaf node reached, you remove the node, remove the
PTE and flush the relevant TLB entry. The per-node time overhead is bounded
and you can be preempted in between such node operations.

Granted, unmap operations can take a long time to complete for the unmapper,
depending on the size of the mapping tree for the unmapped page frame.

-Udo.

pgpVS0Q_UB6Q0.pgp
Description: PGP signature