Skip to contentSkip to conversation

sched: Avoid unnecessarily moving highest priority task move_tasks()

PATCH In review Peter Williams 2 participants 8 messages Apr 21, 2006 – Apr 25, 2006

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: Avoid unnecessarily moving highest priority task move_tasks()

Problem:

To help distribute high priority tasks evenly across the available CPUs move_tasks() does not, under some circumstances, skip tasks whose load weight is bigger than the designated amount. Because the highest priority task on the busiest queue may be on the expired array it may be moved as a result of this mechanism. Apart from not being the most desirable way to redistribute the high priority tasks (we'd rather move the second highest priority task), there is a risk that this could set up a loop with this task bouncing backwards and forwards between the two queues. (This latter possibility can be demonstrated by running a nice==-20 CPU bound task on an otherwise quiet 2 CPU system.)

Solution:

Modify the mechanism so that it does not override skip for the highest priority task on the CPU. Of course, if there are more than one tasks at the highest priority then it will allow the override for one of them as this is a desirable redistribution of high priority tasks.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
kernel/sched.c +19 -5
Index: MM-2.6.17-rc1-mm3/kernel/sched.c
===================================================================
@@ -2029,6 +2029,7 @@ int can_migrate_task(task_t *p, runqueue
 	return 1;
 }
 
+#define rq_best_prio(rq) min((rq)->curr->prio, (rq)->best_expired_prio)
 /*
  * move_tasks tries to move up to max_nr_move tasks and max_load_move weighted
  * load from busiest to this_rq, as part of a balancing operation within
@@ -2043,7 +2044,9 @@ static int move_tasks(runqueue_t *this_r
 {
 	prio_array_t *array, *dst_array;
 	struct list_head *head, *curr;
-	int idx, pulled = 0, pinned = 0, this_min_prio;
+	int idx, pulled = 0, pinned = 0, this_best_prio, busiest_best_prio;
+	int busiest_best_prio_seen;
+	int skip_for_load; /* skip the task based on weighted load issues */
 	long rem_load_move;
 	task_t *tmp;
 
@@ -2052,7 +2055,13 @@ static int move_tasks(runqueue_t *this_r
 
 	rem_load_move = max_load_move;
 	pinned = 1;
-	this_min_prio = this_rq->curr->prio;
+	this_best_prio = rq_best_prio(this_rq);
+	busiest_best_prio = rq_best_prio(busiest);
+	/*
+	 * Enable handling of the case where there is more than one task
+	 * with the best priority.
+	 */
+	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 
 	/*
 	 * We first consider expired tasks. Those will likely not be
@@ -2097,7 +2106,10 @@ skip_queue:
 	 * skip a task if it will be the highest priority task (i.e. smallest
 	 * prio value) on its new queue regardless of its load weight
 	 */
-	if ((idx >= this_min_prio && tmp->load_weight > rem_load_move) ||
+	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;
+	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
 		if (curr != head)
 			goto skip_queue;
@@ -2119,8 +2131,10 @@ skip_queue:
 	 * and the prescribed amount of weighted load.
 	 */
 	if (pulled < max_nr_move && rem_load_move > 0) {
-		if (idx < this_min_prio)
-			this_min_prio = idx;
+		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 13 lines · Peter Williams
kernel/sched.c +7 -1
@@ -2052,7 +2055,13 @@ static int move_tasks(runqueue_t *this_r
 
 	rem_load_move = max_load_move;
 	pinned = 1;
-	this_min_prio = this_rq->curr->prio;
+	this_best_prio = rq_best_prio(this_rq);
+	busiest_best_prio = rq_best_prio(busiest);
+	/*
+	 * Enable handling of the case where there is more than one task
+	 * with the best priority.
+	 */
+	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 
Quoted 1 line

From this hunk, it seems like we don't want to override the skip of highest

priority task as long as there is one such task in active list(even though there may be few such tasks on expired list). Right? And why?

If we fix the above, we don't need busiest_best_prio_seen. Once we move one highest priority task, we are changing this_best_prio anyhow right?

This patch doesn't address the issue where we can skip the highest priority task movement if there is only one such task on the busy runqueue (and is on the expired list..)

I can send a fix if I understand your intention for the above hunk.

thanks,
suresh

#2 lore raw
Quoted 14 lines · Suresh B
Quoted 12 lines · Peter Williams
kernel/sched.c +7 -1
@@ -2052,7 +2055,13 @@ static int move_tasks(runqueue_t *this_r
 
 	rem_load_move = max_load_move;
 	pinned = 1;
-	this_min_prio = this_rq->curr->prio;
+	this_best_prio = rq_best_prio(this_rq);
+	busiest_best_prio = rq_best_prio(busiest);
+	/*
+	 * Enable handling of the case where there is more than one task
+	 * with the best priority.
+	 */
+	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
Quoted 3 lines
Quoted 1 line

From this hunk, it seems like we don't want to override the skip of highest

priority task as long as there is one such task in active list(even though there may be few such tasks on expired list). Right?

No, but nearly. We don't want to override the skip of a task with the highest priority until we've skipped one such task OR we're sure one such task will be skipped (e.g. because it's the currently running task).

Quoted 1 line

And why?

If there are more than one task with the highest priority then it is desirable to move one of them by overriding the skip mechanism as it can be considered the second highest priority task. This initialization just checks to see if the currently running task is one of the highest priority tasks. If it is then it's OK to move the first task we find that also has the same priority otherwise we wait until we've skipped one before we move one.

Quoted 2 lines

If we fix the above, we don't need busiest_best_prio_seen. Once we move one highest priority task, we are changing this_best_prio anyhow right?

Yes, but this is recording the fact that we've skipped one and that it's now OK to move one.

Quoted 3 lines

This patch doesn't address the issue where we can skip the highest priority task movement if there is only one such task on the busy runqueue (and is on the expired list..)

I think that it does.

Quoted 2 lines

I can send a fix if I understand your intention for the above hunk.

If you think that there's still a problem after the above explanation then sending a patch might help me understand why you think it's wrong.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

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

If there are more than one task with the highest priority then it is desirable to move one of them by overriding the skip mechanism as it can be considered the second highest priority task.

I think your patch is not doing what you intend to do.

Quoted 5 lines

This initialization
just checks to see if the currently running task is one of the highest priority tasks. If it is then it's OK to move the first task we find that also has the same priority otherwise we wait until we've skipped one before we move one.

If this currently running task is of the highest priority, we set busiest_best_prio_seen to '1' and looking at the code, because of this we never consider any other busiest task which we come across on the expired list.. This is coming from this piece of code.

	skip_for_load = busiest_best_prio_seen || idx != busiest_best_prio;

skip_for_load is always set to '1'(because of busiest_best_prio_seen) and we will never be able to move any busiest task to the new queue.

Quoted 5 lines
Quoted 3 lines

This patch doesn't address the issue where we can skip the highest priority task movement if there is only one such task on the busy runqueue (and is on the expired list..)

I think that it does.

No. It doesn't. In this case busiest_best_prio_seen will be set to '0', when we traverse the only highest priority task on this queue(which happens to be on expired list), we set skip_for_load to '0' And we will try pulling the only highest priority task on this queue to the new queue..

Appended patch(ontop of sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch) fixes these issues.

kernel/sched.c renamed from kernel/sched.c~ +12 -10
@@ -2045,7 +2045,7 @@ static int move_tasks(runqueue_t *this_r
 	prio_array_t *array, *dst_array;
 	struct list_head *head, *curr;
 	int idx, pulled = 0, pinned = 0, this_best_prio, busiest_best_prio;
-	int busiest_best_prio_seen;
+	int busiest_best_prio_seen = 0;
 	int skip_for_load; /* skip the task based on weighted load issues */
 	long rem_load_move;
 	task_t *tmp;
@@ -2057,11 +2057,6 @@ static int move_tasks(runqueue_t *this_r
 	pinned = 1;
 	this_best_prio = rq_best_prio(this_rq);
 	busiest_best_prio = rq_best_prio(busiest);
-	/*
-	 * Enable handling of the case where there is more than one task
-	 * with the best priority.
-	 */
-	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 
 	/*
 	 * We first consider expired tasks. Those will likely not be
@@ -2072,6 +2067,13 @@ static int move_tasks(runqueue_t *this_r
 	if (busiest->expired->nr_active) {
 		array = busiest->expired;
 		dst_array = this_rq->expired;
+		/*
+		 * We already have one or more busiest best prio tasks on
+		 * active list. So if we encounter any busiest best prio task
+		 * on expired list, consider it for the move, if it becomes
+		 * the best prio on new queue.
+		 */
+		busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 	} else {
 		array = busiest->active;
 		dst_array = this_rq->active;
@@ -2089,6 +2091,7 @@ skip_bitmap:
 		if (array == busiest->expired && busiest->active->nr_active) {
 			array = busiest->active;
 			dst_array = this_rq->active;
+			busiest_best_prio_seen = 0;
 			goto new_array;
 		}
 		goto out;
@@ -2107,8 +2110,9 @@ skip_queue:
 	 * prio value) on its new queue regardless of its load weight
 	 */
 	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;
+	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
+		skip_for_load = !busiest_best_prio_seen &&
+				head->next == head->prev;
 	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
 		if (curr != head)
@@ -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++;
#4 lore raw
Quoted 12 lines · Suresh B
Quoted 1 line · Peter Williams

If there are more than one task with the highest priority then it is desirable to move one of them by overriding the skip mechanism as it can be considered the second highest priority task.

I think your patch is not doing what you intend to do.

Quoted 1 line

This initialization just checks to see if the currently running task is one of the highest priority tasks. If it is then it's OK to move the first task we find that also has the same priority otherwise we wait until we've skipped one before we move one.

If this currently running task is of the highest priority, we set busiest_best_prio_seen to '1' and looking at the code, because of this we never consider any other busiest task which we come across on the expired list.. This is coming from this piece of code.

Quoted 4 lines
	skip_for_load = busiest_best_prio_seen || idx != busiest_best_prio;

skip_for_load is always set to '1'(because of busiest_best_prio_seen) and we will never be able to move any busiest task to the new queue.

Looks like there's a NOT missing doesn't it. So there is an error but I don't think that your patch is the right way to fix it. We just need to negate the above assignment. E.g.

skip_for_load = !(busiest_best_prio_seen || idx != busiest_best_prio);

or

skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;

whichever is more efficient.

Quoted 39 lines
Quoted 4 lines
Quoted 3 lines

This patch doesn't address the issue where we can skip the highest priority task movement if there is only one such task on the busy runqueue (and is on the expired list..)

I think that it does.

No. It doesn't. In this case busiest_best_prio_seen will be set to '0', when we traverse the only highest priority task on this queue(which happens to be on expired list), we set skip_for_load to '0' And we will try pulling the only highest priority task on this queue to the new queue..

Appended patch(ontop of sched-avoid-unnecessarily-moving-highest-priority-task-move_tasks.patch) fixes these issues.

kernel/sched.c renamed from kernel/sched.c~ +1 -6
@@ -2045,7 +2045,7 @@ static int move_tasks(runqueue_t *this_r
 	prio_array_t *array, *dst_array;
 	struct list_head *head, *curr;
 	int idx, pulled = 0, pinned = 0, this_best_prio, busiest_best_prio;
-	int busiest_best_prio_seen;
+	int busiest_best_prio_seen = 0;
 	int skip_for_load; /* skip the task based on weighted load issues */
 	long rem_load_move;
 	task_t *tmp;
@@ -2057,11 +2057,6 @@ static int move_tasks(runqueue_t *this_r
 	pinned = 1;
 	this_best_prio = rq_best_prio(this_rq);
 	busiest_best_prio = rq_best_prio(busiest);
-	/*
-	 * Enable handling of the case where there is more than one task
-	 * with the best priority.
-	 */
-	busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 
 	/*
 	 * We first consider expired tasks. Those will likely not be

kernel/sched.c static int move_tasks(runqueue_t *this_r · line 2072

Quoted 6 lines
kernel/sched.c renamed from kernel/sched.c~ +3 -0
@@ -2072,6 +2067,13 @@ static int move_tasks(runqueue_t *this_r
 	if (busiest->expired->nr_active) {
 		array = busiest->expired;
 		dst_array = this_rq->expired;
+		/*
+		 * We already have one or more busiest best prio tasks on
+		 * active list.

This is a pretty bold assertion. How do we know that this is true.

Quoted 29 lines

So if we encounter any busiest best prio task

kernel/sched.c renamed from kernel/sched.c~ +8 -2
+		 * on expired list, consider it for the move, if it becomes
+		 * the best prio on new queue.
+		 */
+		busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 	} else {
 		array = busiest->active;
 		dst_array = this_rq->active;
@@ -2089,6 +2091,7 @@ skip_bitmap:
 		if (array == busiest->expired && busiest->active->nr_active) {
 			array = busiest->active;
 			dst_array = this_rq->active;
+			busiest_best_prio_seen = 0;
 			goto new_array;
 		}
 		goto out;
@@ -2107,8 +2110,9 @@ skip_queue:
 	 * prio value) on its new queue regardless of its load weight
 	 */
 	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;
+	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
+		skip_for_load = !busiest_best_prio_seen &&
+				head->next == head->prev;
 	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
 		if (curr != head)

kernel/sched.c skip_queue: · line 2142

Quoted 8 lines
kernel/sched.c renamed from kernel/sched.c~ +0 -2
@@ -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++;

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

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

Looks like there's a NOT missing doesn't it. So there is an error but I don't think that your patch is the right way to fix it. We just need to negate the above assignment. E.g.

skip_for_load = !(busiest_best_prio_seen || idx != busiest_best_prio);

or

skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;

whichever is more efficient.

That just will not be enough. busiest_best_prio needs to be set to '1' whenever we skip the first best priority task(not whenever we move it)

And we also need to initialize busiest_best_prio_seen inside this check. (like in my patch)

	if (busiest->expired->nr_active) {

And we need to reset busiest_best_prio_seen to '0' whenever we finished the checking of expired list (and move onto active list) and there are no best prio tasks on expired list..

Quoted 9 lines

kernel/sched.c static int move_tasks(runqueue_t *this_r · line 2072

Quoted 7 lines
kernel/sched.c renamed from kernel/sched.c~ +3 -0
@@ -2072,6 +2067,13 @@ static int move_tasks(runqueue_t *this_r
 	if (busiest->expired->nr_active) {
 		array = busiest->expired;
 		dst_array = this_rq->expired;
+		/*
+		 * We already have one or more busiest best prio tasks on
+		 * active list.

This is a pretty bold assertion. How do we know that this is true.

That comment refers to when 'busiest_best_prio_seen' is initialized to '1'. Comment needs to be fixed.

thanks,
suresh

Quoted 46 lines
Quoted 30 lines

So if we encounter any busiest best prio task

kernel/sched.c renamed from kernel/sched.c~ +8 -2
+		 * on expired list, consider it for the move, if it becomes
+		 * the best prio on new queue.
+		 */
+		busiest_best_prio_seen = busiest_best_prio == busiest->curr->prio;
 	} else {
 		array = busiest->active;
 		dst_array = this_rq->active;
@@ -2089,6 +2091,7 @@ skip_bitmap:
 		if (array == busiest->expired && busiest->active->nr_active) {
 			array = busiest->active;
 			dst_array = this_rq->active;
+			busiest_best_prio_seen = 0;
 			goto new_array;
 		}
 		goto out;
@@ -2107,8 +2110,9 @@ skip_queue:
 	 * prio value) on its new queue regardless of its load weight
 	 */
 	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;
+	if (skip_for_load && idx < this_best_prio && idx == busiest_best_prio)
+		skip_for_load = !busiest_best_prio_seen &&
+				head->next == head->prev;
 	if (skip_for_load ||
 	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
 		if (curr != head)

kernel/sched.c skip_queue: · line 2142

Quoted 8 lines
kernel/sched.c renamed from kernel/sched.c~ +0 -2
@@ -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++;

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

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

Looks like there's a NOT missing doesn't it. So there is an error but I don't think that your patch is the right way to fix it. We just need to negate the above assignment. E.g.

skip_for_load = !(busiest_best_prio_seen || idx != busiest_best_prio);

Quoted 8 lines
Quoted 5 lines

or

skip_for_load = !busiest_best_prio_seen && idx == busiest_best_prio;

whichever is more efficient.

That just will not be enough. busiest_best_prio needs to be set to '1' whenever we skip the first best priority task(not whenever we move it)

Yes, I just realized that. It needs to be done after skip_for_load has been finalized.

Quoted 4 lines

And we also need to initialize busiest_best_prio_seen inside this check. (like in my patch)

	if (busiest->expired->nr_active) {

Why? It's already initialized. If the current running task has prio==busiest_best_prio then we know that can_migrate_task() will prevent it from being moved so it's safe to move any other tasks we meet with that priority.

Quoted 4 lines

And we need to reset busiest_best_prio_seen to '0' whenever we finished the checking of expired list (and move onto active list) and there are no best prio tasks on expired list..

No we don't. Once we've skipped one it's OK to move any others that we find. We'll never move more than one as a result of overriding the skip anyhow .

Quoted 10 lines
Quoted 9 lines

kernel/sched.c static int move_tasks(runqueue_t *this_r · line 2072

Quoted 8 lines
kernel/sched.c renamed from kernel/sched.c~ +3 -0
@@ -2072,6 +2067,13 @@ static int move_tasks(runqueue_t *this_r
 	if (busiest->expired->nr_active) {
 		array = busiest->expired;
 		dst_array = this_rq->expired;
+		/*
+		 * We already have one or more busiest best prio tasks on
+		 * active list.

This is a pretty bold assertion. How do we know that this is true.

Quoted 2 lines

That comment refers to when 'busiest_best_prio_seen' is initialized to '1'. Comment needs to be fixed.

But you initialized it to zero.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

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

And we also need to initialize busiest_best_prio_seen inside this check. (like in my patch)

	if (busiest->expired->nr_active) {

Why? It's already initialized. If the current running task has prio==busiest_best_prio then we know that can_migrate_task() will prevent it from being moved so it's safe to move any other tasks we meet with that priority.

Quoted 7 lines
Quoted 3 lines

And we need to reset busiest_best_prio_seen to '0' whenever we finished the checking of expired list (and move onto active list) and there are no best prio tasks on expired list..

No we don't. Once we've skipped one it's OK to move any others that we find. We'll never move more than one as a result of overriding the skip anyhow .

Ok.

Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

kernel/sched.c static int move_tasks(runqueue_t *this_r · line 2072

Quoted 9 lines
kernel/sched.c renamed from kernel/sched.c~ +3 -0
@@ -2072,6 +2067,13 @@ static int move_tasks(runqueue_t *this_r
 	if (busiest->expired->nr_active) {
 		array = busiest->expired;
 		dst_array = this_rq->expired;
+		/*
+		 * We already have one or more busiest best prio tasks on
+		 * active list.

This is a pretty bold assertion. How do we know that this is true.

Quoted 4 lines
Quoted 2 lines

That comment refers to when 'busiest_best_prio_seen' is initialized to '1'. Comment needs to be fixed.

But you initialized it to zero.

That comment refers to the assignment code below it..

Anyhow, now that we are going with fixes to your patch, this is a moot point.

thanks,
suresh