Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755186Ab3FRJzm (ORCPT ); Tue, 18 Jun 2013 05:55:42 -0400 Received: from merlin.infradead.org ([205.233.59.134]:39629 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753678Ab3FRJzl (ORCPT ); Tue, 18 Jun 2013 05:55:41 -0400 Date: Tue, 18 Jun 2013 11:55:33 +0200 From: Peter Zijlstra To: Lei Wen Cc: linux-kernel@vger.kernel.org, Ingo Molnar Subject: Re: Question regarding put_prev_task in preempted condition Message-ID: <20130618095533.GI3204@twins.programming.kicks-ass.net> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2012-12-30) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2680 Lines: 74 On Sun, Jun 09, 2013 at 11:59:36PM +0800, Lei Wen wrote: > Hi Peter, > > While I am checking the preempt related code, I find a interesting part. > That is when preempt_schedule is called, for its preempt_count be added > PREEMPT_ACTIVE, so in __schedule() it could not be dequeued from rq > by deactivate_task. > > Thus in put_prev_task, which is called a little later in __schedule(), it > would call put_prev_task_fair, which finally calls put_prev_entity. > For current task is not dequeued from rq, so in this function, it would > enqueue it again to the rq by __enqueue_entity. > > Is there any reason to do like this, since entity already is over rq, > why need to queue it again? Because we keep the current running task outside of the actual queue structure. This is because every time we update the runtime (__update_curr) the key on which the tree is sorted (vruntime) is changed and we'd need to dequeue + enqueue to keep the tree in sync. By not having the actively running task in the tree we can avoid this; at the cost of having to dequeue on switching to the task and enqueue when switching from the task. > And if current rq's vruntime distribution like below, and vruntime with 8 > is the task that would be get preempted. So in __enqueue_entity, > its rb_left/rb_right would be set as NULL and reinserted into this RB tree. > Then seems to me now, the entity with vruntime of 3 would be disappeared > from the RB tree. > 13 > / \ > 8 19 > / \ > 3 11 > > I am not sure whether I understand the whole process correctly... > Would the example as above happen in our real life? No, the RB tree code will ensure we'll not loose 3. I suppose you're confused by rb_link_node() which does indeed clear the left and right node of the entity we're about to link. However, we link the previously unlinked entity as a leaf node. So your example is flawed; before insertion the tree would look something like: 13 / \ 11 19 / 3 Then the lookup in __enqueue_entity would find the place to insert 8 and would select the right sibling of 3: 13 / \ 11 19 / 3 \ (8) We'd then link 8 as a child leaf of 3; which will indeed have NULL leafs. rb_insert_color() will then fix up the tree so we conform to the RB constraints. Please read lib/rbtree.c:__rb_insert() the code is quite readable. -- 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/