Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1640171 > unrolled thread

[PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline Xunlei Pang <xlpang@redhat.com> - 2017-05-12 05:40 +0200
    Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 08:00 +0200
      Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-12 09:00 +0200
        Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 09:10 +0200
          Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-12 09:20 +0200
            Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 23:00 +0200
              Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-15 05:50 +0200

#1640171 — [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

dl_runtime_exceeded() only checks negative runtime, actually
when the current deadline past, we should start a new period
and zero out the remaining runtime as well.

This patch improves dl_runtime_exceeded() to achieve that.

Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case of missed deadlines")
Cc: Luca Abeni <luca.abeni@unitn.it>
Signed-off-by: Xunlei Pang <xlpang@redhat.com>
---
 kernel/sched/deadline.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index d3d291e..5691149 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -729,8 +729,13 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
+	bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq));
+
+	if (dmiss && dl_se->runtime > 0)
+		dl_se->runtime = 0;
+
 	return (dl_se->runtime <= 0);
 }
 
@@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq)
 	dl_se->runtime -= delta_exec;
 
 throttle:
-	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+	if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
 		dl_se->dl_throttled = 1;
 		__dequeue_task_dl(rq, curr, 0);
 		if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
-- 
1.8.3.1

[toc] | [next] | [standalone]

#1640216 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

Hi again,

(sorry for the previous email; I replied from gmail and I did not
realize I was sending it in html).


On Fri, 12 May 2017 11:32:08 +0800
Xunlei Pang <xlpang@redhat.com> wrote:

> dl_runtime_exceeded() only checks negative runtime, actually
> when the current deadline past, we should start a new period
> and zero out the remaining runtime as well.

In this case, I think global EDF wants to allow the task to run with
its remaining runtime even also missing a deadline, so I think this
change is not correct.
(when using global EDF, tasks scheduled on multiple CPUs can miss their
deadlines... Setting the runtime to 0 as soon as a deadline is missed
would break global EDF scheduling)

Which kind of issue is this patch fixing? If it is something you saw
with deadline-constrained tasks, maybe you can add a check for
deadline!=period?


				Luca
> 
> This patch improves dl_runtime_exceeded() to achieve that.
> 
> Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case
> of missed deadlines") Cc: Luca Abeni <luca.abeni@unitn.it>
> Signed-off-by: Xunlei Pang <xlpang@redhat.com>
> ---
>  kernel/sched/deadline.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index d3d291e..5691149 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -729,8 +729,13 @@ static inline void
> dl_check_constrained_dl(struct sched_dl_entity *dl_se) }
>  
>  static
> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
>  {
> +	bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq));
> +
> +	if (dmiss && dl_se->runtime > 0)
> +		dl_se->runtime = 0;
> +
>  	return (dl_se->runtime <= 0);
>  }
>  
> @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq)
>  	dl_se->runtime -= delta_exec;
>  
>  throttle:
> -	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
> +	if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
>  		dl_se->dl_throttled = 1;
>  		__dequeue_task_dl(rq, curr, 0);
>  		if (unlikely(dl_se->dl_boosted
> || !start_dl_timer(curr)))

[toc] | [prev] | [next] | [standalone]

#1640232 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

On 05/12/2017 at 01:57 PM, luca abeni wrote:
> Hi again,
>
> (sorry for the previous email; I replied from gmail and I did not
> realize I was sending it in html).
>
>
> On Fri, 12 May 2017 11:32:08 +0800
> Xunlei Pang <xlpang@redhat.com> wrote:
>
>> dl_runtime_exceeded() only checks negative runtime, actually
>> when the current deadline past, we should start a new period
>> and zero out the remaining runtime as well.
> In this case, I think global EDF wants to allow the task to run with
> its remaining runtime even also missing a deadline, so I think this
> change is not correct.
> (when using global EDF, tasks scheduled on multiple CPUs can miss their
> deadlines... Setting the runtime to 0 as soon as a deadline is missed
> would break global EDF scheduling)

Hi Luca,

Thanks for the comment, looks like I neglected the theoretical analysis.

Cited from Documentation/scheduler/sched-deadline.txt:
 "As a matter of fact, in this case it is possible to provide an upper bound
 for tardiness (defined as the maximum between 0 and the difference
 between the finishing time of a job and its absolute deadline).
 More precisely, it can be proven that using a global EDF scheduler the
 maximum tardiness of each task is smaller or equal than
    ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_m
 where WCET_max = max{WCET_i} is the maximum WCET, WCET_min=min{WCET_i}
 is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
 utilization[12]."

And
 "As seen, enforcing that the total utilization is smaller than M does not
 guarantee that global EDF schedules the tasks without missing any deadline
 (in other words, global EDF is not an optimal scheduling algorithm). However,
 a total utilization smaller than M is enough to guarantee that non real-time
 tasks are not starved and that the tardiness of real-time tasks has an upper
 bound[12] (as previously noted). Different bounds on the maximum tardiness
 experienced by real-time tasks have been developed in various papers[13,14],
 but the theoretical result that is important for SCHED_DEADLINE is that if
 the total utilization is smaller or equal than M then the response times of
 the tasks are limited."

Do you mean there is some tardiness allowed in theory(global EDF is not an
optimal scheduling algorithm), thus missed deadline is allowed for global EDF?

>
> Which kind of issue is this patch fixing? If it is something you saw
> with deadline-constrained tasks, maybe you can add a check for
> deadline!=period?

No, It's an issue(I thought so back then) during making the last patch.

Regards,
Xunlei

>
> 				Luca
>> This patch improves dl_runtime_exceeded() to achieve that.
>>
>> Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case
>> of missed deadlines") Cc: Luca Abeni <luca.abeni@unitn.it>
>> Signed-off-by: Xunlei Pang <xlpang@redhat.com>
>> ---
>>  kernel/sched/deadline.c | 9 +++++++--
>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>> index d3d291e..5691149 100644
>> --- a/kernel/sched/deadline.c
>> +++ b/kernel/sched/deadline.c
>> @@ -729,8 +729,13 @@ static inline void
>> dl_check_constrained_dl(struct sched_dl_entity *dl_se) }
>>  
>>  static
>> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
>> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
>>  {
>> +	bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq));
>> +
>> +	if (dmiss && dl_se->runtime > 0)
>> +		dl_se->runtime = 0;
>> +
>>  	return (dl_se->runtime <= 0);
>>  }
>>  
>> @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq)
>>  	dl_se->runtime -= delta_exec;
>>  
>>  throttle:
>> -	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
>> +	if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
>>  		dl_se->dl_throttled = 1;
>>  		__dequeue_task_dl(rq, curr, 0);
>>  		if (unlikely(dl_se->dl_boosted
>> || !start_dl_timer(curr)))

[toc] | [prev] | [next] | [standalone]

#1640237 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

Hi,

On Fri, 12 May 2017 14:53:33 +0800
Xunlei Pang <xpang@redhat.com> wrote:

> On 05/12/2017 at 01:57 PM, luca abeni wrote:
> > Hi again,
> >
> > (sorry for the previous email; I replied from gmail and I did not
> > realize I was sending it in html).
> >
> >
> > On Fri, 12 May 2017 11:32:08 +0800
> > Xunlei Pang <xlpang@redhat.com> wrote:
> >  
> >> dl_runtime_exceeded() only checks negative runtime, actually
> >> when the current deadline past, we should start a new period
> >> and zero out the remaining runtime as well.  
> > In this case, I think global EDF wants to allow the task to run with
> > its remaining runtime even also missing a deadline, so I think this
> > change is not correct.
> > (when using global EDF, tasks scheduled on multiple CPUs can miss
> > their deadlines... Setting the runtime to 0 as soon as a deadline
> > is missed would break global EDF scheduling)  
> 
> Hi Luca,
> 
> Thanks for the comment, looks like I neglected the theoretical
> analysis.
> 
> Cited from Documentation/scheduler/sched-deadline.txt:
>  "As a matter of fact, in this case it is possible to provide an
> upper bound for tardiness (defined as the maximum between 0 and the
> difference between the finishing time of a job and its absolute
> deadline). More precisely, it can be proven that using a global EDF
> scheduler the maximum tardiness of each task is smaller or equal than
>     ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_m
>  where WCET_max = max{WCET_i} is the maximum WCET,
> WCET_min=min{WCET_i} is the minimum WCET, and U_max = max{WCET_i/P_i}
> is the maximum utilization[12]."
> 
> And
>  "As seen, enforcing that the total utilization is smaller than M
> does not guarantee that global EDF schedules the tasks without
> missing any deadline (in other words, global EDF is not an optimal
> scheduling algorithm). However, a total utilization smaller than M is
> enough to guarantee that non real-time tasks are not starved and that
> the tardiness of real-time tasks has an upper bound[12] (as
> previously noted). Different bounds on the maximum tardiness
> experienced by real-time tasks have been developed in various
> papers[13,14], but the theoretical result that is important for
> SCHED_DEADLINE is that if the total utilization is smaller or equal
> than M then the response times of the tasks are limited."
> 
> Do you mean there is some tardiness allowed in theory(global EDF is
> not an optimal scheduling algorithm), thus missed deadline is allowed
> for global EDF?

Right.

With the admission test currently used by the kernel (sum of
utilizations <= 1), tasks are guaranteed to have a tardiness smaller
than a theoretical maximum... But this theoretical maximum can be larger
than 0.

If you want to strictly respect all of the deadlines, you need a
stricter admission test (for example, the one based on WCET_max that is
mentioned above).



				Luca

[toc] | [prev] | [next] | [standalone]

#1640246 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

On 05/12/2017 at 03:01 PM, luca abeni wrote:
> Hi,
>
> On Fri, 12 May 2017 14:53:33 +0800
> Xunlei Pang <xpang@redhat.com> wrote:
>
>> On 05/12/2017 at 01:57 PM, luca abeni wrote:
>>> Hi again,
>>>
>>> (sorry for the previous email; I replied from gmail and I did not
>>> realize I was sending it in html).
>>>
>>>
>>> On Fri, 12 May 2017 11:32:08 +0800
>>> Xunlei Pang <xlpang@redhat.com> wrote:
>>>  
>>>> dl_runtime_exceeded() only checks negative runtime, actually
>>>> when the current deadline past, we should start a new period
>>>> and zero out the remaining runtime as well.  
>>> In this case, I think global EDF wants to allow the task to run with
>>> its remaining runtime even also missing a deadline, so I think this
>>> change is not correct.
>>> (when using global EDF, tasks scheduled on multiple CPUs can miss
>>> their deadlines... Setting the runtime to 0 as soon as a deadline
>>> is missed would break global EDF scheduling)  
>> Hi Luca,
>>
>> Thanks for the comment, looks like I neglected the theoretical
>> analysis.
>>
>> Cited from Documentation/scheduler/sched-deadline.txt:
>>  "As a matter of fact, in this case it is possible to provide an
>> upper bound for tardiness (defined as the maximum between 0 and the
>> difference between the finishing time of a job and its absolute
>> deadline). More precisely, it can be proven that using a global EDF
>> scheduler the maximum tardiness of each task is smaller or equal than
>>     ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_m
>>  where WCET_max = max{WCET_i} is the maximum WCET,
>> WCET_min=min{WCET_i} is the minimum WCET, and U_max = max{WCET_i/P_i}
>> is the maximum utilization[12]."
>>
>> And
>>  "As seen, enforcing that the total utilization is smaller than M
>> does not guarantee that global EDF schedules the tasks without
>> missing any deadline (in other words, global EDF is not an optimal
>> scheduling algorithm). However, a total utilization smaller than M is
>> enough to guarantee that non real-time tasks are not starved and that
>> the tardiness of real-time tasks has an upper bound[12] (as
>> previously noted). Different bounds on the maximum tardiness
>> experienced by real-time tasks have been developed in various
>> papers[13,14], but the theoretical result that is important for
>> SCHED_DEADLINE is that if the total utilization is smaller or equal
>> than M then the response times of the tasks are limited."
>>
>> Do you mean there is some tardiness allowed in theory(global EDF is
>> not an optimal scheduling algorithm), thus missed deadline is allowed
>> for global EDF?
> Right.
>
> With the admission test currently used by the kernel (sum of
> utilizations <= 1), tasks are guaranteed to have a tardiness smaller
> than a theoretical maximum... But this theoretical maximum can be larger
> than 0.
>
> If you want to strictly respect all of the deadlines, you need a
> stricter admission test (for example, the one based on WCET_max that is
> mentioned above).

Understood.

I think in Patch 3, it is still worthy to add the accounting in dl_runtime_exceeded(),
to track the dl scheduling tardiness(after all tardiness is not a good thing) like:
    if (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0)
        ++dl_se->nr_underrun_sched;

Maybe changing the name to use "nr_underrun_tardy" is better, large value
does need our attention. What do you think?

Regards,
Xunlei

[toc] | [prev] | [next] | [standalone]

#1640745 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

On Fri, 12 May 2017 15:19:55 +0800
Xunlei Pang <xpang@redhat.com> wrote:
[...]
> >>  "As seen, enforcing that the total utilization is smaller than M
> >> does not guarantee that global EDF schedules the tasks without
> >> missing any deadline (in other words, global EDF is not an optimal
> >> scheduling algorithm). However, a total utilization smaller than M
> >> is enough to guarantee that non real-time tasks are not starved
> >> and that the tardiness of real-time tasks has an upper bound[12]
> >> (as previously noted). Different bounds on the maximum tardiness
> >> experienced by real-time tasks have been developed in various
> >> papers[13,14], but the theoretical result that is important for
> >> SCHED_DEADLINE is that if the total utilization is smaller or equal
> >> than M then the response times of the tasks are limited."
> >>
> >> Do you mean there is some tardiness allowed in theory(global EDF is
> >> not an optimal scheduling algorithm), thus missed deadline is
> >> allowed for global EDF?  
> > Right.
> >
> > With the admission test currently used by the kernel (sum of
> > utilizations <= 1), tasks are guaranteed to have a tardiness smaller
> > than a theoretical maximum... But this theoretical maximum can be
> > larger than 0.
> >
> > If you want to strictly respect all of the deadlines, you need a
> > stricter admission test (for example, the one based on WCET_max
> > that is mentioned above).  
> 
> Understood.
> 
> I think in Patch 3, it is still worthy to add the accounting in
> dl_runtime_exceeded(), to track the dl scheduling tardiness(after all
> tardiness is not a good thing) like: if
> (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0)
> ++dl_se->nr_underrun_sched;
> 
> Maybe changing the name to use "nr_underrun_tardy" is better, large
> value does need our attention. What do you think?

I do not know, I never used statistics like these...

If there are enough people having a good usecase for these statistics,
it might be worth adding them, but I do not know other people's
opinions about this.



				Luca

[toc] | [prev] | [next] | [standalone]

#1641262 — Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

On 05/13/2017 at 04:58 AM, luca abeni wrote:
> On Fri, 12 May 2017 15:19:55 +0800
> Xunlei Pang <xpang@redhat.com> wrote:
> [...]
>>>>  "As seen, enforcing that the total utilization is smaller than M
>>>> does not guarantee that global EDF schedules the tasks without
>>>> missing any deadline (in other words, global EDF is not an optimal
>>>> scheduling algorithm). However, a total utilization smaller than M
>>>> is enough to guarantee that non real-time tasks are not starved
>>>> and that the tardiness of real-time tasks has an upper bound[12]
>>>> (as previously noted). Different bounds on the maximum tardiness
>>>> experienced by real-time tasks have been developed in various
>>>> papers[13,14], but the theoretical result that is important for
>>>> SCHED_DEADLINE is that if the total utilization is smaller or equal
>>>> than M then the response times of the tasks are limited."
>>>>
>>>> Do you mean there is some tardiness allowed in theory(global EDF is
>>>> not an optimal scheduling algorithm), thus missed deadline is
>>>> allowed for global EDF?  
>>> Right.
>>>
>>> With the admission test currently used by the kernel (sum of
>>> utilizations <= 1), tasks are guaranteed to have a tardiness smaller
>>> than a theoretical maximum... But this theoretical maximum can be
>>> larger than 0.
>>>
>>> If you want to strictly respect all of the deadlines, you need a
>>> stricter admission test (for example, the one based on WCET_max
>>> that is mentioned above).  
>> Understood.
>>
>> I think in Patch 3, it is still worthy to add the accounting in
>> dl_runtime_exceeded(), to track the dl scheduling tardiness(after all
>> tardiness is not a good thing) like: if
>> (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0)
>> ++dl_se->nr_underrun_sched;
>>
>> Maybe changing the name to use "nr_underrun_tardy" is better, large
>> value does need our attention. What do you think?
> I do not know, I never used statistics like these...
>
> If there are enough people having a good usecase for these statistics,
> it might be worth adding them, but I do not know other people's
> opinions about this.
>

Hi Luca,

Thanks for the feedback.

I think I can defer the statistics patch after Daniel's "sched/deadline: Use the
revised wakeup rule for suspending constrained dl tasks", since there will
be another underrun case in the fix, let's wait for other's opinions then.

Regards,
Xunlei

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web