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
