[Click] SortedTaskSched

[Eddie Kohler]

Should've read through to the end, sorry :(

> I can observe a situation like this:
> chatter: 58869: pd0, cycles 22874, on 0
> 
> chatter: 58869: td0, cycles 8000, on 0
> 
> chatter: 58869: pd1, cycles 22561, on 1
> 
> chatter: 58869: td1, cycles 7369, on 1
> 
> instead of : pd0 and td1 on 0
>                  pd1 and td0 on 1

Well the difference between 22874+8000 and 22874+7369 is pretty trivial.  I 
don't think the old SortedTaskSched guaranteed that it would provide exactly 
equal or optimal allocations.  In fact, if the difference between thread load is 
small enough (less than 1/8 the average load, which is the case here), 
SortedTaskSched will preserve the current allocation.  This is the right thing: 
constantly swapping allocations will kill cache behavior.

> Are there some other mechanisms which can take place during the rebalancing
> and
> the CPU cycles calculation?
> Moreover, which are the main differences in the implementation of the new
> BalancedThreadSched element?

The old element sorted all tasks in the router and did an overall assignment 
with little consideration of which tasks used to be scheduled where.  There were 
some subtle racecondition-type problems with this, in the case that tasks are 
created and destroyed dynamically.  The new element repeatedly moves tasks from 
the least-loaded thread to the most-loaded thread until it gets a pretty good 
allocation; its locking behavior is better, so it avoids potential race 
conditions.  The new element will probably have *more* of a tendency to stick 
with "pretty good but not perfect" allocations.

Eddie