[lkml]   [2009]   [Sep]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [RFC][PATCH] SCHED_EDF scheduling class
Hi Linus,

Linus Walleij ha scritto:
> Hi Raistlin,
> it's great fun to see this scheduler materialize, I was present at the
> workshop in Kaiserslautern and waited for the code since. What I'm
> interested in getting a briefing on right now is what practical use EDF
> schedulers have, since I think this is what many people will ask for.
> I think actually the answers are the same as when I asked at Meld
> (of all places) what HRtimers are actually for. And I I got the non-all
> inclusive answer that they're for Flight simulators.
> Which is obviously in the domain of automatic control.
> So one application of HRTimers has been to trigger events in
> userspace programs, especially when your dealing with issues
> related to automatic control. Automatic control is also
> mentioned throughout this patch. (Yes, I know HRtimers
> have other great uses also, especially in-kernel, those will
> remain.)
> I am very interested in if you or someone else
> could elaborate on the relation between HRtimers and deadline
> scheduling. To my untrained mind it looks like HRtimers will
> fire events to your task in a very precise manner, but
> you cannot currently guarantee that they will then proceed to
> process their target task in time (meet a deadline).

Yes. With HRT you have timing measures with a higher resolution than
using normal timers. This means that everything in the system runs more
precisely, and latencies are reduced.

However, "how" it runs, depends on the scheduling algorithm, which is
the part of the kernel that at any instant chooses which task must be
executed. Our scheduling class introduces the chance of ordering tasks
execution in a further manner, that is according to the Earliest
Deadline First (EDF) algorithm. Therefore, after the patch is applied, a
new scheduling policy is available for scheduling tasks. Consider that
old policies (sched_fair and sched_rt) still remain, and you are not
forced to use EDF ordering. This way, if you don't use EDF tasks, the
system still behaves as without our patch.

> I'm under the impression that some people currently use
> some periodic HRtimers (through either the timerfd_create system
> call I guess, or POSIX timer_create(CLOCK_REALTIME_HR...)
> timers combined with some SHED_FIFO or so to achieve the same
> thing a deadline scheduler would do, but since SCHED_FIFO cannot
> really guarantee that this will work, you simply underutilize
> the system a bit, add the CONFIG_PREEMPT_RT patch so the
> timers are not blocked by things like slow interrupthandlers or
> starvation (priority inversion) and then hope for the best. It turns
> out to work. You measure on the system and it has the desired
> "hard realtime" characteristics.

Let's take a step back. The problem in real-time scheduling is to find
an order of scheduling tasks so that each of them meets its deadlines.
This way, you get determinism and predictability (i.e., you can trust
that your tasks will be executed at the "right" instant of time).
Several scheduling algorithms exist to generate different orders of
execution that ensure this property.

In particular, several differences exist between fixed priority and
dynamic priority algorithms (like SCHED_EDF). In my opinion, the most
relevant is the following one.

Suppose you have a single processor and a set composed by periodic
real-time tasks, each one characterized by an amount of execution time
("budget") that must be executed every "period". This way, the deadline
for each task is equal to the end of its current period.

The sum of (budget/period) of all tasks is usually called "bandwidth".

Using fixed priority schedulers, you need a quite complicated equation
to understand if it is possible to guarantee the deadlines of every
task. This equation must be re-computed each time you change a budget or
period of some task.
Even worse, depending on the task set, it may happen that the bandwidth
must be lower than 100% (sometimes as low as 69%), otherwise you cannot
be sure that all tasks will meet their deadline (they might, but you
cannot trust).

With EDF, instead, the test is much easier: if the bandwidth is less
than 100%, then you are sure that the deadlines will be met. In other
words, you can fully exploit processor bandwidth up to 100% being sure
that timing constraints of EDF tasks will be guaranteed.

> Do people do such things? I haven't seen those applications,
> they all tend to be closed-source really. I would assume the
> vxWorks/pSOS/etc compatibility wrapper libraries do things
> like this, do they not?

Well, ACTORS is an example of an industrial application which needs an
EDF scheduler on Linux, isn't it ?

But I've also seen a couple of multimedia applications which needed an
EDF scheduler to meet deadlines of periodic tasks and, at the same time,
exploit CPU utilization up to 100%.



 \ /
  Last update: 2009-09-23 15:25    [W:0.245 / U:2.256 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site