[PATCH 0/2] Enforce hierarchical order of leaf CFS runqueues

From: Jan H. SchÃnherr
Date: Mon Jul 18 2011 - 06:52:03 EST

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.


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(-)


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