sched/deadline: Zero out positive runtime after throttling constrained tasks
PATCH v2 1/3 sched/deadline: Zero out positive runtime after throttling constrained tasks
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.
--- kernel/sched/deadline.c | 2 ++ 1 file changed, 2 insertions(+)
kernel/sched/deadline.c +2 -0
@@ -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 ; } }
Signature · 1 line
1.8.3.1
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.
--- kernel/sched/deadline.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/sched/deadline.c +7 -2
@@ -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)))
Signature · 1 line
1.8.3.1
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).
Quoted 3 lines · On Fri, 12 May 2017 11:32:08 +0800 Xunlei Pang <[email protected]> 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
Quoted 39 lines
This patch improves
dl_runtime_exceeded()to achieve that.Fixes 269ad8015a6b ("sched/deadline: Avoid double-accounting in caseof missed deadlines") Cc: Luca Abeni <[email protected]>
Signed-off-by Xunlei Pang <[email protected]>--- kernel/sched/deadline.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)kernel/sched/deadline.c +7
-2@@ -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
Quoted 12 lines · luca abeni
Hi again,
(sorry for the previous email; I replied from gmail and I did not realize I was sending it in html).
Quoted 3 lines · On Fri, 12 May 2017 11:32:08 +0800 Xunlei Pang <[email protected]> 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.
Quoted 6 lines
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?
Quoted 4 lines
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
Quoted 40 lines
Luca
Quoted 38 lines
This patch improves
dl_runtime_exceeded()to achieve that.Fixes 269ad8015a6b ("sched/deadline: Avoid double-accounting in caseof missed deadlines") Cc: Luca Abeni <[email protected]>
Signed-off-by Xunlei Pang <[email protected]>--- kernel/sched/deadline.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)kernel/sched/deadline.c +7
-2@@ -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
Hi,
Quoted 49 lines · On Fri, 12 May 2017 14:53:33 +0800 Xunlei Pang <[email protected]> wrote:
Quoted 12 lines · luca abeni
Hi again,
(sorry for the previous email; I replied from gmail and I did not realize I was sending it in html).
Quoted 3 lines · On Fri, 12 May 2017 11:32:08 +0800 Xunlei Pang <[email protected]> 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.Quoted 6 lines
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
whereWCET_max= max{WCET_i} is the maximum WCET,
WCET_min=min{WCET_i} is the minimum WCET, andU_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 forSCHED_DEADLINEis that if the total utilization is smaller or equal than M then the response times of the tasks are limited."
Quoted 3 lines
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
Quoted 58 lines · luca abeni
Hi,
Quoted 48 lines · On Fri, 12 May 2017 14:53:33 +0800 Xunlei Pang <[email protected]> wrote:
Quoted 12 lines · luca abeni
Hi again,
(sorry for the previous email; I replied from gmail and I did not realize I was sending it in html).
Quoted 3 lines · On Fri, 12 May 2017 11:32:08 +0800 Xunlei Pang <[email protected]> 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.Quoted 6 lines
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
whereWCET_max= max{WCET_i} is the maximum WCET,
WCET_min=min{WCET_i} is the minimum WCET, andU_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 forSCHED_DEADLINEis that if the total utilization is smaller or equal than M then the response times of the tasks are limited."Quoted 3 lines
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.
Quoted 8 lines
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_maxthat 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
On Fri, 12 May 2017 15:19:55 +0800
Xunlei Pang <[email protected]> wrote:
[...]
Quoted 28 lines
Quoted 17 lines
Quoted 12 lines
"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 forSCHED_DEADLINEis that if the total utilization is smaller or equal than M then the response times of the tasks are limited."Quoted 3 lines
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.
Quoted 8 lines
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_maxthat is mentioned above).Understood.
Quoted 8 lines
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
Quoted 36 lines · luca abeni
On Fri, 12 May 2017 15:19:55 +0800
Xunlei Pang <[email protected]> wrote:
[...]Quoted 33 lines
Quoted 17 lines
Quoted 12 lines
"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 forSCHED_DEADLINEis that if the total utilization is smaller or equal than M then the response times of the tasks are limited."Quoted 3 lines
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.
Quoted 8 lines
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_maxthat 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;
Quoted 8 lines
Quoted 2 lines
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
PATCH v2 3/3 sched/deadline: Add statistics to track runtime underruns
In reply to Xunlei PangAdd 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).
--- 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(-)
include/linux/sched.h +10 -0
@@ -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 {
kernel/sched/core.c +3 -0
@@ -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
kernel/sched/deadline.c +9 -3
@@ -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 ); }
kernel/sched/debug.c +3 -0
@@ -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
Signature · 1 line
1.8.3.1
Quoted 10 lines · Xunlei Pang
When a contrained task is throttled by
dl_check_constrained_dl(), it may carry the remaining positive runtime, as a result whendl_task_timer()fires and callsreplenish_dl_entity(), it will not be replenished correctly due to the positivedl_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)Signed-off-by Xunlei Pang <[email protected]>
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
Quoted 17 lines
--- kernel/sched/deadline.c | 2 ++ 1 file changed, 2 insertions(+)kernel/sched/deadline.c +2
-0@@ -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 ; } }