[PATCH] sched: Skip looking at skip if next or last is set

[PATCH] sched: Skip looking at skip if next or last is set

[Srikar Dronamraju]

pick_next_entity() prefers next, then last. However code checks if the
left entity can be skipped even if next / last is set.

Check if left entity should be skipped only if next/last is not set.

Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 files changed, 15 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fdee793..cc97b12 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 	struct sched_entity *left = se;
 
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Someone really wants next to run. If it's not unfair, run it.
 	 */
-	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
+		se = cfs_rq->next;
+	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
+		/*
+		 * Prefer last buddy, try to return the CPU to a preempted
+		 * task.
+		 */
+		se = cfs_rq->last;
+	} else if (cfs_rq->skip == left) {
+		/*
+		 * Avoid running the skip buddy, if running something else
+		 * can be done without getting too unfair.
+		 */
+		struct sched_entity *second = __pick_next_entity(left);
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
 
-	/*
-	 * Prefer last buddy, try to return the CPU to a preempted task.
-	 */
-	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
-		se = cfs_rq->last;
-
-	/*
-	 * Someone really wants this to run. If it's not unfair, run it.
-	 */
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
-		se = cfs_rq->next;
-
 	clear_buddies(cfs_rq, se);
 
 	return se;

Re: [PATCH] sched: Skip looking at skip if next or last is set

[Peter Zijlstra]

On Mon, 2013-02-18 at 18:31 +0530, Srikar Dronamraju wrote:
> pick_next_entity() prefers next, then last. However code checks if the
> left entity can be skipped even if next / last is set.
> 
> Check if left entity should be skipped only if next/last is not set.

You fail to explain why its a problem and continue to make a horrid mess
of the code..

> Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> ---
>  kernel/sched/fair.c |   31 +++++++++++++++----------------
>  1 files changed, 15 insertions(+), 16 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index fdee793..cc97b12 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
>  	struct sched_entity *left = se;
>  
>  	/*
> -	 * Avoid running the skip buddy, if running something else can
> -	 * be done without getting too unfair.
> +	 * Someone really wants next to run. If it's not unfair, run it.
>  	 */
> -	if (cfs_rq->skip == se) {
> -		struct sched_entity *second = __pick_next_entity(se);
> +	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
> +		se = cfs_rq->next;
> +	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
> +		/*
> +		 * Prefer last buddy, try to return the CPU to a preempted
> +		 * task.
> +		 */
> +		se = cfs_rq->last;
> +	} else if (cfs_rq->skip == left) {
> +		/*
> +		 * Avoid running the skip buddy, if running something else
> +		 * can be done without getting too unfair.
> +		 */
> +		struct sched_entity *second = __pick_next_entity(left);
>  		if (second && wakeup_preempt_entity(second, left) < 1)
>  			se = second;
>  	}
>  
> -	/*
> -	 * Prefer last buddy, try to return the CPU to a preempted task.
> -	 */
> -	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
> -		se = cfs_rq->last;
> -
> -	/*
> -	 * Someone really wants this to run. If it's not unfair, run it.
> -	 */
> -	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
> -		se = cfs_rq->next;
> -
>  	clear_buddies(cfs_rq, se);
>  
>  	return se;
> 

Re: [PATCH] sched: Skip looking at skip if next or last is set

[Srikar Dronamraju]

* Peter Zijlstra <peterz@infradead.org> [2013-02-20 09:46:25]:

> On Mon, 2013-02-18 at 18:31 +0530, Srikar Dronamraju wrote:
> > pick_next_entity() prefers next, then last. However code checks if the
> > left entity can be skipped even if next / last is set.
> > 
> > Check if left entity should be skipped only if next/last is not set.
> 
> You fail to explain why its a problem and continue to make a horrid mess
> of the code..
> 

If we look at the comments above pick_next_entity(),  it states:
/*
 * Pick the next process, keeping these things in mind, in this order:
 * 1) keep things fair between processes/task groups
 * 2) pick the "next" process, since someone really wants that to run
 * 3) pick the "last" process, for cache locality
 * 4) do not run the "skip" process, if something else is available
 */ 

Currently the code checks in the reverse order, though the preference is
correctly maintained as listed in comments.  But in some cases, we might be
doing redundant checks.  Lets assume next is set, then we should avoid 
checking for skip, last and their fairness with left.

So what I intended to do was change the order, i.e check for last only if next
is not set (or was picking next was unfair wrt left) and check for "something
else (second from left)" if last is not set (or picking last was unfair wrt
left).

However after sending the patch, I stumbled across these links.
https://lkml.org/lkml/2012/1/16/500 and https://lkml.org/lkml/2012/1/25/195

> > Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> > ---
> >  kernel/sched/fair.c |   31 +++++++++++++++----------------
> >  1 files changed, 15 insertions(+), 16 deletions(-)
> > 
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index fdee793..cc97b12 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
> >  	struct sched_entity *left = se;
> >  
> >  	/*
> > -	 * Avoid running the skip buddy, if running something else can
> > -	 * be done without getting too unfair.
> > +	 * Someone really wants next to run. If it's not unfair, run it.
> >  	 */
> > -	if (cfs_rq->skip == se) {
> > -		struct sched_entity *second = __pick_next_entity(se);
> > +	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
> > +		se = cfs_rq->next;
> > +	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
> > +		/*
> > +		 * Prefer last buddy, try to return the CPU to a preempted
> > +		 * task.
> > +		 */
> > +		se = cfs_rq->last;
> > +	} else if (cfs_rq->skip == left) {
> > +		/*
> > +		 * Avoid running the skip buddy, if running something else
> > +		 * can be done without getting too unfair.
> > +		 */
> > +		struct sched_entity *second = __pick_next_entity(left);
> >  		if (second && wakeup_preempt_entity(second, left) < 1)
> >  			se = second;
> >  	}
> >  
> > -	/*
> > -	 * Prefer last buddy, try to return the CPU to a preempted task.
> > -	 */
> > -	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
> > -		se = cfs_rq->last;
> > -
> > -	/*
> > -	 * Someone really wants this to run. If it's not unfair, run it.
> > -	 */
> > -	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
> > -		se = cfs_rq->next;
> > -
> >  	clear_buddies(cfs_rq, se);
> >  
> >  	return se;
> > 
> 
> 

-- 
Thanks and Regards
Srikar Dronamraju

Re: [PATCH] sched: Skip looking at skip if next or last is set

[Michael Wang]

On 02/22/2013 12:06 AM, Srikar Dronamraju wrote:
> * Peter Zijlstra <peterz@infradead.org> [2013-02-20 09:46:25]:
> 
>> On Mon, 2013-02-18 at 18:31 +0530, Srikar Dronamraju wrote:
>>> pick_next_entity() prefers next, then last. However code checks if the
>>> left entity can be skipped even if next / last is set.
>>>
>>> Check if left entity should be skipped only if next/last is not set.
>>
>> You fail to explain why its a problem and continue to make a horrid mess
>> of the code..
>>
> 
> If we look at the comments above pick_next_entity(),  it states:
> /*
>  * Pick the next process, keeping these things in mind, in this order:
>  * 1) keep things fair between processes/task groups
>  * 2) pick the "next" process, since someone really wants that to run
>  * 3) pick the "last" process, for cache locality
>  * 4) do not run the "skip" process, if something else is available
>  */ 
> 
> Currently the code checks in the reverse order, though the preference is
> correctly maintained as listed in comments.  But in some cases, we might be
> doing redundant checks.  Lets assume next is set, then we should avoid 
> checking for skip, last and their fairness with left.
> 
> So what I intended to do was change the order, i.e check for last only if next
> is not set (or was picking next was unfair wrt left) and check for "something
> else (second from left)" if last is not set (or picking last was unfair wrt
> left).
> 
> However after sending the patch, I stumbled across these links.
> https://lkml.org/lkml/2012/1/16/500 and https://lkml.org/lkml/2012/1/25/195

Hi, Srikar

That drag me back to the time when I'm starting to look at scheduler ;-)

Actually I give up this idea since I missed one point that the code will
be optimized by the compiler, and usually it will become some logical we
could not image.

My patch is correct logically, but it may not benefit scheduler a lot, I
don't think there will be a benchmark show us better results, and in
scheduler world, benchmark talks...

Regards,
Michael Wang

> 
>>> Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
>>> ---
>>>  kernel/sched/fair.c |   31 +++++++++++++++----------------
>>>  1 files changed, 15 insertions(+), 16 deletions(-)
>>>
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index fdee793..cc97b12 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
>>>  	struct sched_entity *left = se;
>>>  
>>>  	/*
>>> -	 * Avoid running the skip buddy, if running something else can
>>> -	 * be done without getting too unfair.
>>> +	 * Someone really wants next to run. If it's not unfair, run it.
>>>  	 */
>>> -	if (cfs_rq->skip == se) {
>>> -		struct sched_entity *second = __pick_next_entity(se);
>>> +	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
>>> +		se = cfs_rq->next;
>>> +	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
>>> +		/*
>>> +		 * Prefer last buddy, try to return the CPU to a preempted
>>> +		 * task.
>>> +		 */
>>> +		se = cfs_rq->last;
>>> +	} else if (cfs_rq->skip == left) {
>>> +		/*
>>> +		 * Avoid running the skip buddy, if running something else
>>> +		 * can be done without getting too unfair.
>>> +		 */
>>> +		struct sched_entity *second = __pick_next_entity(left);
>>>  		if (second && wakeup_preempt_entity(second, left) < 1)
>>>  			se = second;
>>>  	}
>>>  
>>> -	/*
>>> -	 * Prefer last buddy, try to return the CPU to a preempted task.
>>> -	 */
>>> -	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
>>> -		se = cfs_rq->last;
>>> -
>>> -	/*
>>> -	 * Someone really wants this to run. If it's not unfair, run it.
>>> -	 */
>>> -	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>> -		se = cfs_rq->next;
>>> -
>>>  	clear_buddies(cfs_rq, se);
>>>  
>>>  	return se;
>>>
>>
>>
>