Skip to contentSkip to conversation

sched: fix evaluation of skip_for_load in move_tasks()

PATCH In review Peter Williams 2 participants 5 messages Apr 25, 2006 – Apr 26, 2006

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: fix evaluation of skip_for_load in move_tasks()

Problem:

In the patch sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch
I got a the sense of a boolean expression wrong when assigning a value to skip_for_load. The expression should have been negated before being assigned.

Additionally, busiest_best_prio_seen is being set when tasks are moved instead of when they are skipped which will cause problems when the current task does not have prio=busiest_best_prio.

Solution:

Negate the expression and apply de Marcos rule to simplify it and move the setting of busiest_best_prio_seen.

This patch is on top of sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
kernel/sched.c +6 -4
Index: MM-2.6.17-rc1-mm3/kernel/sched.c
===================================================================
@@ -2059,7 +2059,10 @@ static int move_tasks(runqueue_t *this_r
 	busiest_best_prio = rq_best_prio(busiest);
 	/*
 	 * Enable handling of the case where there is more than one task
-	 * with the best priority.
+	 * with the best priority.   If the current running task is one
+	 * of those with prio==busiest_best_prio we know it won't be moved
+	 * and therefore it's safe to override the skip (based on load) of
+	 * any task we find with that prio.
 	 */
 	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 
@@ -2108,9 +2111,10 @@ skip_queue:
 	 */
 	skip_for_load = tmp->load_weight > rem_load_move;
 	if (skip_for_load && idx < this_best_prio)
-		skip_for_load = busiest_best_prio_seen || idx != busiest_best_prio;
+		skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;
 	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
+		busiest_best_prio_seen |= idx == busiest_best_prio;
 		if (curr != head)
 			goto skip_queue;
 		idx++;
@@ -2133,8 +2137,6 @@ skip_queue:
 	if (pulled < max_nr_move && rem_load_move > 0) {
 		if (idx < this_best_prio)
 			this_best_prio = idx;
-		if (idx == busiest_best_prio)
-			busiest_best_prio_seen = 1;
 		if (curr != head)
 			goto skip_queue;
 		idx++;
#1 lore raw
Quoted 45 lines · Peter Williams

Problem:

In the patch sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch I got a the sense of a boolean expression wrong when assigning a value to skip_for_load. The expression should have been negated before being assigned.

Additionally, busiest_best_prio_seen is being set when tasks are moved instead of when they are skipped which will cause problems when the current task does not have prio=busiest_best_prio.

Solution:

Negate the expression and apply de Marcos rule to simplify it and move the setting of busiest_best_prio_seen.

This patch is on top of sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch

Signature · 7 lines
Peter Williams                                   [email protected]

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

Index: MM-2.6.17-rc1-mm3/kernel/sched.c
===================================================================
kernel/sched.c +4 -1
@@ -2059,7 +2059,10 @@ static int move_tasks(runqueue_t *this_r
 	busiest_best_prio = rq_best_prio(busiest);
 	/*
 	 * Enable handling of the case where there is more than one task
-	 * with the best priority.
+	 * with the best priority.   If the current running task is one
+	 * of those with prio==busiest_best_prio we know it won't be moved
+	 * and therefore it's safe to override the skip (based on load) of
+	 * any task we find with that prio.
 	 */
 	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 

kernel/sched.c skip_queue: · line 2114

Quoted 5 lines
kernel/sched.c +1 -1
@@ -2108,9 +2111,10 @@ skip_queue:
 	 */
 	skip_for_load = tmp->load_weight > rem_load_move;
 	if (skip_for_load && idx < this_best_prio)
-		skip_for_load = busiest_best_prio_seen || idx != busiest_best_prio;
+		skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;

I think we need to change this to

	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
		skip_for_load = !busiest_best_prio_seen;

Otherwise we will reset skip_for_load to '0' even for the tasks whose prio is less than this_best_prio but not equal to busiest_best_prio.

Quoted 15 lines
kernel/sched.c +1 -2
 	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
+		busiest_best_prio_seen |= idx == busiest_best_prio;
 		if (curr != head)
 			goto skip_queue;
 		idx++;
@@ -2133,8 +2137,6 @@ skip_queue:
 	if (pulled < max_nr_move && rem_load_move > 0) {
 		if (idx < this_best_prio)
 			this_best_prio = idx;
-		if (idx == busiest_best_prio)
-			busiest_best_prio_seen = 1;
 		if (curr != head)
 			goto skip_queue;
 		idx++;
#2 lore raw
Quoted 46 lines · Suresh B
Quoted 38 lines · Peter Williams

Problem:

In the patch sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch
I got a the sense of a boolean expression wrong when assigning a value to skip_for_load. The expression should have been negated before being assigned.

Additionally, busiest_best_prio_seen is being set when tasks are moved instead of when they are skipped which will cause problems when the current task does not have prio=busiest_best_prio.

Solution:

Negate the expression and apply de Marcos rule to simplify it and move the setting of busiest_best_prio_seen.

This patch is on top of sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch

Signature · 7 lines
Peter Williams                                   [email protected]

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

Index: MM-2.6.17-rc1-mm3/kernel/sched.c
===================================================================
kernel/sched.c +4 -1
@@ -2059,7 +2059,10 @@ static int move_tasks(runqueue_t *this_r
 	busiest_best_prio = rq_best_prio(busiest);
 	/*
 	 * Enable handling of the case where there is more than one task
-	 * with the best priority.
+	 * with the best priority.   If the current running task is one
+	 * of those with prio==busiest_best_prio we know it won't be moved
+	 * and therefore it's safe to override the skip (based on load) of
+	 * any task we find with that prio.
 	 */
 	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 

kernel/sched.c skip_queue: · line 2114

Quoted 5 lines
kernel/sched.c +1 -1
@@ -2108,9 +2111,10 @@ skip_queue:
 	 */
 	skip_for_load = tmp->load_weight > rem_load_move;
 	if (skip_for_load && idx < this_best_prio)
-		skip_for_load = busiest_best_prio_seen || idx != busiest_best_prio;
+		skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;

I think we need to change this to

Quoted 4 lines
	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
		skip_for_load = !busiest_best_prio_seen;

Otherwise we will reset skip_for_load to '0' even for the tasks whose prio is less than this_best_prio but not equal to busiest_best_prio.

And why is that a problem? The intention of this code is to make sure at least one busiest_best_prio task doesn't get moved as a result of the "skip for reasons of load weight" mechanism being overridden by the "idx < this_best_prio" exception. I can't see how this intention is being subverted.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#3 lore raw
Quoted 5 lines · Peter Williams
Quoted 4 lines · Suresh B

I think we need to change this to

	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
		skip_for_load = !busiest_best_prio_seen;
Quoted 8 lines
Quoted 2 lines

Otherwise we will reset skip_for_load to '0' even for the tasks whose prio is less than this_best_prio but not equal to busiest_best_prio.

And why is that a problem? The intention of this code is to make sure at least one busiest_best_prio task doesn't get moved as a result of the "skip for reasons of load weight" mechanism being overridden by the "idx < this_best_prio" exception. I can't see how this intention is being subverted.

There might be scenarios where we will endup moving other priority tasks( not those with busiest_best_prio) which will still become highest priority on new queue. This may or may not be bad. But this was not our intention with the intended code, right?

thanks,
suresh

#4 lore raw
Quoted 6 lines · Suresh B
Quoted 5 lines · Peter Williams
Quoted 4 lines · Suresh B

I think we need to change this to

	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
		skip_for_load = !busiest_best_prio_seen;
Quoted 7 lines
Quoted 2 lines
Quoted 1 line

Otherwise we will reset skip_for_load to '0' even for the tasks whose prio is less than this_best_prio but not equal to busiest_best_prio.

And why is that a problem? The intention of this code is to make sure at least one busiest_best_prio task doesn't get moved as a result of the "skip for reasons of load weight" mechanism being overridden by the "idx < this_best_prio" exception. I can't see how this intention is being subverted.

There might be scenarios where we will endup moving other priority tasks( not those with busiest_best_prio) which will still become highest priority on new queue. This may or may not be bad. But this was not our intention with the intended code, right?

I considered this (as part of the original code to allow override of the skip for cases where moving a task will make it the best priority on the CPU -- NB no extra caveats about finding the best priority task which meets the criteria) and decided that it wasn't worth worrying about as the complexity of the code required to handle it would be considerable.

Also, because we are actually moving a bigger load than is required to balance the total weighted loads on the two queues, there's an argument that we should move the smallest one that meets the requirement. With these conflicting arguments, it seems best just to move the first one we find that meets the criteria and is movable.

Load balancing is probabilistic at best and extra effort trying to be perfect will be wasted. This is even more the case when you take into account the fact that as soon as you release the locks on the queues everything is highly likely to change anyway.

I figured that this code is consistent with the original load balancing code in this regard.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

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