Capacity awareness for SCHED_DEADLINE
Dietmar Eggemann
reviewercover Capacity awareness for SCHED_DEADLINE
The SCHED_DEADLINE (DL) admission control does not work correctly on heterogeneous (asymmetric CPU capacity) systems such as Arm big.LITTLE or DynamIQ.
Let's fix this by explicitly considering CPU capacity in DL admission control and task migration.
The DL sched class now attempts to avoid missing task deadlines due to smaller CPU (CPU capacity < 1024) not being capable enough to finish a task in time. It does so by trying to place a task so that its CPU capacity scaled deadline is not smaller than its runtime.
Changes RFC [1] -> v1:
Only use static values for CPU bandwidth (sched_dl_entity::dl_runtime, ::dl_deadline) and CPU capacity (arch_scale_cpu_capacity()) to fix DL admission control.
Dynamic values for CPU bandwidth (sched_dl_entity::runtime, ::deadline) and CPU capacity (capacity_of()) are considered to be more related to energy trade-off calculations which could be later introduced using the Energy Model.
Since the design of the DL and RT sched classes are very similar, the implementation follows the overall design of RT capacity awareness (commit 804d402fb6f6 ("sched/rt: Make RT capacity-aware")).
Per-patch changes:
(1) Store CPU capacity sum in the root domain during
build_sched_domains() [patch 1/4]
(2) Adjust to RT capacity awareness design [patch 3/4]
(3) Remove CPU capacity aware placement in switched_to_dl() (dl_migrate callback) [RFC patch 3/6]
Balance callbacks (push, pull) run only in schedule_tail() __schedule(), rt_mutex_setprio() or __sched_setscheduler(). DL throttling leads to a call to __dequeue_task_dl() which is not a full task dequeue. The task is still enqueued and only removed from the rq.
So a queue_balance_callback() call in update_curr_dl()-> __dequeue_task_dl() will not be followed by a balance_callback() call in one of the 4 functions mentioned above.
(4) Remove 'dynamic CPU bandwidth' consideration and only support 'static CPU bandwidth' (ratio between sched_dl_entity::dl_runtime and ::dl_deadline) [RFC patch 4/6]
(5) Remove modification to migration logic which tried to schedule small tasks on LITTLE CPUs [RFC patch 6/6]
[1] https://lore.kernel.org/r/[email protected]
The following rt-app testcase tailored to Arm64 Hikey960:
root@h960:~# cat /sys/devices/system/cpu/cpu*/cpu_capacity 462 462 462 462 1024 1024 1024 1024
shows the expected behavior.
According to the following condition in dl_task_fits_capacity()
cap_scale(dl_deadline, arch_scale_cpu_capacity(cpu)) >= dl_runtime
thread0-[0-3] are placed on a big CPUs whereas thread1-[0-3] run on a LITTLE CPU respectively.
...
"tasks" : {
"thread0" : {
"policy" : "SCHED_DEADLINE",
"instance" : 4,
"timer" : { "ref" : "unique0", "period" : 16000, "mode" : "absolute" }, "run" : 10000,
"dl-runtime" : 11000,
"dl-period" : 16000,
"dl-deadline" : 16000
},
"thread1" : {
"policy" : "SCHED_DEADLINE",
"instance" : 4,
"delay" : 1000,
"timer" : { "ref" : "unique1", "period" : 16000, "mode" : "absolute" }, "run" : 5500,
"dl-runtime" : 6500
"dl-period" : 16000,
"dl-deadline" : 16000
}
...
Tests were run with Performance CPUfreq governor so that the Schedutil CPUfreq governor DL threads (sugov:[0,4]), necessary on a slow-switching platform like Hikey960, do not interfere with the rt-app test tasks. Using Schedutil would require to lower the number of tasks to 3 instances each.
Dietmar Eggemann (1):
sched/topology: Store root domain CPU capacity sum
Luca Abeni (3):
sched/deadline: Improve admission control for asymmetric CPU
capacities
sched/deadline: Make DL capacity-aware sched/deadline: Implement fallback mechanism for !fit case
kernel/sched/cpudeadline.c | 23 +++++++++++++++++++++ kernel/sched/deadline.c | 41 +++++++++++++++++++++++--------------- kernel/sched/sched.h | 33 ++++++++++++++++++++++++++++-- kernel/sched/topology.c | 14 +++++++++---- 4 files changed, 89 insertions(+), 22 deletions(-)
Signature · 1 line
2.17.1
Dietmar Eggemann
reviewerPATCH 1/4 sched/topology: Store root domain CPU capacity sum
Add the sum of (original) CPU capacity of all member CPUs to the root domain.
This is needed for capacity-aware SCHED_DEADLINE admission control.
--- kernel/sched/sched.h | 11 +++++++++++ kernel/sched/topology.c | 14 ++++++++++---- 2 files changed, 21 insertions(+), 4 deletions(-)
kernel/sched/sched.h +11 -0
@@ -797,6 +797,7 @@ struct root_domain {cpumask_var_t rto_mask;struct cpupri cpupri; +unsigned long sum_cpu_capacity;unsigned long max_cpu_capacity;/*
@@ -2393,6 +2394,16 @@ static inline unsigned long capacity_orig_of(int cpu) {return cpu_rq (cpu)->cpu_capacity_orig; } + +static inline unsigned long rd_capacity (int cpu) +{ +return cpu_rq (cpu)->rd->sum_cpu_capacity; +} +#else +static inline unsigned long rd_capacity (int cpu) +{ +return SCHED_CAPACITY_SCALE ; +}#endif /**
kernel/sched/topology.c +10 -4
@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i); + rq =cpu_rq (i); sd = *per_cpu_ptr (d.sd, i);/* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */ -if (rq->cpu_capacity_orig >READ_ONCE (d.rd->max_cpu_capacity)) -WRITE_ONCE (d.rd->max_cpu_capacity, rq->cpu_capacity_orig); +if (cap >READ_ONCE (d.rd->max_cpu_capacity)) +WRITE_ONCE (d.rd->max_cpu_capacity, cap); + +WRITE_ONCE (d.rd->sum_cpu_capacity, +READ_ONCE (d.rd->sum_cpu_capacity) + cap);cpu_attach_domain (sd, d.rd, i); }
@@ -2067,8 +2072,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attstatic_branch_inc_cpuslocked (&sched_asym_cpucapacity);if (rq && sched_debug_enabled) { -pr_info ("root domain span: %*pbl (max cpu_capacity = %lu)\n" , -cpumask_pr_args (cpu_map), rq->rd->max_cpu_capacity); +pr_info ("root domain span: %*pbl (capacity = %lu max cpu_capacity = %lu)\n" , +cpumask_pr_args (cpu_map), rq->rd->sum_cpu_capacity, + rq->rd->max_cpu_capacity); } ret =0 ;
Signature · 1 line
2.17.1
Vincent Guittot
maintainerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 46 lines · Dietmar Eggemann
Add the sum of (original) CPU capacity of all member CPUs to the root domain.
This is needed for capacity-aware
SCHED_DEADLINEadmission control.Signed-off-by Dietmar Eggemann <[email protected]>--- kernel/sched/sched.h | 11 +++++++++++ kernel/sched/topology.c | 14 ++++++++++---- 2 files changed, 21 insertions(+), 4 deletions(-)kernel/sched/sched.h +11
-0@@ -797,6 +797,7 @@ struct root_domain {cpumask_var_t rto_mask;struct cpupri cpupri; +unsigned long sum_cpu_capacity;unsigned long max_cpu_capacity;/* @@ -2393,6 +2394,16 @@ static inline unsigned long capacity_orig_of(int cpu) {return cpu_rq (cpu)->cpu_capacity_orig; } + +static inline unsigned long rd_capacity (int cpu) +{ +return cpu_rq (cpu)->rd->sum_cpu_capacity; +} +#else +static inline unsigned long rd_capacity (int cpu) +{ +return SCHED_CAPACITY_SCALE ; +}#endif /** kernel/sched/topology.c +0
-0
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2055
Quoted 4 lines
kernel/sched/topology.c +1
-0@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i);
Why do you replace the use of rq->cpu_capacity_orig by arch_scale_cpu_capacity(i) ?
There is nothing about this change in the commit message
Quoted 30 lines
kernel/sched/topology.c +9
-5+ rq =cpu_rq (i); sd = *per_cpu_ptr (d.sd, i);/* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */ -if (rq->cpu_capacity_orig >READ_ONCE (d.rd->max_cpu_capacity)) -WRITE_ONCE (d.rd->max_cpu_capacity, rq->cpu_capacity_orig); +if (cap >READ_ONCE (d.rd->max_cpu_capacity)) +WRITE_ONCE (d.rd->max_cpu_capacity, cap); + +WRITE_ONCE (d.rd->sum_cpu_capacity, +READ_ONCE (d.rd->sum_cpu_capacity) + cap);cpu_attach_domain (sd, d.rd, i); }@@ -2067,8 +2072,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attstatic_branch_inc_cpuslocked (&sched_asym_cpucapacity);if (rq && sched_debug_enabled) { -pr_info ("root domain span: %*pbl (max cpu_capacity = %lu)\n" , -cpumask_pr_args (cpu_map), rq->rd->max_cpu_capacity); +pr_info ("root domain span: %*pbl (capacity = %lu max cpu_capacity = %lu)\n" , +cpumask_pr_args (cpu_map), rq->rd->sum_cpu_capacity, + rq->rd->max_cpu_capacity); } ret =0 ; --2.17.1
Dietmar Eggemann
reviewerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 1 line · Vincent Guittot
On Wed, 8 Apr 2020 at 11:50, Dietmar Eggemann <[email protected]> wrote:
[...]
Quoted 6 lines
Quoted 6 lines
/**
kernel/sched/topology.c +0
-0@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
Quoted 8 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2055
Quoted 4 lines
kernel/sched/topology.c +1
-0/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i);Why do you replace the use of
rq->cpu_capacity_origbyarch_scale_cpu_capacity(i)?
There is nothing about this change in the commit message
True. And I can change this back.
It seems though that the solution is not sufficient because of the 'rd->span &nsub cpu_active_mask' issue discussed under patch 2/4.
But this remind me of another question I have.
Currently we use arch_scale_cpu_capacity() more often (16 times) than capacity_orig_of()/rq->cpu_capacity_orig .
What's hindering us to remove rq->cpu_capacity_orig and the code around it and solely rely on arch_scale_cpu_capacity()? I mean the arch implementation should be fast.
Vincent Guittot
maintainerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 26 lines · Dietmar Eggemann
Quoted 1 line · Vincent Guittot
On Wed, 8 Apr 2020 at 11:50, Dietmar Eggemann <[email protected]> wrote:
[...]
Quoted 6 lines
Quoted 6 lines
/**
kernel/sched/topology.c +0
-0@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attQuoted 8 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2055
Quoted 4 lines
kernel/sched/topology.c +1
-0/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i);Why do you replace the use of
rq->cpu_capacity_origbyarch_scale_cpu_capacity(i)?
There is nothing about this change in the commit messageTrue. And I can change this back.
It seems though that the solution is not sufficient because of the '
rd->span&nsubcpu_active_mask' issue discussed under patch 2/4.
Quoted 8 lines
But this remind me of another question I have.
Currently we use
arch_scale_cpu_capacity()more often (16 times) than capacity_orig_of()/rq->cpu_capacity_orig .What's hindering us to remove
rq->cpu_capacity_origand the code around it and solely rely onarch_scale_cpu_capacity()? I mean the arch implementation should be fast.
Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Is there a case where the max cpu capacity changes over time ? So I would prefer to use cpu_capacity_orig which is a field of scheduler instead of always calling an external arch specific function
Dietmar Eggemann
reviewerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 36 lines · Vincent Guittot
Quoted 28 lines · Dietmar Eggemann
Quoted 1 line · Vincent Guittot
On Wed, 8 Apr 2020 at 11:50, Dietmar Eggemann <[email protected]> wrote:
[...]
Quoted 6 lines
Quoted 6 lines
/**
kernel/sched/topology.c +0
-0@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attQuoted 8 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2055
Quoted 4 lines
kernel/sched/topology.c +1
-0/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i);Why do you replace the use of
rq->cpu_capacity_origbyarch_scale_cpu_capacity(i)?
There is nothing about this change in the commit messageTrue. And I can change this back.
It seems though that the solution is not sufficient because of the '
rd->span&nsubcpu_active_mask' issue discussed under patch 2/4. ap
But this remind me of another question I have.Quoted 6 lines
Currently we use
arch_scale_cpu_capacity()more often (16 times) than capacity_orig_of()/rq->cpu_capacity_orig .What's hindering us to remove
rq->cpu_capacity_origand the code around it and solely rely onarch_scale_cpu_capacity()? I mean the arch implementation should be fast.
Quoted 5 lines
Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Is there a case where the max cpu capacity changes over time ? So I would prefer to use
cpu_capacity_origwhich is a field of scheduler instead of always calling an external arch specific function
I see. So far it only changes during startup.
And it looks like that asym_cpu_capacity_level() [topology.c] would fail if we would use capacity_orig_of() instead of arch_scale_cpu_capacity().
post_init_entity_util_avg() [fair.c] and sugov_get_util() [cpufreq_schedutil.c] would be temporarily off until update_cpu_capacity() has updated cpu_rq(cpu)->cpu_capacity_orig.
compute_energy() [fair.c] is guarded by sched_energy_enabled() from being used at startup.
scale_rt_capacity() could be changed in case we call it after the cpu_rq(cpu)->cpu_capacity_orig = arch_scale_cpu_capacity(cpu) in update_cpu_capacity().
The Energy Model (and CPUfreq cooling) code would need capacity_orig_of() exported. arch_scale_cpu_capacity() currently is exported via include/linux/sched/topology.h.
I guess Pelt and 'scale invariant Deadline bandwidth enforcement' should continue using arch_scale_cpu_capacity() in sync with arch_scale_freq_capacity().
IMHO it's hard to give clear advice when to use the one or the other.
We probably don't want to set cpu_rq(cpu)->cpu_capacity_orig in the arch cpu scale setter. We have arch_scale_cpu_capacity() to decouple that.
Vincent Guittot
maintainerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 40 lines · Dietmar Eggemann
Quoted 38 lines · Vincent Guittot
Quoted 28 lines · Dietmar Eggemann
Quoted 1 line · Vincent Guittot
On Wed, 8 Apr 2020 at 11:50, Dietmar Eggemann <[email protected]> wrote:
[...]
Quoted 6 lines
Quoted 6 lines
/**
kernel/sched/topology.c +0
-0@@ -2052,12 +2052,17 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attQuoted 8 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2055
Quoted 4 lines
kernel/sched/topology.c +1
-0/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap =arch_scale_cpu_capacity (i);Why do you replace the use of
rq->cpu_capacity_origbyarch_scale_cpu_capacity(i)?
There is nothing about this change in the commit messageTrue. And I can change this back.
It seems though that the solution is not sufficient because of the '
rd->span&nsubcpu_active_mask' issue discussed under patch 2/4. ap
But this remind me of another question I have.Quoted 6 lines
Currently we use
arch_scale_cpu_capacity()more often (16 times) than capacity_orig_of()/rq->cpu_capacity_orig .What's hindering us to remove
rq->cpu_capacity_origand the code around it and solely rely onarch_scale_cpu_capacity()? I mean the arch implementation should be fast.Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Quoted 8 lines
Quoted 3 lines
Is there a case where the max cpu capacity changes over time ? So I would prefer to use
cpu_capacity_origwhich is a field of scheduler instead of always calling an external arch specific functionI see. So far it only changes during startup.
And it looks like that
asym_cpu_capacity_level()[topology.c] would fail if we would usecapacity_orig_of()instead ofarch_scale_cpu_capacity().
Yes I agree. See below
Quoted 4 lines
post_init_entity_util_avg()[fair.c] andsugov_get_util()[cpufreq_schedutil.c] would be temporarily off untilupdate_cpu_capacity()has updated cpu_rq(cpu)->cpu_capacity_orig.
I think that we could even get rid of this update in update_cpu_capacity(). cpu_capacity_orig should be set while building the sched_domain topology because the topology itself is built based on this max cpu capacity with asym_cpu_capacity_level(). So changing the capacity without rebuilding the domain could break the sched_domain topology correctness.
And we can't really set cpu_capacity_orig earlier during the boot because the capacity of b.L is set late during the boot and a rebuild of the sched_domain topology is then triggered.
Quoted 7 lines
compute_energy()[fair.c] is guarded bysched_energy_enabled()from being used at startup.
scale_rt_capacity()could be changed in case we call it after the cpu_rq(cpu)->cpu_capacity_orig =arch_scale_cpu_capacity(cpu)inupdate_cpu_capacity().
With the removal of the update in update_cpu_capacity(), we don't have a problem anymore, isn't it ?
Quoted 4 lines
The Energy Model (and CPUfreq cooling) code would need
capacity_orig_of()exported.arch_scale_cpu_capacity()currently is exported viainclude/linux/sched/topology.h.
Not sure that we need to export it outside scheduler, they can still use arch_scale_cpu_capacity()
Quoted 4 lines
I guess Pelt and 'scale invariant Deadline bandwidth enforcement' should continue using
arch_scale_cpu_capacity()in sync witharch_scale_freq_capacity().
Why can't they use capacity_orig_of ?
we keep using arch_scale_freq_capacity() because it's dynamic but we don't really need to keep using arch_scale_cpu_capacity()
Quoted 5 lines
IMHO it's hard to give clear advice when to use the one or the other.
We probably don't want to set cpu_rq(cpu)->cpu_capacity_orig in the arch cpu scale setter. We have
arch_scale_cpu_capacity()to decouple that.
Yes I agree
Dietmar Eggemann
reviewerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 7 lines · Vincent Guittot
Quoted 6 lines · Dietmar Eggemann
Quoted 4 lines · Vincent Guittot
Quoted 3 lines · Dietmar Eggemann
Quoted 1 line · Vincent Guittot
On Wed, 8 Apr 2020 at 11:50, Dietmar Eggemann <[email protected]> wrote:
[...]
Quoted 9 lines
Quoted 2 lines
And it looks like that
asym_cpu_capacity_level()[topology.c] would fail if we would usecapacity_orig_of()instead ofarch_scale_cpu_capacity().Yes I agree. See below
Quoted 3 lines
post_init_entity_util_avg()[fair.c] andsugov_get_util()[cpufreq_schedutil.c] would be temporarily off untilupdate_cpu_capacity()has updated cpu_rq(cpu)->cpu_capacity_orig.
Quoted 6 lines
I think that we could even get rid of this update in
update_cpu_capacity().cpu_capacity_origshould be set while building thesched_domaintopology because the topology itself is built based on this max cpu capacity withasym_cpu_capacity_level(). So changing the capacity without rebuilding the domain could break thesched_domaintopology correctness.
True. rq->cpu_capacity_orig could be set early in build_sched_domains(), before the call to asym_cpu_capacity_level() or within this function.
Quoted 8 lines
And we can't really set
cpu_capacity_origearlier during the boot because the capacity of b.L is set late during the boot and a rebuild of thesched_domaintopology is then triggered.Quoted 4 lines
compute_energy()[fair.c] is guarded bysched_energy_enabled()from being used at startup.
Quoted 6 lines
Quoted 3 lines
scale_rt_capacity()could be changed in case we call it after the cpu_rq(cpu)->cpu_capacity_orig =arch_scale_cpu_capacity(cpu)inupdate_cpu_capacity().With the removal of the update in
update_cpu_capacity(), we don't have a problem anymore, isn't it ?
True.
Quoted 6 lines
Quoted 3 lines
The Energy Model (and CPUfreq cooling) code would need
capacity_orig_of()exported.arch_scale_cpu_capacity()currently is exported viainclude/linux/sched/topology.h.Not sure that we need to export it outside scheduler, they can still use
arch_scale_cpu_capacity()
OK, let's change this for the task scheduler only.
Quoted 7 lines
Quoted 3 lines
I guess Pelt and 'scale invariant Deadline bandwidth enforcement' should continue using
arch_scale_cpu_capacity()in sync witharch_scale_freq_capacity().Why can't they use
capacity_orig_of?
we keep usingarch_scale_freq_capacity()because it's dynamic but we don't really need to keep usingarch_scale_cpu_capacity()
OK, Pelt is task scheduler so it can be changed here as well.
I'm going to create a patch following these ideas.
[...]
Re: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
In reply to Vincent GuittotQuoted 5 lines · Vincent Guittot
Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Is there a case where the max cpu capacity changes over time ? So I would prefer to use
cpu_capacity_origwhich is a field of scheduler instead of always calling an external arch specific function
Note however that using arch_scale_cpu_capacity() would be more efficient, especially on non-arm/arm64 systems where it is a compile-time constant.
It's probably a matter of personal taste, but I find rq->cpu_capacity_orig superfluous. It wastes space without actually giving you anything no? Anybody remembers why it was introduced in the first place?
Thanks,
Quentin
Dietmar Eggemann
reviewerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 10 lines · Quentin Perret
Quoted 5 lines · Vincent Guittot
Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Is there a case where the max cpu capacity changes over time ? So I would prefer to use
cpu_capacity_origwhich is a field of scheduler instead of always calling an external arch specific functionNote however that using
arch_scale_cpu_capacity()would be more efficient, especially on non-arm/arm64 systems where it is a compile-time constant.
or essentially all ARCHs not defining it.
Quoted 4 lines
It's probably a matter of personal taste, but I find
rq->cpu_capacity_origsuperfluous. It wastes space without actually giving you anything no? Anybody remembers why it was introduced in the first place?
v3.18 arm providing arch_scale_cpu_capacity()
v4.1 introduction of rq->cpu_capacity_orig
v4.10 arm64 providing arch_scale_cpu_capacity()
...
So it's down to the question of 'minimizing the scheduler calls to an external arch function' vs 'efficiency'.
Vincent Guittot
maintainerRe: [PATCH 1/4] sched/topology: Store root domain CPU capacity sum
Quoted 20 lines · Dietmar Eggemann
Quoted 10 lines · Quentin Perret
Quoted 5 lines · Vincent Guittot
Or we can do the opposite and only use capacity_orig_of()/rq->cpu_capacity_orig.
Is there a case where the max cpu capacity changes over time ? So I would prefer to use
cpu_capacity_origwhich is a field of scheduler instead of always calling an external arch specific functionNote however that using
arch_scale_cpu_capacity()would be more efficient, especially on non-arm/arm64 systems where it is a compile-time constant.or essentially all ARCHs not defining it.
Quoted 4 lines
It's probably a matter of personal taste, but I find
rq->cpu_capacity_origsuperfluous. It wastes space without actually giving you anything no? Anybody remembers why it was introduced in the first place?
Quoted 7 lines
v3.18 arm providing
arch_scale_cpu_capacity()
v4.1 introduction ofrq->cpu_capacity_orig
v4.10 arm64 providingarch_scale_cpu_capacity()
...So it's down to the question of 'minimizing the scheduler calls to an external arch function' vs 'efficiency'.
Using cpu_capacity_orig will provide more consistency because it will be set while setting the sched_domain topology
Dietmar Eggemann
reviewerPATCH 2/4 sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
The current SCHED_DEADLINE (DL) admission control ensures that
sum of reserved CPU bandwidth < x * M
where
x = /proc/sys/kernel/sched_rt_{runtime,period}_us M = # CPUs in root domain.
DL admission control works well for homogeneous systems where the capacity of all CPUs are equal (1024). I.e. bounded tardiness for DL and non-starvation of non-DL tasks is guaranteed.
But on heterogeneous systems where capacity of CPUs are different it could fail by over-allocating CPU time on smaller capacity CPUs.
On an Arm big.LITTLE/DynamIQ system DL tasks can easily starve other tasks making it unusable.
Fix this by explicitly considering the CPU capacity in the DL admission test by replacing M with the root domain CPU capacity sum.
--- kernel/sched/deadline.c | 23 +++++++++++------------ kernel/sched/sched.h | 7 +++++-- 2 files changed, 16 insertions(+), 14 deletions(-)
kernel/sched/deadline.c +11 -12
@@ -2551,11 +2551,11 @@ void sched_dl_do_global(void)int sched_dl_overflow (struct task_struct *p,int policy,const struct sched_attr *attr) { -struct dl_bw *dl_b =dl_bw_of (task_cpu (p));u64 period = attr->sched_period ?: attr->sched_deadline;u64 runtime = attr->sched_runtime;u64 new_bw =dl_policy (policy) ?to_ratio (period, runtime) :0 ; -int cpus, err =-1 ; +int cpus, err =-1 , cpu =task_cpu (p); +struct dl_bw *dl_b =dl_bw_of (cpu);if (attr->sched_flags &SCHED_FLAG_SUGOV )return 0 ;
@@ -2570,15 +2570,15 @@ int sched_dl_overflow(struct task_struct *p, int policy,* allocated bandwidth of the container. */ raw_spin_lock (&dl_b->lock); - cpus =dl_bw_cpus (task_cpu (p)); + cpus =dl_bw_cpus (cpu);if (dl_policy (policy) && !task_has_dl_policy (p) && - !__dl_overflow (dl_b, cpus,0 , new_bw)) { + !__dl_overflow (dl_b, cpu,0 , new_bw)) {if (hrtimer_active (&p->dl.inactive_timer))__dl_sub (dl_b, p->dl.dl_bw, cpus);__dl_add (dl_b, new_bw, cpus); err =0 ; }else if (dl_policy (policy) &&task_has_dl_policy (p) && - !__dl_overflow (dl_b, cpus, p->dl.dl_bw, new_bw)) { + !__dl_overflow (dl_b, cpu, p->dl.dl_bw, new_bw)) {/* * XXX this is slightly incorrect: when the task * utilization decreases, we should delay the total
@@ -2715,18 +2715,17 @@ bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)int dl_task_can_attach (struct task_struct *p,const struct cpumask *cs_cpus_allowed) {unsigned int dest_cpu; +unsigned long flags;struct dl_bw *dl_b;bool overflow; -int cpus, ret; -unsigned long flags; +int ret; dest_cpu =cpumask_any_and (cpu_active_mask, cs_cpus_allowed);rcu_read_lock_sched (); dl_b =dl_bw_of (dest_cpu);raw_spin_lock_irqsave (&dl_b->lock, flags); - cpus =dl_bw_cpus (dest_cpu); - overflow =__dl_overflow (dl_b, cpus,0 , p->dl.dl_bw); + overflow =__dl_overflow (dl_b, dest_cpu,0 , p->dl.dl_bw);if (overflow) { ret = -EBUSY ; }else {
@@ -2736,6 +2735,8 @@ int dl_task_can_attach(struct task_struct *p, const struct cpumask *cs_cpus_allo* We will free resources in the source root_domain * later on (see set_cpus_allowed_dl()). */ +int cpus =dl_bw_cpus (dest_cpu); +__dl_add (dl_b, p->dl.dl_bw, cpus); ret =0 ; }
@@ -2771,13 +2772,11 @@ bool dl_cpu_busy(unsigned int cpu)unsigned long flags;struct dl_bw *dl_b;bool overflow; -int cpus;rcu_read_lock_sched (); dl_b =dl_bw_of (cpu);raw_spin_lock_irqsave (&dl_b->lock, flags); - cpus =dl_bw_cpus (cpu); - overflow =__dl_overflow (dl_b, cpus,0 ,0 ); + overflow =__dl_overflow (dl_b, cpu,0 ,0 );raw_spin_unlock_irqrestore (&dl_b->lock, flags);rcu_read_unlock_sched ();
kernel/sched/sched.h +5 -2
@@ -304,11 +304,14 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)__dl_update (dl_b, -((s32 )tsk_bw / cpus)); } +static inline unsigned long rd_capacity (int cpu); +static inline -bool __dl_overflow (struct dl_bw *dl_b,int cpus,u64 old_bw,u64 new_bw) +bool __dl_overflow (struct dl_bw *dl_b,int cpu,u64 old_bw,u64 new_bw) {return dl_b->bw !=-1 && - dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw,rd_capacity (cpu)) < + dl_b->total_bw - old_bw + new_bw; }extern void init_dl_bw (struct dl_bw *dl_b);
Signature · 1 line
2.17.1
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 7 lines · Dietmar Eggemann
+++
b/kernel/sched/sched.hkernel/sched/sched.h +2
-0@@ -304,11 +304,14 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)__dl_update (dl_b, -((s32 )tsk_bw / cpus)); } +static inline unsigned long rd_capacity (int cpu); +
kernel/sched/sched.h void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) · line 316
Quoted 10 lines
kernel/sched/sched.h +3
-2static inline -bool __dl_overflow (struct dl_bw *dl_b,int cpus,u64 old_bw,u64 new_bw) +bool __dl_overflow (struct dl_bw *dl_b,int cpu,u64 old_bw,u64 new_bw) {return dl_b->bw !=-1 && - dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw,rd_capacity (cpu)) < + dl_b->total_bw - old_bw + new_bw; }
I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from dl_bw_cpus(), which is an ugly way of writing
cpumask_weight(rd->span AND cpu_active_mask);
The rd->cpu_capacity_orig field you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touching cpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see its capacity_orig accounted in a root_domain.
Quoted 1 line
kernel/sched/sched.h +0
-0extern void init_dl_bw (struct dl_bw *dl_b);
Dietmar Eggemann
reviewerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 24 lines · Valentin Schneider
Quoted 7 lines · Dietmar Eggemann
+++
b/kernel/sched/sched.hkernel/sched/sched.h +2
-0@@ -304,11 +304,14 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)__dl_update (dl_b, -((s32 )tsk_bw / cpus)); } +static inline unsigned long rd_capacity (int cpu); +kernel/sched/sched.h void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) · line 316
Quoted 10 lines
kernel/sched/sched.h +3
-2static inline -bool __dl_overflow (struct dl_bw *dl_b,int cpus,u64 old_bw,u64 new_bw) +bool __dl_overflow (struct dl_bw *dl_b,int cpu,u64 old_bw,u64 new_bw) {return dl_b->bw !=-1 && - dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw,rd_capacity (cpu)) < + dl_b->total_bw - old_bw + new_bw; }I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from
dl_bw_cpus(), which is an ugly way of writing
Quoted 6 lines
cpumask_weight(rd->span AND cpu_active_mask);The
rd->cpu_capacity_origfield you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touchingcpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see itscapacity_origaccounted in aroot_domain.
I see what you mean.
The
int dl_bw_cpus(int i) {
...
for_each_cpu_and(i, rd->span, cpu_active_mask)
cpus++;
...
}should be there to handle the 'rd->span &nsub cpu_active_mask' case.
We could use a similar implementation for s/cpus/capacity:
unsigned long dl_bw_capacity(int i) {
...
for_each_cpu_and(i, rd->span, cpu_active_mask)
cap += arch_scale_cpu_capacity(i);
...
}[...]
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to Valentin SchneiderHi Valentin,
Quoted 23 lines · On Wed, 08 Apr 2020 11:42:14 +0100 Valentin Schneider…
Quoted 13 lines · Dietmar Eggemann
+++
b/kernel/sched/sched.hkernel/sched/sched.h +2
-1@@ -304,11 +304,14 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) __dl_update(dl_b, -((s32)tsk_bw / cpus)); } +static inline unsigned long rd_capacity(int cpu); + static inline -bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64
new_bw) +bool __dl_overflow(structdl_bw*dl_b, int cpu, u64old_bw, u64 new_bw) { return dl_b->bw != -1 &&kernel/sched/sched.h void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) · line 315
Quoted 4 lines
kernel/sched/sched.h +2
-1- dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw,rd_capacity (cpu)) < + dl_b->total_bw - old_bw + new_bw; }I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from
dl_bw_cpus(), which is an ugly way of writing
Quoted 7 lines
cpumask_weight(rd->span AND cpu_active_mask);The
rd->cpu_capacity_origfield you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touchingcpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see itscapacity_origaccounted in aroot_domain.
Sorry, I suspect this is my fault, because the bug comes from my original patch.
When I wrote the original code, I believed that when a CPU is deactivated it is also removed from its root domain.
I now see that I was wrong.
Luca
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 36 lines · luca abeni
Hi Valentin,
Quoted 23 lines · On Wed, 08 Apr 2020 11:42:14 +0100 Valentin Schneider…
Quoted 13 lines · Dietmar Eggemann
+++
b/kernel/sched/sched.hkernel/sched/sched.h +2
-1@@ -304,11 +304,14 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) __dl_update(dl_b, -((s32)tsk_bw / cpus)); } +static inline unsigned long rd_capacity(int cpu); + static inline -bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64
new_bw) +bool __dl_overflow(structdl_bw*dl_b, int cpu, u64old_bw, u64 new_bw) { return dl_b->bw != -1 &&kernel/sched/sched.h void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus) · line 315
Quoted 4 lines
kernel/sched/sched.h +2
-1- dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw,rd_capacity (cpu)) < + dl_b->total_bw - old_bw + new_bw; }I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from
dl_bw_cpus(), which is an ugly way of writingQuoted 7 lines
cpumask_weight(rd->span AND cpu_active_mask);The
rd->cpu_capacity_origfield you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touchingcpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see itscapacity_origaccounted in aroot_domain.
Quoted 6 lines
Sorry, I suspect this is my fault, because the bug comes from my original patch.
When I wrote the original code, I believed that when a CPU is deactivated it is also removed from its root domain.I now see that I was wrong.
Shouldn't rd->online be equivalent to (rd->span & cpu-active_mask)?
--
Qais Yousef
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to luca abeniQuoted 13 lines · luca abeni
Quoted 5 lines
I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from
dl_bw_cpus(), which is an ugly way of writingQuoted 7 lines
cpumask_weight(rd->span AND cpu_active_mask);The
rd->cpu_capacity_origfield you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touchingcpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see itscapacity_origaccounted in aroot_domain.
Quoted 7 lines
Sorry, I suspect this is my fault, because the bug comes from my original patch.
When I wrote the original code, I believed that when a CPU is deactivated it is also removed from its root domain.I now see that I was wrong.
Well it is indeed the case, but sadly it's not an atomic step - AFAICT with cpusets we do hold some cpuset lock when calling __dl_overflow() and when rebuilding the domains, but not when fiddling with the active mask.
I just realized it's even more obvious for dl_cpu_busy(): IIUC it is meant to prevent the removal of a CPU if it would lead to a DL overflow - it works now because the active mask is modified before it gets called, but here it breaks because it's called before the sched_domain rebuild.
Perhaps re-computing the root domain capacity sum at every dl_bw_cpus() call would be simpler. It's a bit more work, but then we already have a for_each_cpu_*() loop, and we only rely on the masks being correct.
Quoted 2 lines
Luca
Dietmar Eggemann
reviewerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 27 lines · Valentin Schneider
Quoted 13 lines · luca abeni
Quoted 5 lines
I don't think this is strictly equivalent to what we have now for the SMP case. 'cpus' used to come from
dl_bw_cpus(), which is an ugly way of writingQuoted 7 lines
cpumask_weight(rd->span AND cpu_active_mask);The
rd->cpu_capacity_origfield you added gets set once per domain rebuild, so it also happens in sched_cpu_(de)activate() but is separate from touchingcpu_active_mask. AFAICT this mean we can observe a CPU as !active but still see itscapacity_origaccounted in aroot_domain.Quoted 7 lines
Sorry, I suspect this is my fault, because the bug comes from my original patch.
When I wrote the original code, I believed that when a CPU is deactivated it is also removed from its root domain.I now see that I was wrong.
Well it is indeed the case, but sadly it's not an atomic step - AFAICT with cpusets we do hold some cpuset lock when calling
__dl_overflow()and when rebuilding the domains, but not when fiddling with the active mask.
Quoted 8 lines
I just realized it's even more obvious for
dl_cpu_busy(): IIUC it is meant to prevent the removal of a CPU if it would lead to a DL overflow - it works now because the active mask is modified before it gets called, but here it breaks because it's called before thesched_domainrebuild.Perhaps re-computing the root domain capacity sum at every
dl_bw_cpus()call would be simpler. It's a bit more work, but then we already have a for_each_cpu_*() loop, and we only rely on the masks being correct.
Maybe we can do a hybrid. We have rd->span and rd->sum_cpu_capacity and with the help of an extra per-cpu cpumask we could just
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i) {
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask);
...
cpumask_and(cpus, rd->span, cpu_active_mask);
return cpumask_weight(cpus);
}and
dl_bw_capacity(int i) {
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask);
...
cpumask_and(cpus, rd->span, cpu_active_mask);
if (cpumask_equal(cpus, rd->span))
return rd->sum_cpu_capacity;
for_each_cpu(i, cpus)
cap += capacity_orig_of(i);
return cap;
}So only in cases in which rd->span and cpu_active_mask differ we would have to sum up again.
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
On 04/09/20 19:29, Dietmar Eggemann wrote:
[...]
Quoted 30 lines
Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could just
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i){struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); return cpumask_weight(cpus); }and
dl_bw_capacity(int i){struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); if (cpumask_equal(cpus, rd->span)) return rd->sum_cpu_capacity; for_each_cpu(i, cpus) cap += capacity_orig_of(i); return cap; }
Quoted 2 lines
So only in cases in which
rd->spanandcpu_active_maskdiffer we would have to sum up again.
I haven't followed this discussion closely, so I could be missing something here.
In sched_cpu_dying() we call set_rq_offline() which clears the cpu in rq->rd->online.
So the way I read the code
rd->online = cpumask_and(rd->span, cpu_active_mask)
But I could have easily missed some detail.
Regardless, it seems to me that DL is working around something not right in the definition of rd->span or using the wrong variable.
My 2p :-). I have to go back and read the discussion in more detail.
Thanks
--
Qais Yousef
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 4 lines · Qais Yousef
I haven't followed this discussion closely, so I could be missing something here.
Quoted 9 lines
In
sched_cpu_dying()we callset_rq_offline()which clears the cpu inrq->rd->online.So the way I read the code
rd->online = cpumask_and(rd->span, cpu_active_mask)But I could have easily missed some detail.
sched_cpu_dying() is wayyyy below sched_cpu_deactivate(). This doesn't help at all for the dl_cpu_busy() check in sched_cpu_deactivate().
Quoted 3 lines
Regardless, it seems to me that DL is working around something not right in the definition of
rd->spanor using the wrong variable.
What DL is doing now is fine, it only needs to be aligned with the active mask (which it is). We're making things a bit trickier by adding capacity values into the mix.
Quoted 3 lines
My 2p :-). I have to go back and read the discussion in more detail.
Thanks
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 11 lines · Valentin Schneider
Quoted 9 lines · Qais Yousef
I haven't followed this discussion closely, so I could be missing something here.
In
sched_cpu_dying()we callset_rq_offline()which clears the cpu inrq->rd->online.So the way I read the code
Quoted 7 lines
Quoted 4 lines
rd->online = cpumask_and(rd->span, cpu_active_mask)But I could have easily missed some detail.
sched_cpu_dying()is wayyyy belowsched_cpu_deactivate(). This doesn't help at all for thedl_cpu_busy()check insched_cpu_deactivate().
It'd makes more sense to introduce rd->active then rather than a PERCPU global variable IMHO.
Quoted 8 lines
Quoted 4 lines
Regardless, it seems to me that DL is working around something not right in the definition of
rd->spanor using the wrong variable.What DL is doing now is fine, it only needs to be aligned with the active mask (which it is). We're making things a bit trickier by adding capacity values into the mix.
I'm still worried that others might be affected by a similar problem.
Will dig deeper next week when I'm back from hols.
Thanks
--
Qais Yousef
Re: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to Dietmar EggemannQuoted 18 lines · Dietmar Eggemann
Quoted 4 lines
Well it is indeed the case, but sadly it's not an atomic step - AFAICT with cpusets we do hold some cpuset lock when calling
__dl_overflow()and when rebuilding the domains, but not when fiddling with the active mask.Quoted 8 lines
I just realized it's even more obvious for
dl_cpu_busy(): IIUC it is meant to prevent the removal of a CPU if it would lead to a DL overflow - it works now because the active mask is modified before it gets called, but here it breaks because it's called before thesched_domainrebuild.Perhaps re-computing the root domain capacity sum at every
dl_bw_cpus()call would be simpler. It's a bit more work, but then we already have a for_each_cpu_*() loop, and we only rely on the masks being correct.Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could just
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
Quoted 7 lines
dl_bw_cpus(int i){struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); return cpumask_weight(cpus);
+1 on making this use cpumask_weight() :)
Quoted 18 lines
}
and
dl_bw_capacity(int i){struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); if (cpumask_equal(cpus, rd->span)) return rd->sum_cpu_capacity; for_each_cpu(i, cpus) cap += capacity_orig_of(i); return cap; }
Quoted 2 lines
So only in cases in which
rd->spanandcpu_active_maskdiffer we would have to sum up again.
I think this might just work. In the "stable" case (i.e. not racing with hotplug), we can use the value cached in the root_domain. Otherwise we'll detect the mismatch between the cpumask and the root_domain (i.e. CPU active but not yet included in root_domain, or CPU !active but still included in root_domain).
Juri Lelli
maintainerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to Dietmar EggemannOn 09/04/20 19:29, Dietmar Eggemann wrote:
[...]
Quoted 3 lines
Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could just
Hummm, I like the idea, but
Quoted 3 lines
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i){
This works if calls are always local to the rd we are interested into (argument 'i' isn't used). Are we always doing that?
Quoted 9 lines
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); return cpumask_weight(cpus); }and
Quoted 7 lines
dl_bw_capacity(int i){struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); if (cpumask_equal(cpus, rd->span)) return rd->sum_cpu_capacity;
What if capacities change between invocations (with the same span)? Can that happen?
Quoted 9 lines
for_each_cpu(i, cpus) cap += capacity_orig_of(i); return cap; }So only in cases in which
rd->spanandcpu_active_maskdiffer we would have to sum up again.
Thanks,
Juri
Dietmar Eggemann
reviewerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 1 line · Juri Lelli
On 09/04/20 19:29, Dietmar Eggemann wrote:
[...]
Quoted 11 lines
Quoted 2 lines
Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could justHummm, I like the idea, but
Quoted 3 lines
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i){This works if calls are always local to the rd we are interested into (argument 'i' isn't used). Are we always doing that?
I thought so. The existing dl_bw_cpus(int i) implementation already assumes this by using:
struct root_domain *rd = cpu_rq(i)->rd;
...
for_each_cpu_and(i, rd->span, cpu_active_mask)Or did you refer to something else here?
And the patch would not introduce new places in which we call dl_bw_cpus(). It will just replace some with a dl_bw_capacity() call.
Quoted 11 lines
Quoted 11 lines
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); return cpumask_weight(cpus); }and
dl_bw_capacity(int i){
Quoted 8 lines
Quoted 5 lines
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); if (cpumask_equal(cpus, rd->span)) return rd->sum_cpu_capacity;What if capacities change between invocations (with the same span)? Can that happen?
The CPU capacity should only change during initial bring-up. On asymmetric CPU capacity systems we have to re-create the Sched Domain (SD) topology after CPUfreq becomes available.
After the initial build and this first rebuild of the SD topology, the CPU capacity should be stable.
Everything which might follow afterwards (starting EAS, exclusive cpusets or CPU hp) will not change the CPU capacity.
Obviously, if you defer loading CPUfreq driver after you started DL scheduling you can break things. But this is not considered a valid environment here.
[...]
Juri Lelli
maintainerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 14 lines · Dietmar Eggemann
Quoted 1 line · Juri Lelli
On 09/04/20 19:29, Dietmar Eggemann wrote:
[...]
Quoted 9 lines
Quoted 2 lines
Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could justHummm, I like the idea, but
Quoted 3 lines
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i){
Quoted 7 lines
Quoted 2 lines
This works if calls are always local to the rd we are interested into (argument 'i' isn't used). Are we always doing that?
I thought so. The existing
dl_bw_cpus(int i)implementation already assumes this by using:struct root_domain *rd = cpu_rq(i)->rd;
Hummm, can't dl_task_can_attach() call it with a dest_cpu different from this_cpu?
Current implementation uses 'i' argument to get to the right root_domain (e.g., when moving tasks between execlusive set).
Quoted 36 lines
... for_each_cpu_and(i, rd->span, cpu_active_mask)Or did you refer to something else here?
And the patch would not introduce new places in which we call
dl_bw_cpus(). It will just replace some with adl_bw_capacity()call.Quoted 11 lines
Quoted 11 lines
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); return cpumask_weight(cpus); }and
dl_bw_capacity(int i){Quoted 8 lines
Quoted 5 lines
struct cpumask *cpus = this_cpu_cpumask_var_ptr(dl_bw_mask); ... cpumask_and(cpus, rd->span, cpu_active_mask); if (cpumask_equal(cpus, rd->span)) return rd->sum_cpu_capacity;What if capacities change between invocations (with the same span)? Can that happen?
The CPU capacity should only change during initial bring-up. On asymmetric CPU capacity systems we have to re-create the Sched Domain (SD) topology after CPUfreq becomes available.
After the initial build and this first rebuild of the SD topology, the CPU capacity should be stable.
Quoted 6 lines
Everything which might follow afterwards (starting EAS, exclusive cpusets or CPU hp) will not change the CPU capacity.
Obviously, if you defer loading CPUfreq driver after you started DL scheduling you can break things. But this is not considered a valid environment here.
OK. Makes sense.
Juri Lelli
maintainerRe: [PATCH 2/4] sched/deadline: Improve admission control for asymmetric CPU capacities
Quoted 21 lines · Juri Lelli
Quoted 20 lines · Dietmar Eggemann
Quoted 1 line · Juri Lelli
On 09/04/20 19:29, Dietmar Eggemann wrote:
[...]
Quoted 11 lines
Quoted 2 lines
Maybe we can do a hybrid. We have
rd->spanandrd->sum_cpu_capacityand with the help of an extra per-cpu cpumask we could justHummm, I like the idea, but
Quoted 3 lines
DEFINE_PER_CPU(cpumask_var_t, dl_bw_mask);
dl_bw_cpus(int i){This works if calls are always local to the rd we are interested into (argument 'i' isn't used). Are we always doing that?
I thought so. The existing
dl_bw_cpus(int i)implementation already assumes this by using:
Quoted 9 lines
Quoted 1 line
struct root_domain *rd = cpu_rq(i)->rd;Hummm, can't
dl_task_can_attach()call it with adest_cpudifferent fromthis_cpu?Current implementation uses 'i' argument to get to the right
root_domain(e.g., when moving tasks between execlusive set).Quoted 1 line
...
Bah, forget that. If everything else stays the same (get rd using 'i') this should work ok.
Dietmar Eggemann
reviewerPATCH 3/4 sched/deadline: Make DL capacity-aware
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
The current SCHED_DEADLINE (DL) scheduler uses a global EDF scheduling algorithm w/o considering CPU capacity or task utilization. This works well on homogeneous systems where DL tasks are guaranteed to have a bounded tardiness but presents issues on heterogeneous systems.
A DL task can migrate to a CPU which does not have enough CPU capacity to correctly serve the task (e.g. a task w/ 70ms runtime and 100ms period on a CPU w/ 512 capacity).
Add the DL fitness function dl_task_fits_capacity() for DL admission control on heterogeneous systems. A task fits onto a CPU if:
CPU original capacity / 1024 >= task runtime / task deadline
Use this function on heterogeneous systems to try to find a CPU which meets this criterion during task wakeup, push and offline migration.
On homogeneous systems the original behavior of the DL admission control should be retained.
--- kernel/sched/cpudeadline.c | 14 +++++++++++++- kernel/sched/deadline.c | 18 ++++++++++++++---- kernel/sched/sched.h | 15 +++++++++++++++ 3 files changed, 42 insertions(+), 5 deletions(-)
kernel/sched/cpudeadline.c +13 -1
@@ -121,7 +121,19 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -return 1 ; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return 1 ; + +/* Ensure the capacity of the CPUs fits the task. */ +for_each_cpu (cpu, later_mask) { +if (!dl_task_fits_capacity (p, cpu)) +cpumask_clear_cpu (cpu, later_mask); + } + +if (!cpumask_empty (later_mask)) +return 1 ; }else {int best_cpu =cpudl_maximum (cp);
kernel/sched/deadline.c +14 -4
@@ -1604,6 +1604,7 @@ static int select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) { struct task_struct *curr; +bool select_rq;struct rq *rq;if (sd_flag !=SD_BALANCE_WAKE )
@@ -1623,10 +1624,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* We take into account the capacity of the CPU to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu); + +if (select_rq) {int target =find_later_rq (p); if (target != -1 &&
kernel/sched/sched.h +15 -0
@@ -306,6 +306,21 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)static inline unsigned long rd_capacity (int cpu); +/* +* Verify the fitness of task @p to run on @cpu taking into account the +* CPU original capacity and the runtime/deadline ratio of the task. +* +* The function will return true if the CPU original capacity of the +* @cpu scaled by SCHED_CAPACITY_SCALE >= runtime/deadline ratio of the +* task and false otherwise. +*/ +static inline bool dl_task_fits_capacity (struct task_struct *p,int cpu) +{ +unsigned long cap =arch_scale_cpu_capacity (cpu); + +return cap_scale (p->dl.dl_deadline, cap) >= p->dl.dl_runtime; +} +static inline bool __dl_overflow (struct dl_bw *dl_b,int cpu,u64 old_bw,u64 new_bw) {
Signature · 1 line
2.17.1
Juri Lelli
maintainerRe: [PATCH 3/4] sched/deadline: Make DL capacity-aware
Hi,
Quoted 77 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
The current
SCHED_DEADLINE(DL) scheduler uses a global EDF scheduling algorithm w/o considering CPU capacity or task utilization. This works well on homogeneous systems where DL tasks are guaranteed to have a bounded tardiness but presents issues on heterogeneous systems.A DL task can migrate to a CPU which does not have enough CPU capacity to correctly serve the task (e.g. a task w/ 70ms runtime and 100ms period on a CPU w/ 512 capacity).
Add the DL fitness function
dl_task_fits_capacity()for DL admission control on heterogeneous systems. A task fits onto a CPU if:CPU original capacity / 1024 >= task runtime / task deadline
Use this function on heterogeneous systems to try to find a CPU which meets this criterion during task wakeup, push and offline migration.
On homogeneous systems the original behavior of the DL admission control should be retained.
Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>--- kernel/sched/cpudeadline.c | 14 +++++++++++++- kernel/sched/deadline.c | 18 ++++++++++++++---- kernel/sched/sched.h | 15 +++++++++++++++ 3 files changed, 42 insertions(+), 5 deletions(-)kernel/sched/cpudeadline.c +13
-1@@ -121,7 +121,19 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -return 1 ; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return 1 ; + +/* Ensure the capacity of the CPUs fits the task. */ +for_each_cpu (cpu, later_mask) { +if (!dl_task_fits_capacity (p, cpu)) +cpumask_clear_cpu (cpu, later_mask); + } + +if (!cpumask_empty (later_mask)) +return 1 ; }else {int best_cpu =cpudl_maximum (cp);kernel/sched/deadline.c +2
-4@@ -1604,6 +1604,7 @@ static int select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) { struct task_struct *curr; +bool select_rq;struct rq *rq;if (sd_flag !=SD_BALANCE_WAKE )@@ -1623,10 +1624,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq = unlikely(dl_task(curr)) &&
kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1637
Quoted 10 lines
kernel/sched/deadline.c +10
-0+ (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* We take into account the capacity of the CPU to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);
I'm thinking that, while dl_task_fits_capacity() works well when selecting idle cpus, in this case we should consider the fact that curr might be deadline as well and already consuming some of the rq capacity.
Do you think we should try to take that into account, maybe using dl_rq->this_bw ?
Thanks,
Juri
Dietmar Eggemann
reviewerRe: [PATCH 3/4] sched/deadline: Make DL capacity-aware
Quoted 4 lines · Juri Lelli
Hi,
Quoted 1 line · Dietmar Eggemann
From: Luca Abeni <[email protected]>
[...]
Quoted 24 lines
Quoted 9 lines
kernel/sched/deadline.c +1
-4@@ -1623,10 +1624,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq = unlikely(dl_task(curr)) &&kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1637
Quoted 10 lines
kernel/sched/deadline.c +10
-0+ (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* We take into account the capacity of the CPU to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);I'm thinking that, while
dl_task_fits_capacity()works well when selecting idle cpus, in this case we should consider the fact that curr might be deadline as well and already consuming some of the rq capacity.
Quoted 2 lines
Do you think we should try to take that into account, maybe using
dl_rq->this_bw?
So you're saying that cpudl_find(..., later_mask) could return 1 (w/ best_cpu (cp->elements[0].cpu) in later_mask).
And that this best_cpu could be a non-fitting CPU for p.
This could happen if cp->free_cpus is empty (no idle CPUs) so we take cpudl_find()'s else path and in case p's deadline < cp->elements[0] deadline.
We could condition the 'return 1' on best_cpu fitting p.
But should we do this for cpudl_find(..., NULL) calls from check_preempt_equal_dl() as well or will this break GEDF?
Juri Lelli
maintainerRe: [PATCH 3/4] sched/deadline: Make DL capacity-aware
Quoted 40 lines · Dietmar Eggemann
Quoted 4 lines · Juri Lelli
Hi,
Quoted 1 line · Dietmar Eggemann
From: Luca Abeni <[email protected]>
[...]
Quoted 24 lines
Quoted 9 lines
kernel/sched/deadline.c +1
-4@@ -1623,10 +1624,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq = unlikely(dl_task(curr)) &&kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1637
Quoted 10 lines
kernel/sched/deadline.c +10
-0+ (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* We take into account the capacity of the CPU to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);I'm thinking that, while
dl_task_fits_capacity()works well when selecting idle cpus, in this case we should consider the fact that curr might be deadline as well and already consuming some of the rq capacity.Quoted 2 lines
Do you think we should try to take that into account, maybe using
dl_rq->this_bw?So you're saying that
cpudl_find(..., later_mask)could return 1 (w/best_cpu(cp->elements[0].cpu) inlater_mask).And that this
best_cpucould be a non-fitting CPU for p.
Quoted 8 lines
This could happen if
cp->free_cpusis empty (no idle CPUs) so we take cpudl_find()'s else path and in case p's deadline < cp->elements[0] deadline.We could condition the 'return 1' on
best_cpufitting p.But should we do this for
cpudl_find(..., NULL)calls fromcheck_preempt_equal_dl()as well or will this break GEDF?
So, even by not returning best_cpu, as above, if it doesn't fit p's bw requirement, I think we would be breaking GEDF, which however doesn't take asym capacities into account. OTOH, if we let p migrate to a cpu that can't suit it, it will still be missing its deadlines (plus it would be causing deadline misses on the task that was running on best_cpu).
check_preempt_equal_dl() worries me less, as it is there to service corner cases (hopefully not so frequent).
Re: [PATCH 3/4] sched/deadline: Make DL capacity-aware
Hi Juri,
On Wed, 15 Apr 2020 15:20:04 +0200
Juri Lelli <[email protected]> wrote:
[...]
Quoted 17 lines
Quoted 17 lines
Quoted 7 lines
I'm thinking that, while
dl_task_fits_capacity()works well when selecting idle cpus, in this case we should consider the fact that curr might be deadline as well and already consuming some of the rq capacity.Do you think we should try to take that into account, maybe using
dl_rq->this_bw?So you're saying that
cpudl_find(..., later_mask)could return 1 (w/best_cpu(cp->elements[0].cpu) inlater_mask).And that this
best_cpucould be a non-fitting CPU for p.This could happen if
cp->free_cpusis empty (no idle CPUs) so we take cpudl_find()'s else path and in case p's deadline < cp->elements[0] deadline.
Quoted 8 lines
Quoted 4 lines
We could condition the 'return 1' on
best_cpufitting p.But should we do this for
cpudl_find(..., NULL)calls fromcheck_preempt_equal_dl()as well or will this break GEDF?So, even by not returning
best_cpu, as above, if it doesn't fit p's bw requirement, I think we would be breaking GEDF, which however doesn't take asym capacities into account.
Well, gEDF could take asymmetric capacities into account by scheduling the earliest deadline task on the fastest CPU (and the task with the second earliest deadline on the second fastest CPU, and so on...)
But this could cause a lot of unneeded migrations (I tried to discuss this issue in a previous OSPM presentation). My original approach to work around this issue was to schedule a task on the slowest core on which the task can fit (some experiments revealed that this heuristic can approximate the gEDF behaviour without causing too many migrations)... But this patch is not included on the current patchset, and will be proposed later, after the most important patches have been merged.
Quoted 4 lines
OTOH, if we let p migrate to a cpu
that can't suit it, it will still be missing its deadlines (plus it would be causing deadline misses on the task that was running onbest_cpu).
In theory, if the task is scheduled on a core that is too slow for it then we must allow faster cores to pull it later (when tasks with earlier deadlines block). But this might be problematic, because it can require to migrate a currently scheduled task.
Luca
Quoted 4 lines
check_preempt_equal_dl()worries me less, as it is there to service corner cases (hopefully not so frequent).
Juri Lelli
maintainerRe: [PATCH 3/4] sched/deadline: Make DL capacity-aware
Quoted 35 lines · luca abeni
Hi Juri,
On Wed, 15 Apr 2020 15:20:04 +0200
Juri Lelli <[email protected]> wrote:
[...]Quoted 17 lines
Quoted 17 lines
Quoted 7 lines
I'm thinking that, while
dl_task_fits_capacity()works well when selecting idle cpus, in this case we should consider the fact that curr might be deadline as well and already consuming some of the rq capacity.Do you think we should try to take that into account, maybe using
dl_rq->this_bw?So you're saying that
cpudl_find(..., later_mask)could return 1 (w/best_cpu(cp->elements[0].cpu) inlater_mask).And that this
best_cpucould be a non-fitting CPU for p.This could happen if
cp->free_cpusis empty (no idle CPUs) so we take cpudl_find()'s else path and in case p's deadline < cp->elements[0] deadline.Quoted 8 lines
Quoted 4 lines
We could condition the 'return 1' on
best_cpufitting p.But should we do this for
cpudl_find(..., NULL)calls fromcheck_preempt_equal_dl()as well or will this break GEDF?So, even by not returning
best_cpu, as above, if it doesn't fit p's bw requirement, I think we would be breaking GEDF, which however doesn't take asym capacities into account.Well, gEDF could take asymmetric capacities into account by scheduling the earliest deadline task on the fastest CPU (and the task with the second earliest deadline on the second fastest CPU, and so on...)
Quoted 8 lines
But this could cause a lot of unneeded migrations (I tried to discuss this issue in a previous OSPM presentation). My original approach to work around this issue was to schedule a task on the slowest core on which the task can fit (some experiments revealed that this heuristic can approximate the gEDF behaviour without causing too many migrations)... But this patch is not included on the current patchset, and will be proposed later, after the most important patches have been merged.
OK, makes sense to me. And I'm ok also with a 2 steps approach. Asym idle now and asym busy with a later series.
Best,
Juri
Dietmar Eggemann
reviewerPATCH 4/4 sched/deadline: Implement fallback mechanism for !fit case
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (later_mask) the task is doomed to miss its deadline.
This can happen since the SCHED_DEADLINE admission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.
--- kernel/sched/cpudeadline.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)
kernel/sched/cpudeadline.c +15 -4
@@ -121,19 +121,30 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -int cpu; +unsigned long cap, max_cap =0 ; +int cpu, max_cpu =-1 ;if (!static_branch_unlikely (&sched_asym_cpucapacity))return 1 ;/* Ensure the capacity of the CPUs fits the task. */ for_each_cpu (cpu, later_mask) { -if (!dl_task_fits_capacity (p, cpu)) +if (!dl_task_fits_capacity (p, cpu)) {cpumask_clear_cpu (cpu, later_mask); + + cap =arch_scale_cpu_capacity (cpu); + +if (cap > max_cap) { + max_cap = cap; + max_cpu = cpu; + } + } } -if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask); + +return 1 ; }else {int best_cpu =cpudl_maximum (cp);
Signature · 1 line
2.17.1
Re: [PATCH 4/4] sched/deadline: Implement fallback mechanism for !fit case
Quoted 6 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.
Quoted 8 lines
This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>---
Outside of the scope of this series. But does it make sense to make sched_setattr() fail to create a new deadline task if the system will be overcommitted, hence causing some dl tasks to miss their deadlines?
If some overcommitting is fine (some deadlines are soft and are okay to fail every once in a while), does it make sense for this to be a tunable of how much the system can be overcommitted before disallowing new DL tasks to be created?
Just thinking out loudly. This fallback is fine, but it made me think why did we have to end up in a situation that we can fail in the first place since the same info is available when a new DL task is created, and being preventative might be a better approach..
Thanks
--
Qais Yousef
Quoted 45 lines
kernel/sched/cpudeadline.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)kernel/sched/cpudeadline.c +15
-4@@ -121,19 +121,30 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -int cpu; +unsigned long cap, max_cap =0 ; +int cpu, max_cpu =-1 ;if (!static_branch_unlikely (&sched_asym_cpucapacity))return 1 ;/* Ensure the capacity of the CPUs fits the task. */ for_each_cpu (cpu, later_mask) { -if (!dl_task_fits_capacity (p, cpu)) +if (!dl_task_fits_capacity (p, cpu)) {cpumask_clear_cpu (cpu, later_mask); + + cap =arch_scale_cpu_capacity (cpu); + +if (cap > max_cap) { + max_cap = cap; + max_cpu = cpu; + } + } } -if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask); + +return 1 ; }else {int best_cpu =cpudl_maximum (cp);Signature · 1 line
2.17.1
Re: [PATCH 4/4] sched/deadline: Implement fallback mechanism for !fit case
Hi,
Quoted 12 lines · On Thu, 9 Apr 2020 11:25:58 +0100 Qais Yousef <[email protected]> wrote:
Quoted 11 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.
Quoted 7 lines
Quoted 3 lines
Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>---
Outside of the scope of this series. But does it make sense to make
sched_setattr()fail to create a new deadline task if the system will be overcommitted, hence causing some dl tasks to miss their deadlines?
The problem is that with multiple processors/cores it is not easy to know in advance if any task will miss a deadline (see section 3.3 of Documentation/scheduler/sched-deadline.rst).
The admission control we are currently using should prevent SCHED_DEADLINE tasks from overloading the system (starving non-deadline tasks); proving hard deadline guarantees with global EDF scheduling is much more difficult (and could be probably done in user-space, I think).
Quoted 4 lines
If some overcommitting is fine (some deadlines are soft and are okay to fail every once in a while), does it make sense for this to be a tunable of how much the system can be overcommitted before disallowing new DL tasks to be created?
There is already a tunable for the SCHED_DEADLINE admission test (/proc/sys/kernel/sched_rt_{runtime,period}_us, if I understand well what you are suggesting). The problem is that it is not easy to find a value for this tunable that guarantees the hard respect of all deadlines.
But IMHO if someone really wants hard deadline guarantees it is better to use partitioned scheduling (see Section 5 of the SCHED_DEADLINE documentation).
Luca
Quoted 56 lines
Just thinking out loudly. This fallback is fine, but it made me think why did we have to end up in a situation that we can fail in the first place since the same info is available when a new DL task is created, and being preventative might be a better approach..
Thanks
--
Qais YousefQuoted 45 lines
kernel/sched/cpudeadline.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)kernel/sched/cpudeadline.c +15
-4@@ -121,19 +121,30 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p, if (later_mask && cpumask_and(later_mask, cp->free_cpus, p->cpus_ptr)) { -int cpu; +unsigned long cap, max_cap =0 ; +int cpu, max_cpu =-1 ;if (!static_branch_unlikely (&sched_asym_cpucapacity))return 1 ;/* Ensure the capacity of the CPUs fits the task. */ for_each_cpu(cpu, later_mask) { -if (!dl_task_fits_capacity (p, cpu)) +if (!dl_task_fits_capacity (p, cpu)) {cpumask_clear_cpu (cpu, later_mask); + + cap =arch_scale_cpu_capacity (cpu); + +if (cap > max_cap) { + max_cap = cap; + max_cpu = cpu; + } + } } -if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask); + +return 1 ; } else {int best_cpu =cpudl_maximum (cp);Signature · 1 line
2.17.1
Re: [PATCH 4/4] sched/deadline: Implement fallback mechanism for !fit case
Hi Luca
Quoted 4 lines · luca abeni
Quoted 3 lines
Outside of the scope of this series. But does it make sense to make
sched_setattr()fail to create a new deadline task if the system will be overcommitted, hence causing some dl tasks to miss their deadlines?
Quoted 8 lines
The problem is that with multiple processors/cores it is not easy to know in advance if any task will miss a deadline (see section 3.3 of
Documentation/scheduler/sched-deadline.rst).The admission control we are currently using should prevent
SCHED_DEADLINEtasks from overloading the system (starving non-deadline tasks); proving hard deadline guarantees with global EDF scheduling is much more difficult (and could be probably done in user-space, I think).
I see. I'll dig through the docs, thanks for the reference.
Quoted 10 lines
Quoted 4 lines
If some overcommitting is fine (some deadlines are soft and are okay to fail every once in a while), does it make sense for this to be a tunable of how much the system can be overcommitted before disallowing new DL tasks to be created?
There is already a tunable for the
SCHED_DEADLINEadmission test (/proc/sys/kernel/sched_rt_{runtime,period}_us, if I understand well what you are suggesting). The problem is that it is not easy to find a value for this tunable that guarantees the hard respect of all deadlines.
I don't think it's similar to what I was referring to. But my knowledge about DL could have failed me to fully appreciate what you're saying.
This tunable for RT prevents a single task from using 100% CPU time. I think DL uses it in a similar manner.
What I meant by overcommiting, is allowing more DL tasks than the system can guarantee to meet their deadlines.
For example, in the context of capacity awareness, if you have 2 big cores, but 4 DL tasks request a bandwidth that can only be satisfied by the big cores, then 2 of them will miss their deadlines (almost) consistently, IIUC.
This can be generalized on SMP (I believe). But judging from your earlier response, it's not as straightforward as it seems :)
Quoted 4 lines
But IMHO if someone really wants hard deadline guarantees it is better to use partitioned scheduling (see Section 5 of the
SCHED_DEADLINEdocumentation).
RT is the same. So this makes sense. Though one would hope to be able to improve on this in the future. Something for me to ponder over :)
Thanks
--
Qais Yousef
Dietmar Eggemann
reviewerRe: [PATCH 4/4] sched/deadline: Implement fallback mechanism for !fit case
Quoted 3 lines · Qais Yousef
Hi Luca
On 04/09/20 15:00, luca abeni wrote:
[...]
Quoted 12 lines
Quoted 5 lines
There is already a tunable for the
SCHED_DEADLINEadmission test (/proc/sys/kernel/sched_rt_{runtime,period}_us, if I understand well what you are suggesting). The problem is that it is not easy to find a value for this tunable that guarantees the hard respect of all deadlines.I don't think it's similar to what I was referring to. But my knowledge about DL could have failed me to fully appreciate what you're saying.
This tunable for RT prevents a single task from using 100% CPU time. I think DL uses it in a similar manner.
Quoted 6 lines
What I meant by overcommiting, is allowing more DL tasks than the system can guarantee to meet their deadlines.
For example, in the context of capacity awareness, if you have 2 big cores, but 4 DL tasks request a bandwidth that can only be satisfied by the big cores, then 2 of them will miss their deadlines (almost) consistently, IIUC.
__dl_overflow() now uses
X = cap_scale(dl_b->bw, rd_capacity(cpu)) instead of X = cpus
in
dl_b->bw * X < dl_b->total_bw - old_bw + new_bw;
As an example, Arm64 Hikey64 with 4 LITTLE and 4 big CPUs uses now (4x462 + 4x1024)/1024 = 5944/1024 ~ 5,80 instead of 8 CPUs.
On mainline, the rt-app tests:
"tasks" : {
"thread0" : {
"policy" : "SCHED_DEADLINE",
"instance" : 8,
"timer" : {"ref" : "unique0", "period" : 16000, "mode" : "absolute" }, "run" : 10000,
"dl-runtime" :11000,
"dl-period" : 16000,
"dl-deadline" : 16000
}
}
is admitted on this board whereas with the patchset some of the tasks are rejected:
[rt-app] <crit> [7] sched_setattr returned -1sched_setattr: failed to set deadline attributes: Device or resource busy
---
IMHO, one of the 3 places where DL Admission Control hooks into is:
__sched_setscheduler -> sched_dl_overflow() ->__dl_overflow()
[...]
Re: [PATCH 4/4] sched/deadline: Implement fallback mechanism for !fit case
Quoted 58 lines · Dietmar Eggemann
Quoted 3 lines · Qais Yousef
Hi Luca
On 04/09/20 15:00, luca abeni wrote:
[...]
Quoted 12 lines
Quoted 5 lines
There is already a tunable for the
SCHED_DEADLINEadmission test (/proc/sys/kernel/sched_rt_{runtime,period}_us, if I understand well what you are suggesting). The problem is that it is not easy to find a value for this tunable that guarantees the hard respect of all deadlines.I don't think it's similar to what I was referring to. But my knowledge about DL could have failed me to fully appreciate what you're saying.
This tunable for RT prevents a single task from using 100% CPU time. I think DL uses it in a similar manner.
Quoted 6 lines
What I meant by overcommiting, is allowing more DL tasks than the system can guarantee to meet their deadlines.
For example, in the context of capacity awareness, if you have 2 big cores, but 4 DL tasks request a bandwidth that can only be satisfied by the big cores, then 2 of them will miss their deadlines (almost) consistently, IIUC.
__dl_overflow()now usesX = cap_scale(dl_b->bw, rd_capacity(cpu)) instead of X = cpusin
dl_b->bw * X < dl_b->total_bw - old_bw + new_bw;As an example, Arm64 Hikey64 with 4 LITTLE and 4 big CPUs uses now (4x462 + 4x1024)/1024 = 5944/1024 ~ 5,80 instead of 8 CPUs.
On mainline, the rt-app tests:
"tasks" : {
"thread0" : {
"policy" : "SCHED_DEADLINE",
"instance" : 8,
"timer" : {"ref" : "unique0", "period" : 16000, "mode" : "absolute" }, "run" : 10000,
"dl-runtime" :11000,
"dl-period" : 16000,
"dl-deadline" : 16000
}
}is admitted on this board whereas with the patchset some of the tasks are rejected:
[rt-app] <crit> [7]
sched_setattrreturned -1sched_setattr: failed to set deadline attributes: Device or resource busy
Quoted 7 lines
---
IMHO, one of the 3 places where DL Admission Control hooks into is:
__sched_setscheduler -> sched_dl_overflow() ->__dl_overflow()[...]
Thanks Dietmar! I should have looked at the code with more intent.
--
Qais Yousef