Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1198879 > unrolled thread

Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency mask model

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency  mask model Peter Zijlstra <peterz@infradead.org> - 2015-08-03 16:10 +0200
    Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency  mask model Frederic Weisbecker <fweisbec@gmail.com> - 2015-08-03 17:00 +0200
      Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency  mask model Peter Zijlstra <peterz@infradead.org> - 2015-08-03 19:10 +0200
        Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency  mask model Frederic Weisbecker <fweisbec@gmail.com> - 2015-08-03 19:40 +0200
          Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency  mask model Peter Zijlstra <peterz@infradead.org> - 2015-08-04 09:50 +0200

#1198879 — Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency mask model

On Thu, Jul 23, 2015 at 06:42:12PM +0200, Frederic Weisbecker wrote:
> Instead of providing asynchronous checks for the nohz subsystem to verify
> sched tick dependency, migrate sched to the new mask.
> 
> The easiest is to recycle the current asynchronous tick dependency check
> which verifies the class of the current task and its requirements for
> periodic preemption checks.
> 
> We need to evaluate this tick dependency on three places:
> 
> 1) Task enqueue: One or more tasks have been enqueued, we must check
>    if those are competing with the current task.
> 
> 2) Task dequeue: A possibly competing task has been dequeued, clear the
>    tick dependency if needed.
> 
> 3) schedule(): we might be switching to a task of another scheduler
>    class. Each class has its preemption rules, we must re-evaluate it.

This is insane.. You add a whole bunch of work per wakeup/sleep/context
switch to avoid some work at tick time. That's a broken trade-off.

We can context switch _waaaay_ more than we have ticks.

Furthermore, you do tons of pointless work, we call add_nr_running()
from the individual classes, and then your routine goes and checks what
class we're in etc..


--
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/

[toc] | [next] | [standalone]

#1198918

On Mon, Aug 03, 2015 at 04:00:46PM +0200, Peter Zijlstra wrote:
> On Thu, Jul 23, 2015 at 06:42:12PM +0200, Frederic Weisbecker wrote:
> > Instead of providing asynchronous checks for the nohz subsystem to verify
> > sched tick dependency, migrate sched to the new mask.
> > 
> > The easiest is to recycle the current asynchronous tick dependency check
> > which verifies the class of the current task and its requirements for
> > periodic preemption checks.
> > 
> > We need to evaluate this tick dependency on three places:
> > 
> > 1) Task enqueue: One or more tasks have been enqueued, we must check
> >    if those are competing with the current task.
> > 
> > 2) Task dequeue: A possibly competing task has been dequeued, clear the
> >    tick dependency if needed.
> > 
> > 3) schedule(): we might be switching to a task of another scheduler
> >    class. Each class has its preemption rules, we must re-evaluate it.
> 
> This is insane.. You add a whole bunch of work per wakeup/sleep/context
> switch to avoid some work at tick time. That's a broken trade-off.
> 
> We can context switch _waaaay_ more than we have ticks.
> 
> Furthermore, you do tons of pointless work, we call add_nr_running()
> from the individual classes, and then your routine goes and checks what
> class we're in etc..

I think I could remove the context switch part. But then I need to find a
way to perform these checks on enqueue and dequeue task time:

  sched_update_dependency(cpu)
  {
      if (SCHED_FIFO task on the cpu runqueue) {
          tick_nohz_clear_dep(cpu)
	  return;
      }

      if (SCHED_RR task on the cpu runqueue) {
          if (more than one such task) {
              tick_nohz_set_dep(cpu)
	      return;
	  }
      }

      if (SCHED_NORMAL task on the cpu runqueue) {
          if (more than one such task) {
	      tick_nohz_set_dep(cpu)
	      return;
	  }
      }

      tick_nohz_clear_dep();
   }

That's still heavyweight because enqueue and dequeue can be very frequent
but we get rid of the sched_switch hook because we don't care about the
current task at all.

Now, consider that we could cut all this checks into parts and optimize
that per sched class::enqueue/dequeue.

So we can divide the dependency into:

         struct rq {
	     ...
	     int nr_fifo;
	     int nr_rr;
	     int nr_normal;
	}


	int rq_update_tick_dep(struct rq *rq)
	{
	     if (rq->nr_fifo && (rq->nr_rr > 1 || rq->nr_normal > 1))
	         tick_nohz_set_dep(SCHED_TICK_DEP);
             else
	         tick_nohz_set_dep(SCHED_TICK_DEP)
        }

Then we add or dec the relevant counter fields from the various sched_class::enqueue/dequeue.
I think I saw some of these counters already exist but perhaps not all of them. There are
per class rqs but rt_nr_running counts tasks without distinction of policies.
--
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/

[toc] | [prev] | [next] | [standalone]

#1199076

On Mon, Aug 03, 2015 at 04:50:33PM +0200, Frederic Weisbecker wrote:
> On Mon, Aug 03, 2015 at 04:00:46PM +0200, Peter Zijlstra wrote:
> > On Thu, Jul 23, 2015 at 06:42:12PM +0200, Frederic Weisbecker wrote:
> > > Instead of providing asynchronous checks for the nohz subsystem to verify
> > > sched tick dependency, migrate sched to the new mask.
> > > 
> > > The easiest is to recycle the current asynchronous tick dependency check
> > > which verifies the class of the current task and its requirements for
> > > periodic preemption checks.
> > > 
> > > We need to evaluate this tick dependency on three places:
> > > 
> > > 1) Task enqueue: One or more tasks have been enqueued, we must check
> > >    if those are competing with the current task.
> > > 
> > > 2) Task dequeue: A possibly competing task has been dequeued, clear the
> > >    tick dependency if needed.
> > > 
> > > 3) schedule(): we might be switching to a task of another scheduler
> > >    class. Each class has its preemption rules, we must re-evaluate it.
> > 
> > This is insane.. You add a whole bunch of work per wakeup/sleep/context
> > switch to avoid some work at tick time. That's a broken trade-off.
> > 
> > We can context switch _waaaay_ more than we have ticks.
> > 
> > Furthermore, you do tons of pointless work, we call add_nr_running()
> > from the individual classes, and then your routine goes and checks what
> > class we're in etc..
> 
> I think I could remove the context switch part. But then I need to find a
> way to perform these checks on enqueue and dequeue task time:

Uhm, but you already do!?

>   sched_update_dependency(cpu)
>   {
>       if (SCHED_FIFO task on the cpu runqueue) {
>           tick_nohz_clear_dep(cpu)
> 	  return;
>       }
> 
>       if (SCHED_RR task on the cpu runqueue) {
>           if (more than one such task) {
>               tick_nohz_set_dep(cpu)
> 	      return;
> 	  }
>       }
> 
>       if (SCHED_NORMAL task on the cpu runqueue) {
>           if (more than one such task) {
> 	      tick_nohz_set_dep(cpu)
> 	      return;
> 	  }
>       }
> 
>       tick_nohz_clear_dep();
>    }
> 
> That's still heavyweight because enqueue and dequeue can be very frequent
> but we get rid of the sched_switch hook because we don't care about the
> current task at all.
> 
> Now, consider that we could cut all this checks into parts and optimize
> that per sched class::enqueue/dequeue.

You can, seeing how {add,sub}_nr_running() is called from the individual
classes.

> So we can divide the dependency into:
> 
>          struct rq {
> 	     ...
> 	     int nr_fifo;
> 	     int nr_rr;

Those are currently summed together in: rq->rt.rt_nr_total, I suppose we
can split RR out.

> 	     int nr_normal;

That's called: rq->cfs.h_nr_running

But you've forgotten about SCHED_DEADLINE, we count those in:
rq->dl.dl_nr_running.

> 	}
> 
> 
> 	int rq_update_tick_dep(struct rq *rq)
> 	{
> 	     if (rq->nr_fifo && (rq->nr_rr > 1 || rq->nr_normal > 1))
> 	         tick_nohz_set_dep(SCHED_TICK_DEP);
>              else
> 	         tick_nohz_set_dep(SCHED_TICK_DEP)
>         }
> 
> Then we add or dec the relevant counter fields from the various
> sched_class::enqueue/dequeue.  I think I saw some of these counters
> already exist but perhaps not all of them. There are per class rqs but
> rt_nr_running counts tasks without distinction of policies.

Right. At which point you'll end up with:

	if (rq->dl.dl_nr_running > 1 || rq->rt.rr_nr_total > 1 || rq->cfs.h_nr_running > 1)
		tick_nohz_set_dep(SCHED_TICK_DEP)
	else
		tick_nohz_clear_dep(SCHED_TICK_DEP)

But I fear that'll still be rather expensive in some cases. Imagine a
case where we frequently flip between 1-2 tasks on the queue for any one
of those classes, then we'll do a whole bunch of dep flips, which is an
atomic op.
--
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/

[toc] | [prev] | [next] | [standalone]

#1199118

On Mon, Aug 03, 2015 at 07:09:11PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 03, 2015 at 04:50:33PM +0200, Frederic Weisbecker wrote:
> > I think I could remove the context switch part. But then I need to find a
> > way to perform these checks on enqueue and dequeue task time:
> 
> Uhm, but you already do!?

Sure but I would like to avoid adding a context switch step, although
dequeuing itself often happens on context switch but we don't have
the choice but to check at that step.

> > So we can divide the dependency into:
> > 
> >          struct rq {
> > 	     ...
> > 	     int nr_fifo;
> > 	     int nr_rr;
> 
> Those are currently summed together in: rq->rt.rt_nr_total, I suppose we
> can split RR out.

Right

> 
> > 	     int nr_normal;
> 
> That's called: rq->cfs.h_nr_running

Ok.

> 
> But you've forgotten about SCHED_DEADLINE, we count those in:
> rq->dl.dl_nr_running.

Indeed. Hmm, there is no preemption between SCHED_DEALINE tasks, right?
So I can treat it like SCHED_FIFO.

> > 	}
> > 
> > 
> > 	int rq_update_tick_dep(struct rq *rq)
> > 	{
> > 	     if (rq->nr_fifo && (rq->nr_rr > 1 || rq->nr_normal > 1))

Oops I meant:

    if (rq->nr_fifo || (rq->nr_rr < 2 && rq->nr_normal < 2))
       clear_dep()
    else
       set_dep()

> > 	         tick_nohz_set_dep(SCHED_TICK_DEP);
> >              else
> > 	         tick_nohz_set_dep(SCHED_TICK_DEP)
> >         }
> > 
> > Then we add or dec the relevant counter fields from the various
> > sched_class::enqueue/dequeue.  I think I saw some of these counters
> > already exist but perhaps not all of them. There are per class rqs but
> > rt_nr_running counts tasks without distinction of policies.
> 
> Right. At which point you'll end up with:
> 
> 	if (rq->dl.dl_nr_running > 1 || rq->rt.rr_nr_total > 1 || rq->cfs.h_nr_running > 1)
> 		tick_nohz_set_dep(SCHED_TICK_DEP)
> 	else
> 		tick_nohz_clear_dep(SCHED_TICK_DEP)

It there is no preemption between deadline tasks, and SCHED_DEALINE is of higher
priority than SCHED_RR that would rather be:

        if (rq->dl.dl_nr_running || rq->rt.ff_nr_running || (rq->rt.rr_nr_running < 2 && rq->cfs.h_nr_running < 2))
	    clear_dep()
	else
	    set_dep()

> 
> But I fear that'll still be rather expensive in some cases. Imagine a
> case where we frequently flip between 1-2 tasks on the queue for any one
> of those classes, then we'll do a whole bunch of dep flips, which is an
> atomic op.

Indeed. Now doing such a thing on a nohz full CPU sounds insane.
--
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/

[toc] | [prev] | [next] | [standalone]

#1199483

On Mon, Aug 03, 2015 at 07:30:32PM +0200, Frederic Weisbecker wrote:
> > But you've forgotten about SCHED_DEADLINE, we count those in:
> > rq->dl.dl_nr_running.
> 
> Indeed. Hmm, there is no preemption between SCHED_DEALINE tasks, right?
> So I can treat it like SCHED_FIFO.

Sadly no. Even though EDF has static job priority (once a job is
activated its priority doesn't change anymore) DEADLINE also has a CBS
component and that needs the tick regardless, even with a single task.

So any deadline task running means we cannot stop the tick.
--
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/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web