[PATCH v2 1/3] sched/deadline: Zero out positive runtime after throttling constrained tasks

[PATCH v2 1/3] sched/deadline: Zero out positive runtime after throttling constrained tasks

[Xunlei Pang]

When a contrained task is throttled by dl_check_constrained_dl(),
it may carry the remaining positive runtime, as a result when
dl_task_timer() fires and calls replenish_dl_entity(), it will
not be replenished correctly due to the positive dl_se->runtime.

This patch assigns its runtime to 0 if positive after throttling.

Fixes: df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline)
Acked-by: Daniel Bristot de Oliveira <bristot@redhat.com>
Signed-off-by: Xunlei Pang <xlpang@redhat.com>
---
 kernel/sched/deadline.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..d3d291e 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -723,6 +723,8 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
 			return;
 		dl_se->dl_throttled = 1;
+		if (dl_se->runtime > 0)
+			dl_se->runtime = 0;
 	}
 }
 
-- 
1.8.3.1

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

[Xunlei Pang]

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

[PATCH v2 3/3] sched/deadline: Add statistics to track runtime underruns

[Xunlei Pang]

Add accounting to track cases that runtime isn't running
out, and export the information in "/proc/<pid>/sched".

Specifically, the patch adds three members "nr_underrun_sched",
"nr_underrun_block", and "nr_underrun_yield" in sched_dl_entity:
 -@nr_underrun_sched hints some scheduling issue.
 -@nr_underrun_block hints some block reason. E.g. long sleep.
 -@nr_underrun_yield hints the yield reason.

This is helpful to spot/debug deadline issues, for example,
I launched three 50% dl tasks on my dual-core machine, plus
several buggy contrained dl tasks that Daniel is trying to
address in "sched/deadline: Use the revised wakeup rule for
suspending constrained dl tasks", then I observed one 50%
deadline task's proc sched output:
$ cat /proc/3389/sched |grep underrun
dl.nr_underrun_sched                :        981
dl.nr_underrun_block                :          0
dl.nr_underrun_yield                :          0

Very large "dl.nr_underrun_sched" hints it's very likely that
there is some underlying scheduling issue.

Note that we don't use CONFIG_SCHED_DEBUG as the accounting
added has little overhead(also happens infrequently).

Suggested-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Xunlei Pang <xlpang@redhat.com>
---
 include/linux/sched.h   | 10 ++++++++++
 kernel/sched/core.c     |  3 +++
 kernel/sched/deadline.c | 12 +++++++++---
 kernel/sched/debug.c    |  3 +++
 4 files changed, 25 insertions(+), 3 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index ba080e5..e17928f 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -455,6 +455,16 @@ struct sched_dl_entity {
 	 * own bandwidth to be enforced, thus we need one timer per task.
 	 */
 	struct hrtimer			dl_timer;
+
+	/*
+	 * Accounting for periods that run less than @dl_runtime:
+	 * @nr_underrun_sched hints some scheduling issue.
+	 * @nr_underrun_block hints some block reason. E.g. long sleep.
+	 * @nr_underrun_yield hints the yield reason.
+	 */
+	u64				nr_underrun_sched;
+	u64				nr_underrun_block;
+	u64				nr_underrun_yield;
 };
 
 union rcu_special {
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index bccd819..6214ada 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -4004,6 +4004,9 @@ static struct task_struct *find_process_by_pid(pid_t pid)
 	dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
 	dl_se->flags = attr->sched_flags;
 	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
+	dl_se->nr_underrun_sched = 0;
+	dl_se->nr_underrun_block = 0;
+	dl_se->nr_underrun_yield = 0;
 
 	/*
 	 * Changing the parameters of a task is 'tricky' and we're not doing
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 5691149..a7ddc03 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -394,8 +394,10 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
 		dl_se->runtime = pi_se->dl_runtime;
 	}
 
-	if (dl_se->dl_yielded && dl_se->runtime > 0)
+	if (dl_se->dl_yielded && dl_se->runtime > 0) {
 		dl_se->runtime = 0;
+		++dl_se->nr_underrun_yield;
+	}
 
 	/*
 	 * We keep moving the deadline away until we get some
@@ -723,8 +725,10 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
 			return;
 		dl_se->dl_throttled = 1;
-		if (dl_se->runtime > 0)
+		if (dl_se->runtime > 0) {
 			dl_se->runtime = 0;
+			++dl_se->nr_underrun_block;
+		}
 	}
 }
 
@@ -733,8 +737,10 @@ 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)
+	if (dmiss && dl_se->runtime > 0) {
 		dl_se->runtime = 0;
+		++dl_se->nr_underrun_sched;
+	}
 
 	return (dl_se->runtime <= 0);
 }
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 38f0193..904b43f 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -957,6 +957,9 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
 	if (p->policy == SCHED_DEADLINE) {
 		P(dl.runtime);
 		P(dl.deadline);
+		P(dl.nr_underrun_sched);
+		P(dl.nr_underrun_block);
+		P(dl.nr_underrun_yield);
 	}
 #undef PN_SCHEDSTAT
 #undef PN
-- 
1.8.3.1

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

[luca abeni]

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)))

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

[Xunlei Pang]

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)))

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

[luca abeni]

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

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

[Xunlei Pang]

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

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

[luca abeni]

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

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

[Xunlei Pang]

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

Re: [PATCH v2 1/3] sched/deadline: Zero out positive runtime after throttling constrained tasks

[Xunlei Pang]

On 05/12/2017 at 11:32 AM, Xunlei Pang wrote:
> When a contrained task is throttled by dl_check_constrained_dl(),
> it may carry the remaining positive runtime, as a result when
> dl_task_timer() fires and calls replenish_dl_entity(), it will
> not be replenished correctly due to the positive dl_se->runtime.
>
> This patch assigns its runtime to 0 if positive after throttling.
>
> Fixes: df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline)
> Acked-by: Daniel Bristot de Oliveira <bristot@redhat.com>
> Signed-off-by: Xunlei Pang <xlpang@redhat.com>

Hi Peter,

According to the previous discussion with Luca, please ignore the last two patches of this series.
Could you please only help review or pick up this one?

Regards,
Xunlei

> ---
>  kernel/sched/deadline.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a2ce590..d3d291e 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -723,6 +723,8 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
>  		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
>  			return;
>  		dl_se->dl_throttled = 1;
> +		if (dl_se->runtime > 0)
> +			dl_se->runtime = 0;
>  	}
>  }
>