RE: fair group scheduler not so fair?

[Peter Zijlstra <a.p.zijlstra@chello.nl>]

On Thu, 2008-05-22 at 13:18 -0700, Li, Tong N wrote:
> Peter,
> 
> I didn't look at your patches, but I thought you were flattening group
> weights down to task-level so that the scheduler only looks at per-task
> weights. That'd make group fairness as good as task fairness gets. Is
> this still the case?

We still have hierarchical runqueues - getting rid of that is another
tree I'm working on, it has an EEVDF based rq scheduler.

For load balancing purposes we are indeed projecting everything to a
flat level.

A rather quick description of what we do:


We'll have:

  task-weight     - the weight for a task
  group-weight    - the weight for a group (same units as for tasks)
  group-shares    - the weight for a group on a particular cpu
  runqueue-weight - the sum of weights

we compute group-shares as:

  s_(i,g) = W_g * rw_(i,g) / \Sum_j rw_(j,g)
  
s_(i,g)  := group g's shares for cpu i
W_g      := group g's weight
rw_(i,g) := group g's runqueue weight for cpu i

(all for a given group)

We compute these shares while walking the task group tree bottom up,
since the shares for a child's group will affect the runqueue weight for
its parent.

We then select the busiest runqueue from the available set solely based
on top level runqueue weight (since that accurately reflects all the
child group weights after updating the shares).

We compute an imbalance between this rq and the busiest rq in top
weight.

Then, for this busiest cpu we compute the hierarchical load for each
group:

 h_load_(i,g) = rw_(i,0) \Prod_{l=1} s_(i,l)/rw_(i,{l-1})

Where l iterates over the tree levels (not the cpus).

h_load represents the full weight of the group as seen from the top
level. This is used to convert the weight of each moved task to top
weight, and we'll keep on moving tasks until the imbalance is satisfied.


Given the following:

      root
     / | \
   _A_ 1  2
  /| |\
 3 4 5 B
      / \
     6   7

     CPU0            CPU1
     root            root
     /  \            /  \
    A    1          A    2
   / \             / \
  4   B           3   5
     / \
    6   7


Numerical examples given the above scenario, assuming every body's
weight is 1024:

 s_(0,A) = s_(1,A) = 512
 s_(0,B) = 1024, s_(1,B) = 0

 rw_(0,A) = rw(1,A) = 2048
 rw_(0,B) = 2048, rw_(1,B) = 0

 h_load_(0,A) = h_load_(1,A) = 512
 h_load_(0,B) = 256, h_load(1,B) = 0