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

[Meng Xu <xumengpanda@xxxxxxxxx>]

Hi Dario,

I think I got what you meant 100% now. :-)
I will ping Dagaen to see what he thinks and if he has any concerns.

>
> > > Here's how I envision things to go. Again, I'm talking about sticking
> > > with option a), so no per-vcpu timers, just 1 timer and a global queue,
> > > which now is a replenishment queue:
> > >
> > >   timer interrupt
> > >     TIMER_SOFTIRQ raised
> > >       process softirqs
> > >         replenishment_timer_handler()
> > >           [spin_lock]
> > >             <for_each_replenishment_event(repl_time < NOW()) {
> > >                replenish(vcpu)
> > >                runq_tickle(vcpu)
> > >              }>
> > >           [spin_lock]
> > >
> > > Then, on the tickled pcpus (if any):
> > >
> > >   process softirqs
> > >     SCHEDULE_SOFTIRQ
> > >       rt_schedule()
> > >         [spin_lock]
> > >         snext = runq_pick(): snext == vcpu X
> > >         [spin_unlock]
> > >
> > > And get rid of __repl_update(), which makes my eyes bleed every time I
> > > open sched_rt.c. :-)
> > >
> > > Oh, and note that we probably can use a new spin lock for the
> > > replenishment queue, different from the existing global scheduler
> > > spinlock, lowering contention and increasing scalabiliy even further!
> >
> > Here is the main question I have about your advice.
> > If we are introducing a new spin lock for the replenishment queue,
> > what is the relation between the new lock and the old lock of the
> > runq?
> >
> That's hard to tell in advance, you'll know it completely only when
> trying to implement it. But, yes, when more locks are involved, it's
> impotant to figure out the relationships between each other, or we risk
> introducing deadlock or, even if things are correct, fail to improve the
> performance (or do even worse!!).
>
> The idea is, since the two operations (scheduling/budget enforcement and
> replenishments) are logically independent, and if they're implemented in
> a way that stress this independence, then it make sens to try to use
> different spin locks.
>
> As soon as you have more than one spin lock, what you should pay the
> most attention to is, if they need to 'nest' (one is acquired when the
> other is already being held), that has to happen consistently, or
> deadlock will occur! :-/
>
> > Because the deadline decides the priority of VCPUs and thus decides
> > the ordering of VCPUs in the runq, the "replenish(vcpu)" will operate
> > on the runq as well. As shown in the workflow in your reply:
> >      >                replenish(vcpu)
> >      >                runq_tickle(vcpu)
> > The runq_tickle(vcpu) will pick the desired CPU. On that CPU,
> > rt_schedule will pick snext by runq_pick(). Therefore, the replenished
> > VCPU need to be resorted in the runq. So replenish(vcpu) will operates
> > on the runq.
> >
> Oh, sure, absolutely. Calling __runq_insert() and runq_tickle(), clearly
> must be done with the runqueue lock (which is the global scheduler lock,
> at the moment) held.
>
> Reading again what I wrote, I realize that I probably expressed myself
> really bad, when hinting at that "let's use another lock" thing.
>
> What I really wanted to say is that, if there will be a replenishment
> queue, i.e., an event queue on which replenishment events are queued,
> and that the timer handling routine scans, there may be some locking
> required for consistently dealing with the queue itself. If that will be
> the case, we probably can use _another_ spin lock, and let the timer
> handling routine acquire the runqueue lock *only* when/if it gets to do
> the insertions and the ticklings.
> Sorry for this... I added that paragraph quickly, right before hitting
> 'send'... I probably would have better not done so! :-P
>
> Again, this may or may not be necessary, and may or may not be possible,
> depending on whether the two locks would nest nicely everywhere they're
> required. This also depends on how we'll deal with the replenishment
> timer.
>
> So, the bottom line of all this is: get down to it, ad we'll see how it
> will be better put together! :-D

I see. Got it. :-)

>
> > Another question in my mind is: do we really need the replenish queue
> > to record the replenish time? Because the period = deadline in the
> > current implementation, the deadline of VCPUs in runq is actually the
> > replenish time. (We are reusing the runq here and I'm unsure if it
> > good or not in terms of maintenance.)
> >
> Again, let's see. The timer will be always programmed to fire at the
> most imminent replenishment event, so it seems to me that you need
> something that will tell you, when servicing replenishment X, what's the
> next time instant you want the timer to fire, to perform the next
> replenishment.
>
> Actually, the depleted queue you have know, can well become the
> replenishment queue (it will have to be kept sorted, though, I think).
> Whether you want to keep it as the tail of the actual runqueue, or split
> the two of them, it does not matter much, IMO.

Right. The runq and the depleted queue actually has the information of
the next replenish time for all VCPUs, after the depleted queue is
changed to be sorted.


Best regards,

Meng


-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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