From mboxrd@z Thu Jan 1 00:00:00 1970 From: Dario Faggioli Subject: Re: [PATCH v7]xen: sched: convert RTDS from time to event driven model Date: Thu, 10 Mar 2016 17:43:18 +0100 Message-ID: <1457628198.3102.525.camel@citrix.com> References: <1457141967-3340-1-git-send-email-tiche@seas.upenn.edu> <1457538364.3102.418.camel@citrix.com> <1457606291.3102.473.camel@citrix.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="===============3762802757789028120==" Return-path: Received: from mail6.bemta14.messagelabs.com ([193.109.254.103]) by lists.xen.org with esmtp (Exim 4.84) (envelope-from ) id 1ae3gZ-0004ln-6r for xen-devel@lists.xenproject.org; Thu, 10 Mar 2016 16:43:39 +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: "xen-devel@lists.xenproject.org" , Tianyang Chen , Meng Xu , George Dunlap , Dagaen Golomb List-Id: xen-devel@lists.xenproject.org --===============3762802757789028120== Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-5riwtiPv/PRKc/cds1fM" --=-5riwtiPv/PRKc/cds1fM Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thu, 2016-03-10 at 10:28 -0500, Meng Xu wrote: > On Thu, Mar 10, 2016 at 5:38 AM, Dario Faggioli > wrote: > >=20 > > I don't think we really need to count anything. In fact, what I had > > in > > mind and tried to put down in pseudocode is that we traverse the > > list > > of replenishment events twice. During the first traversal, we do > > not > > remove the elements that we replenish (i.e., the ones that we call > > rt_update_deadline() on). Therefore, we can just do the second > > traversal, find them all in there, handle the tickling, and --in > > this > > case-- remove and re-insert them. Wouldn't this work? > My concern is that: > Once we run rt_update_deadline() in the first traversal of the list, > we have updated the cur_deadline and cur_budget already. > Since the replenish queue is sorted by the cur_deadline, how can we > know which vcpu has been updated in the first traversal and need to > be > reinsert?=C2=A0=C2=A0We don't have to traverse the whole replq to reinser= t all > vcpus since some of them haven't been replenished yet. >=20 Ah, you're right, doing all the rt_update_deadline() in the first loop, we screw the stop condition of the second loop. I still don't like counting, it looks fragile. :-/ This that you propose here... > If we wan to avoid the counting, we can add a flag like > =C2=A0#define __RTDS_delayed_reinsert_replq=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= 4 > #define RTDS_delayed_reinsert_replq=C2=A0=C2=A0(1<< > __RTDS_delayed_reinsert_replq) > so that we know when we should stop at the second traversal. >=20 ...seems like it could work, but I also am not super happy about it, as it does not look to me there should be the need of such a generic piece of information such as a flag, for this very specific purpose. I mean, I know we have plenty of free bits in flag, but it's something that happens *all* *inside* one function (replenishment timer handler). What about an internal (to the timer replenishment fucntion), temporary, list. Something along the lines of: =C2=A0 ... =C2=A0 LIST_HEAD(tmp_replq); =C2=A0 list_for_each_safe(iter, tmp, replq) =C2=A0 { =C2=A0 =C2=A0 =C2=A0 svc =3D replq_elem(iter); =C2=A0 =C2=A0 =C2=A0 if ( now < svc->cur_deadline ) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 break; =C2=A0 =C2=A0 =C2=A0 list_del(&svc->replq_elem); =C2=A0 =C2=A0 =C2=A0 rt_update_deadline(now, svc); =C2=A0 =C2=A0 =C2=A0 list_add(&svc->replq_elem, &tmp_replq); =C2=A0 } =C2=A0 list_for_each_safe(iter, tmp, tmp_replq) =C2=A0 { =C2=A0 =C2=A0 =C2=A0=C2=A0svc =3D replq_elem(iter); =C2=A0 =C2=A0 =C2=A0 < tickling logic > =C2=A0 =C2=A0 =C2=A0 list_del(&svc->replq_elem); =C2=A0 =C2=A0 =C2=A0=C2=A0deadline_queue_insert(&replq_elem, svc, &svc->rep= lq_elem, replq); =C2=A0 } =C2=A0 ... So, basically, the idea is: =C2=A0- first, we fetch all the vcpus that needs a replenishment, remove =C2=A0 =C2=A0them from replenishment queue, do the replenishment and stash = them =C2=A0 =C2=A0in a temp list; =C2=A0- second, for all the vcpus that we replenished (which we know which= =C2=A0 =C2=A0 =C2=A0ones they are: all the ones in the temp list!) we apply the pr= oper =C2=A0 =C2=A0tickling logic, remove them from the temp list and queue their= new =C2=A0 =C2=A0replenishment event. It may look a bit convoluted, all these list moving, but I do like the fact that is is super self-contained. How does that sound / What did I forget this time ? :-) BTW, I hope I got the code snippet right, but please, let's focus and discuss the idea. Regards, Dario --=20 <> (Raistlin Majere) ----------------------------------------------------------------- Dario Faggioli, Ph.D, http://about.me/dario.faggioli Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK) --=-5riwtiPv/PRKc/cds1fM 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 iEYEABECAAYFAlbhpCcACgkQk4XaBE3IOsTz0QCgggqb159s+n/5znxXrtKVZbuz XnEAn3UIyXwmJvpHUYCADCaB2i3GJnI2 =2Zz0 -----END PGP SIGNATURE----- --=-5riwtiPv/PRKc/cds1fM-- --===============3762802757789028120== Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: base64 Content-Disposition: inline X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KWGVuLWRldmVs IG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9yZwpodHRwOi8vbGlzdHMueGVuLm9y Zy94ZW4tZGV2ZWwK --===============3762802757789028120==--