[coyotos-dev] Sleep for interval

[William Leslie]

On 10/4/07, Sam Mason <sam at samason.me.uk> 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.


I imagined most of them wait on I/O, which is something of a different
beast, taken care of with regular blocking capability invocation.

But you are right, of course- real time media, for example, would be
impeded if each wait required an extra pair of context switches.

> Sleep for interval seems trivial- don't
> > bother scheduling the process before that time.  Sleep until wall time
> is
> > just as easy, a scheduler can keep a linked list of processes to be
> > woken up and check it against a time server every now and then.
>
> They're both really the same thing, it's just that for the relative-wait
> we need to add the current time on and then we can do an absolute wait
> (or your could implement it the other way around).  Either way, we need
> to maintain a list of processes that need to be woken up.


except that they differ across reboots.

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


assume you have two lists, ordered in time. One is for relative waits,
the other for absolute. Check the absolute list- if something is expired,
take it off the sleep queue. Place the previously running process at the
end of the (relative) list [O(1) if you maintain a pointer there], and pop
a process of the bottom of the list. That whole thing is O(1) in time.

However, requesting to wait a certain period of time takes longer- you
would have to cdr down to the relevant place in the list. Is that unreas-
onable? I'm not sure. I mean, you -have- explicitly asked to wait!

You also bring up the important space issue. You're going to need to
store some data for each scheduling capability no matter what you
do, even if it is just the order in which they are to be run. If that data
is a pointer to the next scheduling stub and the name capability of
that process, you can't beat that. And I don't like the idea, but if you
want real accountability, you could put that pointer in the per task
state. [just kidding.]

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.


Of course.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/coyotos-dev/attachments/20071005/3db936cb/attachment.html