Messages in this thread | | | Date | Mon, 24 Jan 2011 13:04:39 -0500 | From | Rik van Riel <> | Subject | Re: [RFC -v6 PATCH 2/8] sched: limit the scope of clear_buddies |
| |
On 01/24/2011 12:57 PM, Peter Zijlstra wrote: > On Thu, 2011-01-20 at 16:33 -0500, Rik van Riel wrote: >> The clear_buddies function does not seem to play well with the concept >> of hierarchical runqueues. In the following tree, task groups are >> represented by 'G', tasks by 'T', next by 'n' and last by 'l'. >> >> (nl) >> / \ >> G(nl) G >> / \ \ >> T(l) T(n) T >> >> This situation can arise when a task is woken up T(n), and the previously >> running task T(l) is marked last. >> >> When clear_buddies is called from either T(l) or T(n), the next and last >> buddies of the group G(nl) will be cleared. This is not the desired >> result, since we would like to be able to find the other type of buddy >> in many cases. >> >> This especially a worry when implementing yield_task_fair through the >> buddy system. >> >> The fix is simple: only clear the buddy type that the task itself >> is indicated to be. As an added bonus, we stop walking up the tree >> when the buddy has already been cleared or pointed elsewhere. >> >> Signed-off-by: Rik van Riel<riel@redhat.coM> >> --- >> kernel/sched_fair.c | 30 +++++++++++++++++++++++------- >> 1 files changed, 23 insertions(+), 7 deletions(-) >> >> diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c >> index f4ee445..0321473 100644 >> --- a/kernel/sched_fair.c >> +++ b/kernel/sched_fair.c >> @@ -784,19 +784,35 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) >> __enqueue_entity(cfs_rq, se); >> } >> >> -static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se) >> +static void __clear_buddies_last(struct sched_entity *se) >> { >> - if (!se || cfs_rq->last == se) >> - cfs_rq->last = NULL; >> + for_each_sched_entity(se) { >> + struct cfs_rq *cfs_rq = cfs_rq_of(se); >> + if (cfs_rq->last == se) >> + cfs_rq->last = NULL; >> + else >> + break; >> + } >> +} >> >> - if (!se || cfs_rq->next == se) >> - cfs_rq->next = NULL; >> +static void __clear_buddies_next(struct sched_entity *se) >> +{ >> + for_each_sched_entity(se) { >> + struct cfs_rq *cfs_rq = cfs_rq_of(se); >> + if (cfs_rq->next == se) >> + cfs_rq->next = NULL; >> + else >> + break; >> + } >> } >> >> static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se) >> { >> - for_each_sched_entity(se) >> - __clear_buddies(cfs_rq_of(se), se); >> + if (cfs_rq->last == se) >> + __clear_buddies_last(se); >> + >> + if (cfs_rq->next == se) >> + __clear_buddies_next(se); >> } >> > > Right, I think this sorta matches with something the Google guys talked > about, they wanted to change pick_next_task() no always start from the > top but only go up one level when the current level ran out. > > It looks ok, just sad that we can now have two hierarchy traversals (and > 3 with the next patch).
On the other hand, I don't think we'll actually _do_ the hierarchy traversal most of the time, since pick_next_entity calls clear_buddies, every step of the way down the tree.
A hierarchy traversal will only be done if a task already has one type of buddy set, and then gets another type of buddy set, before it is rescheduled.
Eg. a task can have ->last set and then call yield, causing the ->yield buddy to get pointed at itself. When doing that, it will walk up the tree, clearing ->last.
I suspect that with this patch, we'll end up doing less tree traversal than before.
| |