Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* Peter Zijlstra (peterz@infradead.org) wrote:
> On Mon, 2010-09-13 at 14:53 +0200, Peter Zijlstra wrote:
> > On Sun, 2010-09-12 at 16:37 -0400, Mathieu Desnoyers wrote:
> > > The whole point of my patch is not to have to do this latency vs performance
> > > tradeoff for low number of running threads. With your approach, lowering the
> > > granularity even when there are few threads running will very likely hurt
> > > performance, no ? 
> > 
> > But you presented it as a latency patch, not a throughput patch. And I'm
> > not sure it will matter enough to offset the computational cost it
> > introduces.

Can we agree that the patch I proposed is a patch that try to improve _latency_
under high load while preserving good throughput under lower load ? I find this
"performance" XOR "latency" dichotomy itching: it's like looking at an american
TV show where all bad guys are dressed in black, and the hero is in white.

> 
> 
> ---
> On Mon, 2010-09-13 at 14:53 +0200, Peter Zijlstra wrote:
> On Sun, 2010-09-12 at 16:37 -0400, Mathieu Desnoyers wrote:
> > > The whole point of my patch is not to have to do this latency vs performance
> > > tradeoff for low number of running threads. With your approach, lowering the
> > > granularity even when there are few threads running will very likely hurt
> > > performance, no ? 
> > 
> > But you presented it as a latency patch, not a throughput patch. And I'm
> > not sure it will matter enough to offset the computational cost it
> > introduces.
> > 
> 
> One option is to simply get rid of that stuff in check_preempt_tick()
> and instead do a wakeup-preempt check on the leftmost task instead.
> 
> The code as it stands today does that delta_exec < min_gran check to
> ensure current gets some runtime before doing that second preemption
> check, which compares vruntime with a wall-time measure.
> 
> Making that gran more complex doesn't really buy us much because for a
> system with different weights in the gran and slice lengths don't match
> up anyway.

So I bet this last sentence is about the example of a system with many nice 19
processes I told you about on IRC. Yes, this one is a bummer, as we would not
like to count them as running threads at all.

More comments below,

> 
> ---
> Subject: sched: Simplify tick preemption
> From: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Date: Mon Jul 05 13:56:30 CEST 2010
> 
> Check the current slice, if not expired, see if the leftmost task
> would otherwise have preempted current.
> 
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
>  kernel/sched_fair.c |   43 +++++++++++++++----------------------------
>  1 file changed, 15 insertions(+), 28 deletions(-)
> 
> Index: linux-2.6/kernel/sched_fair.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_fair.c
> +++ linux-2.6/kernel/sched_fair.c
> @@ -838,44 +838,34 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>  		se->vruntime -= cfs_rq->min_vruntime;
>  }
>  
> +static int
> +wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
> +
>  /*
>   * Preempt the current task with a newly woken task if needed:
>   */
>  static void
>  check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
>  {
> -	unsigned long ideal_runtime, delta_exec;
> +	unsigned long slice = sched_slice(cfs_rq, curr);

So you still compute the sched_slice(), based on sched_period(), based on
sysctl_sched_min_granularity *= nr_running when there are more than nr_latency
running threads.

> +
> +	if (curr->sum_exec_runtime - curr->prev_sum_exec_runtime < slice) {
> +		struct sched_entity *pse = __pick_next_entity(cfs_rq);
> +
> +		if (pse && wakeup_preempt_entity(curr, pse) == 1)
> +			goto preempt;
>  
> -	ideal_runtime = sched_slice(cfs_rq, curr);
> -	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
> -	if (delta_exec > ideal_runtime) {
> -		resched_task(rq_of(cfs_rq)->curr);
> -		/*
> -		 * The current task ran long enough, ensure it doesn't get
> -		 * re-elected due to buddy favours.
> -		 */
> -		clear_buddies(cfs_rq, curr);
>  		return;
>  	}
>  
>  	/*
> -	 * Ensure that a task that missed wakeup preemption by a
> -	 * narrow margin doesn't have to wait for a full slice.
> -	 * This also mitigates buddy induced latencies under load.
> +	 * The current task ran long enough, ensure it doesn't get
> +	 * re-elected due to buddy favours.
>  	 */
> -	if (!sched_feat(WAKEUP_PREEMPT))
> -		return;
> -
> -	if (delta_exec < sysctl_sched_min_granularity)
> -		return;

Well, the reason why this test is here seems to be that we don't want to trigger
"resched_task" more often than needed, and here it's defined by the granularity.
I don't quite see with what you are replacing this, other than "let's set the
resched flag all the time to save a 32-bit division". I figure out it's more
expensive the call the scheduler than to do a 32-bit div.

Thanks,

Mathieu

> +	clear_buddies(cfs_rq, curr);
>  
> -	if (cfs_rq->nr_running > 1) {
> -		struct sched_entity *se = __pick_next_entity(cfs_rq);
> -		s64 delta = curr->vruntime - se->vruntime;
> -
> -		if (delta > ideal_runtime)
> -			resched_task(rq_of(cfs_rq)->curr);
> -	}
> +preempt:
> +	resched_task(rq_of(cfs_rq)->curr);
>  }
>  
>  static void
> @@ -908,9 +898,6 @@ set_next_entity(struct cfs_rq *cfs_rq, s
>  	se->prev_sum_exec_runtime = se->sum_exec_runtime;
>  }
>  
> -static int
> -wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
> -
>  static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
>  {
>  	struct sched_entity *se = __pick_next_entity(cfs_rq);
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com