[coyotos-dev] Sleep for interval

[Jonathan S. Shapiro]

On Thu, 2007-10-04 at 11:50 +0100, Sam Mason wrote:
> On Thu, Oct 04, 2007 at 04:30:48PM +1000, Math Gasm wrote:
> > Does [the sleep call] need to be in the kernel? 
> 
> As I understand it, it's perfectly possible to implement it in
> user-space.  The problem comes with the performance characteristics
> if it is.  Lots of programs perform lots of little waits/timeouts and
> requiring an unnecessary context switch for all of them is bad.

This is not the issue -- or at least, it is not one of the issues that I
have been thinking about.

Suppose, for a moment, that *all* sleep handling is done at user level.
We then require a user-level sleep agent that can wait for the interval
clock interrupt.  Unfortunately, the kernel must *also* wait for the
interval clock interrupt in order to implement preemption and primary
scheduling functions.

Having two parties attempt to handle an interrupt independent of each
other is just begging for problems.

> The Coyotos kernel has, as one of it's main design criteria, a
> requirement that all operations should complete in a small (i.e.
> can be modelled as O(1)) number of instructions.  This rules out a
> lot of common data structures/algorithms that are commonly used in
> the design of these sort of things.

You have the right idea, but the statement is not quite precise. O(1)
instructions is very nice when we can get it, and we definitely try to
use the simplest algorithms possible. The more relevant constraint is
that every operation should touch no more than a constant number of
*objects*, and a relatively small constant at that.

For this purpose, however, log(n-objects) is small enough to be okay in
all realistic implementations. Tree inserts, for example, are no real
problem.

There are a few places where we violate this rule. The big one is
probably the object hash table, where the depth of a bucket can get
pretty large. That table is rarely consulted, however.

>   The kernel also requires that
> user-space designates the memory that it uses to store things, so if
> we were maintaining a list of processes to run, then this list must
> be accountable to the calling program.  Again, this complicates the
> maintenance of your "linked list of processes".

Yes. More generally, we try to design our server subsystems to obey this
rule as well. That is much harder. The kernel can sometimes cheat. For
example, we can stick linked list pointers in your process structure
that we can use for queue links. Application-level servers generally
cannot cheat in that way.

> It seems annoying that the current design is left with this scheduling
> artifact, but I can't think of any cases where it'll compromise
> anything.  I'm not nearly experienced enough with this sort of thing to
> know if it's actually going to impact on anything later, so I'm happy to
> assume Shap knows best and trust his judgement.

I don't claim to know best. I only claim that I have been beating my
head against this wall a little longer than you have. The effect on my
wall is impressive, but I'm not any closer to a good solution.

I would very much prefer to implement Charlie Landau's suggestion.
Unfortunately, we don't have resume capabilities in Coyotos, so the
mechanics of that implementation would be very different for us. I think
we need to consider it more carefully, but offhand I simply don't see a
way to make Charlie's design work at the moment. I spoke to Charlie on
the phone the other night, and he doesn't seem to see a way to do it
either right now. Basically, the cost of the change would be to rip out
the entire IPC system and go back to the EROS design. On balance, I
think that the irritations of the EROS IPC design that we found while
building applications are more important than the irritation of an
imperfect primordial sleep mechanism.

shap
-- 
Jonathan S. Shapiro
Managing Director
The EROS Group, LLC
www.coyotos.org, www.eros-os.org