Skip to contentSkip to conversation

sched: Rewrite runnable load and utilization average tracking

PATCH RESEND Superseded Yuyang Du 4 participants 23 messages Jun 16, 2015 – Jun 22, 2015 1 message not in the archive Scheduler

v8 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Yuyang Du

author
#0 lore raw

v8 cover sched: Rewrite runnable load and utilization average tracking

Hi Peter and Ingo,

Changes are made for the 8th version:

1) Rebase to the latest tip tree
2) scale_load_down the weight when doing the averages
3) change util_sum to u32

Thanks a lot for Ben's comments, which lead to this version. Thanks to Vincent for review.

Regards,
Yuyang

v7 changes:

The 7th version mostly is to accommodate the utilization load average recently merged into kernel. The general idea is as well to update the cfs_rq as a whole as opposed to only updating an entity at a time and update the cfs_rq with the only updated entity.

1) Rename utilization_load_avg to util_avg to be concise and meaningful

2) To track the cfs_rq util_avg, simply use "cfs_rq->curr != NULL" as the predicate. This should be equivalent to but simpler than aggregating each individual child sched_entity's util_avg when "cfs_rq->curr == se". Because if cfs_rq->curr != NULL, the cfs_rq->curr has to be some se.

3) Remove se's util_avg from its cfs_rq's when migrating it, this was already proposed by Morten and patches sent

3) The group entity's load average is initiated when the entity is created

4) Small nits: the entity's util_avg is removed from switched_from_fair() and task_move_group_fair().

Thanks a lot for Vincent and Morten's help for the 7th version.

Thanks,
Yuyang

v6 changes:

Many thanks to PeterZ for his review, to Dietmar, and to Fengguang for 0Day and LKP.

Rebased on v3.18-rc2.

- Unify decay_load 32 and 64 bits by mul_u64_u32_shr
- Add force option in update_tg_load_avg
- Read real-time cfs's load_avg for calc_tg_weight
- Have tg_load_avg_contrib ifdef CONFIG_FAIR_GROUP_SCHED
- Bug fix

v5 changes:

Thank Peter intensively for reviewing this patchset in detail and all his comments. And Mike for general and cgroup pipe-test. Morten, Ben, and Vincent in the discussion.

- Remove dead task and task group load_avg
- Do not update trivial delta to task_group load_avg (threshold 1/64 old_contrib)
- mul_u64_u32_shr() is used in decay_load, so on 64bit, load_sum can afford about 4353082796 (=2^64/47742/88761) entities with the highest weight (=88761) always runnable, greater than previous theoretical maximum 132845
- Various code efficiency and style changes

We carried out some performance tests (thanks to Fengguang and his LKP). The results are shown as follows. The patchset (including threepatches) is on top of mainline v3.16-rc5. We may report more perf numbers later.

Overall, this rewrite has better performance, and reduced net overhead in load average tracking, flat efficiency in multi-layer cgroup pipe-test.

v4 changes:

Thanks to Morten, Ben, and Fengguang for v4 revision.

- Insert memory barrier before writing cfs_rq->load_last_update_copy.
- Fix typos.

v3 changes:

Many thanks to Ben for v3 revision.

Regarding the overflow issue, we now have for both entity and cfs_rq:

struct sched_avg {
    .....
    u64 load_sum;
    unsigned long load_avg;
    .....
};

Given the weight for both entity and cfs_rq is:

struct load_weight {
    unsigned long weight;
    .....
};

So, load_sum's max is 47742 * load.weight (which is unsigned long), then on 32bit, it is absolutly safe. On 64bit, with unsigned long being 64bit, but we can afford about 4353082796 (=2^64/47742/88761) entities with the highest weight (=88761) always runnable, even considering we may multiply 1<<15 in decay_load64, we can still support 132845 (=4353082796/2^15) always runnable, which should be acceptible.

load_avg = load_sum / 47742 = load.weight (which is unsigned long), so it should be perfectly safe for both entity (even with arbitrary user group share) and cfs_rq on both 32bit and 64bit. Originally, we saved this division, but have to get it back because of the overflow issue on 32bit (actually load average itself is safe from overflow, but the rest of the code referencing it always uses long, such as cpu_load, etc., which prevents it from saving).

- Fix overflow issue both for entity and cfs_rq on both 32bit and 64bit.
- Track all entities (both task and group entity) due to group entity's clock issue. This actually improves code simplicity.
- Make a copy of cfs_rq sched_avg's last_update_time, to read an intact 64bit variable on 32bit machine when in data race (hope I did it right).
- Minor fixes and code improvement.

v2 changes:

Thanks to PeterZ and Ben for their help in fixing the issues and improving the quality, and Fengguang and his 0Day in finding compile errors in different configurations for version 2.

- Batch update the tg->load_avg, making sure it is up-to-date before update_cfs_shares
- Remove migrating task from the old CPU/cfs_rq, and do so with atomic operations

Yuyang Du (4):
sched: Remove rq's runnable avg
sched: Rewrite runnable load and utilization average tracking
sched: Init cfs_rq's sched_entity load average
sched: Remove task and group entity load when they are dead

 include/linux/sched.h |   40 ++-
 kernel/sched/core.c   |    5 +-
 kernel/sched/debug.c  |   42 +---
 kernel/sched/fair.c   |  668 ++++++++++++++++---------------------------------
 kernel/sched/sched.h  |   32 +--
 5 files changed, 261 insertions(+), 526 deletions(-)
Signature · 1 line
1.7.9.5
author
#1 lore raw

PATCH v8 1/4 sched: Remove rq's runnable avg

The current rq->avg is not used at all since its merge into kernel, and the code is in the scheduler's hot path, so remove it.

---
 kernel/sched/debug.c |    7 +------
 kernel/sched/fair.c  |   25 ++++---------------------
 kernel/sched/sched.h |    2 --
 3 files changed, 5 insertions(+), 29 deletions(-)
kernel/sched/debug.c +1 -6
index f94724e..ca39cb7 100644
@@ -68,13 +68,8 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
 #define PN(F) \
 	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", #F, SPLIT_NS((long long)F))
 
-	if (!se) {
-		struct sched_avg *avg = &cpu_rq(cpu)->avg;
-		P(avg->runnable_avg_sum);
-		P(avg->avg_period);
+	if (!se)
 		return;
-	}
-
 
 	PN(se->exec_start);
 	PN(se->vruntime);
kernel/sched/fair.c +4 -21
index d597aea..56c1b94 100644
@@ -2713,19 +2713,12 @@ static inline void __update_group_entity_contrib(struct sched_entity *se)
 	}
 }
 
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
-{
-	__update_entity_runnable_avg(rq_clock_task(rq), cpu_of(rq), &rq->avg,
-			runnable, runnable);
-	__update_tg_runnable_avg(&rq->avg, &rq->cfs);
-}
 #else /* CONFIG_FAIR_GROUP_SCHED */
 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
 						 int force_update) {}
 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
 						  struct cfs_rq *cfs_rq) {}
 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 static inline void __update_task_entity_contrib(struct sched_entity *se)
@@ -2929,7 +2922,6 @@ static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
  */
 void idle_enter_fair(struct rq *this_rq)
 {
-	update_rq_runnable_avg(this_rq, 1);
 }
 
 /*
@@ -2939,7 +2931,6 @@ void idle_enter_fair(struct rq *this_rq)
  */
 void idle_exit_fair(struct rq *this_rq)
 {
-	update_rq_runnable_avg(this_rq, 0);
 }
 
 static int idle_balance(struct rq *this_rq);
@@ -2948,7 +2939,6 @@ static int idle_balance(struct rq *this_rq);
 
 static inline void update_entity_load_avg(struct sched_entity *se,
 					  int update_cfs_rq) {}
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
 					   struct sched_entity *se,
 					   int wakeup) {}
@@ -4247,10 +4237,9 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_entity_load_avg(se, 1);
 	}
 
-	if (!se) {
-		update_rq_runnable_avg(rq, rq->nr_running);
+	if (!se)
 		add_nr_running(rq, 1);
-	}
+
 	hrtick_update(rq);
 }
 
@@ -4308,10 +4297,9 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_entity_load_avg(se, 1);
 	}
 
-	if (!se) {
+	if (!se)
 		sub_nr_running(rq, 1);
-		update_rq_runnable_avg(rq, 1);
-	}
+
 	hrtick_update(rq);
 }
 
@@ -6016,9 +6004,6 @@ static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
 		 */
 		if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
 			list_del_leaf_cfs_rq(cfs_rq);
-	} else {
-		struct rq *rq = rq_of(cfs_rq);
-		update_rq_runnable_avg(rq, rq->nr_running);
 	}
 }
 
@@ -8002,8 +7987,6 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 
 	if (numabalancing_enabled)
 		task_tick_numa(rq, curr);
-
-	update_rq_runnable_avg(rq, 1);
 }
 
 /*
kernel/sched/sched.h +0 -2
index f10a445..d465a5c 100644
@@ -595,8 +595,6 @@ struct rq {
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/* list of leaf cfs_rq on this cpu: */
 	struct list_head leaf_cfs_rq_list;
-
-	struct sched_avg avg;
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 	/*
Signature · 1 line
1.7.9.5
#2 lore raw

Re: [PATCH v8 1/4] sched: Remove rq's runnable avg

Hi Yuyang,

Quoted 2 lines · Yuyang Du

The current rq->avg is not used at all since its merge into kernel, and the code is in the scheduler's hot path, so remove it.

are you sure that this is the case? I was always under the impression that w/ CONFIG_FAIR_GROUP_SCHED=y rq->avg (runnable_avg_sum, avg_period) is used to calculate contrib in __update_tg_runnable_avg() for the root group (cfs_rq->tg->css.id = 1).

On tg's w/ cfs_rq->tg->css.id > 1, se->avg (runnable_avg_sum, avg_period) is used instead but we simply don't have a tg related se for the root group. IMHO, that's why we have this rq::avg.

I understand that w/ the second patch in your series you don't need rq::avg any more.

[...]

-- Dietmar

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

author
#3 lore raw

Re: [PATCH v8 1/4] sched: Remove rq's runnable avg

Hi Dietmar,

Quoted 6 lines · Dietmar Eggemann

Hi Yuyang,

Quoted 2 lines · Yuyang Du

The current rq->avg is not used at all since its merge into kernel, and the code is in the scheduler's hot path, so remove it.

Quoted 8 lines

are you sure that this is the case? I was always under the impression that w/ CONFIG_FAIR_GROUP_SCHED=y rq->avg (runnable_avg_sum, avg_period) is used to calculate contrib in __update_tg_runnable_avg() for the root group (cfs_rq->tg->css.id = 1).

On tg's w/ cfs_rq->tg->css.id > 1, se->avg (runnable_avg_sum, avg_period) is used instead but we simply don't have a tg related se for the root group. IMHO, that's why we have this rq::avg.

Yes, I agree. But the root group's avg is not useful anyway. If it is, we sure should keep it.

Quoted 2 lines

I understand that w/ the second patch in your series you don't need rq::avg any more.

And the rq->avg can be replaced by the root cfs_rq's util_avg, too.

Thanks,
Yuyang
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#4 lore raw

Re: [PATCH v8 1/4] sched: Remove rq's runnable avg

Quoted 14 lines · Yuyang Du

Hi Dietmar,

Quoted 11 lines · Dietmar Eggemann

Hi Yuyang,

Quoted 2 lines · Yuyang Du

The current rq->avg is not used at all since its merge into kernel, and the code is in the scheduler's hot path, so remove it.

are you sure that this is the case? I was always under the impression that w/ CONFIG_FAIR_GROUP_SCHED=y rq->avg (runnable_avg_sum, avg_period) is used to calculate contrib in __update_tg_runnable_avg() for the root group (cfs_rq->tg->css.id = 1).

Quoted 6 lines
Quoted 3 lines

On tg's w/ cfs_rq->tg->css.id > 1, se->avg (runnable_avg_sum, avg_period) is used instead but we simply don't have a tg related se for the root group. IMHO, that's why we have this rq::avg.

Yes, I agree. But the root group's avg is not useful anyway. If it is, we sure should keep it.

You're right. Both consumers of tg->load_avg and tg->runnable_avg (__update_group_entity_contrib() and calc_tg_weight()) are never called w/ cfs_rq->tg->css.id < 2 .

I did some tests w/ task groups on my ARM platform. The system survives an appropriate BUG_ON in both functions just fine.

Maybe you can put a little bit more information why rq::avg isn't needed even in the CONFIG_FAIR_GROUP_SCHED=y case into the patch header?

I assume getting rid of extra code in the current per-entity load-tracking code is a good thing. And this patch is probably less complicated to understand than your second one :-)

Quoted 5 lines
Quoted 3 lines

I understand that w/ the second patch in your series you don't need rq::avg any more.

And the rq->avg can be replaced by the root cfs_rq's util_avg, too.

Given the fact that it is not used this wouldn't be necessary.

[...]

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

author
#5 lore raw

PATCH v8 2/4 sched: Rewrite runnable load and utilization average tracking

In reply to Yuyang Du

The idea of runnable load average (let runnable time contribute to weight) was proposed by Paul Turner, and it is still followed by this rewrite. This rewrite aims to solve the following issues:

1. cfs_rq's load average (namely runnable_load_avg and blocked_load_avg) is updated at the granularity of an entity at a time, which results in the cfs_rq's load average is stale or partially updated: at any time, only one entity is up to date, all other entities are effectively lagging behind. This is undesirable.

To illustrate, if we have n runnable entities in the cfs_rq, as time elapses, they certainly become outdated:

t0: cfs_rq { e1_old, e2_old, ..., en_old }

and when we update:

t1: update e1, then we have cfs_rq { e1_new, e2_old, ..., en_old }

t2: update e2, then we have cfs_rq { e1_old, e2_new, ..., en_old }

...

We solve this by combining all runnable entities' load averages together in cfs_rq's avg, and update the cfs_rq's avg as a whole. This is based on the fact that if we regard the update as a function, then:

w * update(e) = update(w * e) and

update(e1) + update(e2) = update(e1 + e2), then

w1 * update(e1) + w2 * update(e2) = update(w1 * e1 + w2 * e2)

therefore, by this rewrite, we have an entirely updated cfs_rq at the time we update it:

t1: update cfs_rq { e1_new, e2_new, ..., en_new }

t2: update cfs_rq { e1_new, e2_new, ..., en_new }

...

2. cfs_rq's load average is different between top rq->cfs_rq and other task_group's per CPU cfs_rqs in whether or not blocked_load_average contributes to the load.

The basic idea behind runnable load average (the same for utilization) is that the blocked state is taken into account as opposed to only accounting for the currently runnable state. Therefore, the average should include both the runnable/running and blocked load averages. This rewrite does that.

In addition, we also combine runnable/running and blocked averages of all entities into the cfs_rq's average, and update it together at once. This is based on the fact that:

update(runnable) + update(blocked) = update(runnable + blocked)

This significantly reduces the codes as we don't need to separately maintain/update runnable/running load and blocked load.

3. How task_group entities' share is calculated is complex.

We reduce the complexity in this rewrite to allow a very simple rule:
the task_group's load_avg is aggregated from its per CPU cfs_rqs's load_avgs. Then group entity's weight is simply proportional to its own cfs_rq's load_avg / task_group's load_avg. To illustrate,

if a task_group has { cfs_rq1, cfs_rq2, ..., cfs_rqn }, then,

task_group_avg = cfs_rq1_avg + cfs_rq2_avg + ... + cfs_rqn_avg, then

cfs_rqx's entity's share = cfs_rqx_avg / task_group_avg * task_group's share

To sum up, this rewrite in principle is equivalent to the current one, but fixes the issues described above. Turns out, it significantly reduces the code complexity and hence increases clarity and efficiency. In addition, the new averages are more smooth/continuous (no spurious spikes and valleys) and updated more consistently and quickly to reflect the load dynamics. As a result, we have less load tracking overhead, better performance, and especially better power efficiency due to more balanced load.

---
 include/linux/sched.h |   40 ++--
 kernel/sched/core.c   |    3 -
 kernel/sched/debug.c  |   35 +--
 kernel/sched/fair.c   |  625 ++++++++++++++++---------------------------------
 kernel/sched/sched.h  |   28 +--
 5 files changed, 240 insertions(+), 491 deletions(-)
include/linux/sched.h +17 -23
index af0eeba..8b4bc4f 100644
@@ -1183,29 +1183,23 @@ struct load_weight {
 	u32 inv_weight;
 };
 
+/*
+ * The load_avg/util_avg represents an infinite geometric series:
+ * 1) load_avg describes the amount of time that a sched_entity
+ * is runnable on a rq. It is based on both load_sum and the
+ * weight of the task.
+ * 2) util_avg describes the amount of time that a sched_entity
+ * is running on a CPU. It is based on util_sum and is scaled
+ * in the range [0..SCHED_LOAD_SCALE].
+ * The 64 bit load_sum can:
+ * 1) for cfs_rq, afford 4353082796 (=2^64/47742/88761) entities with
+ * the highest weight (=88761) always runnable, we should not overflow
+ * 2) for entity, support any load.weight always runnable
+ */
 struct sched_avg {
-	u64 last_runnable_update;
-	s64 decay_count;
-	/*
-	 * utilization_avg_contrib describes the amount of time that a
-	 * sched_entity is running on a CPU. It is based on running_avg_sum
-	 * and is scaled in the range [0..SCHED_LOAD_SCALE].
-	 * load_avg_contrib described the amount of time that a sched_entity
-	 * is runnable on a rq. It is based on both runnable_avg_sum and the
-	 * weight of the task.
-	 */
-	unsigned long load_avg_contrib, utilization_avg_contrib;
-	/*
-	 * These sums represent an infinite geometric series and so are bound
-	 * above by 1024/(1-y).  Thus we only need a u32 to store them for all
-	 * choices of y < 1-2^(-32)*1024.
-	 * running_avg_sum reflects the time that the sched_entity is
-	 * effectively running on the CPU.
-	 * runnable_avg_sum represents the amount of time a sched_entity is on
-	 * a runqueue which includes the running time that is monitored by
-	 * running_avg_sum.
-	 */
-	u32 runnable_avg_sum, avg_period, running_avg_sum;
+	u64 last_update_time, load_sum;
+	u32 util_sum, period_contrib;
+	unsigned long load_avg, util_avg;
 };
 
 #ifdef CONFIG_SCHEDSTATS
@@ -1271,7 +1265,7 @@ struct sched_entity {
 #endif
 
 #ifdef CONFIG_SMP
-	/* Per-entity load-tracking */
+	/* Per entity load average tracking */
 	struct sched_avg	avg;
 #endif
 };
kernel/sched/core.c +0 -3
index 921a754..724de5b 100644
@@ -1828,9 +1828,6 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 	p->se.prev_sum_exec_runtime	= 0;
 	p->se.nr_migrations		= 0;
 	p->se.vruntime			= 0;
-#ifdef CONFIG_SMP
-	p->se.avg.decay_count		= 0;
-#endif
 	INIT_LIST_HEAD(&p->se.group_node);
 
 #ifdef CONFIG_SCHEDSTATS
kernel/sched/debug.c +11 -24
index ca39cb7..db3e875 100644
@@ -88,12 +88,8 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
 #endif
 	P(se->load.weight);
 #ifdef CONFIG_SMP
-	P(se->avg.runnable_avg_sum);
-	P(se->avg.running_avg_sum);
-	P(se->avg.avg_period);
-	P(se->avg.load_avg_contrib);
-	P(se->avg.utilization_avg_contrib);
-	P(se->avg.decay_count);
+	P(se->avg.load_avg);
+	P(se->avg.util_avg);
 #endif
 #undef PN
 #undef P
@@ -207,21 +203,13 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
 	SEQ_printf(m, "  .%-30s: %d\n", "nr_running", cfs_rq->nr_running);
 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);
 #ifdef CONFIG_SMP
-	SEQ_printf(m, "  .%-30s: %ld\n", "runnable_load_avg",
-			cfs_rq->runnable_load_avg);
-	SEQ_printf(m, "  .%-30s: %ld\n", "blocked_load_avg",
-			cfs_rq->blocked_load_avg);
-	SEQ_printf(m, "  .%-30s: %ld\n", "utilization_load_avg",
-			cfs_rq->utilization_load_avg);
+	SEQ_printf(m, "  .%-30s: %lu\n", "load_avg",
+			cfs_rq->avg.load_avg);
+	SEQ_printf(m, "  .%-30s: %lu\n", "util_avg",
+			cfs_rq->avg.util_avg);
 #ifdef CONFIG_FAIR_GROUP_SCHED
-	SEQ_printf(m, "  .%-30s: %ld\n", "tg_load_contrib",
-			cfs_rq->tg_load_contrib);
-	SEQ_printf(m, "  .%-30s: %d\n", "tg_runnable_contrib",
-			cfs_rq->tg_runnable_contrib);
 	SEQ_printf(m, "  .%-30s: %ld\n", "tg_load_avg",
 			atomic_long_read(&cfs_rq->tg->load_avg));
-	SEQ_printf(m, "  .%-30s: %d\n", "tg->runnable_avg",
-			atomic_read(&cfs_rq->tg->runnable_avg));
 #endif
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
@@ -632,12 +620,11 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
 
 	P(se.load.weight);
 #ifdef CONFIG_SMP
-	P(se.avg.runnable_avg_sum);
-	P(se.avg.running_avg_sum);
-	P(se.avg.avg_period);
-	P(se.avg.load_avg_contrib);
-	P(se.avg.utilization_avg_contrib);
-	P(se.avg.decay_count);
+	P(se.avg.load_sum);
+	P(se.avg.util_sum);
+	P(se.avg.load_avg);
+	P(se.avg.util_avg);
+	P(se.avg.last_update_time);
 #endif
 	P(policy);
 	P(prio);
kernel/sched/fair.c +203 -422

961 lines not on this page · raw message

kernel/sched/sched.h +9 -19
index d465a5c..3dfec8d 100644
@@ -245,7 +245,6 @@ struct task_group {
 
 #ifdef	CONFIG_SMP
 	atomic_long_t load_avg;
-	atomic_t runnable_avg;
 #endif
 #endif
 
@@ -366,27 +365,18 @@ struct cfs_rq {
 
 #ifdef CONFIG_SMP
 	/*
-	 * CFS Load tracking
-	 * Under CFS, load is tracked on a per-entity basis and aggregated up.
-	 * This allows for the description of both thread and group usage (in
-	 * the FAIR_GROUP_SCHED case).
-	 * runnable_load_avg is the sum of the load_avg_contrib of the
-	 * sched_entities on the rq.
-	 * blocked_load_avg is similar to runnable_load_avg except that its
-	 * the blocked sched_entities on the rq.
-	 * utilization_load_avg is the sum of the average running time of the
-	 * sched_entities on the rq.
+	 * CFS load tracking
 	 */
-	unsigned long runnable_load_avg, blocked_load_avg, utilization_load_avg;
-	atomic64_t decay_counter;
-	u64 last_decay;
-	atomic_long_t removed_load;
-
+	struct sched_avg avg;
 #ifdef CONFIG_FAIR_GROUP_SCHED
-	/* Required to track per-cpu representation of a task_group */
-	u32 tg_runnable_contrib;
-	unsigned long tg_load_contrib;
+	unsigned long tg_load_avg_contrib;
+#endif
+	atomic_long_t removed_load_avg, removed_util_avg;
+#ifndef CONFIG_64BIT
+	u64 load_last_update_time_copy;
+#endif
 
+#ifdef CONFIG_FAIR_GROUP_SCHED
 	/*
 	 *   h_load = weight * f(tg)
 	 *
Signature · 1 line
1.7.9.5
#6 lore raw

Hi Yuyang,

Quoted 48 lines · Yuyang Du
kernel/sched/fair.c +1 -31
@@ -5977,36 +5786,6 @@ static void attach_tasks(struct lb_env *env)
 }
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-/*
- * update tg->load_weight by folding this cpu's load_avg
- */
-static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
-{
-	struct sched_entity *se = tg->se[cpu];
-	struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];
-
-	/* throttled entities do not contribute to load */
-	if (throttled_hierarchy(cfs_rq))
-		return;
-
-	update_cfs_rq_blocked_load(cfs_rq, 1);
-
-	if (se) {
-		update_entity_load_avg(se, 1);
-		/*
-		 * We pivot on our runnable average having decayed to zero for
-		 * list removal.  This generally implies that all our children
-		 * have also been removed (modulo rounding error or bandwidth
-		 * control); however, such cases are rare and we can fix these
-		 * at enqueue.
-		 *
-		 * TODO: fix up out-of-order children on enqueue.
-		 */
-		if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
-			list_del_leaf_cfs_rq(cfs_rq);
-	}
-}
-
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
@@ -6015,17 +5794,17 @@ static void update_blocked_averages(int cpu)
 
 	raw_spin_lock_irqsave(&rq->lock, flags);
 	update_rq_clock(rq);
+
 	/*
 	 * Iterates the task_group tree in a bottom up fashion, see
 	 * list_add_leaf_cfs_rq() for details.
 	 */
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		/*

kernel/sched/fair.c static void update_blocked_averages(int cpu) · line 5807

Quoted 10 lines
kernel/sched/fair.c +5 -5
-		 * Note: We may want to consider periodically releasing
-		 * rq->lock about these updates so that creating many task
-		 * groups does not result in continually extending hold time.
-		 */
-		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
+		/* throttled entities do not contribute to load */
+		if (throttled_hierarchy(cfs_rq))
+			continue;
+
+		update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);

We iterates task_group tree(actually the corresponding cfs_rq tree on that cpu), because we want to do a bottom-up update. And we want a bottom-up update, because we want to update the weigthed_cpuload().

__update_blocked_averages_cpu(tg, cpu) does three things:

Let's say:
cfs_rq = tg->cfs_rq[cpu]
se = tg->cfs_rq[cpu]
pcfs_rq = cfs_rq_of(se) ,which is the parent of cfs_rq.

1. update cfs_rq->blocked_load_avg, and its contrib to its task group.
2. update se->avg and calculate the deltas of se->avg.*_avg_contrib.
3. update pcfs_rq->*_load_avg with the deltas in step 2

In this way, __update_blocked_averages_cpu(tg, cpu) can contributes tg's load changes to its parent. So that update_blocked_averages() can aggregate all load changes to weighted_cpuload().

However, update_cfs_rq_load_avg() only updates cfs_rq->avg, the change won't be contributed or aggregated to cfs_rq's parent in the for_each_leaf_cfs_rq loop, therefore that's actually not a bottom-up update.

To fix this, I think we can add a update_cfs_shares(cfs_rq) after update_cfs_rq_load_avg(). Like:

for_each_leaf_cfs_rq(rq, cfs_rq) {
- /*
- * Note: We may want to consider periodically releasing
- * rq->lock about these updates so that creating many task
- * groups does not result in continually extending hold time.
- */
- __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
+ /* throttled entities do not contribute to load */
+ if (throttled_hierarchy(cfs_rq))
+ continue;
+
+ update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
+ update_cfs_share(cfs_rq);
}

However, I think update_cfs_share isn't cheap, because it may do a bottom-up update once called. So how about just update the root cfs_rq? Like:

- /*
- * Iterates the task_group tree in a bottom up fashion, see
- * list_add_leaf_cfs_rq() for details.
- */
- for_each_leaf_cfs_rq(rq, cfs_rq) {
- /*
- * Note: We may want to consider periodically releasing
- * rq->lock about these updates so that creating many task
- * groups does not result in continually extending hold time.
- */
- __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
- }
+ update_cfs_rq_load_avg(rq_clock_task(rq), rq->cfs_rq);

Thanks and Best Regards,
Boqun

author
#7 lore raw
Quoted 30 lines · Boqun Feng

However, update_cfs_rq_load_avg() only updates cfs_rq->avg, the change won't be contributed or aggregated to cfs_rq's parent in the for_each_leaf_cfs_rq loop, therefore that's actually not a bottom-up update.

To fix this, I think we can add a update_cfs_shares(cfs_rq) after update_cfs_rq_load_avg(). Like:

kernel/sched/fair.c +6 -6
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		/*
-		 * Note: We may want to consider periodically releasing
-		 * rq->lock about these updates so that creating many task
-		 * groups does not result in continually extending hold time.
-		 */
-		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
+		/* throttled entities do not contribute to load */
+		if (throttled_hierarchy(cfs_rq))
+			continue;
+
+		update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
+		update_cfs_share(cfs_rq);
 	}

However, I think update_cfs_share isn't cheap, because it may do a bottom-up update once called. So how about just update the root cfs_rq? Like:

(quoted diff) +0 -3
-	/*
-	 * Iterates the task_group tree in a bottom up fashion, see
-	 * list_add_leaf_cfs_rq() for details.

Review

Quoted 10 lines
(quoted diff) +1 -9
-	 */
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		/*
-		 * Note: We may want to consider periodically releasing
-		 * rq->lock about these updates so that creating many task
-		 * groups does not result in continually extending hold time.
-		 */
-		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
-	}
+	update_cfs_rq_load_avg(rq_clock_task(rq), rq->cfs_rq);

Hi Boqun,

Did I get you right:

This rewrite patch does not NEED to aggregate entity's load to cfs_rq, but rather directly update the cfs_rq's load (both runnable and blocked), so there is NO NEED to iterate all of the cfs_rqs.

So simply updating the top cfs_rq is already equivalent to the stock.

It is better if we iterate the cfs_rq to update the actually weight (update_cfs_share), because the weight may have already changed, which would in turn change the load. But update_cfs_share is not cheap.

Right?

Thanks,
Yuyang

#8 lore raw

Hi Yuyang,

Quoted 44 lines · Yuyang Du
Quoted 30 lines · Boqun Feng

However, update_cfs_rq_load_avg() only updates cfs_rq->avg, the change won't be contributed or aggregated to cfs_rq's parent in the for_each_leaf_cfs_rq loop, therefore that's actually not a bottom-up update.

To fix this, I think we can add a update_cfs_shares(cfs_rq) after update_cfs_rq_load_avg(). Like:

kernel/sched/fair.c +6 -6
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		/*
-		 * Note: We may want to consider periodically releasing
-		 * rq->lock about these updates so that creating many task
-		 * groups does not result in continually extending hold time.
-		 */
-		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
+		/* throttled entities do not contribute to load */
+		if (throttled_hierarchy(cfs_rq))
+			continue;
+
+		update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
+		update_cfs_share(cfs_rq);
 	}

However, I think update_cfs_share isn't cheap, because it may do a bottom-up update once called. So how about just update the root cfs_rq? Like:

(quoted diff) +0 -3
-	/*
-	 * Iterates the task_group tree in a bottom up fashion, see
-	 * list_add_leaf_cfs_rq() for details.

Review

Quoted 10 lines
(quoted diff) +1 -9
-	 */
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		/*
-		 * Note: We may want to consider periodically releasing
-		 * rq->lock about these updates so that creating many task
-		 * groups does not result in continually extending hold time.
-		 */
-		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
-	}
+	update_cfs_rq_load_avg(rq_clock_task(rq), rq->cfs_rq);

Hi Boqun,

Quoted 5 lines

Did I get you right:

This rewrite patch does not NEED to aggregate entity's load to cfs_rq, but rather directly update the cfs_rq's load (both runnable and blocked), so there is NO NEED to iterate all of the cfs_rqs.

Actually, I'm not sure whether we NEED to aggregate or NOT.

Quoted 3 lines

So simply updating the top cfs_rq is already equivalent to the stock.

The stock does have a bottom up update, so simply updating the top cfs_rq is not equivalent to it. Simply updateing the top cfs_rq is equivalent to the rewrite patch, because the rewrite patch lacks of the aggregation.

Quoted 5 lines

It is better if we iterate the cfs_rq to update the actually weight (update_cfs_share), because the weight may have already changed, which would in turn change the load. But update_cfs_share is not cheap.

Right?

You get me right for most part ;-)

My points are:

1. We *may not* need to aggregate entity's load to cfs_rq in update_blocked_averages(), simply updating the top cfs_rq may be just fine, but I'm not sure, so scheduler experts' insights are needed here.

2. Whether we need to aggregate or not, the update_blocked_averages() in the rewrite patch could be improved. If we need to aggregate, we have to add something like update_cfs_shares(). If we don't need, we can just replace the loop with one update_cfs_rq_load_avg() on root cfs_rq.

I think we'd better to figure out the "may not" part in point 1 first to get a reasonable implemenation of update_blocked_averages().

Is that clear now?

Thanks and Best Regards,
Boqun

author
#9 lore raw
Quoted 10 lines · Boqun Feng
Quoted 4 lines

This rewrite patch does not NEED to aggregate entity's load to cfs_rq, but rather directly update the cfs_rq's load (both runnable and blocked), so there is NO NEED to iterate all of the cfs_rqs.

Actually, I'm not sure whether we NEED to aggregate or NOT.

Quoted 3 lines

So simply updating the top cfs_rq is already equivalent to the stock.

Ok. By aggregate, the rewrite patch does not need it, because the cfs_rq's load is calculated at once with all its runnable and blocked tasks counted, assuming the all children's weights are up-to-date, of course. Please refer to the changelog to get an idea.

Quoted 5 lines

The stock does have a bottom up update, so simply updating the top cfs_rq is not equivalent to it. Simply updateing the top cfs_rq is equivalent to the rewrite patch, because the rewrite patch lacks of the aggregation.

It is not the rewrite patch "lacks" aggregation, it is needless. The stock has to do a bottom-up update and aggregate, because 1) it updates the load at an entity granularity, 2) the blocked load is separate.

Quoted 6 lines
Quoted 5 lines

It is better if we iterate the cfs_rq to update the actually weight (update_cfs_share), because the weight may have already changed, which would in turn change the load. But update_cfs_share is not cheap.

Right?

Quoted 7 lines

You get me right for most part ;-)

My points are:

1. We *may not* need to aggregate entity's load to cfs_rq in update_blocked_averages(), simply updating the top cfs_rq may be just fine, but I'm not sure, so scheduler experts' insights are needed here.

Then I don't need to say anything about this.

Quoted 4 lines

2. Whether we need to aggregate or not, the update_blocked_averages() in the rewrite patch could be improved. If we need to aggregate, we have to add something like update_cfs_shares(). If we don't need, we can just replace the loop with one update_cfs_rq_load_avg() on root cfs_rq.

If update_cfs_shares() is done here, it is good, but probably not necessary though. However, we do need to update_tg_load_avg() here, because if cfs_rq's load change, the parent tg's load_avg should change too. I will upload a next version soon.

In addition, an update to the stress + dbench test case:

I have a Core i7, not a Xeon Nehalem, and I have a patch that may not impact the result. Then, the dbench runs at very low CPU utilization ~1%. Boqun said this may result from cgroup control, the dbench I/O is low.

Anyway, I can't reproduce the results, the CPU0's util is 92+%, and other CPUs have ~100% util.

Thanks,
Yuyang
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#10 lore raw

Hi Yuyang,

Quoted 18 lines · Yuyang Du
Quoted 10 lines · Boqun Feng
Quoted 4 lines

This rewrite patch does not NEED to aggregate entity's load to cfs_rq, but rather directly update the cfs_rq's load (both runnable and blocked), so there is NO NEED to iterate all of the cfs_rqs.

Actually, I'm not sure whether we NEED to aggregate or NOT.

Quoted 3 lines

So simply updating the top cfs_rq is already equivalent to the stock.

Ok. By aggregate, the rewrite patch does not need it, because the cfs_rq's load is calculated at once with all its runnable and blocked tasks counted, assuming the all children's weights are up-to-date, of course. Please refer to the changelog to get an idea.

Quoted 1 line
Quoted 8 lines
Quoted 4 lines

The stock does have a bottom up update, so simply updating the top cfs_rq is not equivalent to it. Simply updateing the top cfs_rq is equivalent to the rewrite patch, because the rewrite patch lacks of the aggregation.

It is not the rewrite patch "lacks" aggregation, it is needless. The stock has to do a bottom-up update and aggregate, because 1) it updates the load at an entity granularity, 2) the blocked load is separate.

Yep, you are right, the aggregation is not necessary.

Let me see if I understand you, in the rewrite, when we update_cfs_rq_load_avg() we need neither to aggregate child's load_avg, nor to update cfs_rq->load.weight. Because:

1) For the load before cfs_rq->last_update_time, it's already in the ->load_avg, and decay will do the job.
2) For the load from cfs_rq->last_update_time to now, we calculate with cfs_rq->load.weight, and the weight should be weight at ->last_update_time rather than now.

Right?

Quoted 17 lines
Quoted 7 lines
Quoted 6 lines

It is better if we iterate the cfs_rq to update the actually weight (update_cfs_share), because the weight may have already changed, which would in turn change the load. But update_cfs_share is not cheap.

Right?

Quoted 7 lines

You get me right for most part ;-)

My points are:

1. We *may not* need to aggregate entity's load to cfs_rq in update_blocked_averages(), simply updating the top cfs_rq may be just fine, but I'm not sure, so scheduler experts' insights are needed here.

Then I don't need to say anything about this.

Quoted 7 lines
Quoted 4 lines

2. Whether we need to aggregate or not, the update_blocked_averages() in the rewrite patch could be improved. If we need to aggregate, we have to add something like update_cfs_shares(). If we don't need, we can just replace the loop with one update_cfs_rq_load_avg() on root cfs_rq.

If update_cfs_shares() is done here, it is good, but probably not necessary though. However, we do need to update_tg_load_avg() here, because if cfs_rq's

We may have another problem even we udpate_tg_load_avg(), because after the loop, for each cfs_rq, ->load.weight is not up-to-date, right? So next time before we update_cfs_rq_load_avg(), we need to guarantee that the cfs_rq->load.weight is already updated, right? And IMO, we don't have that guarantee yet, do we?

Quoted 11 lines

load change, the parent tg's load_avg should change too. I will upload a next version soon.

In addition, an update to the stress + dbench test case:

I have a Core i7, not a Xeon Nehalem, and I have a patch that may not impact the result. Then, the dbench runs at very low CPU utilization ~1%. Boqun said this may result from cgroup control, the dbench I/O is low.

Anyway, I can't reproduce the results, the CPU0's util is 92+%, and other CPUs have ~100% util.

Thank you for looking into that problem, and I will test with your new version of patch ;-)

Thanks,
Boqun

Quoted 3 lines

Thanks,
Yuyang

author
#11 lore raw
Quoted 10 lines · Boqun Feng
Quoted 3 lines

It is not the rewrite patch "lacks" aggregation, it is needless. The stock has to do a bottom-up update and aggregate, because 1) it updates the load at an entity granularity, 2) the blocked load is separate.

Yep, you are right, the aggregation is not necessary.

Let me see if I understand you, in the rewrite, when we update_cfs_rq_load_avg() we need neither to aggregate child's load_avg, nor to update cfs_rq->load.weight. Because:

Quoted 7 lines

1) For the load before cfs_rq->last_update_time, it's already in the ->load_avg, and decay will do the job.
2) For the load from cfs_rq->last_update_time to now, we calculate with cfs_rq->load.weight, and the weight should be weight at ->last_update_time rather than now.

Right?

Yes.

Quoted 8 lines
Quoted 2 lines

If update_cfs_shares() is done here, it is good, but probably not necessary though. However, we do need to update_tg_load_avg() here, because if cfs_rq's

We may have another problem even we udpate_tg_load_avg(), because after the loop, for each cfs_rq, ->load.weight is not up-to-date, right? So next time before we update_cfs_rq_load_avg(), we need to guarantee that the cfs_rq->load.weight is already updated, right? And IMO, we don't have that guarantee yet, do we?

If we update weight, we must update load_avg. But if we update load_avg, we may need to update weight. Yes, your comment here is valid, but we already update the shares as needed in the cases when they are "active", update_blocked_averages() is largely for inactive group entities, so we should be fine here.

Quoted 9 lines
Quoted 9 lines

load change, the parent tg's load_avg should change too. I will upload a next version soon.

In addition, an update to the stress + dbench test case:

I have a Core i7, not a Xeon Nehalem, and I have a patch that may not impact the result. Then, the dbench runs at very low CPU utilization ~1%. Boqun said this may result from cgroup control, the dbench I/O is low.

Quoted 5 lines
Quoted 2 lines

Anyway, I can't reproduce the results, the CPU0's util is 92+%, and other CPUs have ~100% util.

Thank you for looking into that problem, and I will test with your new version of patch ;-)

That would be good. I played the dbench "as is", and its output looks pretty fine.

Thanks,
Yuyang
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

author
#12 lore raw

PATCH v8 3/4 sched: Init cfs_rq's sched_entity load average

In reply to Yuyang Du

The runnable load and utilization averages of cfs_rq's sched_entity were not initiated. Like done to a task, give new cfs_rq' sched_entity start values to heavy its load in infant time.

---
 kernel/sched/core.c  |    2 +-
 kernel/sched/fair.c  |   11 ++++++-----
 kernel/sched/sched.h |    2 +-
 3 files changed, 8 insertions(+), 7 deletions(-)
kernel/sched/core.c +1 -1
index 724de5b..c8dad9b 100644
@@ -2112,7 +2112,7 @@ void wake_up_new_task(struct task_struct *p)
 #endif
 
 	/* Initialize new task's runnable average */
-	init_task_runnable_average(p);
+	init_entity_runnable_average(&p->se);
 	rq = __task_rq_lock(p);
 	activate_task(rq, p, 0);
 	p->on_rq = TASK_ON_RQ_QUEUED;
kernel/sched/fair.c +6 -5
index f336f6e..08ab789 100644
@@ -672,10 +672,10 @@ static unsigned long task_h_load(struct task_struct *p);
 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
 
-/* Give new task start runnable values to heavy its load in infant time */
-void init_task_runnable_average(struct task_struct *p)
+/* Give new sched_entity start runnable values to heavy its load in infant time */
+void init_entity_runnable_average(struct sched_entity *se)
 {
-	struct sched_avg *sa = &p->se.avg;
+	struct sched_avg *sa = &se->avg;
 
 	sa->last_update_time = 0;
 	/*
@@ -684,14 +684,14 @@ void init_task_runnable_average(struct task_struct *p)
 	 * will definitely be update (after enqueue).
 	 */
 	sa->period_contrib = 1023;
-	sa->load_avg = scale_load_down(p->se.load.weight);
+	sa->load_avg = scale_load_down(se->load.weight);
 	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
 	sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
 	sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
 	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 #else
-void init_task_runnable_average(struct task_struct *p)
+void init_entity_runnable_average(struct sched_entity *se)
 {
 }
 #endif
@@ -8036,6 +8036,7 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
 
 		init_cfs_rq(cfs_rq);
 		init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
+		init_entity_runnable_average(se);
 	}
 
 	return 1;
kernel/sched/sched.h +1 -1
index 3dfec8d..f2b17ea 100644
@@ -1293,7 +1293,7 @@ extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
 
 unsigned long to_ratio(u64 period, u64 runtime);
 
-extern void init_task_runnable_average(struct task_struct *p);
+extern void init_entity_runnable_average(struct sched_entity *se);
 
 static inline void add_nr_running(struct rq *rq, unsigned count)
 {
Signature · 1 line
1.7.9.5
author
#13 lore raw

PATCH v8 4/4 sched: Remove task and group entity load when they are dead

In reply to Yuyang Du

When task exits or group is destroyed, the entity's load should be removed from its parent cfs_rq's load. Otherwise, it will take time for the parent cfs_rq to decay the dead entity's load to 0, which is not desired.

---
 kernel/sched/fair.c |   11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +10 -1
index 08ab789..a8fd7b9 100644
@@ -4904,6 +4904,11 @@ static void migrate_task_rq_fair(struct task_struct *p, int next_cpu)
 	/* We have migrated, no longer consider this task hot */
 	p->se.exec_start = 0;
 }
+
+static void task_dead_fair(struct task_struct *p)
+{
+	remove_entity_load_avg(&p->se);
+}
 #endif /* CONFIG_SMP */
 
 static unsigned long
@@ -7998,8 +8003,11 @@ void free_fair_sched_group(struct task_group *tg)
 	for_each_possible_cpu(i) {
 		if (tg->cfs_rq)
 			kfree(tg->cfs_rq[i]);
-		if (tg->se)
+		if (tg->se) {
+			if (tg->se[i])
+				remove_entity_load_avg(tg->se[i]);
 			kfree(tg->se[i]);
+		}
 	}
 
 	kfree(tg->cfs_rq);
@@ -8186,6 +8194,7 @@ const struct sched_class fair_sched_class = {
 	.rq_offline		= rq_offline_fair,
 
 	.task_waking		= task_waking_fair,
+	.task_dead			= task_dead_fair,
 #endif
 
 	.set_curr_task          = set_curr_task_fair,
Signature · 1 line
1.7.9.5

A message that is not in the archive (sent off-list or not yet received): [email protected]

#15 lore raw
Quoted 8 lines · Boqun Feng

Hi Yuyang,

I've run the test as follow on tip/master without and with your patchset:

On a 12-core system (Intel(R) Xeon(R) CPU X5690 @ 3.47GHz) run stress --cpu 12
run dbench 1

Sorry, I forget to say that stress --cpu 12 and dbench 1 are running simultaneously. Thank Yuyang for reminding me that.

Regards,
Boqun

author
#16 lore raw

Hi,

The sched_debug is informative, lets first give it some analysis.

The workload is 12 CPU hogging tasks (always runnable) and 1 dbench task doing fs ops (70% runnable) running at the same time.

Actually, these 13 tasks are in a task group /autogroup-9617, which has weight 1024.

So the 13 tasks at most can contribute to an average of 79 (=1024/13) to the group entity's load_avg:

cfs_rq[0]:/autogroup-9617
.se->load.weight : 2
.se->avg.load_avg : 0

cfs_rq[1]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[2]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

cfs_rq[3]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 81

cfs_rq[4]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[5]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 77

cfs_rq[6]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

cfs_rq[8]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 78

cfs_rq[9]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

cfs_rq[10]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 78

cfs_rq[11]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

So this is very good runnable load avg accrued in the task group structure.

However, why the cpu0 is very underload?

The top cfs's load_avg is:

cfs_rq[0]: 754
cfs_rq[1]: 81
cfs_rq[2]: 85
cfs_rq[3]: 80
cfs_rq[4]: 142
cfs_rq[5]: 86
cfs_rq[6]: 159
cfs_rq[7]: 264
cfs_rq[8]: 79
cfs_rq[9]: 156
cfs_rq[10]: 78
cfs_rq[11]: 79

We see cfs_rq[0]'s load_avg is 754 even it is underloaded.

So the problem is:

1) The tasks in the workload have too small weight (only 79), because they share a task group.

2) Probably some "high" weight task even runnable a small time contribute "big" to cfs_rq's load_avg.

The patchset does what it wants to do:

1) very precise task group's load avg tracking from group to children tasks and from children tasks to group.

2) the combined runnable + blocked load_avg is effective, so the blocked avg made its impact.

I will try to figure out what makes the cfs_rq[0]'s 754 load_avg, but I also think that the tasks have so small weight that they are very easy to be fairly "imbalanced" ....

Peter, Ben, and others?

In addition, the util_avg sometimes is insanely big, I think I already found the problem.

Thanks,
Yuyang

Quoted 15 lines · Boqun Feng
Quoted 8 lines · Boqun Feng

Hi Yuyang,

I've run the test as follow on tip/master without and with your patchset:

On a 12-core system (Intel(R) Xeon(R) CPU X5690 @ 3.47GHz) run stress --cpu 12
run dbench 1

Sorry, I forget to say that stress --cpu 12 and dbench 1 are running simultaneously. Thank Yuyang for reminding me that.

Regards,
Boqun

#17 lore raw

Hi Yuyang,

Quoted 12 lines · Yuyang Du

Hi,

The sched_debug is informative, lets first give it some analysis.

The workload is 12 CPU hogging tasks (always runnable) and 1 dbench task doing fs ops (70% runnable) running at the same time.

Actually, these 13 tasks are in a task group /autogroup-9617, which has weight 1024.

So the 13 tasks at most can contribute to an average of 79 (=1024/13)

[snip]

Quoted 7 lines

So the problem is:

1) The tasks in the workload have too small weight (only 79), because they share a task group.

2) Probably some "high" weight task even runnable a small time contribute "big" to cfs_rq's load_avg.

Thank you for your analysis.

Some updates:

I created a task group /g and set /g/cpu.shares to 13312 (1024 * 13), and then ran stress --cpu 12 and dbench 1 simultaneously in that group. The situation is much better, only one CPU is not fully loaded, and its utilization rate stays around 85%.

Regards,
Boqun

author
#18 lore raw
Quoted 9 lines · Boqun Feng
Quoted 8 lines

So the problem is:

1) The tasks in the workload have too small weight (only 79), because they share a task group.

2) Probably some "high" weight task even runnable a small time contribute "big" to cfs_rq's load_avg.

Quoted 9 lines

Thank you for your analysis.

Some updates:

I created a task group /g and set /g/cpu.shares to 13312 (1024 * 13), and then ran stress --cpu 12 and dbench 1 simultaneously in that group. The situation is much better, only one CPU is not fully loaded, and its utilization rate stays around 85%.

Hi,

That is good. You can as well disable autogroup, or "nicer" the autogroup, or exec the dbench from another shell, etc...

Thank you for the tests. This may not be intuitive, but actually the results showcased that:

1) the patchset improves the task group share management, accomplishes what it is said to be in terms of fair share, finally.

2) the seamlessly combined runnable + blocked load_avg improves the share of the sometimes runnable sometimes blocked tasks by preserving the blocked load in the avg, fairness is achieved as the dbench has the same weight as the 12 stress tasks, and the dbench (buried in CPU hogging tasks) performance is thus improved.

Peter?

In addition, to correct the util_avg odd value, the following patch should work. Send it here before I send another version.

Thanks,
Yuyang

kernel/sched/fair.c +1 -1
index a8fd7b9..2b0907c 100644
@@ -687,7 +687,7 @@ void init_entity_runnable_average(struct sched_entity *se)
 	sa->load_avg = scale_load_down(se->load.weight);
 	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
 	sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
-	sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
+	sa->util_sum = LOAD_AVG_MAX;
 	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 #else
#19 lore raw
In reply to Yuyang Du
Quoted 37 lines · Yuyang Du

Hi,

The sched_debug is informative, lets first give it some analysis.

The workload is 12 CPU hogging tasks (always runnable) and 1 dbench task doing fs ops (70% runnable) running at the same time.

Actually, these 13 tasks are in a task group /autogroup-9617, which has weight 1024.

So the 13 tasks at most can contribute to an average of 79 (=1024/13) to the group entity's load_avg:

cfs_rq[0]:/autogroup-9617
.se->load.weight : 2
.se->avg.load_avg : 0

cfs_rq[1]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[2]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

cfs_rq[3]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 81

cfs_rq[4]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[5]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 77

Quoted 7 lines

cfs_rq[6]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

How you figure out this one is dbench?

Regards,
Wanpeng Li

Quoted 88 lines

cfs_rq[8]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 78

cfs_rq[9]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

cfs_rq[10]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 78

cfs_rq[11]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

So this is very good runnable load avg accrued in the task group structure.

However, why the cpu0 is very underload?

The top cfs's load_avg is:

cfs_rq[0]: 754
cfs_rq[1]: 81
cfs_rq[2]: 85
cfs_rq[3]: 80
cfs_rq[4]: 142
cfs_rq[5]: 86
cfs_rq[6]: 159
cfs_rq[7]: 264
cfs_rq[8]: 79
cfs_rq[9]: 156
cfs_rq[10]: 78
cfs_rq[11]: 79

We see cfs_rq[0]'s load_avg is 754 even it is underloaded.

So the problem is:

1) The tasks in the workload have too small weight (only 79), because they share a task group.

2) Probably some "high" weight task even runnable a small time contribute "big" to cfs_rq's load_avg.

The patchset does what it wants to do:

1) very precise task group's load avg tracking from group to children tasks and from children tasks to group.

2) the combined runnable + blocked load_avg is effective, so the blocked avg made its impact.

I will try to figure out what makes the cfs_rq[0]'s 754 load_avg, but I also think that the tasks have so small weight that they are very easy to be fairly "imbalanced" ....

Peter, Ben, and others?

In addition, the util_avg sometimes is insanely big, I think I already found the problem.

Thanks,
Yuyang

Quoted 6 lines · Boqun Feng
Quoted 5 lines · Boqun Feng

Hi Yuyang,

I've run the test as follow on tip/master without and with your patchset:

Quoted 8 lines
Quoted 3 lines

On a 12-core system (Intel(R) Xeon(R) CPU X5690 @ 3.47GHz) run stress --cpu 12
run dbench 1

Sorry, I forget to say that stress --cpu 12 and dbench 1 are running simultaneously. Thank Yuyang for reminding me that.

Regards,
Boqun

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

author
#20 lore raw
Quoted 43 lines · Wanpeng Li
Quoted 41 lines · Yuyang Du

Hi,

The sched_debug is informative, lets first give it some analysis.

The workload is 12 CPU hogging tasks (always runnable) and 1 dbench task doing fs ops (70% runnable) running at the same time.

Actually, these 13 tasks are in a task group /autogroup-9617, which has weight 1024.

So the 13 tasks at most can contribute to an average of 79 (=1024/13) to the group entity's load_avg:

cfs_rq[0]:/autogroup-9617
.se->load.weight : 2
.se->avg.load_avg : 0

cfs_rq[1]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[2]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

cfs_rq[3]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 81

cfs_rq[4]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[5]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 77

cfs_rq[6]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

Quoted 6 lines
Quoted 3 lines

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

How you figure out this one is dbench?

dbench is on CPU7 and running there?

#21 lore raw
Quoted 43 lines · Yuyang Du
Quoted 42 lines · Wanpeng Li
Quoted 41 lines · Yuyang Du

Hi,

The sched_debug is informative, lets first give it some analysis.

The workload is 12 CPU hogging tasks (always runnable) and 1 dbench task doing fs ops (70% runnable) running at the same time.

Actually, these 13 tasks are in a task group /autogroup-9617, which has weight 1024.

So the 13 tasks at most can contribute to an average of 79 (=1024/13) to the group entity's load_avg:

cfs_rq[0]:/autogroup-9617
.se->load.weight : 2
.se->avg.load_avg : 0

cfs_rq[1]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[2]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 78

cfs_rq[3]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 81

cfs_rq[4]:/autogroup-9617
.se->load.weight : 80
.se->avg.load_avg : 79

cfs_rq[5]:/autogroup-9617
.se->load.weight : 79
.se->avg.load_avg : 77

cfs_rq[6]:/autogroup-9617
.se->load.weight : 159
.se->avg.load_avg : 156

Quoted 6 lines
Quoted 5 lines
Quoted 3 lines

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

How you figure out this one is dbench?

dbench is on CPU7 and running there?

Sorry, do you mean you pin dbench to CPU7?

Regards,
Wanpeng Li

author
#22 lore raw
Quoted 9 lines · Wanpeng Li
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

How you figure out this one is dbench?

dbench is on CPU7 and running there?

Sorry, do you mean you pin dbench to CPU7?

No, no pin.

Did you see the attached sched_debug file by sent Boqun?

In that file, we see dbench running on CPU7:

R dbench ..... /autogroup-9617

The autugroup-9617 on CPU7 only has the dbench task.

Thanks,
Yuyang

#23 lore raw
Quoted 11 lines · Yuyang Du
Quoted 8 lines · Wanpeng Li
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines

cfs_rq[7]:/autogroup-9617
.se->load.weight : 64 (dbench)
.se->avg.load_avg : 50

How you figure out this one is dbench?

dbench is on CPU7 and running there?

Sorry, do you mean you pin dbench to CPU7?

No, no pin.

Quoted 7 lines

Did you see the attached sched_debug file by sent Boqun?

In that file, we see dbench running on CPU7:

R dbench ..... /autogroup-9617

The autugroup-9617 on CPU7 only has the dbench task.

Ah ok, I miss the attached file. :(

Regards,
Wanpeng Li

Quoted 8 lines

Thanks,
Yuyang
--
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/