sched: group scheduler related patches (V2)

PATCH New Srivatsa Vaddagiri 1 participant 3 messages Nov 19, 2007

Subsystems (2)

Scheduler Proc sysctl

lore

Share & tools

lore

Srivatsa Vaddagiri

author

2007-11-19 18:08 UTC #0 lore raw

cover sched: group scheduler related patches (V2)

Hi Ingo,
Here's V2 of the two patches related to group cpu scheduling I
sent a while ago:

Patch 1/2 -> Fixes minor bugs and coding style issues Patch 2/2 -> Improves group fairness on SMP systems.

Changes since V1:
- Introduced a task_group_mutex to serialize add/removal of task groups (as pointed by Dipankar)

Both the patches should not have any functional/runtime effect to the scheduler for !CONFIG_FAIR_GROUP_SCHED case.

This is also probably one of the last big changes related to group scheduler that I had on my plate. Pls apply if there is no objection from anyone.

Signature · 2 lines

Regards,
vatsa

Srivatsa Vaddagiri

author

2007-11-19 18:13 UTC #1 lore raw

PATCH 1/2 sched: Fix minor bugs and coding style issues

Fix these minor bugs/coding-style issues:

- s/INIT_TASK_GRP_LOAD/INIT_TASK_GROUP_LOAD
- remove obsolete comment
- Use list_for_each_entry_rcu when walking task group list in for_each_leaf_cfs_rq() macro
- Serialize addition/removal of task groups from rq->leaf_cfs_rq_list by using a mutex(task_group_mutex). Use the same mutex in print_cfs_stats when walking the task group list.

Signed-off-by Srivatsa Vaddagiri <[email protected]>

---
 kernel/sched.c      |   55 +++++++++++++++++++++++++++++-----------------------
 kernel/sched_fair.c |    5 +++-
 2 files changed, 35 insertions(+), 25 deletions(-)

kernel/sched.c +31 ~~-24~~

Index: current/kernel/sched.c
===================================================================
@@ -169,8 +169,6 @@ struct task_group {
 	/* runqueue "owned" by this group on each cpu */
 	struct cfs_rq **cfs_rq;
 	unsigned long shares;
-	/* spinlock to serialize modification to shares */
-	spinlock_t lock;
 	struct rcu_head rcu;
 };

@@ -182,6 +180,11 @@ static DEFINE_PER_CPU(struct cfs_rq, ini
 static struct sched_entity *init_sched_entity_p[NR_CPUS];
 static struct cfs_rq *init_cfs_rq_p[NR_CPUS];
 
+/* task_group_mutex serializes add/remove of task groups and also changes to
+ * a task group's cpu shares.
+ */
+static DEFINE_MUTEX(task_group_mutex);
+
 /* Default task group.
  *	Every task in system belong to this group at bootup.
  */

@@ -191,12 +194,12 @@ struct task_group init_task_group = {
 };
 
 #ifdef CONFIG_FAIR_USER_SCHED
-# define INIT_TASK_GRP_LOAD	2*NICE_0_LOAD
+# define INIT_TASK_GROUP_LOAD	2*NICE_0_LOAD	/* root user's cpu share */
 #else
-# define INIT_TASK_GRP_LOAD	NICE_0_LOAD
+# define INIT_TASK_GROUP_LOAD	NICE_0_LOAD
 #endif
 
-static int init_task_group_load = INIT_TASK_GRP_LOAD;
+static int init_task_group_load = INIT_TASK_GROUP_LOAD;
 
 /* return group to which a task belongs */
 static inline struct task_group *task_group(struct task_struct *p)

@@ -222,9 +225,21 @@ static inline void set_task_cfs_rq(struc
 	p->se.parent = task_group(p)->se[cpu];
 }
 
+static inline void lock_task_group_list(void)
+{
+	mutex_lock(&task_group_mutex);
+}
+
+static inline void unlock_task_group_list(void)
+{
+	mutex_unlock(&task_group_mutex);
+}
+
 #else
 
 static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { }
+static inline void lock_task_group_list(void) { }
+static inline void unlock_task_group_list(void) { }
 
 #endif	/* CONFIG_FAIR_GROUP_SCHED */

@@ -864,21 +879,6 @@ iter_move_one_task(struct rq *this_rq, i
 
 #define sched_class_highest (&rt_sched_class)
 
-/*
- * Update delta_exec, delta_fair fields for rq.
- *
- * delta_fair clock advances at a rate inversely proportional to
- * total load (rq->load.weight) on the runqueue, while
- * delta_exec advances at the same rate as wall-clock (provided
- * cpu is not idle).
- *
- * delta_exec / delta_fair is a measure of the (smoothened) load on this
- * runqueue over any given interval. This (smoothened) load is used
- * during load balance.
- *
- * This function is called /before/ updating rq->load
- * and when switching tasks.
- */
 static inline void inc_load(struct rq *rq, const struct task_struct *p)
 {
 	update_load_add(&rq->load, p->se.load.weight);

@@ -6762,7 +6762,6 @@ void __init sched_init(void)
 			se->parent = NULL;
 		}
 		init_task_group.shares = init_task_group_load;
-		spin_lock_init(&init_task_group.lock);
 #endif
 
 		for (j = 0; j < CPU_LOAD_IDX_MAX; j++)

@@ -7002,14 +7001,17 @@ struct task_group *sched_create_group(vo
 		se->parent = NULL;
 	}
 
+	lock_task_group_list();
+
 	for_each_possible_cpu(i) {
 		rq = cpu_rq(i);
 		cfs_rq = tg->cfs_rq[i];
 		list_add_rcu(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
 	}
 
+	unlock_task_group_list();
+
 	tg->shares = NICE_0_LOAD;
-	spin_lock_init(&tg->lock);
 
 	return tg;

@@ -7055,11 +7057,15 @@ void sched_destroy_group(struct task_gro
 	struct cfs_rq *cfs_rq = NULL;
 	int i;
 
+	lock_task_group_list();
+
 	for_each_possible_cpu(i) {
 		cfs_rq = tg->cfs_rq[i];
 		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
 	}
 
+	unlock_task_group_list();
+
 	BUG_ON(!cfs_rq);
 
 	/* wait for possible concurrent references to cfs_rqs complete */

@@ -7132,7 +7138,8 @@ int sched_group_set_shares(struct task_g
 {
 	int i;
 
-	spin_lock(&tg->lock);
+	lock_task_group_list();
+
 	if (tg->shares == shares)
 		goto done;

@@ -7141,7 +7148,7 @@ int sched_group_set_shares(struct task_g
 		set_se_shares(tg->se[i], shares);
 
 done:
-	spin_unlock(&tg->lock);
+	unlock_task_group_list();
 	return 0;
 }

kernel/sched_fair.c +4 -1

Index: current/kernel/sched_fair.c
===================================================================
@@ -685,7 +685,7 @@ static inline struct cfs_rq *cpu_cfs_rq(
 
 /* Iterate thr' all leaf cfs_rq's on a runqueue */
 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
-	list_for_each_entry(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
+	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
 
 /* Do the two (enqueued) entities belong to the same group ? */
 static inline int

@@ -1126,7 +1126,10 @@ static void print_cfs_stats(struct seq_f
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	print_cfs_rq(m, cpu, &cpu_rq(cpu)->cfs);
 #endif
+
+	lock_task_group_list();
 	for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
 		print_cfs_rq(m, cpu, cfs_rq);
+	unlock_task_group_list();
 }
 #endif

Signature · 2 lines

Regards,
vatsa

Srivatsa Vaddagiri

author

2007-11-19 18:19 UTC #2 lore raw

PATCH 2/2 sched: Improve fairness of cpu allocation for task groups

In reply to Srivatsa Vaddagiri

The current load balancing scheme isn't good for group fairness.

For ex: on a 8-cpu system, I created 3 groups as under:

	a = 8 tasks (cpu.shares = 1024) 
	b = 4 tasks (cpu.shares = 1024) 
	c = 3 tasks (cpu.shares = 1024)

a, b and c are task groups that have equal weight. We would expect each of the groups to receive 33.33% of cpu bandwidth under a fair scheduler.

This is what I get with the latest scheduler git tree:

Before this patch:
--------------------------------------------------------------------------------

Col1  | Col2    | Col3  |  Col4
------|---------|-------|-------------------------------------------------------
a     | 277.676 | 57.8% | 54.1%  54.1%  54.1%  54.2%  56.7%  62.2%  62.8% 64.5%
b     | 116.108 | 24.2% | 47.4%  48.1%  48.7%  49.3%
c     |  86.326 | 18.0% | 47.5%  47.9%  48.5%

--------------------------------------------------------------------------------

Explanation of o/p:

Col1 -> Group name
Col2 -> Cumulative execution time (in seconds) receive by all tasks of that
group in a 60sec window across 8 cpus
Col3 -> CPU bandwidth received by the group in the 60sec window, expressed in
percentage. Col3 data is derived as:
Col3 = 100 * Col2 / (NR_CPUS * 60)
Col4 -> CPU bandwidth received by each individual task of the group.

		Col4 = 100 * cpu_time_recd_by_task / 60

[I can share the test scripts that produce such an o/p if reqd]

The deviation from desired group fairness is as below:

	a = +24.47%
	b = -9.13%
	c = -15.33%

which is quite high.

After the patch below is applied, here are the results:

--------------------------------------------------------------------------------

Col1  | Col2    | Col3  |  Col4
------|---------|-------|-------------------------------------------------------
a     | 163.112 | 34.0% | 33.2%  33.4%  33.5%  33.5%  33.7%  34.4%  34.8% 35.3%
b     | 156.220 | 32.5% | 63.3%  64.5%  66.1%  66.5%
c     | 160.653 | 33.5% | 85.8%  90.6%  91.4%

--------------------------------------------------------------------------------

Deviation from desired group fairness is as below:

	a = +0.67%
	b = -0.83%

c = +0.17%

which is far better IMO. Most of other runs have yielded a deviation within +-2% at the most, which is good.

Why do we see bad (group) fairness with current scheuler?
=========================================================

Currently cpu's weight is just the summation of individual task weights. This can yield incorrect results. For ex: consider three groups as below on a 2-cpu system:

	CPU0	CPU1
---------------------------
	A (10)  B(5)
		C(5)

---------------------------

Group A has 10 tasks, all on CPU0, Group B and C have 5 tasks each all of which are on CPU1. Each task has the same weight (NICE_0_LOAD = 1024).

The current scheme would yield a cpu weight of 10240 (10*1024) for each cpu and the load balancer will think both CPUs are perfectly balanced and won't move around any tasks. This, however, would yield this bandwidth:

	A = 50%
	B = 25%
	C = 25%

which is not the desired result.

What's changing in the patch?
=============================

- How cpu weights are calculated when CONFIF_FAIR_GROUP_SCHED is defined (see below)
- API Change
- Minimum shares that can be allocated to a group is set to 100 (MIN_GROUP_SHARES macro introduced)
- Two tunables introduced in sysfs (under SCHED_DEBUG) to control the frequency at which the load balance monitor thread runs.

The basic change made in this patch is how cpu weight (rq->load.weight) is calculated. Its now calculated as the summation of group weights on a cpu, rather than summation of task weights. Weight exerted by a group on a cpu is dependent on the shares allocated to it and also the number of tasks the group has on that cpu compared to the total number of (runnable) tasks the group has in the system.

Let,

	W(K,i)  = Weight of group K on cpu i
	T(K,i)  = Task load present in group K's cfs_rq on cpu i
	T(K)    = Total task load of group K across various cpus

S(K) = Shares allocated to group K
NRCPUS = Number of online cpus in the scheduler domain to
which group K is assigned.

Then,

	W(K,i) = S(K) * NRCPUS * T(K,i) / T(K)

A load balance monitor thread is created at bootup, which periodically runs and adjusts group's weight on each cpu. To avoid its overhead, two min/max tunables are introduced (under SCHED_DEBUG) to control the rate at which it runs.

Impact to sched.o size
======================

CONFIG_FAIR_GROUP_SCHED not defined ->

text data bss dec hex filename

               36829    2766      48   39643    9adb sched.o-before
               36843    2766      48   39657    9ae9 sched.o-after
	                              ---------
					+14
				      --------

CONFIG_FAIR_GROUP_SCHED defined ->

text data bss dec hex filename

               39019    3346     336   42701    a6cd sched.o-before
	       40206    3482     308   43996    abdc sched.o-yes-after
				       ------
				       +1295
				       ------

Signed-off-by Srivatsa Vaddagiri <[email protected]>

---
 include/linux/sched.h |    4 
 kernel/sched.c        |  278 ++++++++++++++++++++++++++++++++++++++++++++++----
 kernel/sched_fair.c   |   95 +++++++++++------
 kernel/sched_rt.c     |    2 
 kernel/sysctl.c       |   18 +++
 5 files changed, 342 insertions(+), 55 deletions(-)

include/linux/sched.h +4 -0

Index: current/include/linux/sched.h
===================================================================
@@ -1467,6 +1467,10 @@ extern unsigned int sysctl_sched_child_r
 extern unsigned int sysctl_sched_features;
 extern unsigned int sysctl_sched_migration_cost;
 extern unsigned int sysctl_sched_nr_migrate;
+#ifdef CONFIG_FAIR_GROUP_SCHED
+extern unsigned int sysctl_sched_min_bal_int_shares;
+extern unsigned int sysctl_sched_max_bal_int_shares;
+#endif
 
 int sched_nr_latency_handler(struct ctl_table *table, int write,
 		struct file *file, void __user *buffer, size_t *length,

kernel/sched.c +256 ~~-22~~

398 lines not on this page · raw message

kernel/sched_fair.c +62 ~~-33~~

156 lines not on this page · raw message

kernel/sched_rt.c +2 -0

Index: current/kernel/sched_rt.c
===================================================================
@@ -31,6 +31,7 @@ static void enqueue_task_rt(struct rq *r
 
 	list_add_tail(&p->run_list, array->queue + p->prio);
 	__set_bit(p->prio, array->bitmap);
+	inc_load(rq, p->se.load.weight);
 }
 
 /*

@@ -45,6 +46,7 @@ static void dequeue_task_rt(struct rq *r
 	list_del(&p->run_list);
 	if (list_empty(array->queue + p->prio))
 		__clear_bit(p->prio, array->bitmap);
+	dec_load(rq, p->se.load.weight);
 }
 
 /*

kernel/sysctl.c +18 -0

Index: current/kernel/sysctl.c
===================================================================
@@ -309,6 +309,24 @@ static struct ctl_table kern_table[] = {
 		.mode		= 644,
 		.proc_handler	= &proc_dointvec,
 	},
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "sched_min_bal_int_shares",
+		.data		= &sysctl_sched_min_bal_int_shares,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "sched_max_bal_int_shares",
+		.data		= &sysctl_sched_max_bal_int_shares,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
+#endif
 #endif
 	{
 		.ctl_name	= CTL_UNNUMBERED,

Signature · 2 lines

Regards,
vatsa