Skip to contentSkip to conversation

sched: Reduce overhead in balance_tasks()

PATCH In review Peter Williams 2 participants 3 messages Aug 15, 2007 – Aug 25, 2007 Scheduler

lore
Share & tools
lore

Peter Williams

author
#0 lore raw

PATCH 1/1 sched: Reduce overhead in balance_tasks()

At the moment, balance_tasks() provides low level functionality for both
move_tasks() and move_one_task() (indirectly) via the load_balance()
function (in the sched_class interface) which also provides dual functionality. This dual functionality complicates the interfaces and internal mechanisms and makes the run time overhead of operations that are called with two run queue locks held.

This patch addresses this issue and reduces the overhead of these operations.

This patch is not urgent and can be held back until the next merge window without compromising the safety of the kernel.

Signed-off-by Peter Williams <[email protected]>

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
   -- Ambrose Bierce
include/linux/sched.h +5 -2
diff -r 90691a597f06 include/linux/sched.h
@@ -865,10 +865,13 @@ struct sched_class {
 	void (*put_prev_task) (struct rq *rq, struct task_struct *p);
 
 	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
-			struct rq *busiest,
-			unsigned long max_nr_move, unsigned long max_load_move,
+			struct rq *busiest, unsigned long max_load_move,
 			struct sched_domain *sd, enum cpu_idle_type idle,
 			int *all_pinned, int *this_best_prio);
+
+	int (*move_one_task) (struct rq *this_rq, int this_cpu,
+			      struct rq *busiest, struct sched_domain *sd,
+			      enum cpu_idle_type idle);
 
 	void (*set_curr_task) (struct rq *rq);
 	void (*task_tick) (struct rq *rq, struct task_struct *p);
kernel/sched.c +67 -32

160 lines not on this page · raw message

kernel/sched_fair.c +28 -18

81 lines not on this page · raw message

kernel/sched_idletask.c +11 -3
diff -r 90691a597f06 kernel/sched_idletask.c
@@ -39,9 +39,16 @@ static void put_prev_task_idle(struct rq
 
 static unsigned long
 load_balance_idle(struct rq *this_rq, int this_cpu, struct rq *busiest,
-			unsigned long max_nr_move, unsigned long max_load_move,
-			struct sched_domain *sd, enum cpu_idle_type idle,
-			int *all_pinned, int *this_best_prio)
+		  unsigned long max_load_move,
+		  struct sched_domain *sd, enum cpu_idle_type idle,
+		  int *all_pinned, int *this_best_prio)
+{
+	return 0;
+}
+
+static int
+move_one_task_idle(struct rq *this_rq, int this_cpu, struct rq *busiest,
+		   struct sched_domain *sd, enum cpu_idle_type idle)
 {
 	return 0;
 }

@@ -65,6 +72,7 @@ static struct sched_class idle_sched_cla
 	.put_prev_task		= put_prev_task_idle,
 
 	.load_balance		= load_balance_idle,
+	.move_one_task		= move_one_task_idle,
 
 	.task_tick		= task_tick_idle,
 	/* no .task_new for idle tasks */
kernel/sched_rt.c +21 -11
diff -r 90691a597f06 kernel/sched_rt.c
@@ -172,13 +172,11 @@ static struct task_struct *load_balance_
 
 static unsigned long
 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
-			unsigned long max_nr_move, unsigned long max_load_move,
-			struct sched_domain *sd, enum cpu_idle_type idle,
-			int *all_pinned, int *this_best_prio)
-{
-	int nr_moved;
+		unsigned long max_load_move,
+		struct sched_domain *sd, enum cpu_idle_type idle,
+		int *all_pinned, int *this_best_prio)
+{
 	struct rq_iterator rt_rq_iterator;
-	unsigned long load_moved;
 
 	rt_rq_iterator.start = load_balance_start_rt;
 	rt_rq_iterator.next = load_balance_next_rt;

@@ -187,11 +185,22 @@ load_balance_rt(struct rq *this_rq, int 
 	 */
 	rt_rq_iterator.arg = busiest;
 
-	nr_moved = balance_tasks(this_rq, this_cpu, busiest, max_nr_move,
-			max_load_move, sd, idle, all_pinned, &load_moved,
-			this_best_prio, &rt_rq_iterator);
-
-	return load_moved;
+	return balance_tasks(this_rq, this_cpu, busiest, max_load_move, sd,
+			     idle, all_pinned, this_best_prio, &rt_rq_iterator);
+}
+
+static int
+move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
+		 struct sched_domain *sd, enum cpu_idle_type idle)
+{
+	struct rq_iterator rt_rq_iterator;
+
+	rt_rq_iterator.start = load_balance_start_rt;
+	rt_rq_iterator.next = load_balance_next_rt;
+	rt_rq_iterator.arg = busiest;
+
+	return iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
+				  &rt_rq_iterator);
 }
 
 static void task_tick_rt(struct rq *rq, struct task_struct *p)

@@ -224,6 +233,7 @@ static struct sched_class rt_sched_class
 	.put_prev_task		= put_prev_task_rt,
 
 	.load_balance		= load_balance_rt,
+	.move_one_task		= move_one_task_rt,
 
 	.task_tick		= task_tick_rt,
 };
#1 lore raw
Quoted 10 lines · Peter Williams

At the moment, balance_tasks() provides low level functionality for both
move_tasks() and move_one_task() (indirectly) via the load_balance()
function (in the sched_class interface) which also provides dual functionality. This dual functionality complicates the interfaces and internal mechanisms and makes the run time overhead of operations that are called with two run queue locks held.

This patch addresses this issue and reduces the overhead of these operations.

hm, i like it, and added it to my queue (probably .24 material though), but note that it increases .text and .data overhead:

text data bss dec hex filename

  41028   37794    2168   80990   13c5e sched.o.before
  41349   37826    2168   81343   13dbf sched.o.after

is that expected?

Ingo

author
#2 lore raw
Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Peter Williams

At the moment, balance_tasks() provides low level functionality for both
move_tasks() and move_one_task() (indirectly) via the load_balance()
function (in the sched_class interface) which also provides dual functionality. This dual functionality complicates the interfaces and internal mechanisms and makes the run time overhead of operations that are called with two run queue locks held.

This patch addresses this issue and reduces the overhead of these operations.

Quoted 7 lines

hm, i like it, and added it to my queue (probably .24 material though), but note that it increases .text and .data overhead:

text data bss dec hex filename

  41028   37794    2168   80990   13c5e sched.o.before
  41349   37826    2168   81343   13dbf sched.o.after

is that expected?

Yes, sort off. It's a trade off of space for time and I expected an increase (although I didn't think that it would be quite that much). But it's still less than 1% and since the time saved is time when two run queue locks are held I figure that it's a trade worth making. Also this separation lays the ground for a clean up of the active load balancing code which should gain some space including making it possible to exclude active load balancing on systems that don't need it (i.e. those that don't have multiple multi core/hyperthreading packages).

I've got a patch available that reduces the .text and .data for non SMP systems by excluding the load balancing stuff (that has crept into those systems) so that should help on embedded systems where memory is tight.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce