On migrate_disable() and latencies

[Peter Zijlstra <peterz@infradead.org>]

On Wed, 2011-07-20 at 02:37 +0200, Thomas Gleixner wrote:
>    - Twist your brain around the schedulability impact of the
>      migrate_disable() approach.
> 
>      A really interesting research topic for our friends from the
>      academic universe. Relevant and conclusive (even short notice)
>      papers and/or talks on that topic have a reserved slot in the
>      Kernel developers track at the Realtime Linux Workshop in Prague
>      in October this year. 

>From what I can tell it can induce a latency in the order of
max-migrate-disable-period * nr-cpus.

The scenario is on where you stack N migrate-disable tasks on a run
queue (necessarily of increasing priority). Doing this requires all cpus
in the system to be as busy, for otherwise the task would simply be
moved to another cpu.

Anyway, once you manage to stack these migrate-disable tasks, all other
tasks go to sleep, leaving a vacuum. Normally we would migrate tasks to
fill the vacuum left by the tasks going to sleep, but clearly
migrate-disable prohibits this.

So we have this stack of migrate-disable tasks and M-1 idle cpus (loss
of utilization). Now it takes the length of the migrate-disable region
of the highest priority task on the stack (the one running) to complete
and enable migration again. This will instantly move the task away to an
idle cpu. This will then need to happen min(N-1, M-1) times before the
lowest priority migrate_disable task can run again or all cpus are busy.

Therefore the worst case latency is in the order of
max-migrate-disable-period * nr-cpus.

Currently we have no means of measuring these latencies, this is
something we need to grow, I think Steven can fairly easy craft a
migrate_disable runtime tracer -- it needs to use t->se.sum_exec_runtime
for measure so as to only count the actual time spend on the task and
ignore any time it was blocked.

Once we have this, its back to the old game of 'lock'-breaking.