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

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

On Tue, 2015-06-16 at 22:45 -0700, Meng Xu wrote:

> > So here's my proposal, lets see if it fits what you want:
>
> I will leave this to Dario to answer if it fits what he wants. :-P

> > 1.) The scheduler does not do any timing,

> Not really. The rt_schedule does the budget enforcement. When a
> current VCPU runs out of budget, the rt_schedule will be invoked by a
> timer (you can refer to the schedule function in xen/sched/schedule.c
> to have a look how the timer is armed/disarmed.). When the rt_schedule
> is invoked, it needs to:
> a) update the budget of the current running VCPU and move it from runq
> to depleted queue;
> b) pick the current highest VCPU from runq and return it as the snext VCPU.
> 
> So scheduling logic is still  involved in the rt_schedule function.
> 
Correct, thanks Meng.

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

> This is right.
> 
Yeah, sort of. I mean, I'm not sure what "Each replenishment resorts the
replenished vCPUs" means. If it means that a replenished vCPU is given a
new deadline, and hence needs to move from depleted queue to runqueue,
in a position within runqueue that reflects its new deadline... then, I
agree.

This requires holding the runqueue lock, but we need it anyway, for now.

This may or may not require a pCPU to be tickled, and it's
runq_tickle()'s job to decide whether that is the case and, if yes,
which one.

Also, about this "we tickle a pCPU for each change": first of all, as I
just said, that's not _always_ the case, and we should avoid tickling
when it's not necessary. Also, when it's necessary in principle, it
makes few sense to tickle a pCPU twice in a very tight loop (i.e.,
without giving it the chance to reschedule).

So if, for instance, two different replenishments (no matter whether
being serviced together, or in different invocations of the
replenishment timer handler) both determine that pCPU Y is the one that
should be tickled (because it's the one running the vCPU with the latest
deadline, and both the two replenished vCPUs have more imminent deadline
than what's running on Y, but later than what's running everywhere
else), there's no point in tickling twice. Not that doing it would be
harmful, it just won't have any effect. What I mean is much rather that
you can use this information to keep runq_tickle() simple/quick.

Note that this is pretty much what's happening already in runq_tickle(),
thanks to the use of the prv->tickled bitmap, so the point here is
making sure that "we tickle a pCPU for each change" doesn't mean
removing this, because I think that would be wrong. It's probably
unlikely that this was what Dagaen meant, but I though I better state
things clearly. :-)

> > In this case, we can use one timer.
>
> We actually have two: one for budget enforcement and the other for
> budget replenishment.
> 
EXACTLY!! :-)

> > 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 don't think so, but I will leave it for Dario's for his opinion.
> 
"use current one as replenishment timer, and make it so rt_schedule
isn't the default invoked method"

Please, please, please, don't do that! :-P

> In Dario's suggestion, you just simply remove the update_budget
> function out of rt_schedule. This is because budget enforcement, which
> is the work of rt_schedule, does not naturelly involves budget
> replenishment.
> 
Yes. Or at least, that's the core of my suggestion, yes. In more
details, my suggestion includes getting rid of a bunch of other
invocations of scheduling/picking and replenishment related functions
from many other places, as I tried to make clear in my last email.

Perhaps, the fact that I haven't stated that clearly enough since now,
was what was making it a bit harder for you to see what I meant with
'making things simple', etc. I hope I explained myself better now.

> In order to achieve budget replenishment, we need another timer to
> invoke another function (budget_replenish function), that is dedicated
> to that.
> 
Yep, indeed.

> > I have to ask
> > because I thought
> > you wouldn't like the idea,
>
> I guess Dario won't like this idea. :-P (I'm kidding, but it should be
> the case.)
> 
You're right, it's not. :-)

> >
> > 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?
> 
This need for an strict ordering between replenishments and scheduling
is something that you're (Dagaen) insisting a lot on, while I really
don't see why it would be a good thing.

I've stated countless time that they're independent, which also mean
there's no strict ordering requirement between them.

Maybe what you're hinting at is that we may want to think to a better
way of handling rescheduling on the 'local' pCPU. That is to say, if
replenishment timer fires on pCPU X, and runq_tickle() determines that
it's pCPU X itself that should reschedule, there may be a quicker way to
do so, than raising the SCHEDULE_SOFTIRQ and waiting. I.e., some kind of
"hey man, we're here, let's just call (rt_)schedule() and get done with
it!".

If it's this, I thought about it too, many times, but whether it is an
actualy issue, and whether it would actually be a good thing, it's still
unclear. For instance, Linux has this, but, of course, we are not
Linux. :-)

In any case, this is independent from Dagaen's work, and it's even
general enough that other schedulers may be interested in it, so I'm
happy to leave this for future investigation.

Regards,
Dario

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