Re: Getting Started with Hurd-L4

[Marcus Brinkmann]

At Tue, 26 Oct 2004 00:02:41 +0100,
Sam Mason <address@hidden> wrote:
> 
> Marcus Brinkmann wrote:
> >Neal H. Walfield wrote:
> >> If you do an IPC, do you not donate the rest of your time slice to the
> >> receiving process (assuming you don't block).  (Hence the scheduler is
> >> not invoked.)
> 
> Just out of interest, do you know who came up with this idea?  It's
> beautifully simple, and I'm sure I've seen it around before but can't
> remember where!

It's part of the L4 implementation.  Maybe look into research papers
that discuss IPC models that buld upon the "migrating thread" idea
(synchronous IPC).
 
> >That seems to be true.  However, like for ThreadSwitch, I'd expect
> >this not to be done if the two threads reside on different processors.
> 
> Sounds good.  What happens in that case?  The L4 manual is a pretty
> big, ominous looking thing!

The remainder of the time slice is lost, I think, and some other
thread will be scheduled (the next thread in the run queue of the
highest priority with any threads in it).

I am not sure this is really explained in the spec.  It's more or less
an implementation detail.  But it's the only thing that makes sense to
do (the only thing I am not sure about is if the remainder of the time
slice is lost, ie, if the timeslice is reinitialized, and if the
remainder is added back to the total quantum of the thread).

> >L4 will never migrate threads from one CPU to another.  So, both
> >threads already have to be on the same CPU for this donation to take
> >place.
> 
> As far as I know this is almost always what you want - propagating a
> thread from one CPU to another is generally quite expensive.  Whether
> it's obvious from the amount of code executed or not is a very
> different matter though!  Caches and TLBs are going to be thrashed to
> pieces during this.

Certainly this, and the avoidance of defining policy, is the reason
that L4 does not migrate threads.

> The L4 model may want rethinking with the newer multi-core CPUs that
> we're seeing these days though.  That combined with NUMA architecture
> is pushing things towards building some sort of hierarchy with the
> cost of switching CPUs dependant on how far up the hierarchy you have
> to navigate to the other CPU (not sure what the technical term for
> this is, it's not a straight distance thing and (as far as I can
> remember) only works for tree structures).

You have to do this yourself, in your own scheduler implementation.
L4 only provides the mechanism to change the CPU a thread runs on, and
not which thread should migrate to which CPU at which time.

BTW, the L4 guys plan to use hyper-threading for faster IPC, I think,
and not to emulate an SMP machine (or at least that's an option).
There is a talk about this by some Intel guy, but I didn't find any
papers.
 
> >(The spec does not actually say if and how donation takes place at
> >IPC.  But the above is what we can conclude from what makes sense and
> >what is actually being said elsewhere in the spec.)
> 
> Any pointers?

Well, the description of how scheduling works, and what is said at
ThreadSwitch about switching to a thread on another CPU.  You could
(and probably should) for such things look into the L4 implementation
as well.
 
> >> Second, assuming the server thread is ready (i.e. in receiving
> >> "mode"), it is not running--it is blocked waiting to receive a
> >> message.  Hence, it is not on a CPU (it may have a last CPU where it
> >> has a small cache footprint but that is different as I understand it).
> >
> >It seems to me that there is a fixed thread-to-CPU mapping independent
> >of thread state, that can only be changed by migrating threads using
> >the Schedule system call.
> 
> I guess they're expecting something like that scheduler activations
> reference I sent earlier to be run on top of them then.  What you've
> said so far would make a *lot* of sense if that was the case.

I don't remember something like "scheduler activations reference", but
certainly we are expected to (and actually need to) implement a
user-space scheduler.

Thanks,
Marcus