From mboxrd@z Thu Jan 1 00:00:00 1970 From: Dario Faggioli Subject: Re: [RFC PATCH 1/4] Implement cbs algorithm, remove extra queues, latency scaling, and weight support from sedf Date: Tue, 17 Jun 2014 18:06:18 +0200 Message-ID: <1403021178.16864.190.camel@Solace> References: <1402689488-3577-1-git-send-email-josh.whitehead@dornerworks.com> <1402689488-3577-2-git-send-email-josh.whitehead@dornerworks.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0214315740361365786==" Return-path: In-Reply-To: <1402689488-3577-2-git-send-email-josh.whitehead@dornerworks.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Josh Whitehead Cc: Ian Campbell , Stefano Stabellini , George Dunlap , Ian Jackson , Robert VanVossen , Xen-devel , Nate Studer List-Id: xen-devel@lists.xenproject.org --===============0214315740361365786== Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-x4rajY1oHNV4S+BNCx9Z" --=-x4rajY1oHNV4S+BNCx9Z Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Although very hard, I tried to have a look at the CBS implementation (so, some of the '+' hunks): On ven, 2014-06-13 at 15:58 -0400, Josh Whitehead wrote: > --- > @@ -410,49 +301,59 @@ static void desched_edf_dom(s_time_t now, struct vc= pu* d) > =20 > __del_from_queue(d); > =20 > - /* > - * Manage bookkeeping (i.e. calculate next deadline, memorise > - * overrun-time of slice) of finished domains. > - */ > +#ifdef SEDF_STATS > + /* Manage deadline misses */ > + if ( unlikely(inf->deadl_abs < now) ) > + { > + inf->miss_tot++; > + inf->miss_time +=3D inf->cputime; > + } > +#endif > + > + /* Manage overruns */ > if ( inf->cputime >=3D inf->slice ) > { > inf->cputime -=3D inf->slice; > - =20 > - if ( inf->period < inf->period_orig ) > - { > - /* This domain runs in latency scaling or burst mode */ > - inf->period *=3D 2; > - inf->slice *=3D 2; > - if ( (inf->period > inf->period_orig) || > - (inf->slice > inf->slice_orig) ) > - { > - /* Reset slice and period */ > - inf->period =3D inf->period_orig; > - inf->slice =3D inf->slice_orig; > - } > - } > =20 > /* Set next deadline */ > inf->deadl_abs +=3D inf->period; > + > + /* Ensure that the cputime is always less than slice */ > + if ( unlikely(inf->cputime > inf->slice) ) > + { > +#ifdef SEDF_STATS > + inf->over_tot++; > + inf->over_time +=3D inf->cputime; > +#endif > + > + /* Make up for the overage by pushing the deadline > + into the future */ > + inf->deadl_abs +=3D ((inf->cputime / inf->slice) > + * inf->period) * 2; > + inf->cputime -=3D (inf->cputime / inf->slice) * inf->slice; > + } > Can you enlighten me a bit about the math here? I see what you're up to, but I'm not sure I understand the '*2'... > + /* Ensure that the start of the next period is in the future */ > + if ( unlikely(PERIOD_BEGIN(inf) < now) ) > + inf->deadl_abs +=3D=20 > + (DIV_UP(now - PERIOD_BEGIN(inf), > + inf->period)) * inf->period; > } > @@ -1100,62 +663,65 @@ static void sedf_wake(const struct scheduler *ops,= struct vcpu *d) > inf->block_tot++; > #endif > =20 > - if ( unlikely(now < PERIOD_BEGIN(inf)) ) > - { > - /* Unblocking in extra-time! */ > - if ( inf->status & EXTRA_WANT_PEN_Q ) > + if ( sedf_soft(d) ) > + { > + /* Apply CBS rule > + * Where: > + * c =3D=3D Remaining server slice =3D=3D (inf->slice - cpu= _time)=20 > + * d =3D=3D Server (vcpu) deadline =3D=3D inf->deadl_abs > + * r =3D=3D Wake-up time of vcpu =3D=3D now > + * U =3D=3D Server (vcpu) bandwidth =3D=3D (inf->slice / in= f->period) > + * > + * if c>=3D(d-r)*U ---> =20 > + * (inf->slice - cputime) >=3D (inf->deadl_abs - now) * inf= ->period > + * Well, I think it's rather: (inf->slice - cputime) >=3D (inf->deadl_abs - now) * (inf->slice / inf->period) It's only the comment that is wrong, though, the code is ok. > + * If true, push deadline back by one period and refresh slice, = else > + * use current slice and deadline. > + */ > + if((inf->slice - inf->cputime) >=3D=20 > + ((inf->deadl_abs - now) * (inf->slice / inf->period))) > { > You can shuffle this a bit more, and avoid the '/'. The condition above can be rewritten as: c >=3D (d-r) * (inf->slide/inf->period) i.e.: c * inf->period >=3D (d-r) * inf->slice and this, the code can be rewritten as: if ((inf->slice - inf->cputime) * inf->period >=3D (inf->deadl_abs - now) * inf->slice) which I think it's better. One may worry about the fact that the multiplication can overflow, but that's really unlikely, since all the involved time values are relative (i.e., remaining runtime, time to deadline, etc). Anyway, let's cross that bridge when we get to it. Regards, Dario --=20 <> (Raistlin Majere) ----------------------------------------------------------------- Dario Faggioli, Ph.D, http://about.me/dario.faggioli Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK) --=-x4rajY1oHNV4S+BNCx9Z 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.0.22 (GNU/Linux) iEYEABECAAYFAlOgZ3oACgkQk4XaBE3IOsSk9ACeMQJaenq3LOR9X0VY8nCeepYL t4kAnRCidT4yrJWQl6lHLE2whlNXHZoc =f0xN -----END PGP SIGNATURE----- --=-x4rajY1oHNV4S+BNCx9Z-- --===============0214315740361365786== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Xen-devel mailing list Xen-devel@lists.xen.org http://lists.xen.org/xen-devel --===============0214315740361365786==--