Re: On hierarchy

[ness]

Jonathan S. Shapiro wrote:
> On Fri, 2005-10-21 at 20:01 +0200, ness wrote:
>
> > Jonathan S. Shapiro wrote:
> >
> > > Based on my current understanding of the mapping database -- which is
> > > incomplete -- I have three concerns about the design:
> > >
> > > 1. The hierarchy is unbalanced. In consequence, no time bounds on
> > > traversals less than O(n) can be stated, and these do not satisfy the
> > > stated requirements.
> >
> > This is not entirely correct, IMHO. The hierarchy _may_ be unbalanced.
> > The point is, that the system affects (or better: defines) the
> > hierarchy. This means, if the system relies on a balanced hierarchy, it
> > can create one.
>
>
> What I think *you* are saying is: "it is possible for applications to
> ensure that the mapping database is a hierarchy." It does not appear to
> me that this is correct, because MAP operations form a linear chain, and
> the system must represent and traverse this chain.
That was a fault of mine. The system can't ensure that.

> What *I* am saying is: the kernel must not include *any* operation that
> would *ever*, under *any* circumstances, exceed log(n) time (n = number
> of in-memory objects).
OK, this is your opinion. But you say this is only necessary for
real-time capabilities. In my eyes, the system should decide whether it
wants those rt-caps or not.

> If there is a mapping database representation that supports this, I
> don't know of it. However, I still need to look at Udo and Espen's
> responses.
>
>
> > >       => This relies on the assertion that the mapping database
> > >          is purely a cache. I do not think this is entirely correct.
> > >          More importantly, Kevin Elphinstone (who knows the design
> > >          much better than I do) has expressed doubts about this as
> > >          well.
> >
> > I'm don't know the design very good, too, but the mdb is purely a cache,
> > AFAIK. In 2 papers I read ([1],[2]) is mentioned that the mdb state
> > doesn't have to be exported, as it can be reconstructed.
>
>
> In one of the discussions at the Dresden meeting it came up that (a) the
> L4 teams have always assumed that the mapping database could be
> reconstructed on demand, but (b) there is a counter-example to this
> belief. This creates a difficulty in responding to your statement
> because I do not know whether those papers are written before or after
> the difficulty was noticed. Also, I do not know if the difficulty has
> been resolved.
>
> I think perhaps I should send a note to Kevin and ask him if he
> remembers what the counter-example was.
This would be a good idea.

> shap
--
-ness-