LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: "Dario Faggioli" <raistlin@linux.it>
To: "Peter Zijlstra" <peterz@infradead.org>
Cc: faggioli@gandalf.sssup.it, henrik@austad.us,
	"Ingo Molnar" <mingo@elte.hu>,
	"linux-kernel" <linux-kernel@vger.kernel.org>,
	fabio@gandalf.sssup.it,
	"Michael Trimarchi" <trimarchimichael@yahoo.it>,
	"Thomas Gleixner" <tglx@linutronix.de>,
	"Steven Rostedt" <rostedt@goodmis.org>,
	"gregory.haskins" <gregory.haskins@gmail.com>
Subject: Re: Deadline scheduling (was: Re: Rearranging layout of code in  the scheduler)
Date: Fri, 31 Oct 2008 18:49:10 +0100 (CET)	[thread overview]
Message-ID: <45033.148.202.77.161.1225475350.squirrel@picard.linux.it> (raw)
In-Reply-To: <1225387034.7803.182.camel@twins>

On Gio, 30 Ottobre 2008 6:17 pm, Peter Zijlstra wrote:
> Right, ideally I'd like to see 2 EDF classes on top of FIFO, so that we
> end up with the following classes
>
>   hedf     - hard EDF
>   sedf     - soft EDF (bounded tardiness)
>   fifo/rr  - the current static priority scheduler
>   fair     - the current proportional fair scheduler
>   idle     - the idle scheduler
>
Oh, so two classes? Well, yes, could be nice.

> The two edf classes must share some state, so that the sedf class knows
> about the utilisation consumed by hedf, and the main difference between
> these two classes is the schedulability test.
>
Yep. Actually I think that schedulability test could be an issue as well,
especially if we like group/hierarchical approach, since the known
hierarchical admission tests are quite complex to implement and, probably,
time consuming if performed on-line in an highly dynamic (with respec to
to task arrival and leaving) system.

> The few problems this gives are things like kstopmachine and the
> migration threads, which should run at the max priority available on the
> system.
>
Yeah, that's exactly what we was thinking too.

Actually, I was also thinking that having fixed priority scheduling
_before_ EDF could be of some benefit if you have to be sure that a task
is going to be executed at a very precise instant in time, but have not a
precise about that yet.

> Perhaps we can introduce another class on top of hedf which will run
> just these two tasks and is not exposed to userspace (yes, I understand
> it will ruin just about any schedulability analysis).
Well, could be a solution... And if this is only used for such kind of
special tasks, maybe it is not impossible to bound or account for their
scheduling contribution... But I'm just shooting inthe dark here, sorry
about that! :-P

> We can do deadline inheritance and bandwidth inheritance by changing
> plist to a rb-tree/binary heap and mapping the static priority levels
> somewhere at the back and also propagating the actual task responsible
> for the boost down the chain (so as to be able to do bandwidth
> inheritance).
>
> From what I gather the sssup folks are doing that, although they
> reported that DI between disjoint schedule domains (partitions) posed an
> interesting problem.
>
Yes, that's right, this is what we are investigating and trying to do in
these days (... Or weeks... Or months!).

> Personally I'd like to see the full priority inversion issue solved by
> something like the proxy execution protocol, however the SMP extension
> thereof seems to be a tad expensive - found a book on graph theory, all
> that remains is finding time to read it :-)
>
Wow... So, good luck for that! :-)

Maybe it's my fault, but I see some issues with proxy execution and
similar protocols.
That is, if you have, let's say, task A blocked on task B, blocked on task
C, and you are using proxy execution, that means that you have not
dequeued A and B when they blocked, but that you, for example, filled a
pointer that reminds you, when you schedule them, that you have to
actually run C, am I right?

Now, what happens if C blocks on a non-rt mutex lock, or if it simply go
to sleep? Is that acceptable to track the blocking chain in order to
actually dequeue also A and B, and to requeue them again when C will wake
up as well?

Forgive if that's a stupid point... :-(

> The advantage of proxy execution is that its fully invariant to the
> schedule function and thus even works for proportional fair schedulers
> and any kind of scheduler hierarchy.
>
Yes, I agree and I like it very much too. If you go for it, you could also
add bandwidth inheritance (e.g., for group scheduling) and things like
that almost for free (if wanted! :-))

Regards,
Dario Faggioli



      parent reply	other threads:[~2008-10-31 18:17 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-10-28 15:34 Rearranging layout of code in the scheduler Henrik Austad
2008-10-28 16:50 ` Peter Zijlstra
2008-10-28 19:41   ` Henrik Austad
2008-10-30 16:49   ` faggioli
2008-10-30 17:17     ` Deadline scheduling (was: Re: Rearranging layout of code in the scheduler) Peter Zijlstra
2008-10-30 17:48       ` Peter Zijlstra
2008-10-30 21:44       ` Henrik Austad
2008-10-31  9:03         ` Peter Zijlstra
2008-10-31 12:09           ` Henrik Austad
2008-10-31 13:30             ` Peter Zijlstra
2008-10-31 15:05               ` Henrik Austad
2008-10-31 18:08         ` Dario Faggioli
2008-10-31 17:49       ` Dario Faggioli [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=45033.148.202.77.161.1225475350.squirrel@picard.linux.it \
    --to=raistlin@linux.it \
    --cc=fabio@gandalf.sssup.it \
    --cc=faggioli@gandalf.sssup.it \
    --cc=gregory.haskins@gmail.com \
    --cc=henrik@austad.us \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=tglx@linutronix.de \
    --cc=trimarchimichael@yahoo.it \
    --subject='Re: Deadline scheduling (was: Re: Rearranging layout of code in  the scheduler)' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).