From: Meng Xu <xumengpanda@gmail.com>
To: Dario Faggioli <dario.faggioli@citrix.com>,
Dagaen Golomb <dgolomb@seas.upenn.edu>
Cc: Wei Liu <wei.liu2@citrix.com>, Sisu Xi <xisisu@gmail.com>,
George Dunlap <george.dunlap@eu.citrix.com>,
"xen-devel@lists.xen.org" <xen-devel@lists.xen.org>,
"mengxu@cis.upenn.edu" <mengxu@cis.upenn.edu>,
Jan Beulich <jbeulich@suse.com>, Chong Li <lichong659@gmail.com>
Subject: Re: [PATCH] Modified RTDS scheduler to use an event-driven model instead of polling.
Date: Sat, 13 Jun 2015 10:21:02 -0700 [thread overview]
Message-ID: <CAENZ-+k4XukX=1uecZrUks+rzqVCgtswWi6_D2p=+8ndU_xNiA@mail.gmail.com> (raw)
In-Reply-To: <1434101293.18921.45.camel@citrix.com>
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/
prev parent reply other threads:[~2015-06-13 17:21 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-08 11:46 [PATCH] Modified RTDS scheduler to use an event-driven model instead of polling Dagaen Golomb
2015-06-09 12:53 ` Dario Faggioli
2015-06-10 4:18 ` Dagaen Golomb
2015-06-10 22:30 ` Dario Faggioli
2015-06-13 20:33 ` Dagaen Golomb
2015-06-16 17:07 ` Dagaen Golomb
2015-06-17 0:20 ` Dario Faggioli
2015-06-17 5:24 ` Dagaen Golomb
2015-06-17 5:45 ` Meng Xu
2015-06-17 6:03 ` Dagaen Golomb
2015-06-17 6:09 ` Meng Xu
2015-06-17 9:20 ` Dario Faggioli
2015-06-17 8:27 ` Dario Faggioli
2015-06-18 18:07 ` Dagaen Golomb
2015-06-22 9:11 ` Dario Faggioli
2015-06-22 11:58 ` Dagaen Golomb
2015-06-10 5:54 ` Meng Xu
2015-06-10 17:46 ` Dario Faggioli
2015-06-11 5:50 ` Meng Xu
2015-06-12 9:28 ` Dario Faggioli
2015-06-13 17:21 ` Meng Xu [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAENZ-+k4XukX=1uecZrUks+rzqVCgtswWi6_D2p=+8ndU_xNiA@mail.gmail.com' \
--to=xumengpanda@gmail.com \
--cc=dario.faggioli@citrix.com \
--cc=dgolomb@seas.upenn.edu \
--cc=george.dunlap@eu.citrix.com \
--cc=jbeulich@suse.com \
--cc=lichong659@gmail.com \
--cc=mengxu@cis.upenn.edu \
--cc=wei.liu2@citrix.com \
--cc=xen-devel@lists.xen.org \
--cc=xisisu@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.