Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1246465 > unrolled thread
| Started by | <byungchul.park@lge.com> |
|---|---|
| First post | 2015-10-14 11:50 +0200 |
| Last post | 2015-10-14 11:50 +0200 |
| Articles | 3 — 1 participant |
Back to article view | Back to linux.kernel
[PATCH v4 0/2] sched: consider missed ticks when updating cpu load <byungchul.park@lge.com> - 2015-10-14 11:50 +0200
[PATCH v4 1/2] sched: make __update_cpu_load() handle active tickless case <byungchul.park@lge.com> - 2015-10-14 11:50 +0200
[PATCH v4 2/2] sched: consider missed ticks in full NOHZ <byungchul.park@lge.com> - 2015-10-14 11:50 +0200
| From | <byungchul.park@lge.com> |
|---|---|
| Date | 2015-10-14 11:50 +0200 |
| Subject | [PATCH v4 0/2] sched: consider missed ticks when updating cpu load |
| Message-ID | <qjqR3-31B-1@gated-at.bofh.it> |
From: Byungchul Park <byungchul.park@lge.com> change from v3 to v4 - focus the problem on full NOHZ change from v2 to v3 - add a patch which make __update_cpu_load() handle active tickless change from v1 to v2 - add some additional commit message (logic is same exactly) i will try to fix other stuffs caused by full NOHZ later with another patch. i decided to send this patch at first because "cpu load update" is a standalone problem which is not coupled with other stuffs. Byungchul Park (2): sched: make __update_cpu_load() handle active tickless case sched: consider missed ticks in full NOHZ include/linux/sched.h | 4 ++-- kernel/sched/fair.c | 58 +++++++++++++++++++++++++++++++++++++++------- kernel/time/tick-sched.c | 8 +++---- 3 files changed, 56 insertions(+), 14 deletions(-) -- 1.7.9.5 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[toc] | [next] | [standalone]
| From | <byungchul.park@lge.com> |
|---|---|
| Date | 2015-10-14 11:50 +0200 |
| Subject | [PATCH v4 1/2] sched: make __update_cpu_load() handle active tickless case |
| Message-ID | <qjqR3-31B-3@gated-at.bofh.it> |
| In reply to | #1246465 |
From: Byungchul Park <byungchul.park@lge.com>
There are some cases where distance between ticks is more then one tick,
while the cpu is not idle, e.g. full NOHZ.
However __update_cpu_load() assumes it is the idle tickless case if the
distance between ticks is more than 1, even though it can be the active
tickless case. Thus in the active tickless case, updating cpu load
cannot be performed correctly. To update cpu load properly, this patch
changes __update_cpu_load() so that it can handle active tickless case.
We can consider the new_load for each omitted tick during tickless though
the each new_load would be zero in idle tickless case, while it's not
true in non-idle tickless case. We can approximately consider the
new_load ~= the last this_rq->cpu_load[0] during tickless in non-idle
tickless case. Now, let's define a symbol L which is representing the
each new_load during tickless so that L = 0 in idle tickless case,
L = this_rq->cpu_load[0] in non-idle tickless case. Then, we can get
the cpu_load(n) during tickless since last update, by
cpu_load(n) = (1 - 1/s) * cpu_load(n-1) + (1/s) * L
, where n = the current tick - 1, s = scale
= A * cpu_load(n-1) + B
, where A = 1 - 1/s, B = (1/s) * L
= A * (A * cpu_load(n-2) + B) + B
= A * (A * (A * cpu_load(n-3) + B) + B) + B
= A^3 * cpu_load(n-3) + A^2 * B + A * B + B
= A^i * cpu_load(n-i) + (A^(i-1) + A^(i-2) + ... + 1) * B
, where i = pending_updates - 1
= A^i * cpu_load(n-i) + B * (A^i - 1) / (A - 1)
, by geometric series formula for sum
= (1 - 1/s)^i * (cpu_load(n-i) - L) + L
, by extending A and B
Calculation is over!
1. (1 - 1/s)^i can be handled by decay_load_missed().
2. cpu_load(n-i) is the "old_load".
3. L is the this_rq->cpu_load[0], updated at the last time.
Finally,
cpu_load(n) for current tick will be handled in this turn.
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
kernel/sched/fair.c | 56 ++++++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 49 insertions(+), 7 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 077076f..26473fc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4307,13 +4307,54 @@ decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
/*
* Update rq->cpu_load[] statistics. This function is usually called every
- * scheduler tick (TICK_NSEC). With tickless idle this will not be called
- * every tick. We fix it up based on jiffies.
+ * scheduler tick (TICK_NSEC). With tickless this will not be called every
+ * tick. We fix it up based on jiffies.
+ *
+ * We can consider the new_load for each omitted tick during tickless though
+ * the each new_load would be zero in idle tickless case, while it's not
+ * true in non-idle tickless case e.g. full NOHZ. We can approximately
+ * consider the new_load ~= the last this_rq->cpu_load[0] during tickless
+ * in non-idle tickless case e.g. full NOHZ. Now, let's define a symbol L
+ * which is representing the each new_load during tickless so that L = 0 in
+ * idle tickless case, L = this_rq->cpu_load[0] in non-idle tickless case.
+ * Then, we can get the cpu_load(n) during tickless since last update, by
+ *
+ * cpu_load(n) = (1 - 1/s) * cpu_load(n-1) + (1/s) * L
+ * , where n = the current tick - 1, s = scale
+ *
+ * = A * cpu_load(n-1) + B
+ * , where A = 1 - 1/s, B = (1/s) * L
+ *
+ * = A * (A * cpu_load(n-2) + B) + B
+ *
+ * = A * (A * (A * cpu_load(n-3) + B) + B) + B
+ *
+ * = A^3 * cpu_load(n-3) + A^2 * B + A * B + B
+ *
+ * = A^i * cpu_load(n-i) + (A^(i-1) + A^(i-2) + ... + 1) * B
+ * , where i = pending_updates - 1
+ *
+ * = A^i * cpu_load(n-i) + B * (A^i - 1) / (A - 1)
+ * , by geometric series formula for sum
+ *
+ * = (1 - 1/s)^i * (cpu_load(n-i) - L) + L
+ * , by extending A and B
+ *
+ * Calculation is over!
+ *
+ * 1. (1 - 1/s)^i can be handled by decay_load_missed().
+ * 2. cpu_load(n-i) is the "old_load".
+ * 3. L is the this_rq->cpu_load[0], updated at the last time.
+ *
+ * Finally,
+ *
+ * cpu_load(n) for current tick will be handled in this turn.
*/
static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
- unsigned long pending_updates)
+ unsigned long pending_updates, int active)
{
int i, scale;
+ unsigned long tickless_load = active ? this_rq->cpu_load[0] : 0;
this_rq->nr_load_updates++;
@@ -4324,8 +4365,9 @@ static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
/* scale is effectively 1 << i now, and >> i divides by scale */
- old_load = this_rq->cpu_load[i];
+ old_load = this_rq->cpu_load[i] - tickless_load;
old_load = decay_load_missed(old_load, pending_updates - 1, i);
+ old_load += tickless_load;
new_load = this_load;
/*
* Round up the averaging division if load is increasing. This
@@ -4380,7 +4422,7 @@ static void update_idle_cpu_load(struct rq *this_rq)
pending_updates = curr_jiffies - this_rq->last_load_update_tick;
this_rq->last_load_update_tick = curr_jiffies;
- __update_cpu_load(this_rq, load, pending_updates);
+ __update_cpu_load(this_rq, load, pending_updates, 0);
}
/*
@@ -4403,7 +4445,7 @@ void update_cpu_load_nohz(void)
* We were idle, this means load 0, the current load might be
* !0 due to remote wakeups and the sort.
*/
- __update_cpu_load(this_rq, 0, pending_updates);
+ __update_cpu_load(this_rq, 0, pending_updates, 0);
}
raw_spin_unlock(&this_rq->lock);
}
@@ -4419,7 +4461,7 @@ void update_cpu_load_active(struct rq *this_rq)
* See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
*/
this_rq->last_load_update_tick = jiffies;
- __update_cpu_load(this_rq, load, 1);
+ __update_cpu_load(this_rq, load, 1, 1);
}
/*
--
1.7.9.5
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | <byungchul.park@lge.com> |
|---|---|
| Date | 2015-10-14 11:50 +0200 |
| Subject | [PATCH v4 2/2] sched: consider missed ticks in full NOHZ |
| Message-ID | <qjqR5-31B-33@gated-at.bofh.it> |
| In reply to | #1246465 |
From: Byungchul Park <byungchul.park@lge.com>
Even though the cpu is non-idle when its tick is stoped in full NOHZ,
current "update_cpu_load" code considers as if the cpu has been idle
unconditionally. It's wrong. This patch makes the "update_cpu_load"
code know if the calling path comes from full NOHZ or idle NOHZ.
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
include/linux/sched.h | 4 ++--
kernel/sched/fair.c | 4 ++--
kernel/time/tick-sched.c | 8 ++++----
3 files changed, 8 insertions(+), 8 deletions(-)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 699228b..f1b59aa 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -177,9 +177,9 @@ extern void get_iowait_load(unsigned long *nr_waiters, unsigned long *load);
extern void calc_global_load(unsigned long ticks);
#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
-extern void update_cpu_load_nohz(void);
+extern void update_cpu_load_nohz(int active);
#else
-static inline void update_cpu_load_nohz(void) { }
+static inline void update_cpu_load_nohz(int active) { }
#endif
extern unsigned long get_parent_ip(unsigned long addr);
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 26473fc..63c5ffd 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4428,7 +4428,7 @@ static void update_idle_cpu_load(struct rq *this_rq)
/*
* Called from tick_nohz_idle_exit() -- try and fix up the ticks we missed.
*/
-void update_cpu_load_nohz(void)
+void update_cpu_load_nohz(int active)
{
struct rq *this_rq = this_rq();
unsigned long curr_jiffies = READ_ONCE(jiffies);
@@ -4445,7 +4445,7 @@ void update_cpu_load_nohz(void)
* We were idle, this means load 0, the current load might be
* !0 due to remote wakeups and the sort.
*/
- __update_cpu_load(this_rq, 0, pending_updates, 0);
+ __update_cpu_load(this_rq, 0, pending_updates, active);
}
raw_spin_unlock(&this_rq->lock);
}
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 7c7ec45..515edf3 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -694,11 +694,11 @@ out:
return tick;
}
-static void tick_nohz_restart_sched_tick(struct tick_sched *ts, ktime_t now)
+static void tick_nohz_restart_sched_tick(struct tick_sched *ts, ktime_t now, int active)
{
/* Update jiffies first */
tick_do_update_jiffies64(now);
- update_cpu_load_nohz();
+ update_cpu_load_nohz(active);
calc_load_exit_idle();
touch_softlockup_watchdog();
@@ -725,7 +725,7 @@ static void tick_nohz_full_update_tick(struct tick_sched *ts)
if (can_stop_full_tick())
tick_nohz_stop_sched_tick(ts, ktime_get(), cpu);
else if (ts->tick_stopped)
- tick_nohz_restart_sched_tick(ts, ktime_get());
+ tick_nohz_restart_sched_tick(ts, ktime_get(), 1);
#endif
}
@@ -916,7 +916,7 @@ void tick_nohz_idle_exit(void)
tick_nohz_stop_idle(ts, now);
if (ts->tick_stopped) {
- tick_nohz_restart_sched_tick(ts, now);
+ tick_nohz_restart_sched_tick(ts, now, 0);
tick_nohz_account_idle_ticks(ts);
}
--
1.7.9.5
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web