From mboxrd@z Thu Jan 1 00:00:00 1970 From: Dario Faggioli Subject: Re: [Design RFC] Towards work-conserving RTDS scheduler Date: Thu, 18 Aug 2016 12:22:06 +0200 Message-ID: <1471515726.6806.72.camel@citrix.com> References: <1470649111.9623.79.camel@citrix.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="===============8982560716251373081==" Return-path: Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1baKSj-0000Zq-9K for xen-devel@lists.xenproject.org; Thu, 18 Aug 2016 10:22:13 +0000 In-Reply-To: List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" To: Meng Xu Cc: George Dunlap , "xen-devel@lists.xenproject.org" List-Id: xen-devel@lists.xenproject.org --===============8982560716251373081== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="=-d9tkVSg/CSlAZuLmw7wV" --=-d9tkVSg/CSlAZuLmw7wV Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Tue, 2016-08-09 at 09:57 -0400, Meng Xu wrote: > On Mon, Aug 8, 2016 at 5:38 AM, Dario Faggioli > wrote: > >=20 > > I'm just thinking out loud and > > wondering: > > =C2=A0- could it be useful to have a scheduling analysis in place for > > the > > =C2=A0=C2=A0=C2=A0scheduler in work conserving mode (one, of course, th= at takes > > into > > =C2=A0=C2=A0=C2=A0account and give guarantees on the otherwise idle ban= dwidth... I > > =C2=A0=C2=A0=C2=A0know that the existing one holds! :-P) ? > > =C2=A0- if yes, do you already have one --or do you think it will be > > =C2=A0=C2=A0=C2=A0possible to develop one-- for your priority-index bas= ed model? > I think I could potentially develop one such analysis. >=20 Great. Let me know if you need any help writing the paper! :-P > > Actually, it's quite likely that you either have already noticed > > this > > and done the analysis, or that someone else in literature has done > > something similar --maybe with other schedulers-- before. > Yes, I noticed this but I don't have analysis yet. ;-) I will do some > math formulas to model this situation. > I'm thinking the desired design will be > 1) Work-conserving scheduler; > 2) A *tight* schedulability analysis. If we cannot get tight > analysis, > we should reduce the abstraction overhead, i.e., num_cores - > utilization of all VCPUs. (In order to achieve better analysis, we > may > need to change the scheduling policy a bit. I'm not very clear about > how to do it yet, but I will think about it.) >=20 Err... I'm not sure I got what you exactly mean here, but this is your field, just go ahead with it without bothering explaining everything to me. :-) > > Anyway, the idea itself looks fair enough to me. I'd like to hear, > > if > > that's fine with you, how you plan to actually implement it, as > > there > > of course are multiple different ways to do it, and there are, IMO, > > a > > couple of things that should be kept in mind. > How about letting me think about the analysis first. If we can have > both the work-conserving algorithm and the analysis, that will be > better. If we finally decide not to have the analysis, we can fall > back to the discussion of the current design? >=20 Sure. > > Finally, about the work-conserving*ness on-off switch, what added > > difficulty or increase in code complexity prevents us to, instead > > of > > this: > >=20 > > "2) Priority index: It indicates the current=C2=A0=C2=A0priority level = of the > > =C2=A0=C2=A0=C2=A0=C2=A0VCPU. When a VCPU=E2=80=99s budget is depleted = in the current period, > > its > > =C2=A0=C2=A0=C2=A0=C2=A0priority index will increase by 1 and its budge= t will be > > =C2=A0=C2=A0=C2=A0=C2=A0replenished." > >=20 > > do something like this: > >=20 > > "2) Priority index: It indicates the current=C2=A0=C2=A0priority level = of the > > =C2=A0=C2=A0=C2=A0=C2=A0VCPU. When a VCPU's budget is depleted in the c= urrent period: > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A02a) if the VCPU has the work conserving f= lag set, its priority > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0index will be inc= reased by 1, and its budget replenished; > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A02b) if the VCPU has the work conserving f= lag cleat, it's > > blocked > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0until next period= ." > >=20 > > ? > Agree. We can have the per-VCPU working-conserving flag. >=20 Glad you see it useful/doable too. Regards, Dario --=20 <> (Raistlin Majere) ----------------------------------------------------------------- Dario Faggioli, Ph.D, http://about.me/dario.faggioli Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK) --=-d9tkVSg/CSlAZuLmw7wV Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAABCAAGBQJXtYxOAAoJEBZCeImluHPuboEP/2UetJXI+4MLbx0mKoVXQ2eK chWr3uft8xvjaiPCEUWCOh6IUzI67umaF14RNdfnVl9oCo30kcYsg3sWzk9YO7yR xBf0SMaWtkPFpC/cJC61ZVxFfuXZO43X+1OBKnx8kkbu2EG3rGvc2C8YFZQeZ3+X JzlYvw24rAn53NY91tSFqWfsBNmiyc5XmjPzvpqEle9822VgtAgbfaqJ3KhzTwVU 0KekVjLC4I1jfmg6ujSqcJ8zKWoFlNQECFheOrb8LtPKN/6s+z2UwQM2m2W0TL5E YE8OTtFiMR7dHwseXVwbUaGncSNSAMnER7FQ5WEIgEl/giBvkNe6VppuBJm7Vk5d t8cSKn0A0s9sZtPSjxBzwzcI0SXzGEvlSXhBnl9Ewqy1dpb0dcFFNWFIh6o/cwgF 0vEYxTDLOj6U8sxgl+lzbqctrgKF3GUffbW4DPEluXJxlGE0CLi+mRqf9mctiMXY 6GVA1Arvewe05jhb7vuT3LJpRqY4Tm5Tm/s5dpKRTd+aJ48gP6VkYRtd6kRlmww6 PoPweuV0gcKLeEc/fBmBGHgh+jDV+yv/WdXw44pRTbMFyXsC6ttAzOKeZeJjYiu/ xqiqmiSMZTbSz4ywOz7PqHFrMf/86w7HC//Zlif+T3ydoBpkmsFDoY+KSQBHm15a cPzIYlun+iLHB6KLgadr =T35H -----END PGP SIGNATURE----- --=-d9tkVSg/CSlAZuLmw7wV-- --===============8982560716251373081== Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: base64 Content-Disposition: inline X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KWGVuLWRldmVs IG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9yZwpodHRwczovL2xpc3RzLnhlbi5v cmcveGVuLWRldmVsCg== --===============8982560716251373081==--