Skip to contentSkip to conversation

sched: idle_avg and migration latency

question Daniel Lezcano 3 participants 7 messages Dec 10, 2013 – Dec 11, 2013

lore
Share & tools
lore
#0 lore raw

Hi All,

I am trying to understand how is computed the idle_avg and how it is used regarding the migration latency.

1. What is the sysctl_sched_migration_cost value ? It is initialized to 500000UL. Is it an arbitrarily chosen value ? Could it change depending on the hardware performances ?

2. The idle_balance function checks:

        if (this_rq->avg_idle < sysctl_sched_migration_cost)
                return 0;

IIUC, it is not worth to migrate a task to this cpu as we expect to run another task before we can pull a task to the current cpu, right ?

Then if there is no task to balance we will enter idle, thus we initialize the idle_stamp to the current clock.

When another task is woken up with the ttwu_do_wakeup, the duration of the idle time is computed in there:

	if (rq->idle_stamp) {
		u64 delta = rq_clock(rq) - rq->idle_stamp;
		u64 max = 2*sysctl_sched_migration_cost;

		if (delta > max)
			rq->avg_idle = max;
		else
			update_avg(&rq->avg_idle, delta);
		rq->idle_stamp = 0;
	}

Why is the 'delta' leveraged by 'max' ?

3. And finally the function update_avg does:

	s64 diff = sample - *avg;
	*avg += diff >> 3;

Why is diff >> 3 used instead of the number of values ?

Thanks in advance for any answers

-- Daniel

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#1 lore raw
Quoted 8 lines · Daniel Lezcano

Hi All,

I am trying to understand how is computed the idle_avg and how it is used regarding the migration latency.

1. What is the sysctl_sched_migration_cost value ? It is initialized to 500000UL. Is it an arbitrarily chosen value ? Could it change depending on the hardware performances ?

Yeah, it's a magic number. We used to use boot time measurements.

Quoted 7 lines

2. The idle_balance function checks:

         if (this_rq->avg_idle < sysctl_sched_migration_cost)
                 return 0;

IIUC, it is not worth to migrate a task to this cpu as we expect to run another task before we can pull a task to the current cpu, right ?

No, that's all about not beating living hell outta ourselves on every micro-idle. As with all load balancing, it's usually too much balancing that creates a problem. You need it, but it's really expensive, so less is more.

Quoted 17 lines

Then if there is no task to balance we will enter idle, thus we initialize the idle_stamp to the current clock.

When another task is woken up with the ttwu_do_wakeup, the duration of the idle time is computed in there:

	if (rq->idle_stamp) {
		u64 delta = rq_clock(rq) - rq->idle_stamp;
		u64 max = 2*sysctl_sched_migration_cost;

		if (delta > max)
			rq->avg_idle = max;
		else
			update_avg(&rq->avg_idle, delta);
		rq->idle_stamp = 0;
	}
Quoted 1 line

Why is the 'delta' leveraged by 'max' ?

That has changed a little recently. I originally slammed avg_idle itself straight to max to ensure that a bursty load would idle balance, and not use stale data. If you start cross core switching at high frequency, you'll still shut idle balancing quickly.

Quoted 6 lines

3. And finally the function update_avg does:

	s64 diff = sample - *avg;
	*avg += diff >> 3;

Why is diff >> 3 used instead of the number of values ?

Ingo's quick like bunny smooth average.

-Mike

#5 lore raw
In reply to Daniel Lezcano

CC to MikeG, he written this part. :)
I try to explain sth I know. I am sorry if my understanding incorrect.

Quoted 9 lines · Daniel Lezcano

Hi All,

I am trying to understand how is computed the idle_avg and how it is used regarding the migration latency.

1. What is the sysctl_sched_migration_cost value ? It is initialized to 500000UL. Is it an arbitrarily chosen value ? Could it change depending on the hardware performances ?

current sysctl_sched_mirgration_cost is 0.5ms, used to limit overscheduling. Guess it is a kind of arbitrary. But it can be rewrite at /proc/sys/kernel/sched_migration_cost_ns.
So if you find some new suitable value in particular scenario. guess PeterZ like to modify it. :)

Quoted 9 lines

2. The idle_balance function checks:

        if (this_rq->avg_idle < sysctl_sched_migration_cost)
                return 0;

IIUC, it is not worth to migrate a task to this cpu as we expect to run another task before we can pull a task to the current cpu, right ?

No, that used to prevent every idle_balance cause a task migration if idle balance happens too much and too quick, -- frequency more than task migration limitation.

Quoted 3 lines

Then if there is no task to balance we will enter idle, thus we initialize the idle_stamp to the current clock.

If we pulled task, we will restart frequency calculation by set idle_stamp = 0;
or if new task adding this rq, allow more idle_balance.

Quoted 18 lines

When another task is woken up with the ttwu_do_wakeup, the duration of the idle time is computed in there:

    if (rq->idle_stamp) {
        u64 delta = rq_clock(rq) - rq->idle_stamp;
        u64 max = 2*sysctl_sched_migration_cost;

        if (delta > max)
            rq->avg_idle = max;
        else
            update_avg(&rq->avg_idle, delta);
        rq->idle_stamp = 0;
    }

Why is the 'delta' leveraged by 'max' ?

Quoted 6 lines

3. And finally the function update_avg does:

    s64 diff = sample - *avg;
    *avg += diff >> 3;

Why is diff >> 3 used instead of the number of values ?

It is a kind of decay. but has no idea of why this value '3'. Guess MikeG has some reason.

Quoted 5 lines

Thanks in advance for any answers

-- Daniel

Signature · 2 lines
Thanks
    Alex
#2 lore raw
In reply to Mike Galbraith
Quoted 42 lines · Mike Galbraith
Quoted 8 lines · Daniel Lezcano

Hi All,

I am trying to understand how is computed the idle_avg and how it is used regarding the migration latency.

1. What is the sysctl_sched_migration_cost value ? It is initialized to 500000UL. Is it an arbitrarily chosen value ? Could it change depending on the hardware performances ?

Yeah, it's a magic number. We used to use boot time measurements.

Quoted 7 lines

2. The idle_balance function checks:

          if (this_rq->avg_idle < sysctl_sched_migration_cost)
                  return 0;

IIUC, it is not worth to migrate a task to this cpu as we expect to run another task before we can pull a task to the current cpu, right ?

No, that's all about not beating living hell outta ourselves on every micro-idle. As with all load balancing, it's usually too much balancing that creates a problem. You need it, but it's really expensive, so less is more.

Quoted 17 lines

Then if there is no task to balance we will enter idle, thus we initialize the idle_stamp to the current clock.

When another task is woken up with the ttwu_do_wakeup, the duration of the idle time is computed in there:

	if (rq->idle_stamp) {
		u64 delta = rq_clock(rq) - rq->idle_stamp;
		u64 max = 2*sysctl_sched_migration_cost;

		if (delta > max)
			rq->avg_idle = max;
		else
			update_avg(&rq->avg_idle, delta);
		rq->idle_stamp = 0;
	}
Quoted 6 lines
Quoted 1 line

Why is the 'delta' leveraged by 'max' ?

That has changed a little recently. I originally slammed avg_idle itself straight to max to ensure that a bursty load would idle balance, and not use stale data. If you start cross core switching at high frequency, you'll still shut idle balancing quickly.

Ok, thanks for the explanation.

I think I am a bit puzzled with the 'idle_avg' name. I am guessing the semantic of this variable is "how long this cpu has been idle".

The idle duration, with the no_hz, could be long, several seconds if the work queues have been migrated and if the timer affinity is set to another cpu. So if we fall in this case and there is a burst of activity + micro-idle and idle_avg is not leverage to max, it will stay high during an amount of time, thus pulling tasks at each micro idle period, right ?

Quoted 8 lines
Quoted 6 lines

3. And finally the function update_avg does:

	s64 diff = sample - *avg;
	*avg += diff >> 3;

Why is diff >> 3 used instead of the number of values ?

Ingo's quick like bunny smooth average.

Yeah, average computation on-the-fly. But why 'divide by 8' ? (Cc'ed Ingo).

Thanks for taking the time to answer.

-- Daniel

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#6 lore raw
In reply to Alex Shi
Quoted 34 lines · Alex Shi

CC to MikeG, he written this part. :)
I try to explain sth I know. I am sorry if my understanding incorrect.

Quoted 9 lines · Daniel Lezcano

Hi All,

I am trying to understand how is computed the idle_avg and how it is used regarding the migration latency.

1. What is the sysctl_sched_migration_cost value ? It is initialized to 500000UL. Is it an arbitrarily chosen value ? Could it change depending on the hardware performances ?

current sysctl_sched_mirgration_cost is 0.5ms, used to limit overscheduling. Guess it is a kind of arbitrary. But it can be rewrite at /proc/sys/kernel/sched_migration_cost_ns.
So if you find some new suitable value in particular scenario. guess PeterZ like to modify it. :)

Quoted 9 lines

2. The idle_balance function checks:

         if (this_rq->avg_idle < sysctl_sched_migration_cost)
                 return 0;

IIUC, it is not worth to migrate a task to this cpu as we expect to run another task before we can pull a task to the current cpu, right ?

No, that used to prevent every idle_balance cause a task migration if idle balance happens too much and too quick, -- frequency more than task migration limitation.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

Then if there is no task to balance we will enter idle, thus we initialize the idle_stamp to the current clock.

If we pulled task, we will restart frequency calculation by set idle_stamp = 0;
or if new task adding this rq, allow more idle_balance.

Thanks Alex for the explanation.

Quoted 33 lines
Quoted 17 lines

When another task is woken up with the ttwu_do_wakeup, the duration of the idle time is computed in there:

     if (rq->idle_stamp) {
         u64 delta = rq_clock(rq) - rq->idle_stamp;
         u64 max = 2*sysctl_sched_migration_cost;

         if (delta > max)
             rq->avg_idle = max;
         else
             update_avg(&rq->avg_idle, delta);
         rq->idle_stamp = 0;
     }

Why is the 'delta' leveraged by 'max' ?

Quoted 6 lines

3. And finally the function update_avg does:

     s64 diff = sample - *avg;
     *avg += diff >> 3;

Why is diff >> 3 used instead of the number of values ?

It is a kind of decay. but has no idea of why this value '3'. Guess MikeG has some reason.

Quoted 5 lines

Thanks in advance for any answers

-- Daniel

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#3 lore raw
In reply to Daniel Lezcano
Quoted 11 lines · Daniel Lezcano
Quoted 5 lines

That has changed a little recently. I originally slammed avg_idle itself straight to max to ensure that a bursty load would idle balance, and not use stale data. If you start cross core switching at high frequency, you'll still shut idle balancing quickly.

Ok, thanks for the explanation.

I think I am a bit puzzled with the 'idle_avg' name. I am guessing the semantic of this variable is "how long this cpu has been idle".

Quoted 6 lines

The idle duration, with the no_hz, could be long, several seconds if the work queues have been migrated and if the timer affinity is set to another cpu. So if we fall in this case and there is a burst of activity
+ micro-idle and idle_avg is not leverage to max, it will stay high during an amount of time, thus pulling tasks at each micro idle period, right ?

yes, I think so.

Signature · 2 lines
Thanks
    Alex
#4 lore raw
In reply to Daniel Lezcano
Quoted 2 lines · Daniel Lezcano

I think I am a bit puzzled with the 'idle_avg' name. I am guessing the semantic of this variable is "how long this cpu has been idle".

Average distance between idles.

Quoted 6 lines

The idle duration, with the no_hz, could be long, several seconds if the work queues have been migrated and if the timer affinity is set to another cpu. So if we fall in this case and there is a burst of activity
+ micro-idle and idle_avg is not leverage to max, it will stay high during an amount of time, thus pulling tasks at each micro idle period, right ?

Yeah, it cares about shutting the thing down when idle distance is too small to be affordable, but cranking is back up quickly as to not damage generic bursty load utilization too much. It tries to be dirt simply and cheap, not perfect.

For nohz_full loads, you'll likely want to kill most if not all wake and idle balancing, or at least put some serious roadblocks up.. but then you'll have isolated and pinned everything anyway if you deeply care about perturbation. All load balancing totally sucks in that regard, as do those darn workqueues you mentioned.

-Mike