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

Groups > linux.kernel > #1498005 > unrolled thread

About group scheduling for SCHED_DEADLINE

Back to article view | Back to linux.kernel

Contents

  About group scheduling for SCHED_DEADLINE Luca Abeni <luca.abeni@unitn.it> - 2016-10-09 21:50 +0200
    Re: About group scheduling for SCHED_DEADLINE Peter Zijlstra <peterz@infradead.org> - 2016-10-10 12:20 +0200
      Re: About group scheduling for SCHED_DEADLINE Peter Zijlstra <peterz@infradead.org> - 2016-10-10 13:10 +0200
      Re: About group scheduling for SCHED_DEADLINE Peter Zijlstra <peterz@infradead.org> - 2016-10-10 14:10 +0200

#1498005 — About group scheduling for SCHED_DEADLINE

Hi all,

after the SCHED_DEADLINE TODO page
(https://github.com/jlelli/sched-deadline/wiki/TODOs) has been
published, there has been a private exchange of emails about the "group
scheduling (cgroups)" / "hierarchical DEADLINE server for FIFO/RR"
item.
I'd like to start a discussion about this topic, so that the TODO item
can be implemented in a way that is agreed by everyone.
I add in cc all the people involved in the previous email exchange
about this topic + Andrea, who originally developed a patch
implementing hierarchical SCHED_DEADLINE (see
http://retis.sssup.it/~nino/publication/rtlws14bdm.pdf and cited
papers); I do not know who else to cc, so feel free to forward this
email to the relevant people or to tell me who to add in future emails.

So, I started to think about this, and here are some ideas to start a
discussion:
1) First of all, we need to decide the software interface. If I
   understand correctly (please correct me if I am wrong), cgroups let
   you specify a runtime and a period, and this means that the cgroup is
   reserved the specified runtime every period on all the cgroup's
   CPUs... In other words, it is not possible to reserve different
   runtimes/periods on different CPUs. Is this correct? Is this what we
   want for hierarchical SCHED_DEADLINE? Or do we want to allow the
   possibility to schedule a cgroup with multiple "deadline servers"
   having different runtime/period parameters? (the first solution is
   easier to implement, the second one offers more degrees of freedom
   that might be used to improve the real-time schedulability)
2) Is it ok have only two levels in the scheduling hierarchy (at least
   in the first implementation)?
3) If this "hierarchical SCHED_DEADLINE" is implemented using multiple
   "deadline servers" (one per cgroup's CPU) to schedule the cgroup's
   tasks, should these servers be bound to CPUs, or should they be free
   to migrate between the cgroup's CPUs? In the first case, each one of
   these deadline servers can be implemented as a sched_dl_entity
   structure that can be scheduled only on a specific runqueue. The
   second case is (in my understanding) more complex to implement,
   because the dl push/pull code uses task structures, so a dl
   scheduling entity per server is not enough (unless we modify the
   migration code). At least, this is what I understood when looking at
   the code.
4) From a more theoretical point of view, it would be good to define
   the scheduling model that needs to be implemented (based on something
   previously described on some paper, or defining a new model from
   scratch).

Well, I hope this can be a good starting point for a discussion :)


                                Luca

[toc] | [next] | [standalone]

#1498212

On Sun, Oct 09, 2016 at 09:39:38PM +0200, Luca Abeni wrote:

> So, I started to think about this, and here are some ideas to start a
> discussion:
> 1) First of all, we need to decide the software interface. If I
>    understand correctly (please correct me if I am wrong), cgroups let
>    you specify a runtime and a period, and this means that the cgroup is
>    reserved the specified runtime every period on all the cgroup's
>    CPUs... In other words, it is not possible to reserve different
>    runtimes/periods on different CPUs. Is this correct?

That is the current state for RR/FIFO, but given that that is a complete
trainwreck, I think we can deprecate that and change the interface.

My primary concern is getting something that actually works and makes
theoretical sense, and then we can worry about the interface.

>    Is this what we
>    want for hierarchical SCHED_DEADLINE? Or do we want to allow the
>    possibility to schedule a cgroup with multiple "deadline servers"
>    having different runtime/period parameters? (the first solution is
>    easier to implement, the second one offers more degrees of freedom
>    that might be used to improve the real-time schedulability)

Right, I'm not sure what makes most sense, nor am I entirely sure on
what you mean with multiple deadline servers, is that different
different variables per CPU?

> 2) Is it ok have only two levels in the scheduling hierarchy (at least
>    in the first implementation)?

Yeah, I think so. It doesn't really make sense to stack this stuff too
deep anyway, and it only makes sense to stack downwards (eg, have DL
host RR/FIFO/CFS). Stakcing upwards (have CFS host DL for example)
doesn't make any sense to me.


> 4) From a more theoretical point of view, it would be good to define
>    the scheduling model that needs to be implemented (based on something
>    previously described on some paper, or defining a new model from
>    scratch).
> 
> Well, I hope this can be a good starting point for a discussion :)

Right, so the problem we have is unspecified SCHED_FIFO on SMP and
historical behaviour.

As you know we've extended FIFO to SMP by G-FIFO (run the m highest prio
tasks on m CPUs). But along with that, we allow arbitrary affinity masks
for RR/FIFO tasks.

(Note that RR is broken in the G-FIFO model, but that's a different
discussion for a different day).

Now, the proposed model has identical CBS parameters for every (v)cpu of
the cgroup. This means that a cgroup must be overprovisioned in the
general case where nr_tasks < nr_cpus (and worse, the parameters must
match the max task).

This leads to vast amounts of wasted resources.

The alternative is different but fixed parameters per cpu, but that is
somewhat unwieldy in that it increases the configuration burden. But you
can indeed minimize the wasted resources and deal with the affinity
problem (AFAICT).

However, I think there's a third alternative. I have memories of a paper
from UNC (I'd have to dig through the site to see if I can still find
it) where they argue that for a hierarchical (G-)FIFO you should use
minimal concurrency, that is run the minimal number of (v)cpu servers.

This would mean we give a single CBS parameter and carve out the minimal
number (of max CBS) (v)cpu that fit in that.

I'm just not sure how the random affinity crap works out for that, if we
have the (v)cpu servers migratable in the G-EDF and migrate to whatever
is demanded by the task at runtime it might work, but who knows..
Analysis would be needed I think.



Any other opinions / options?

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

#1498234

On Mon, Oct 10, 2016 at 12:15:58PM +0200, Peter Zijlstra wrote:
> However, I think there's a third alternative. I have memories of a paper
> from UNC (I'd have to dig through the site to see if I can still find
> it) where they argue that for a hierarchical (G-)FIFO you should use
> minimal concurrency, that is run the minimal number of (v)cpu servers.
> 
> This would mean we give a single CBS parameter and carve out the minimal
> number (of max CBS) (v)cpu that fit in that.
> 
> I'm just not sure how the random affinity crap works out for that, if we
> have the (v)cpu servers migratable in the G-EDF and migrate to whatever
> is demanded by the task at runtime it might work, but who knows..
> Analysis would be needed I think.

Hurm,.. thinking slightly more on this, this ends up being a DL task
with random affinity, which is problematic IIRC.

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

#1498252

On Mon, Oct 10, 2016 at 12:15:58PM +0200, Peter Zijlstra wrote:
> Right, so the problem we have is unspecified SCHED_FIFO on SMP and
> historical behaviour.
> 
> As you know we've extended FIFO to SMP by G-FIFO (run the m highest prio
> tasks on m CPUs). But along with that, we allow arbitrary affinity masks
> for RR/FIFO tasks.
> 
> (Note that RR is broken in the G-FIFO model, but that's a different
> discussion for a different day).
> 
> Now, the proposed model has identical CBS parameters for every (v)cpu of
> the cgroup. This means that a cgroup must be overprovisioned in the
> general case where nr_tasks < nr_cpus (and worse, the parameters must
> match the max task).
> 
> This leads to vast amounts of wasted resources.
> 
> The alternative is different but fixed parameters per cpu, but that is
> somewhat unwieldy in that it increases the configuration burden. But you
> can indeed minimize the wasted resources and deal with the affinity
> problem (AFAICT).
> 

Hurm, so I think both proposals above rely on deadline servers with
single CPU affinity, something which we currently do not support at all,
and is something that should be defined/fixed first I think.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web