Re: [Xen-devel] [PATCH] Modified RTDS scheduler to use an event-driven model instead of polling.

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

[Let me just reply to this... Then I'll jump to the end of the thread]

On Wed, 2015-06-17 at 01:24 -0400, Dagaen Golomb wrote:

> >> If replenishments were done by themsevles, then the scheduler may
> >> decide to wait for some period of time, and in this same time period a
> >> replenishment
> >> could change what should be executing.
> >>
> > Well, the scheduler then would better *not* decide to wait for any
> > period of time. It better act like this: as soon as a replenishment
> > happens, and a new deadline is assigned to a vCPU, put the vCPU in the
> > runqueue, in the proper position; and if such a newly replenished vCPU
> > should now preempt any other, currently running, vCPU, 'tickle' the pCPU
> > in question and let it reschedule, and pick up the newly replenished
> > vCPU.
> 
> Yes, this is an option. However, I thought this would actually be an
> option you would
> not like. 
>
How so... I've been arguing for this the whole time?!?! :-O

I'm sure I've put down a sketch of what I think the replenishment
function should do in my first or second email in the thread, and I'm
sure that involved a call to runq_tickle()

> For the replenishment routine to know when to call the
> scheduler and when
> not to, it basically has to perform the the scheduler's logic, at
> which point if there is a
> change... why doesn't it just do it (i.e., be the scheduler) instead
> of adding logic and
> possibly overhead to call it.
> 
It has to call runq_tickle(), which is not "the scheduler's logic", is
the function that decides whether a pCPU should reschedule.

runq_tickle(), right now, is called from within rt_vcpu_wake(), which
makes perfect sense, and from within rt_context_saved(), which makes no
sense. It should be called from within rt_vcpu_wake() and from the
replenishment handling routine.

Scheduling, to me, is __runq_pick() + the if() in rt_schedule() that
checks whether scurr->cur_deadline<=snext->cur_deadline.

Anyway, I've zero interest in turning this into a fight over
terminology... If you want to call runq_tickle() "the scheduler", go
ahead, it would just make communication a bit more difficult, but I'm up
for the challenge! :-)

Oh, BTW, while we're here, __runq_pick() being called from a bunch of
places, outside of rt_schedule(), is also something I never liked (you
can go check that in the archives), and I also blame the confusion
between scheduling and replenishmets, for the fact that such a thing is
necessary. I seriously hope this can be fixed too.

> Also, I'd like to point out that when I said things like "make more 
> intelligent"
> decision handling, I meant exactly things like the above: using as much
> information as possible to prevent scheduler invocations. The current patch
> doesn't reschedule for any replenishment.
>
How does it not? you're arming s_timer to fire at either next
replenishment or budget enforcement point in time...

>  Firstly, it doesn't even look at
> the run queue: replenishments here can only happen on miss.
> 
... Oh, wait, I know! I know! I know! You mean "it doesn't tickle at any
replenishment", or "it doesn't context switch at any replenishment",
don't you?

(See, I'm good at adapting to "the new" terminology! :-D)

> > So, see? Transient  violation of EDF is just there, no matter the
> > approach!
> 
> Of course, violation during the scheduler is possible for any implementation 
> :(
> 
Yeah, well, it was you that said that which should stick to your design
to prevent violations, which would have crept in if going with my
solution. Bha, anyway, it's probably best to let go...

> > I really don't see what you mean here. There won't be anything like that
> > to take care of. Xen offers timers as an abstraction, and deals with
> > them itself. You only need to take care of properly serializing
> > rt_schedule() and the timer handling routine, for the code sections that
> > require that.
> 
> This is good to know, thanks. The question would then change to how does
> Xen handle such an occurrence, but I think this is irrelevant now that I know
> which "side" you had in mind - that is, that the replenishment handler would
> decide when the scheduler should be invoked.
> 
It should call runq_tickle(), yes.

> >> It would be a hard pitch for a gEDF scheduler with a
> >> similar "accounting period" where the gEDF policy could be violated.
> >>
> > There's no accounting period of any sort. It's called overhead!
> 
> This part was referring to if we had two timers without extensive 
> communication,
> cooperation, or information/logic sharing.
> 
I'm in the dark about what this "extensive communication, cooperation,
or information/logic sharing" could be, I have to admit.

If it means that the replenishment handler should call runq_tickle(),
then yes, let me state it once more: replenishment handling routine
should call runq_tickle() (other places, with the only other exception
of rt_vcpu_wake(), shouldn't).

> > You also may know that there is an EDF implementation in mainline Linux,
> > and you may would like to go have a look there too. I'm not including
> > any example from there because I'm one of the  main authors of it, so
> > it's pretty obvious that it uses the approach I think it's best (and,
> > more important, it would be rather inelegant to cite myself! :-D).
> >
> > Anyway, if you fancy doing that, the core is in kernel/sched/deadline.c.
> 
> Thanks for the history and background lesson here :)
> 
NP. Did you have a look? What do you think, do you like it? :-D

> >> I simply
> >> don't see how it can
> >> be done without heavy interaction and information sharing between them
> >> which really
> >> defeats the purpose.
> >>
> > No, it doesn't.
> 
> Ok this last line is the zinger.
> 
> Almost this entire email was built on the premise that you would NOT like the
> idea of the replenishment handler having basically the same decision logic
> as the scheduler and then tickling the pCPU to pick up the new vCPU. 
>
Which is true, they're separate and different things, the must have
separate and different logic. The fact that one may decide when it's
time to call the other is perfectly logical.

And in fact, I want __runq_pick() and related logic to be in
rt_schedule(), and nowhere else, while I want runq_tickle() to be done
from replenishment (and wakeup), and nowhere else.

> Actually,
> with it done this way, I would have a hard time calling the
> tickle-invoked method
> the "scheduler." 
>
With "tickle-invoked method" you mean rt_schedule(), I guess.

> In this case, I'm not too sure
> actually how much
> different this would be from what we have now. 
>
Very different. Mostly because functions will have a clear and well
defined semantic, and will be called to fulfill their own purpose, from
places where it makes sense to do so, not every now and then, like now:

 - rt_schedule() for picking a new vcpu to be run and for doing runtime
   accounting and enforcement;
 - __runq_pick() to do the actual pick operation, from within
   rt_schedule() only, not every now and then, like now;
 - __repl_update() to do replenishments, from within the replenishment
   handling routine, in an event-triggered fashion, not every now and
   then, like now;
 - runq_tickle() to check whether a pCPU needs to go through the
   scheduler, from either the vcpu wakeup path, or because of a
   replenishment, not every now and then, like now.

> It feels like, from
> what you want,
> that we could get the same behavior by modifying rt_schedule to do
> replenishments
> first, then check if a reschedule is needed (these two parts would be in this
> proposed replenishment timer routine) and the perform any move if necessary. I
> know this isn't exactly what you want, but that sounds close right?
>
Ehm... not really? It indeed sounds like the opposite of how I think
things should be done (and I'm running out of different ways in which
I'm able to tell that! :-O)

> But the scheduler will have to decide which to move in, so that logic
> is done twice.
>
Done twice? What's done twice?

> Also, if these are done back-to-back and require the locks, isn't it
> really the same
> as having one long hot path? 
>
What's back-to-back?

> If you want maintainability, couldn't we just do
> replenishment then schedule and move (if necessary) in one timer (the
> one we have
> now) and move them to functions. It seems this can be done with one
> timer neatly.
> 
Not to me, but I may have lost you again, sorry.

> So here's my proposal, lets see if it fits what you want:
>
Ok, let me leave this here, and deal with this last part by replying to
Meng's email.

Regards,
Dario

> 1.) The scheduler does not do any timing,
> 2.) replenishments are scheduled via timer at each [next]
> replenishment period. Each
> replenishment resorts the replenished vCPUs, and if any of the first
> #CPUs in the
> runq change, we tickle a pCPU for each change
> 
> In this case, we can use one timer. We could use the current one as a
> replenishment
> timer, and make it so rt_schedule isn't the default invoked method.
> 
> Does this sound similar to what you are suggesting? I have to ask
> because I thought
> you wouldn't like the idea, and its not really *that* far off from
> what we have now, Its
> a little restructuring so that replenishments occur before any
> scheduling activity and
> the handler checks if switching is needed (basically acting as the
> scheduler) and then
> calls tickle. Sounds like what you had in mind?
> 
> Regards,
> ~Dagaen

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Attachment: signature.asc
Description: This is a digitally signed message part

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel