Load balancing between CPUs

[Sergey Glushchenko]

Hello,

As a part of my lottery scheduler work, I'm trying to figure out
how to implement load balancing between CPUs.

As I understand it, the goal is equal load of all CPUs. Periodically
we obtain number of ready-to-execute processes on each CPU (per-cpu
runqueue length) and 'push' processes from high-loaded CPUs to 
low-loaded. This scheme is quite simple. The problem is CPU affinity,
which we didn't count. 

Here is what I'm thinking about:
	- when new process created via fork(), usched 'pushed' it
	  to the first most low-loaded CPU;
	- add to the struct lwp field 'lastcpu' to track the CPU
	  on which this lwp was scheduled last time;
	- followed Matt's mail on Sat, 26 Nov 2005, add to the 
	  struct lwp field 'desiredcpu', which can be setup by
	  usched's setcpumask();
	- balancing scheme: first we try to find on most high-loaded 
	  CPU lwp with 'desiredcpu' equal to most low-loaded and then 
	  'pushed' it on success. If we can't, doing the same but 
	  with 'lastcpu' field. If both previous are failed, pick up
	  a random lwp and 'push' it to the most low-loaded CPU, breaking
	  cpu affinity.. Do this step until runqueues on both CPUs
	  will be equal (+/- 1).

With this scheme we balance only 2 CPUs at one balancing cycle. Maybe 
we need to do this for more than one CPU pair..

Eventually, we will have (I hope) fully-supported 1:1 threading. So,
maybe we need to do some effort on scheduling different threads of
one multithreaded process on different CPUs?

Feedback and comments are appreciated.

--
Sergey Glushchenko