Re: [PATCH] sched: Avoid unnecessarily moving highest priority taskmove_tasks()

From: Peter Williams
Date: Mon Apr 24 2006 - 19:04:32 EST


Siddha, Suresh B wrote:
On Sat, Apr 22, 2006 at 11:31:29AM +1000, Peter Williams wrote:
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.

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.

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.


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.

Signed-off-by: Suresh Siddha <suresh.b.siddha@xxxxxxxxx>

--- linux-2.6.17-rc1/kernel/sched.c~ 2006-04-21 13:12:01.749853640 -0700
+++ linux-2.6.17-rc1/kernel/sched.c 2006-04-24 10:07:39.624162896 -0700
@@ -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.

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

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++;


Peter
--
Peter Williams pwil3058@xxxxxxxxxxxxxx

"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/