LKML Archive on
help / color / mirror / Atom feed
From: Peter Zijlstra <>
Cc:, Ingo Molnar <>,
	linux-kernel <>,,
	Michael Trimarchi <>,
	Thomas Gleixner <>,
	Steven Rostedt <>,
	"gregory.haskins" <>
Subject: Deadline scheduling (was: Re: Rearranging layout of code in the scheduler)
Date: Thu, 30 Oct 2008 18:17:14 +0100	[thread overview]
Message-ID: <1225387034.7803.182.camel@twins> (raw)
In-Reply-To: <>

On Thu, 2008-10-30 at 17:49 +0100, wrote:
> Quoting Peter Zijlstra <>:
> >> Before I dive in, I should probably justify my motivations for writing
> >> this email. I'm working away on implementing an EDF scheduler for real
> >> time tasks in the kernel. This again leads to hacking at the existing
> >> source as I'm not about to toss out the entire scheduler - just replace
> >> (by some Kconfig switch) the RR/FIFO classes. As to why I'm looking at
> >> EDF, I think the answer to that is a bit too long (and not appropriate
> >> for this email anyway) so I'll leave that part out.
> Well, I understand that, but it could be interesting... At least to me. :-)
> > You and a few other folks.
> Yes, here we are! :-)
> We also have some code, but it still is highly experimental and we are  
> deeply rearranging it.
> > The most interesting part of EDF is not the
> > actual scheduler itself (although there are fun issues with that as
> > well), but extending the Priority Inheritance framework to deal with all
> > the fun cases that come with EDF.
> The main problem is that, especially to deal with SMP systems, we also  
> need to investigate theoretical issues and find out what the best  
> approach could be.
> > Well, adding a sched_class, no need to replace anything besides that.
> >
> I'm not saying anything in possible sched.c and sched_{fair|rt}.c code  
> rearranging, I also only wonder why replacing fixed priority RT  
> scheduling with EDF.
> I think they both could be in... Maybe we can discuss on where, I mean  
> on which position, in the linked list of scheduling classes, to put  
> each of them.

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

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.

[ NOTE: read EDF as any deadline scheduler, so it might as well be
        pfair PD^2 scheduler. ]

The few problems this gives are things like kstopmachine and the
migration threads, which should run at the max priority available on the

[ NOTE: although possibly we could make an exception for the migration
        threads, as we generally don't need to migrate running RT tasks]

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).

Which leaves us with the big issue of priority inversion ;-)

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

>From what I gather the sssup folks are doing that, although they
reported that DI between disjoint schedule domains (partitions) posed an
interesting problem.

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 :-)

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.

  reply	other threads:[~2008-10-30 17: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     ` Peter Zijlstra [this message]
2008-10-30 17:48       ` Deadline scheduling (was: Re: Rearranging layout of code in the scheduler) 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

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:

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

  git send-email \
    --in-reply-to=1225387034.7803.182.camel@twins \ \ \ \ \ \ \ \ \ \ \
    --subject='Deadline scheduling (was: Re: Rearranging layout of code in the scheduler)' \

* 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).