Code review showed, that the hierarchical order of the leaf
CFS runqueues introduced by commit 67e8625 ("sched: Introduce 
hierarchal order on shares update list") is not yet achieved.
(See description of first patch for an example.)

These two patches (against v3.0-rc7) try to fix that.

Patch 1 causes all leaves that are inserted during one 
enqueue_task_fair() call to be inserted right next to each other
at the beginning of the list.

Patch 2 prevents the existing code from punching holes
in the leaf-hierarchy as this would cause patch 1 to
re-insert them at possibly wrong positions.


What remains are some multiprocessor aspects: the leaf_cfs_rq_list
is traversed without holding rq->lock. So it can be modified while
a traversal is in progress. That means: while users of the list are 
guaranteed to traverse all elements in hierarchical order, they
are not guaranteed that they will see the parent of an already visited
child. But as far as I currently understand the code, this seems not
to be a problem as the code only relies on the former guarantee.

Regards
Jan

Jan H. Schönherr (2):
  sched: Enforce order of leaf CFS runqueues
  sched: Prevent removal of leaf CFS runqueues with on_list children

 kernel/sched.c      |    1 +
 kernel/sched_fair.c |   45 +++++++++++++++++++++++++++++----------------
 2 files changed, 30 insertions(+), 16 deletions(-)

-- 
1.7.3.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/