Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Meng Xu]

On Mon, Aug 7, 2017 at 3:14 PM, Dario Faggioli
 wrote:
> On Mon, 2017-08-07 at 14:27 -0400, Meng Xu wrote:
>> On Mon, Aug 7, 2017 at 1:35 PM, Dario Faggioli
>>
>> > Is this wanted or expected?
>>
>> It is wanted.
>>
>> A VCPU i that has already got budget_i * priority_level_i time has
>> higher priority than another VCPU j that got budget_j *
>> priority_level_j time, where priority_level_j > priority_level_i.
>>
>> For the unreserved resource, a VCPU will gets roughly budget/period
>> proportional unreserved CPU time.
>>
>>
>> > Basically, if I'm not wrong, this means that the actual priority,
>> > during the extratime phase, is some combination of deadline and
>> > budget
>> > (which would make me think to utilization)... is this the case?
>>
>> Yes.
>> The higher utilization a VCPU has, the more extra time it will get in
>> the extratime phase.
>>
>> >
>> > I don't care much about the actual schedule during the extratime
>> > phase,
>> > in the sense that it doesn't have to be anything too complicated or
>> > super advanced... but I at least would like:
>> > - to know how it works, and hence what to expect,
>> > - for it to be roughly fair.
>>
>> The unreserved resource is proportionally allocated to VCPUs roughly
>> based on VCPU's budget/period.
>>
> Right. Then this deserves both:
> - a quick mention in the changelog
> - a little bit more detailed explanation in a comment close to one of
>   the place where the policy is enacted (or at the top of the file,
>   or, well, somewhere :-) )
>

Sure. I can do that in the next version.
Hopefully we can reach the agreement on the code based on this version
so that the next version can be the final version for this patch
series. Hopefully. :)

Best,

Meng

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

___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Dario Faggioli]

On Mon, 2017-08-07 at 14:27 -0400, Meng Xu wrote:
> On Mon, Aug 7, 2017 at 1:35 PM, Dario Faggioli
> 
> > Is this wanted or expected?
> 
> It is wanted.
> 
> A VCPU i that has already got budget_i * priority_level_i time has
> higher priority than another VCPU j that got budget_j *
> priority_level_j time, where priority_level_j > priority_level_i.
> 
> For the unreserved resource, a VCPU will gets roughly budget/period
> proportional unreserved CPU time.
> 
> 
> > Basically, if I'm not wrong, this means that the actual priority,
> > during the extratime phase, is some combination of deadline and
> > budget
> > (which would make me think to utilization)... is this the case?
> 
> Yes.
> The higher utilization a VCPU has, the more extra time it will get in
> the extratime phase.
> 
> > 
> > I don't care much about the actual schedule during the extratime
> > phase,
> > in the sense that it doesn't have to be anything too complicated or
> > super advanced... but I at least would like:
> > - to know how it works, and hence what to expect,
> > - for it to be roughly fair.
> 
> The unreserved resource is proportionally allocated to VCPUs roughly
> based on VCPU's budget/period.
> 
Right. Then this deserves both:
- a quick mention in the changelog
- a little bit more detailed explanation in a comment close to one of 
  the place where the policy is enacted (or at the top of the file, 
  or, well, somewhere :-) )

Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)

signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Meng Xu]

On Mon, Aug 7, 2017 at 1:35 PM, Dario Faggioli
 wrote:
> On Sat, 2017-08-05 at 17:35 -0400, Meng Xu wrote:
>> >
>> > > @@ -966,8 +1001,16 @@ burn_budget(const struct scheduler *ops,
>> > > struct
>> > > rt_vcpu *svc, s_time_t now)
>> > >
>> > >  if ( svc->cur_budget <= 0 )
>> > >  {
>> > > -svc->cur_budget = 0;
>> > > -__set_bit(__RTDS_depleted, >flags);
>> > > +if ( is_work_conserving(svc) )
>> > > +{
>> > > +svc->priority_level++;
>> > >
>> >
>> >ASSERT(svc->priority_level <= 1);
>>
>> I'm sorry I didn't see this suggestion in previous email. I don't
>> think this assert makes sense.
>>
>> A vcpu that has extratime can have priority_level > 1.
>> For example, a VCPU (period = 100ms, budget = 10ms) runs alone on a
>> core. The VCPU may get its budget replenished  for 9 times in a
>> period. the vcpu's priority_level may be 9.
>>
> Ah, ok. Yes, I missed this, while I see this now.
>
> But doesn't this mean that, at a certain time t, between both CPUs that
> are both in 'etratime mode' (i.e., they've run out of budget, but
> they're running because they have extratime set), the one that has
> received less replenishments gets priority?

Yes.

>
> Is this wanted or expected?

It is wanted.

A VCPU i that has already got budget_i * priority_level_i time has
higher priority than another VCPU j that got budget_j *
priority_level_j time, where priority_level_j > priority_level_i.

For the unreserved resource, a VCPU will gets roughly budget/period
proportional unreserved CPU time.


> Basically, if I'm not wrong, this means that the actual priority,
> during the extratime phase, is some combination of deadline and budget
> (which would make me think to utilization)... is this the case?

Yes.
The higher utilization a VCPU has, the more extra time it will get in
the extratime phase.

>
> I don't care much about the actual schedule during the extratime phase,
> in the sense that it doesn't have to be anything too complicated or
> super advanced... but I at least would like:
> - to know how it works, and hence what to expect,
> - for it to be roughly fair.

The unreserved resource is proportionally allocated to VCPUs roughly
based on VCPU's budget/period.

Best,

Meng


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

___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Dario Faggioli]

On Sat, 2017-08-05 at 17:35 -0400, Meng Xu wrote:
> > 
> > > @@ -966,8 +1001,16 @@ burn_budget(const struct scheduler *ops,
> > > struct
> > > rt_vcpu *svc, s_time_t now)
> > > 
> > >  if ( svc->cur_budget <= 0 )
> > >  {
> > > -svc->cur_budget = 0;
> > > -__set_bit(__RTDS_depleted, >flags);
> > > +if ( is_work_conserving(svc) )
> > > +{
> > > +svc->priority_level++;
> > > 
> > 
> >    ASSERT(svc->priority_level <= 1);
> 
> I'm sorry I didn't see this suggestion in previous email. I don't
> think this assert makes sense.
> 
> A vcpu that has extratime can have priority_level > 1.
> For example, a VCPU (period = 100ms, budget = 10ms) runs alone on a
> core. The VCPU may get its budget replenished  for 9 times in a
> period. the vcpu's priority_level may be 9.
> 
Ah, ok. Yes, I missed this, while I see this now.

But doesn't this mean that, at a certain time t, between both CPUs that
are both in 'etratime mode' (i.e., they've run out of budget, but
they're running because they have extratime set), the one that has
received less replenishments gets priority?

Is this wanted or expected?

Basically, if I'm not wrong, this means that the actual priority,
during the extratime phase, is some combination of deadline and budget
(which would make me think to utilization)... is this the case?

I don't care much about the actual schedule during the extratime phase,
in the sense that it doesn't have to be anything too complicated or
super advanced... but I at least would like:
- to know how it works, and hence what to expect,
- for it to be roughly fair.

Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)

signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Meng Xu]

>
>> @@ -966,8 +1001,16 @@ burn_budget(const struct scheduler *ops, struct
>> rt_vcpu *svc, s_time_t now)
>>
>>  if ( svc->cur_budget <= 0 )
>>  {
>> -svc->cur_budget = 0;
>> -__set_bit(__RTDS_depleted, >flags);
>> +if ( is_work_conserving(svc) )
>> +{
>> +svc->priority_level++;
>>
>ASSERT(svc->priority_level <= 1);

I'm sorry I didn't see this suggestion in previous email. I don't
think this assert makes sense.

A vcpu that has extratime can have priority_level > 1.
For example, a VCPU (period = 100ms, budget = 10ms) runs alone on a
core. The VCPU may get its budget replenished  for 9 times in a
period. the vcpu's priority_level may be 9.

The priority_level here also indicates how many times the VCPU gets
the extra budget in the current period.

>
>> +svc->cur_budget = svc->budget;
>> +}
>> +else
>> +{
>> +svc->cur_budget = 0;
>> +__set_bit(__RTDS_depleted, >flags);
>> +}
>>  }

Thanks,

Meng

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

___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Meng Xu]

On Wed, Aug 2, 2017 at 1:46 PM, Dario Faggioli
 wrote:
> Hey, Meng!
>
> It's really cool to see progress on this... There was quite a bit of
> interest in scheduling in general at the Summit in Budapest, and one
> important thing for making sure RTDS will be really useful, is for it
> to have a work conserving mode! :-)

Glad to hear that. :-)

>
> On Tue, 2017-08-01 at 14:13 -0400, Meng Xu wrote:
>> Make RTDS scheduler work conserving to utilize the idle resource,
>> without breaking the real-time guarantees.
>
> Just kill the "to utilize the idle resource". We can expect that people
>  that are interested in this commit, also know what 'work conserving'
> means. :-)

Got it. Will do.

>
>> VCPU model:
>> Each real-time VCPU is extended to have a work conserving flag
>> and a priority_level field.
>> When a VCPU's budget is depleted in the current period,
>> if it has work conserving flag set,
>> its priority_level will increase by 1 and its budget will be
>> refilled;
>> othewrise, the VCPU will be moved to the depletedq.
>>
> Mmm... Ok. But is the budget burned, while the vCPU executes at
> priority_level 1? If yes, doesn't this mean we risk having less budget
> when we get back to priority_lvevel 0?
>
> Oh, wait, maybe it's the case that, when we get back to priority_level
> 0, we also get another replenishment, is that the case? If yes, I
> actually think it's fine...

It's the latter case: the vcpu will get another replenishment when it
gets back to priority_level 0.

>
>> diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
>> index 39f6bee..740a712 100644
>> --- a/xen/common/sched_rt.c
>> +++ b/xen/common/sched_rt.c
>> @@ -191,6 +195,7 @@ struct rt_vcpu {
>>  /* VCPU parameters, in nanoseconds */
>>  s_time_t period;
>>  s_time_t budget;
>> +bool_t is_work_conserving;   /* is vcpu work conserving */
>>
>>  /* VCPU current infomation in nanosecond */
>>  s_time_t cur_budget; /* current budget */
>> @@ -201,6 +206,8 @@ struct rt_vcpu {
>>  struct rt_dom *sdom;
>>  struct vcpu *vcpu;
>>
>> +unsigned priority_level;
>> +
>>  unsigned flags;  /* mark __RTDS_scheduled, etc.. */
>>
> So, since we've got a 'flags' field already, can the flag be one of its
> bit, instead of adding a new bool in the struct:
>
> /*
>  * RTDS_work_conserving: Can the vcpu run in the time that is
>  * not part of any real-time reservation, and would therefore
>  * be otherwise left idle?
>  */
> __RTDS_work_conserving   4
> #define RTDS_work_conserving (1<<__RTDS_work_conserving)

Thank you very much for the suggestion! I will modify based on your suggestion.

Actually, I was not very comfortable with the is_work_conserving field either.
It makes the structure verbose and mess up the struct's the cache_line
alignment.

>
>> @@ -245,6 +252,11 @@ static inline struct list_head *rt_replq(const
>> struct scheduler *ops)
>>  return _priv(ops)->replq;
>>  }
>>
>> +static inline bool_t is_work_conserving(const struct rt_vcpu *svc)
>> +{
>>
> Use bool.

OK.

>
>> @@ -273,6 +285,20 @@ vcpu_on_replq(const struct rt_vcpu *svc)
>>  return !list_empty(>replq_elem);
>>  }
>>
>> +/* If v1 priority >= v2 priority, return value > 0
>> + * Otherwise, return value < 0
>> + */
>>
> Comment style.

Got it. Will make it as:
/*
 * If v1 priority >= v2 priority, return value > 0
 * Otherwise, return value < 0
 */

>
> Apart from that, do you want this to return >0 if v1 should have
> priority over v2, and <0 if vice-versa, right? If yes...

Yes.

>
>> +static int
>> +compare_vcpu_priority(const struct rt_vcpu *v1, const struct rt_vcpu
>> *v2)
>> +{
>> +if ( v1->priority_level < v2->priority_level ||
>> + ( v1->priority_level == v2->priority_level &&
>> + v1->cur_deadline <= v2->cur_deadline ) )
>> +return 1;
>> +else
>> +return -1;
>>
>   int prio = v2->priority_level - v1->priority_level;
>
>   if ( prio == 0 )
> return v2->cur_deadline - v1->cur_deadline;
>
>   return prio;
>
> Return type has to become s_time_t, and there's a chance that it'll
> return 0, if they are at the same level, and have the same absolute
> deadline. But I think you can deal with this in the caller.

OK. Will do.

>
>> @@ -966,8 +1001,16 @@ burn_budget(const struct scheduler *ops, struct
>> rt_vcpu *svc, s_time_t now)
>>
>>  if ( svc->cur_budget <= 0 )
>>  {
>> -svc->cur_budget = 0;
>> -__set_bit(__RTDS_depleted, >flags);
>> +if ( is_work_conserving(svc) )
>> +{
>> +svc->priority_level++;
>>
>ASSERT(svc->priority_level <= 1);
>
>> +svc->cur_budget = svc->budget;
>> +}
>> +else
>> +{
>> +svc->cur_budget = 0;
>> +__set_bit(__RTDS_depleted, >flags);
>> +}
>>  }
>>
> The rest looks good to me.

Thank you very much for the review!

I will revise it and combine this patch into the series 

Re: [Xen-devel] [PATCH RFC v1] xen:rtds: towards work conserving RTDS

[Dario Faggioli]

Hey, Meng!

It's really cool to see progress on this... There was quite a bit of
interest in scheduling in general at the Summit in Budapest, and one
important thing for making sure RTDS will be really useful, is for it
to have a work conserving mode! :-)

On Tue, 2017-08-01 at 14:13 -0400, Meng Xu wrote:
> Make RTDS scheduler work conserving to utilize the idle resource,
> without breaking the real-time guarantees.

Just kill the "to utilize the idle resource". We can expect that people
 that are interested in this commit, also know what 'work conserving'
means. :-)

> VCPU model:
> Each real-time VCPU is extended to have a work conserving flag
> and a priority_level field.
> When a VCPU's budget is depleted in the current period,
> if it has work conserving flag set,
> its priority_level will increase by 1 and its budget will be
> refilled;
> othewrise, the VCPU will be moved to the depletedq.
> 
Mmm... Ok. But is the budget burned, while the vCPU executes at
priority_level 1? If yes, doesn't this mean we risk having less budget
when we get back to priority_lvevel 0?

Oh, wait, maybe it's the case that, when we get back to priority_level
0, we also get another replenishment, is that the case? If yes, I
actually think it's fine...

> diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
> index 39f6bee..740a712 100644
> --- a/xen/common/sched_rt.c
> +++ b/xen/common/sched_rt.c
> @@ -191,6 +195,7 @@ struct rt_vcpu {
>  /* VCPU parameters, in nanoseconds */
>  s_time_t period;
>  s_time_t budget;
> +bool_t is_work_conserving;   /* is vcpu work conserving */
>  
>  /* VCPU current infomation in nanosecond */
>  s_time_t cur_budget; /* current budget */
> @@ -201,6 +206,8 @@ struct rt_vcpu {
>  struct rt_dom *sdom;
>  struct vcpu *vcpu;
>  
> +unsigned priority_level;
> +
>  unsigned flags;  /* mark __RTDS_scheduled, etc.. */
>
So, since we've got a 'flags' field already, can the flag be one of its
bit, instead of adding a new bool in the struct:

/*
 * RTDS_work_conserving: Can the vcpu run in the time that is
 * not part of any real-time reservation, and would therefore
 * be otherwise left idle?
 */
__RTDS_work_conserving   4
#define RTDS_work_conserving (1<<__RTDS_work_conserving)

> @@ -245,6 +252,11 @@ static inline struct list_head *rt_replq(const
> struct scheduler *ops)
>  return _priv(ops)->replq;
>  }
>  
> +static inline bool_t is_work_conserving(const struct rt_vcpu *svc)
> +{
>
Use bool.

> @@ -273,6 +285,20 @@ vcpu_on_replq(const struct rt_vcpu *svc)
>  return !list_empty(>replq_elem);
>  }
>  
> +/* If v1 priority >= v2 priority, return value > 0
> + * Otherwise, return value < 0
> + */
>
Comment style.

Apart from that, do you want this to return >0 if v1 should have
priority over v2, and <0 if vice-versa, right? If yes...

> +static int
> +compare_vcpu_priority(const struct rt_vcpu *v1, const struct rt_vcpu
> *v2)
> +{
> +if ( v1->priority_level < v2->priority_level ||
> + ( v1->priority_level == v2->priority_level && 
> + v1->cur_deadline <= v2->cur_deadline ) )
> +return 1;
> +else
> +return -1;
>
  int prio = v2->priority_level - v1->priority_level;

  if ( prio == 0 )
return v2->cur_deadline - v1->cur_deadline;

  return prio;

Return type has to become s_time_t, and there's a chance that it'll
return 0, if they are at the same level, and have the same absolute
deadline. But I think you can deal with this in the caller.

> @@ -966,8 +1001,16 @@ burn_budget(const struct scheduler *ops, struct
> rt_vcpu *svc, s_time_t now)
>  
>  if ( svc->cur_budget <= 0 )
>  {
> -svc->cur_budget = 0;
> -__set_bit(__RTDS_depleted, >flags);
> +if ( is_work_conserving(svc) )
> +{
> +svc->priority_level++;
>
   ASSERT(svc->priority_level <= 1);

> +svc->cur_budget = svc->budget;
> +}
> +else
> +{
> +svc->cur_budget = 0;
> +__set_bit(__RTDS_depleted, >flags);
> +}
>  }
>  
The rest looks good to me.

Regards,
Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)

signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel