Skip to contentSkip to conversation

highest and lowest priority job of a runqueue

DISCUSSION Martin Roehricht 2 participants 10 messages Jul 25, 2007 – Aug 2, 2007 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 7 lines · Martin Roehricht

I thought I might use (given a list with tmp pointers to all CPUs)

	rq = cpu_rq(tmp->cpu);
	task_load = rq->curr->load_weight;

but this always returns 128 regardless of the fact if a task currently runs on that CPU or not. I guess it returns the load of the migration thread, but I'm not sure. I would like to migrate specific tasks throughout find_busiest_group().

Okay, I think I found that my assumption should be just fine and I had trouble with some debugging output via the show_schedstat() function. The "rq->curr->load_weight" returns what it is supposed to return. :-)

I am still uncertain on how to resolve the specific highest or lowest priority job:

Quoted 4 lines

I was wondering how I may retrieve
(a) the priority/load of the highest and the lowest priority task of a runqueue (in a multiprocessor system), and
(b) the corresponding pointer to this task?

I will try something of the form (pseudocode like):

int idx;
struct list_head *head;
struct task_struct *task;

idx = sched_find_first_bit(rq->active->bitmap); head = array->queue + idx;
task = list_entry(head, struct task_struct, run_list);

For the lowest priority task a function like "sched_find_last_bit()" might be useful. Would this be a good way to succeed?

Quoted 2 lines

Furthermore, is it correct, that the current migration strategy (move_tasks()) chooses automatically the highest priority task?

Thanks,
Martin

#2 lore raw

Scheduling the highest priority task

In reply to a message not in the archive

Hi,

perhaps someone can give me a hint what I should consider to look for in order to change the ("old" 2.6.21) scheduler such that it schedules the highest priority task of a given runqueue.
Given a multiprocessor system I currently observe that whenever there are two tasks on one CPU, the lower priority one is migrated to another CPU. But I don't realize why this happens. From looking at the source code I thought it should be the highest priority one (lowest bit set in the runqueue's bitmap) according to

	idx = sched_find_first_bit(array->bitmap);
within move_tasks(). The idx value is then used as an index (surprise) to the linked list of tasks of this particular priority and one task is picked:
	head = array->queue + idx;
        curr = head->prev;
        tmp = list_entry(curr, struct task_struct, run_list);

Is my assumption wrong? Using printk()s within this code section makes the system just hang completely quite soon. The schedstats do not notify me immediately. So I am a bit lost on how to track down or trace the problem.

Can anybody confirm that my observations are correct that the scheduler picks the lowest priority job of a runqueue for migration? What needs to be changed in order to pick the highest priority one?

Martin

#3 lore raw

Re: Scheduling the highest priority task

Quoted 16 lines · Martin Roehricht

perhaps someone can give me a hint what I should consider to look for in order to change the ("old" 2.6.21) scheduler such that it schedules the highest priority task of a given runqueue.
Given a multiprocessor system I currently observe that whenever there are two tasks on one CPU, the lower priority one is migrated to another CPU. But I don't realize why this happens. From looking at the source code I thought it should be the highest priority one (lowest bit set in the runqueue's bitmap) according to

	idx = sched_find_first_bit(array->bitmap);
within move_tasks(). The idx value is then used as an index (surprise) 
to the linked list of tasks of this particular priority and one task is 
picked:
	head = array->queue + idx;
        curr = head->prev;
        tmp = list_entry(curr, struct task_struct, run_list);
Quoted 3 lines

Can anybody confirm that my observations are correct that the scheduler picks the lowest priority job of a runqueue for migration? What needs to be changed in order to pick the highest priority one?

in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one, _except_ if that task is running on another CPU or is too 'cache hot':

        if (skip_for_load ||
            !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {

also, from the priority-queue at 'idx', we pick head->prev, i.e. we process the list in the opposite order as schedule(). (This got changed in CFS to process in the same direction - which is more logical and also yield the most cache-cold tasks for migration.)

i hope this helps.

Quoted 4 lines

Is my assumption wrong? Using printk()s within this code section makes the system just hang completely quite soon. The schedstats do not notify me immediately. So I am a bit lost on how to track down or trace the problem.

yep, printk locks up. You can use my static tracer:

http://people.redhat.com/mingo/latency-tracing-patches/

add explicit static tracepoints to the scheduler code you want to instrument via trace_special(x,y,z) calls [with parameters that interest you most], and you can read out the trace via:

http://people.redhat.com/mingo/latency-tracing-patches/trace-it.c

Ingo

#4 lore raw

Re: Scheduling the highest priority task

Quoted 1 line · Ingo Molnar

in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one, _except_ if that task is running on another CPU or is too 'cache hot':

But why is it, that the scheduler picks the lowest priority one? I thought sched_find_first_bit() picks the index of the lowest order bit in the bitmap and thus the highest priority job. Is that wrong? What needs to be changed to let the scheduler pick the highest priority task from a given runqueue?
I am very confused ...

Martin

#5 lore raw

Re: Scheduling the highest priority task

Quoted 10 lines · Martin Roehricht
Quoted 3 lines · Ingo Molnar

in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one, _except_ if that task is running on another CPU or is too 'cache hot':

But why is it, that the scheduler picks the lowest priority one? I thought sched_find_first_bit() picks the index of the lowest order bit in the bitmap and thus the highest priority job. Is that wrong? What needs to be changed to let the scheduler pick the highest priority task from a given runqueue? I am very confused ...

it first picks the lowest index (i.e. the highest priority active priority-queue), but within those tasks (each task in that priority queue has equal priority) the load-balancer has freedom to pick any. Based on performance data we went for picking from the tail of the queue.

Ingo

#6 lore raw

Re: Scheduling the highest priority task

Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Martin Roehricht
Quoted 1 line · Ingo Molnar

in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one, _except_ if that task is running on another CPU or is too 'cache hot':

But why is it, that the scheduler picks the lowest priority one? I thought sched_find_first_bit() picks the index of the lowest order bit in the bitmap and thus the highest priority job. Is that wrong? What needs to be changed to let the scheduler pick the highest priority task from a given runqueue? I am very confused ...

it first picks the lowest index (i.e. the highest priority active priority-queue), but within those tasks (each task in that priority queue has equal priority) the load-balancer has freedom to pick any. Based on performance data we went for picking from the tail of the queue.

That's fine with me, that within the same priority-queue any task can be chosen. But assume two tasks with highly different priorities, such as 105 and 135 are scheduled on the same processor and one of them is now to be migrated -- shouldn't be the queue with task P=105 considered first for migration by this code? Both tasks would use different queues with their own linked lists, right?

Martin

#7 lore raw

Re: Scheduling the highest priority task

Quoted 6 lines · Martin Roehricht

That's fine with me, that within the same priority-queue any task can be chosen. But assume two tasks with highly different priorities, such as 105 and 135 are scheduled on the same processor and one of them is now to be migrated -- shouldn't be the queue with task P=105 considered first for migration by this code? Both tasks would use different queues with their own linked lists, right?

yes. What makes you believe that the lower priority one (prio 135) is chosen? [ as i said before, that will only be chosen if all tasks in the higher-priority queue (prio 105) are either already running on a CPU or have recently run so that the cache-hot logic skips them. ]

Ingo

#8 lore raw

Re: Scheduling the highest priority task

Quoted 5 lines · Ingo Molnar
Quoted 1 line · Martin Roehricht

That's fine with me, that within the same priority-queue any task can be chosen. But assume two tasks with highly different priorities, such as 105 and 135 are scheduled on the same processor and one of them is now to be migrated -- shouldn't be the queue with task P=105 considered first for migration by this code? Both tasks would use different queues with their own linked lists, right?

yes. What makes you believe that the lower priority one (prio 135) is chosen? [ as i said before, that will only be chosen if all tasks in the higher-priority queue (prio 105) are either already running on a CPU or have recently run so that the cache-hot logic skips them. ]

This believe is primarily based on my observations of multiple benchmark runs and also on your statement earlier: »in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one«.

Perhaps it is just an unfortunate coincidence that at ~90% of the time a migration decision is made, the higher priority process is currently cache hot whereas the lower priority process is not. That would be unlucky for me as I would like to decide upon specific runtime circumstances whether the highest or the lowest priority job of a runqueue should be migrated to another CPU. :-/

Martin

#9 lore raw

Re: Scheduling the highest priority task

Quoted 15 lines · Martin Roehricht
Quoted 9 lines · Ingo Molnar
Quoted 6 lines · Martin Roehricht

That's fine with me, that within the same priority-queue any task can be chosen. But assume two tasks with highly different priorities, such as 105 and 135 are scheduled on the same processor and one of them is now to be migrated -- shouldn't be the queue with task P=105 considered first for migration by this code? Both tasks would use different queues with their own linked lists, right?

Quoted 4 lines

yes. What makes you believe that the lower priority one (prio 135) is chosen? [ as i said before, that will only be chosen if all tasks in the higher-priority queue (prio 105) are either already running on a CPU or have recently run so that the cache-hot logic skips them. ]

Quoted 4 lines

This believe is primarily based on my observations of multiple benchmark runs and also on your statement earlier: »in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one«.

oh, sorry, that was meant to be the 'highest priority one' :-/

so i think you got it all right, i just typoed that first sentence.

Ingo

#10 lore raw

Re: Scheduling the highest priority task

Quoted 7 lines · Ingo Molnar
Quoted 5 lines · Martin Roehricht
Quoted 4 lines · Ingo Molnar
Quoted 1 line · Martin Roehricht

That's fine with me, that within the same priority-queue any task can be chosen. But assume two tasks with highly different priorities, such as 105 and 135 are scheduled on the same processor and one of them is now to be migrated -- shouldn't be the queue with task P=105 considered first for migration by this code? Both tasks would use different queues with their own linked lists, right?

Quoted 7 lines
Quoted 3 lines
Quoted 1 line

yes. What makes you believe that the lower priority one (prio 135) is chosen? [ as i said before, that will only be chosen if all tasks in the higher-priority queue (prio 105) are either already running on a CPU or have recently run so that the cache-hot logic skips them. ]

This believe is primarily based on my observations of multiple benchmark runs and also on your statement earlier: »in the SMP migration code, the 'old scheduler' indeed picks the lowest priority one«.

oh, sorry, that was meant to be the 'highest priority one' :-/

so i think you got it all right, i just typoed that first sentence.

Okay, now I think I understood this part of the code correctly. The reason why I observe a continous migration of the _lower_ priority tasks is most probably due to the fact that the higher priority one is currently running, according to:
can_migrate_task() in move_tasks(), and therein:

if (task_running(rq, p))
return 0;

I tracked down via an extended /proc/schedstats that my tasks fall frequently into this pitfall. I basically solved it by making use of the more active push-strategy which is called later by load_balance() once the move_tasks() function did not succeed. So in case I need the higher priority tasks, I return immediately from move_tasks().

Thanks for your help,
Martin