Re: EDF - "earliest deadline first" scheduler

[Henrik Austad <henrik@austad.us>]

[-- Attachment #1: Type: text/plain, Size: 2721 bytes --]

On Mon, Apr 03, 2017 at 03:53:27PM +0300, Ran Shalit wrote:
> On Mon, Apr 3, 2017 at 8:06 AM, Ran Shalit <ranshalit@gmail.com> wrote:
> > On Mon, Apr 3, 2017 at 5:38 AM, Alison Chaiken <alison@peloton-tech.com> wrote:
> >>  Ran Shalit <ranshalit@gmail.com> wrote:
> >>> I have found in
> >>> https://wiki.linuxfoundation.org/realtime/documentation/howto/applications/cyclic
> >>> that there is EDF scheduler option for creating a periodic RT thread.
> >>> Yet, I could not understand what's behind the EDF scheduler
> >>
> >>
> >> Have a look at "Using SCHED_DEADLINE" at
> >>
> >> http://elinux.org/ELC_Europe_2016_Presentations
> >>
> >> Also, look for papers on this topic by Juri Lelli.
> >>
> >> HTH,
> >> Alison
> >
> > Hi Alison,
> >
> > Thank you very much.
> > I reviewed the material, which is very interesting, but I am not yet
> > sure which timer are used internally in SCHED_DEADLINE.
> > Is it posix or non-posix ?
> >
> > Thanks,
> > Ran
> 
> I am trying to understand which scheduler is better used with RT.
> In the wiki there is an example for SCHED_FIFO, periodic time.
> But in sched_deadline wiki ( https://wiki.automotivelinux.org/sched_deadline )
> it is said as following:
> "
>  Using SCHED_FIFO/SCHED_RR, instead, we can give that kind of
> guarantee only using a global period, with the constraint that “a
> subgroup must have a smaller or equal period to its parent”.
> The latency experienced by a task (i.e., the time between two
> consecutive executions of a task) is not deterministic and cannot be
> bound, since it highly depends on the number of tasks running in the
> system at that time. Using EDF, instead, this time is deterministic,
> bounded and known at any instant of time."
> 
> I am not sure now. Does it mean that using more than one SCHED_FIFO
> periodic thread is not deterministic compared with SCHED_DEADLINE?

It means that when you use priorities, you basically do a one-way mapping 
between the inherit deadlines in your tasks to a set of static priorities. 
As a developer you know *when* the tasks needs to complete, right? So then 
the job is to pick a priority and hope that no other higher-prioritized 
thread preempts you and cause you to miss your deadline.

And that is the problem with a complicated system, many tasks lead to an 
intractable problem of getting all the priorities right, causing you no end 
to the headache.

With SCHED_DEADLINE, you express your requirements directly as deadlines, 
thus avoid that whole one-way mapping and instead the tasks relative 
priority will adjust as the scheduler now has a _much_ more comprehensive 
view of the requirements.

-- 
Henrik Austad

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]