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

[Dagaen Golomb <dgolomb@xxxxxxxxxxxxxx>]

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

I just thought that since you didn't like the scheduler handling replenishments,
that you wouldn't be very fond of replenishment calling the scheduler. I don't
find either an issue so if you like one over the other, then that's
fine of course.

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

I have no interest in a terminology war either. I just figured that if we want
the replenishment function to only tickle when necessary, then it should
check that the replenished vCPU is a greater priority than current ones.
At this point it has essentially done the entire scheduling decision. I agree
it can then tickle and let pCPU pick it up, and I find this a fine solution. As
I said before I guess I just thought you wouldn't like the idea, but its clear
you do.

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

Gotcha.

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

I guess the last remaining question is this: when the scheduler is
enforcing a budget and times out, should it check for replenishment
before kicking the vCPU? Or assume that any relevant replenishments
have occurred? This is the issue I mentioned before about two timers
armed at the same time - I'm not sure what convention Xen uses to
order them. I would assume from your very reason for mentioning this
change that you don't want any replenishment in rt_schedule, but then
it may kick a vCPU who at that very instant is supposed to be replenished
as well, and should actually stay on the pCPU. This is assuming you
still want rt_schedule to be timer-triggered to enforce budget, is this
correct?

However, I think this is a more minor issue that we can sort out via
inspecting the default Xen behavior, or allowing a single replenishment
call before kicking (I don't expect you to like that option :P), or some
other method.

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

Okay, I understand this. My [poor] point was that how it is done now could
be better separated into logical parts with functions.

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

I mean its already moved the vCPU and knows it should go on pCPU X, now
when we call tickle that function itself will have to choose which to kick. It's
doing this work twice, we already knew which one was new. Its not a lot of
work and isn't an issue, just feels like the replenishment routine, in order
to only tickle when necessary, is basically acting as the scheduler. Just a
weird way my mind views it.

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

A replenishment that causes a resched - these will be back to back and will both
involve the lock. Its definetly not worse than the current solution, just that
its likely going to be about the same amount of time in lock. I'm just saying
the lock timing in the current solution doesn't appear like it would be much
worse, although we do have all the maintainability and structure arguments
against it, so this is a moot point.

Overall, I see where you're coming from now. I think the only issue still
is whether rt_schedule should absolutely never check for replenishments.
I guess my last question is, when rt_schedule is reinvoked by timer because
a budget is being exhausted, what do you expect it to do? Nothing? (Besides
move it to the depletedq) and rely on the budget replenish routine to to handle
it? Should it wait for that routine or call it?

Besides this I understand where you want this to go, and I think its worth
pursuing.

Regards,
~Dagaen

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