sched/deadline: Prevent rt_time growth to infinity
RFC 1/1 sched/deadline: Prevent rt_time growth to infinity
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise rt_time may grow up to infinity in update_curr_dl(), if there are no other available RT tasks on top level bandwidth.
I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.
Please say, if I skipped anything in idea. Maybe better put start_top_rt_bandwidth() into set_curr_task_dl()?
--- kernel/sched/deadline.c | 1 + kernel/sched/rt.c | 16 +++++++++++++++- kernel/sched/sched.h | 1 + 3 files changed, 17 insertions(+), 1 deletion(-)
kernel/sched/deadline.c +1 -0
@@ -720,6 +720,7 @@ void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)inc_dl_deadline (dl_rq, deadline);inc_dl_migration (dl_se, dl_rq); +start_top_rt_bandwidth (rq_of_dl_rq (dl_rq)); } static inline
kernel/sched/rt.c +15 -1
@@ -726,7 +726,7 @@ static inline int balance_runtime(struct rt_rq *rt_rq)static int do_sched_rt_period_timer (struct rt_bandwidth *rt_b,int overrun) { -int i, idle =1 , throttled =0 ; +int i, idle =1 , throttled =0 , has_dl_tasks =0 ;const struct cpumask *span; span =sched_rt_period_mask ();
@@ -781,9 +781,15 @@ static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)if (enqueue)sched_rt_rq_enqueue (rt_rq); + +if (rt_rq == &rq->rt && rq->dl.dl_nr_running) + has_dl_tasks =1 ;raw_spin_unlock (&rq->lock); } +if (has_dl_tasks) +return 0 ; +if (!throttled && (!rt_bandwidth_enabled () || rt_b->rt_runtime ==RUNTIME_INF ))return 1 ;
@@ -1005,6 +1011,10 @@ dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)WARN_ON (!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted); } +void start_top_rt_bandwidth (struct rq *rq) +{ +start_rt_bandwidth (&rq->rt.tg->rt_bandwidth); +}#else /* CONFIG_RT_GROUP_SCHED */ static void
@@ -1016,6 +1026,10 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)static inline void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +void start_top_rt_bandwidth (struct rq *rq) +{ +start_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */ static inline
kernel/sched/sched.h +1 -0
@@ -1294,6 +1294,7 @@ static inline void sched_avg_update(struct rq *rq) { }#endif extern void start_bandwidth_timer (struct hrtimer *period_timer,ktime_t period); +extern void start_top_rt_bandwidth (struct rq *rq);#ifdef CONFIG_SMP #ifdef CONFIG_PREEMPT
Steven Rostedt
reviewerPeter, Juri,
Have you seen this?
-- Steve
Quoted 91 lines · On Thu, 20 Feb 2014 02:16:00 +0400 Kirill Tkhai <[email protected]> wrote:
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?--- kernel/sched/deadline.c | 1 + kernel/sched/rt.c | 16 +++++++++++++++- kernel/sched/sched.h | 1 + 3 files changed, 17 insertions(+), 1 deletion(-)kernel/sched/deadline.c +1
-0@@ -720,6 +720,7 @@ void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)inc_dl_deadline (dl_rq, deadline);inc_dl_migration (dl_se, dl_rq); +start_top_rt_bandwidth (rq_of_dl_rq (dl_rq)); } static inlinekernel/sched/rt.c +15
-1@@ -726,7 +726,7 @@ static inline int balance_runtime(struct rt_rq *rt_rq)static int do_sched_rt_period_timer (struct rt_bandwidth *rt_b,int overrun) { -int i, idle =1 , throttled =0 ; +int i, idle =1 , throttled =0 , has_dl_tasks =0 ;const struct cpumask *span; span =sched_rt_period_mask ();@@ -781,9 +781,15 @@ static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)if (enqueue)sched_rt_rq_enqueue (rt_rq); + +if (rt_rq == &rq->rt && rq->dl.dl_nr_running) + has_dl_tasks =1 ;raw_spin_unlock (&rq->lock); } +if (has_dl_tasks) +return 0 ; +if (!throttled && (!rt_bandwidth_enabled () || rt_b->rt_runtime ==RUNTIME_INF ))return 1 ;@@ -1005,6 +1011,10 @@ dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)WARN_ON (!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted); } +void start_top_rt_bandwidth (struct rq *rq) +{ +start_rt_bandwidth (&rq->rt.tg->rt_bandwidth); +}#else /* CONFIG_RT_GROUP_SCHED */ static void@@ -1016,6 +1026,10 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)static inline void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +void start_top_rt_bandwidth (struct rq *rq) +{ +start_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */ static inlinekernel/sched/sched.h +1
-0@@ -1294,6 +1294,7 @@ static inline void sched_avg_update(struct rq *rq) { }#endif extern void start_bandwidth_timer (struct hrtimer *period_timer,ktime_t period); +extern void start_top_rt_bandwidth (struct rq *rq);#ifdef CONFIG_SMP #ifdef CONFIG_PREEMPT
Peter Zijlstra
maintainerQuoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?
How about we only increment rt_time when there's an RT bandwidth timer active?
---
kernel/sched/rt.c +6 -0
@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_active (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); +return hrtimer_active (&rt_b->rt_period_timer); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours.
kernel/sched/deadline.c +6 -2
@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, sreturn 1 ; } +extern bool sched_rt_bandwidth_active (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq).
@@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rqstruct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* * We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_active (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }
21.02.2014, 14:37, "Peter Zijlstra" <[email protected]>:
Quoted 7 lines · Kirill Tkhai
Quoted 6 lines
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.
Quoted 8 lines
Quoted 5 lines
I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?
This case RT and DL may eat all the time:
-------------- time ------------------>
|RT's working |DL's working|
----------------------------
|rt_runtime | |
----------------------------
| rt_period |
Or at least more, than it's allowed.
It looks like, if we want to limit time of high priority classes execution, we have to set the timer anyway.
kernel/sched/rt.c static inline struct rt_bandwidth *sched
Quoted 4 lines
---
kernel/sched/rt.c +0
-0@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched
[snipped by dumb mail client]
21.02.2014, 15:39, "Kirill Tkhai" <[email protected]>:
Quoted 25 lines
21.02.2014, 14:37, "Peter Zijlstra" <[email protected]>:
Quoted 6 lines · Kirill Tkhai
Quoted 5 lines
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.Quoted 7 lines
Quoted 5 lines
I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?This case RT and DL may eat all the time:
-------------- time ------------------>
|RT's working |DL's working|
----------------------------
|rt_runtime | |
----------------------------
| rt_period |
Quoted 4 lines
Or at least more, than it's allowed.
It looks like, if we want to limit time of high priority classes execution, we have to set the timer anyway.
Oh, above is confusing. Sorry.
I mean one RT task and
----------------- time -------------------------->
|DL's working |RT's working| |DL's working |
--------------------------------------------------
| |rt_runtime | | |
--------------------------------------------------
| | rt_period | |
In this case FAIR receives less ratio, than (rt_period-rt_runtime)/rt_period.
Quoted 11 lines
Quoted 4 lines
---
---a/kernel/sched/rt.c
+++b/kernel/sched/rt.c
@@ -568,6 +568,12 @@ static inline structrt_bandwidth*sched[snipped by dumb mail client]
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 37 lines · On Fri, 21 Feb 2014 16:09:25 +0400 Kirill Tkhai <[email protected]> wrote:
21.02.2014, 15:39, "Kirill Tkhai" <[email protected]>:
Quoted 25 lines
21.02.2014, 14:37, "Peter Zijlstra" <[email protected]>:
Quoted 6 lines · Kirill Tkhai
Quoted 5 lines
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.Quoted 7 lines
Quoted 5 lines
I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?This case RT and DL may eat all the time:
-------------- time ------------------>
|RT's working |DL's working|
----------------------------
|rt_runtime | |
----------------------------
| rt_period |Quoted 4 lines
Or at least more, than it's allowed.
It looks like, if we want to limit time of high priority classes execution, we have to set the timer anyway.
Oh, above is confusing. Sorry.
I mean one RT task and
Quoted 9 lines
----------------- time -------------------------->
|DL's working |RT's working| |DL's working |
--------------------------------------------------
| |rt_runtime | | |
--------------------------------------------------
| |rt_period| |In this case FAIR receives less ratio, than (rt_period-rt_runtime)/rt_period.
DL tasks won't be allowed to run in this situation, as their bw exceedes rt_runtime/rt_period.
Thanks,
- Juri
21.02.2014, 16:44, "Juri Lelli" <[email protected]>:
Quoted 42 lines
Quoted 39 lines · On Fri, 21 Feb 2014 16:09:25 +0400 Kirill Tkhai <[email protected]> wrote:
21.02.2014, 15:39, "Kirill Tkhai" <[email protected]>:
Quoted 23 lines
21.02.2014, 14:37, "Peter Zijlstra" <[email protected]>:
Quoted 6 lines · Kirill Tkhai
Quoted 5 lines
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.Quoted 7 lines
Quoted 5 lines
I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?This case RT and DL may eat all the time:
-------------- time ------------------>
|RT's working |DL's working|
----------------------------
|rt_runtime | |
----------------------------
| rt_period |Quoted 4 lines
Or at least more, than it's allowed.
It looks like, if we want to limit time of high priority classes execution, we have to set the timer anyway.
Oh, above is confusing. Sorry.
I mean one RT task and
----------------- time --------------------------> |DL's working |RT's working| |DL's working |
--------------------------------------------------
| |rt_runtime | | |
--------------------------------------------------
| | rt_period | |
Quoted 4 lines
Quoted 1 line
In this case FAIR receives less ratio, than (rt_period-rt_runtime)/rt_period.
DL tasks won't be allowed to run in this situation, as their bw exceedes rt_runtime/rt_period.
Maybe, I don't uderstand. Where does DL control summary (DL+RT) runtime?
RT does not do this too. But it looks like, RT has to do this.
Kirill
Quoted 49 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
kernel/sched/rt.c +6
-0@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_active (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); +return hrtimer_active (&rt_b->rt_period_timer); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours. kernel/sched/deadline.c +2
-1@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, sreturn 1 ; } +extern bool sched_rt_bandwidth_active (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rqstruct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/*
kernel/sched/deadline.c static void update_curr_dl(struct rq *rq · line 664
Quoted 10 lines
kernel/sched/deadline.c +4
-1* We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_active (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }
So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.dat
Here you have a DL task (4/10) and a while(1) RT task, both running inside a rt_bw of 0.5. RT tasks is activated 500ms after DL. As I filtered in sched_rt_period_timer(), you can search for time instants when the rt_bw is replenished. It is evident that the first time after rt timer is activated back (search for start_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we reset rt_bw budget at this time, start decrementing rt_time for both DL and RT tasks, throttle RT tasks when rt_time > runtime, but, since DL tasks acually executes inside their own server, they don't care about rt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.
My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it to rt_bw at replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.
Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
--- kernel/sched/rt.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)
kernel/sched/rt.c +7 -3
@@ -86,12 +86,12 @@ void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init (&rt_rq->rt_runtime_lock); } -#ifdef CONFIG_RT_GROUP_SCHED static void destroy_rt_bandwidth (struct rt_bandwidth *rt_b) {hrtimer_cancel (&rt_b->rt_period_timer); } +#ifdef CONFIG_RT_GROUP_SCHED #define rt_entity_is_task (rt_se) (!(rt_se)->my_q)static inline struct task_struct *rt_task_of (struct sched_rt_entity *rt_se)
@@ -1017,8 +1017,12 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) start_rt_bandwidth(&def_rt_bandwidth); } -static inline -void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +static void +dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) +{ +if (!rt_rq->rt_nr_running) +destroy_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */
Signature · 1 line
1.7.9.5
Quoted 69 lines · On Fri, 21 Feb 2014 17:36:41 +0100 Juri Lelli <[email protected]> wrote:
Quoted 49 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
kernel/sched/rt.c +6
-0@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_active (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); +return hrtimer_active (&rt_b->rt_period_timer); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours. kernel/sched/deadline.c +2
-1@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, sreturn 1 ; } +extern bool sched_rt_bandwidth_active (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rqstruct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* kernel/sched/deadline.c static void update_curr_dl(struct rq *rq · line 664
Quoted 10 lines
kernel/sched/deadline.c +4
-1* We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_active (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.dat
Quoted 7 lines
Here you have a DL task (4/10) and a while(1) RT task, both running inside a
rt_bwof 0.5. RT tasks is activated 500ms after DL. As I filtered insched_rt_period_timer(), you can search for time instants when thert_bwis replenished. It is evident that the first time after rt timer is activated back (search forstart_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we resetrt_bwbudget at this time, start decrementingrt_timefor both DL
The reset happens when rt_bw replenishment timer fires, after a bit:
sched_rt_period_timer <-- __run_hrtimer
Apologies,
- Juri
Quoted 61 lines
and RT tasks, throttle RT tasks when
rt_time> runtime, but, since DL tasks acually executes inside their own server, they don't care aboutrt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it tort_bwat replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
--- kernel/sched/rt.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)kernel/sched/rt.c +7
-3@@ -86,12 +86,12 @@ void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init (&rt_rq->rt_runtime_lock); } -#ifdef CONFIG_RT_GROUP_SCHED static void destroy_rt_bandwidth (struct rt_bandwidth *rt_b) {hrtimer_cancel (&rt_b->rt_period_timer); } +#ifdef CONFIG_RT_GROUP_SCHED #define rt_entity_is_task (rt_se) (!(rt_se)->my_q)static inline struct task_struct *rt_task_of (struct sched_rt_entity *rt_se)@@ -1017,8 +1017,12 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) start_rt_bandwidth(&def_rt_bandwidth); } -static inline -void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +static void +dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) +{ +if (!rt_rq->rt_nr_running) +destroy_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */
21.02.2014, 20:52, "Juri Lelli" <[email protected]>:
Quoted 76 lines
Quoted 65 lines · On Fri, 21 Feb 2014 17:36:41 +0100 Juri Lelli <[email protected]> wrote:
Quoted 44 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
---a/kernel/sched/rt.c
+++b/kernel/sched/rt.c
@@ -568,6 +568,12 @@ static inline structrt_bandwidth*sched#endif /*
CONFIG_RT_GROUP_SCHED*/+bool
sched_rt_bandwidth_active(struct rt_rq *rt_rq)
+{
+ structrt_bandwidth*rt_b=sched_rt_bandwidth(rt_rq);
+ returnhrtimer_active(&rt_b->rt_period_timer);
+}
+
#ifdefCONFIG_SMP
/*
* We ran out of runtime, see if we can borrow some from our neighbours. ---a/kernel/sched/deadline.c
+++b/kernel/sched/deadline.c
@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, s return 1;
}+extern bool
sched_rt_bandwidth_active(struct rt_rq *rt_rq); +
/*
* Update the current task's runtime statistics (provided it is still
* a -deadline task and has not been removed from thedl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rq structrt_rq*rt_rq=&rq->rt;Quoted 13 lines
raw_spin_lock(&rt_rq->rt_runtime_lock);
-rt_rq->rt_time+=delta_exec;
/*
* We'll let actual RT tasks worry about the overflow here, we
- * have our own CBS to keep us inline -- see above.
+ * have our own CBS to keep us inline; only account when RT
+ * bandwidth is relevant.
*/
+ if (sched_rt_bandwidth_active(rt_rq))
+rt_rq->rt_time+=delta_exec;raw_spin_unlock(&rt_rq->rt_runtime_lock);
}
}So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.datQuoted 7 lines
Here you have a DL task (4/10) and a while(1) RT task, both running inside a
rt_bwof 0.5. RT tasks is activated 500ms after DL. As I filtered insched_rt_period_timer(), you can search for time instants when thert_bwis replenished. It is evident that the first time after rt timer is activated back (search forstart_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we resetrt_bwbudget at this time, start decrementingrt_timefor both DL
Quoted 3 lines
The reset happens when
rt_bwreplenishment timer fires, after a bit:sched_rt_period_timer <--
__run_hrtimer
Juri, sorry, I forgot to wrote I mean the situation when only one task is on_rq at every moment.
DL, RT, DL, RT, ...
rt_runtime = n;rt_period = 2n;
| DL's working, RT's sleeping | RT's working, DL's sleeping | all sleep | ------------------------------------------------------------------------------------------| | (1) duration = n | (2) duration = n | (3) duration = n | (repeat) |------------------------------|------------------------------|---------------------------| | (rt_bw timer is not running) | (rt_bw timer is running) |
According to the patch, rt_bw timer is working only if we have queued RT task.
In the case above part (1) has no queued RT tasks, so timer is not working. rt_time is not being increased too.
We have ratio 2/3.
Thanks,
Kirill
Quoted 65 lines
Apologies,
- Juri
Quoted 60 lines
and RT tasks, throttle RT tasks when
rt_time> runtime, but, since DL tasks acually executes inside their own server, they don't care aboutrt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it tort_bwat replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
---
kernel/sched/rt.c | 10 +++++++---1 file changed, 7 insertions(+), 3 deletions(-)diff --git
a/kernel/sched/rt.cb/kernel/sched/rt.c
index 6161de8..274f992 100644
---a/kernel/sched/rt.c
+++b/kernel/sched/rt.c
@@ -86,12 +86,12 @@ voidinit_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init(&rt_rq->rt_runtime_lock);
}-#ifdef
CONFIG_RT_GROUP_SCHED
static voiddestroy_rt_bandwidth(struct rt_bandwidth *rt_b){
hrtimer_cancel(&rt_b->rt_period_timer);
}+#ifdef
CONFIG_RT_GROUP_SCHED
#definert_entity_is_task(rt_se)(!(rt_se)->my_q)static inline struct
task_struct*rt_task_of(structsched_rt_entity*rt_se) @@ -1017,8 +1017,12 @@inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)start_rt_bandwidth(&def_rt_bandwidth);
}-static inline
-voiddec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq){} +static void
+dec_rt_group(structsched_rt_entity*rt_se, structrt_rq*rt_rq) +{
+ if (!rt_rq->rt_nr_running)
+destroy_rt_bandwidth(&def_rt_bandwidth);
+}#endif /*
CONFIG_RT_GROUP_SCHED*/
Quoted 127 lines · Juri Lelli
Quoted 49 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
kernel/sched/rt.c +6
-0@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_active (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); +return hrtimer_active (&rt_b->rt_period_timer); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours. kernel/sched/deadline.c +2
-1@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, sreturn 1 ; } +extern bool sched_rt_bandwidth_active (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rqstruct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* kernel/sched/deadline.c static void update_curr_dl(struct rq *rq · line 664
Quoted 10 lines
kernel/sched/deadline.c +4
-1* We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_active (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.datHere you have a DL task (4/10) and a while(1) RT task, both running inside a
rt_bwof 0.5. RT tasks is activated 500ms after DL. As I filtered insched_rt_period_timer(), you can search for time instants when thert_bwis replenished. It is evident that the first time after rt timer is activated back (search forstart_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we resetrt_bwbudget at this time, start decrementingrt_timefor both DL and RT tasks, throttle RT tasks whenrt_time> runtime, but, since DL tasks acually executes inside their own server, they don't care aboutrt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it tort_bwat replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
--- kernel/sched/rt.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)kernel/sched/rt.c +1
-2@@ -86,12 +86,12 @@ void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init (&rt_rq->rt_runtime_lock); } -#ifdef CONFIG_RT_GROUP_SCHED static void destroy_rt_bandwidth (struct rt_bandwidth *rt_b) {hrtimer_cancel (&rt_b->rt_period_timer); } +#ifdef CONFIG_RT_GROUP_SCHED #define rt_entity_is_task (rt_se) (!(rt_se)->my_q)static inline struct task_struct *rt_task_of (struct sched_rt_entity *rt_se)@@ -1017,8 +1017,12 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)start_rt_bandwidth (&def_rt_bandwidth); } -static inline
kernel/sched/rt.c inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) · line 1028
Quoted 10 lines
kernel/sched/rt.c +6
-1-void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +static void +dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) +{ +if (!rt_rq->rt_nr_running) +destroy_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */
It looks with both patches applied, we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime = nrt_period = 2n
| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------
| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |
No time for fair tasks at all.
Kirill
Quoted 145 lines · On Sat, 22 Feb 2014 04:56:59 +0400 Kirill Tkhai <[email protected]> wrote:
Quoted 127 lines · Juri Lelli
Quoted 49 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
kernel/sched/rt.c +6
-0@@ -568,6 +568,12 @@ static inline struct rt_bandwidth *sched#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_active (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); +return hrtimer_active (&rt_b->rt_period_timer); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours. kernel/sched/deadline.c +2
-1@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, sreturn 1 ; } +extern bool sched_rt_bandwidth_active (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rqstruct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* kernel/sched/deadline.c static void update_curr_dl(struct rq *rq · line 664
Quoted 10 lines
kernel/sched/deadline.c +4
-1* We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_active (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.datHere you have a DL task (4/10) and a while(1) RT task, both running inside a
rt_bwof 0.5. RT tasks is activated 500ms after DL. As I filtered insched_rt_period_timer(), you can search for time instants when thert_bwis replenished. It is evident that the first time after rt timer is activated back (search forstart_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we resetrt_bwbudget at this time, start decrementingrt_timefor both DL and RT tasks, throttle RT tasks whenrt_time> runtime, but, since DL tasks acually executes inside their own server, they don't care aboutrt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it tort_bwat replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
--- kernel/sched/rt.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)kernel/sched/rt.c +1
-2@@ -86,12 +86,12 @@ void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init (&rt_rq->rt_runtime_lock); } -#ifdef CONFIG_RT_GROUP_SCHED static void destroy_rt_bandwidth (struct rt_bandwidth *rt_b) {hrtimer_cancel (&rt_b->rt_period_timer); } +#ifdef CONFIG_RT_GROUP_SCHED #define rt_entity_is_task (rt_se) (!(rt_se)->my_q)static inline struct task_struct *rt_task_of (struct sched_rt_entity *rt_se)@@ -1017,8 +1017,12 @@ inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)start_rt_bandwidth (&def_rt_bandwidth); } -static inlinekernel/sched/rt.c inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) · line 1028
Quoted 10 lines
kernel/sched/rt.c +6
-1-void dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) {} +static void +dec_rt_group (struct sched_rt_entity *rt_se,struct rt_rq *rt_rq) +{ +if (!rt_rq->rt_nr_running) +destroy_rt_bandwidth (&def_rt_bandwidth); +}#endif /* CONFIG_RT_GROUP_SCHED */ It looks with both patches applied, we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime= nrt_period= 2n
Quoted 7 lines
| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |No time for fair tasks at all.
Ok, this situation is pathological. DL bandwidth is guaranteed at admission control, while RT isn't. In this case RT tasks are doomed by construction. Still you'd like to let FAIR tasks execute :).
I argumented on a slightly different solution in what follows, what you think?
Thanks,
- Juri
Quoted 1 line
From
e44fe2eef34433a7799cfc153f467f7c62813596Mon Sep 17 00:00:00 2001
From: Juri Lelli <[email protected]>
Date: Fri, 21 Feb 2014 11:37:15 +0100
Subject: [PATCH] sched/deadline: Prevent rt_time growth to infinity
Kirill Tkhai noted:
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise rt_time may grow up to infinity in update_curr_dl(), if there are no other available RT tasks on top level bandwidth.
RT task were in fact throttled right after they got enqueued, and never executed again (rt_time never again went below rt_runtime).
Peter than proposed to accrue DL execution on rt_time only when rt timer is active, and proposed a patch (this patch is a slight modification of that) to implement that behavior. While this solves Kirill problem, it has a drawback.
Indeed, Kirill noted again:
It looks we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime = nrt_period = 2n
| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------
| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |
No time for fair tasks at all.
While this can happen during the first period, if rq is always backlogged, RT tasks won't have the opportunity to execute anymore: rt_time reached rt_runtime during (1), suppose after (2) RT is enqueued back, it gets throttled since rt timer didn't fire, replenishment is from now on eaten up by DL tasks that accrue their execution on rt_time (while rt timer is active - we have an RT task waiting for replenishment). FAIR tasks are not touched after this first period. Ok, this is not ideal, and the situation is even worse!
What above (the nice case), practically never happens in reality, where your rt timer is not aligned to tasks periods, tasks are in general not periodic, etc.. Long story short, you always risk to overload your system.
This patch is based on Peter's idea, but exploits an additional fact:
if you don't have RT tasks enqueued, it makes little sense to continue incrementing rt_time once you reached the upper limit (DL tasks have their own mechanism for throttling).
This cures both problems:
- no matter how many DL instances in the past, you'll have an rt_time slightly above rt_runtime when an RT task is enqueued, and from that point on (after the first replenishment), the task will normally execute;
- you can still eat up all bandwidth during the first period, but not anymore after that, remember that DL execution will increment rt_time till the upper limit is reached.
The situation is still not perfect! But, we have a simple solution for now, that limits how much you can jeopardize your system, as we keep working towards the right answer: RT groups scheduled using deadline servers.
--- kernel/sched/deadline.c | 8 ++++++-- kernel/sched/rt.c | 8 ++++++++ 2 files changed, 14 insertions(+), 2 deletions(-)
kernel/sched/deadline.c +6 -2
@@ -564,6 +564,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)return 1 ; } +extern bool sched_rt_bandwidth_account (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq).
@@ -627,11 +629,13 @@ static void update_curr_dl(struct rq *rq)struct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* * We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_account (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }
kernel/sched/rt.c +8 -0
@@ -538,6 +538,14 @@ static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_account (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); + +return (hrtimer_active (&rt_b->rt_period_timer) || + rt_rq->rt_time < rt_b->rt_runtime); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours.
Signature · 1 line
1.7.9.5
25.02.2014, 18:14, "Juri Lelli" <[email protected]>:
Quoted 219 lines
Quoted 139 lines · On Sat, 22 Feb 2014 04:56:59 +0400 Kirill Tkhai <[email protected]> wrote:
Quoted 131 lines · Juri Lelli
Quoted 44 lines · On Fri, 21 Feb 2014 11:37:15 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 10 lines · Kirill Tkhai
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise
rt_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.I'm going to decide the problem the way below. Almost untested
because of I skipped almost all of recent patches which haveto be applied from lkml.Please say, if I skipped anything in idea. Maybe better put
start_top_rt_bandwidth()intoset_curr_task_dl()?How about we only increment
rt_timewhen there's an RT bandwidth timer active?---
---a/kernel/sched/rt.c
+++b/kernel/sched/rt.c
@@ -568,6 +568,12 @@ static inline structrt_bandwidth*sched#endif /*
CONFIG_RT_GROUP_SCHED*/+bool
sched_rt_bandwidth_active(struct rt_rq *rt_rq)
+{
+ structrt_bandwidth*rt_b=sched_rt_bandwidth(rt_rq);
+ returnhrtimer_active(&rt_b->rt_period_timer);
+}
+
#ifdefCONFIG_SMP
/*
* We ran out of runtime, see if we can borrow some from our neighbours. ---a/kernel/sched/deadline.c
+++b/kernel/sched/deadline.c
@@ -587,6 +587,8 @@ int dl_runtime_exceeded(struct rq *rq, s return 1;
}+extern bool
sched_rt_bandwidth_active(struct rt_rq *rt_rq); +
/*
* Update the current task's runtime statistics (provided it is still
* a -deadline task and has not been removed from thedl_rq). @@ -650,11 +652,13 @@ static void update_curr_dl(struct rq *rq structrt_rq*rt_rq=&rq->rt;Quoted 13 lines
raw_spin_lock(&rt_rq->rt_runtime_lock);
-rt_rq->rt_time+=delta_exec;
/*
* We'll let actual RT tasks worry about the overflow here, we
- * have our own CBS to keep us inline -- see above.
+ * have our own CBS to keep us inline; only account when RT
+ * bandwidth is relevant.
*/
+ if (sched_rt_bandwidth_active(rt_rq))
+rt_rq->rt_time+=delta_exec;raw_spin_unlock(&rt_rq->rt_runtime_lock);
}
}So, I ran some tests with the above and I'd like to share with you what I've found. You can find here a trace-cmd trace that should be feeded to kernelshark to be able to understand what follows (or feel free to reproduce same scenario :)):
http://retis.sssup.it/~jlelli/traces/trace_rt_time.datHere you have a DL task (4/10) and a while(1) RT task, both running inside a
rt_bwof 0.5. RT tasks is activated 500ms after DL. As I filtered insched_rt_period_timer(), you can search for time instants when thert_bwis replenished. It is evident that the first time after rt timer is activated back (search forstart_bandwidth_timer), we can eat some bw to FAIR tasks (if any). This is due to the fact that we resetrt_bwbudget at this time, start decrementingrt_timefor both DL and RT tasks, throttle RT tasks whenrt_time> runtime, but, since DL tasks acually executes inside their own server, they don't care aboutrt_bw. Good news is that steady state is ok: keeping track of overruns we are able to stop eating bw to other guys.My thougths:
- Peter's patch is an easy fix to Kirill's problem (RT tasks were throttled too early);
- something to add to this solution could be to pre-calculate bw of ready DL tasks and subtract it tort_bwat replenishment time, but it sounds quite awkward, pessimistic, and I'm not sure it is gonna work;
- we are stealing bw to best-effort tasks, and just at the beginning of the transistion, is it really a problem?
- I mean, if you want guarantees make your tasks DL! :);
- in the long run we are gonna have RT tasks scheduled inside CBS servers, and all this will be properly fixed up.Comments?
BTW, rt timer activation/deactivation should probably be fixed for !RT_GROUP_SCHED with something like this:
---
kernel/sched/rt.c | 10 +++++++---1 file changed, 7 insertions(+), 3 deletions(-)diff --git
a/kernel/sched/rt.cb/kernel/sched/rt.c
index 6161de8..274f992 100644
---a/kernel/sched/rt.c
+++b/kernel/sched/rt.c
@@ -86,12 +86,12 @@ voidinit_rt_rq(struct rt_rq *rt_rq, struct rq *rq)raw_spin_lock_init(&rt_rq->rt_runtime_lock);
}-#ifdef
CONFIG_RT_GROUP_SCHED
static voiddestroy_rt_bandwidth(struct rt_bandwidth *rt_b){
hrtimer_cancel(&rt_b->rt_period_timer);
}+#ifdef
CONFIG_RT_GROUP_SCHED
#definert_entity_is_task(rt_se)(!(rt_se)->my_q)static inline struct
task_struct*rt_task_of(structsched_rt_entity*rt_se) @@ -1017,8 +1017,12 @@inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)start_rt_bandwidth(&def_rt_bandwidth);
}-static inline
-voiddec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq){} +static void
+dec_rt_group(structsched_rt_entity*rt_se, structrt_rq*rt_rq) +{
+ if (!rt_rq->rt_nr_running)
+destroy_rt_bandwidth(&def_rt_bandwidth);
+}Quoted 1 line
#endif /*
CONFIG_RT_GROUP_SCHED*/It looks with both patches applied, we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime = n
rt_period = 2nQuoted 7 lines
| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |No time for fair tasks at all.
Ok, this situation is pathological. DL bandwidth is guaranteed at admission control, while RT isn't. In this case RT tasks are doomed by construction. Still you'd like to let FAIR tasks execute :).
I argumented on a slightly different solution in what follows, what you think?
Thanks,
- Juri
From
e44fe2eef34433a7799cfc153f467f7c62813596Mon Sep 17 00:00:00 2001
From: Juri Lelli <[email protected]>
Date: Fri, 21 Feb 2014 11:37:15 +0100
Subject: [PATCH] sched/deadline: Preventrt_timegrowth to infinityKirill Tkhai noted:
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwisert_timemay grow up to infinity inupdate_curr_dl(), if there are no other available RT tasks on top level bandwidth.RT task were in fact throttled right after they got enqueued, and never executed again (
rt_timenever again went belowrt_runtime).Peter than proposed to accrue DL execution on
rt_timeonly when rt timer is active, and proposed a patch (this patch is a slight modification of that) to implement that behavior. While this solves Kirill problem, it has a drawback.Indeed, Kirill noted again:
It looks we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime= nrt_period= 2n| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |No time for fair tasks at all.
While this can happen during the first period, if rq is always backlogged, RT tasks won't have the opportunity to execute anymore:
rt_timereachedrt_runtimeduring (1), suppose after (2) RT is enqueued back, it gets throttled since rt timer didn't fire, replenishment is from now on eaten up by DL tasks that accrue their execution onrt_time(while rt timer is active - we have an RT task waiting for replenishment). FAIR tasks are not touched after this first period. Ok, this is not ideal, and the situation is even worse!What above (the nice case), practically never happens in reality, where your rt timer is not aligned to tasks periods, tasks are in general not periodic, etc.. Long story short, you always risk to overload your system.
This patch is based on Peter's idea, but exploits an additional fact:
if you don't have RT tasks enqueued, it makes little sense to continue incrementingrt_timeonce you reached the upper limit (DL tasks have their own mechanism for throttling).This cures both problems:
- no matter how many DL instances in the past, you'll have an
rt_timeslightly abovert_runtimewhen an RT task is enqueued, and from that point on (after the first replenishment), the task will normally execute;
Quoted 7 lines
- you can still eat up all bandwidth during the first period, but not anymore after that, remember that DL execution will increment
rt_timetill the upper limit is reached.The situation is still not perfect! But, we have a simple solution for now, that limits how much you can jeopardize your system, as we keep working towards the right answer: RT groups scheduled using deadline servers.
Excellent, Juri! This is almost perfect.
Thanks,
Kirill
Quoted 56 lines
Signed-off-by Juri Lelli <[email protected]>---
kernel/sched/deadline.c | 8 ++++++--
kernel/sched/rt.c | 8 ++++++++2 files changed, 14 insertions(+), 2 deletions(-)kernel/sched/deadline.c +6
-2@@ -564,6 +564,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) return 1; } +extern bool sched_rt_bandwidth_account (struct rt_rq *rt_rq); + /** Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq). @@ -627,11 +629,13 @@ static void update_curr_dl(struct rq *rq) struct rt_rq *rt_rq = &rq->rt; raw_spin_lock(&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec; /** We'll let actual RT tasks worry about the overflow here, we - * have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_account (rt_rq)) + rt_rq->rt_time += delta_exec; raw_spin_unlock(&rt_rq->rt_runtime_lock); } }kernel/sched/rt.c +8
-1@@ -538,6 +538,14 @@ static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq) #endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_account (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); + +return (hrtimer_active (&rt_b->rt_period_timer) || + rt_rq->rt_time < rt_b->rt_runtime); +} + #ifdef CONFIG_SMP /** We ran out of runtime, see if we can borrow some from our neighbours. -- 1.7.9.5
tip-bot for Juri Lelli
merge botsched/deadline: Prevent rt_time growth to infinity
Commit-ID: faa5993736d9b44b508cab4f1f3a77d66641c6f4 Gitweb: http://git.kernel.org/tip/faa5993736d9b44b508cab4f1f3a77d66641c6f4 Author: Juri Lelli <[email protected]> AuthorDate: Fri, 21 Feb 2014 11:37:15 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 27 Feb 2014 12:29:41 +0100
sched/deadline: Prevent rt_time growth to infinity
Kirill Tkhai noted:
Since deadline tasks share rt bandwidth, we must care about bandwidth timer set. Otherwise rt_time may grow up to infinity in update_curr_dl(), if there are no other available RT tasks on top level bandwidth.
RT task were in fact throttled right after they got enqueued, and never executed again (rt_time never again went below rt_runtime).
Peter then proposed to accrue DL execution on rt_time only when rt timer is active, and proposed a patch (this patch is a slight modification of that) to implement that behavior. While this solves Kirill problem, it has a drawback.
Indeed, Kirill noted again:
It looks we may get into a situation, when all CPU time is shared between RT and DL tasks:
rt_runtime = n
rt_period = 2n
| RT working, DL sleeping | DL working, RT sleeping |
-----------------------------------------------------------
| (1) duration = n | (2) duration = n | (repeat) |--------------------------|------------------------------| | (rt_bw timer is running) | (rt_bw timer is not running) |
No time for fair tasks at all.
While this can happen during the first period, if rq is always backlogged, RT tasks won't have the opportunity to execute anymore: rt_time reached rt_runtime during (1), suppose after (2) RT is enqueued back, it gets throttled since rt timer didn't fire, replenishment is from now on eaten up by DL tasks that accrue their execution on rt_time (while rt timer is active - we have an RT task waiting for replenishment). FAIR tasks are not touched after this first period. Ok, this is not ideal, and the situation is even worse!
What above (the nice case), practically never happens in reality, where your rt timer is not aligned to tasks periods, tasks are in general not periodic, etc.. Long story short, you always risk to overload your system.
This patch is based on Peter's idea, but exploits an additional fact:
if you don't have RT tasks enqueued, it makes little sense to continue incrementing rt_time once you reached the upper limit (DL tasks have their own mechanism for throttling).
This cures both problems:
- no matter how many DL instances in the past, you'll have an rt_time slightly above rt_runtime when an RT task is enqueued, and from that point on (after the first replenishment), the task will normally execute;
- you can still eat up all bandwidth during the first period, but not anymore after that, remember that DL execution will increment rt_time till the upper limit is reached.
The situation is still not perfect! But, we have a simple solution for now, that limits how much you can jeopardize your system, as we keep working towards the right answer: RT groups scheduled using deadline servers.
--- kernel/sched/deadline.c | 8 ++++++-- kernel/sched/rt.c | 8 ++++++++ 2 files changed, 14 insertions(+), 2 deletions(-)
kernel/sched/deadline.c +6 -2
@@ -562,6 +562,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)return 1 ; } +extern bool sched_rt_bandwidth_account (struct rt_rq *rt_rq); +/* * Update the current task's runtime statistics (provided it is still * a -deadline task and has not been removed from the dl_rq).
@@ -625,11 +627,13 @@ static void update_curr_dl(struct rq *rq)struct rt_rq *rt_rq = &rq->rt;raw_spin_lock (&rt_rq->rt_runtime_lock); - rt_rq->rt_time += delta_exec;/* * We'll let actual RT tasks worry about the overflow here, we -* have our own CBS to keep us inline -- see above. +* have our own CBS to keep us inline; only account when RT +* bandwidth is relevant. */ +if (sched_rt_bandwidth_account (rt_rq)) + rt_rq->rt_time += delta_exec;raw_spin_unlock (&rt_rq->rt_runtime_lock); } }
kernel/sched/rt.c +8 -0
@@ -538,6 +538,14 @@ static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)#endif /* CONFIG_RT_GROUP_SCHED */ +bool sched_rt_bandwidth_account (struct rt_rq *rt_rq) +{ +struct rt_bandwidth *rt_b =sched_rt_bandwidth (rt_rq); + +return (hrtimer_active (&rt_b->rt_period_timer) || + rt_rq->rt_time < rt_b->rt_runtime); +} +#ifdef CONFIG_SMP /* * We ran out of runtime, see if we can borrow some from our neighbours.