Re: [RFC PATCH RT] push waiting rt tasks to cpus with lower prios.

[mike kravetz <kravetz@us.ibm.com>]

On Tue, Oct 09, 2007 at 01:59:37PM -0400, Steven Rostedt wrote:
> This has been complied tested (and no more ;-)
> 
> The idea here is when we find a situation that we just scheduled in an
> RT task and we either pushed a lesser RT task away or more than one RT
> task was scheduled on this CPU before scheduling occurred.
> 
> The answer that this patch does is to do a O(n) search of CPUs for the
> CPU with the lowest prio task running. When that CPU is found the next
> highest RT task is pushed to that CPU.
> 
> Some notes:
> 
> 1) no lock is taken while looking for the lowest priority CPU. When one
> is found, only that CPU's lock is taken and after that a check is made
> to see if it is still a candidate to push the RT task over. If not, we
> try the search again, for a max of 3 tries.

I did something like this a while ago for another scheduling project.
A couple 'possible' optimizations to think about are:
1) Only scan the remote runqueues once and keep a local copy of the
   remote priorities for subsequent 'scans'.  Accessing the remote
   runqueus (CPU specific cache lines) can be expensive.
2) When verifying priorities, just perform spin_trylock() on the remote
   runqueue.  If you can immediately get it great.  If not, it implies
   someone else is messing with the runqueue and there is a good chance
   the data you pre-fetched (curr->Priority) is invalid.  In this case
   it might be faster to just 'move on' to the next candidate runqueue/CPU.
   i.e. The next highest priority that the new task can preempt.

Of course, these 'optimizations' would change the algorithm.  Trying to
make any decision based on data that is changing is always a crap shoot. :)
-- 
Mike