sched: Avoid unnecessarily moving highest priority task move_tasks()
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
@@ -2029,6 +2029,7 @@ int can_migrate_task(task_t *p, runqueuereturn 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++;
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
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 changingthis_best_prioanyhow 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
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_rprio_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_rif (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++;
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_seento '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_loadis always set to '1'(because ofbusiest_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_seenwill be set to '0', when we traverse the only highest priority task on this queue(which happens to be on expired list), we setskip_for_loadto '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 <[email protected]>kernel/sched.c renamed from kernel/sched.c~ +1
-6@@ -2045,7 +2045,7 @@ static int move_tasks(runqueue_t *this_rprio_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_rif (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
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_rif (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
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_prioneeds 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_seeninside 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_seento '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_rif (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
Quoted 9 lines · Peter Williams
Quoted 3 lines · Suresh B
And we also need to initialize
busiest_best_prio_seeninside 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_seento '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_rif (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