EDF - "earliest deadline first" scheduler

EDF - "earliest deadline first" scheduler

[Ran Shalit]

Hello,

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. Is it
using posix or non-posix timer ?

I have also found the following information:
http://lxr.free-electrons.com/source/Documentation/scheduler/sched-deadline.txt
Yet it does not provide more details about the timer used with EDF.

Thank you,
Ran

Re: EDF - "earliest deadline first" scheduler

[Alison Chaiken]

 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

Re: EDF - "earliest deadline first" scheduler

[Ran Shalit]

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

Re: EDF - "earliest deadline first" scheduler

[Henrik Austad]

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

On Mon, Apr 03, 2017 at 08:06:23AM +0300, Ran Shalit 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 ?

A "posix-timer" is a userspace-construct. A posix-timer will use the 
hrtimer in the kernel - which ends up in the same subsystem used by the 
deadline scheduler.

-- 
Henrik Austad

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

Re: EDF - "earliest deadline first" scheduler

[Ran Shalit]

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?

Regards,
Ran

Re: EDF - "earliest deadline first" scheduler

[Henrik Austad]

[-- 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 --]

Re: EDF - "earliest deadline first" scheduler

[Ran Shalit]

On Tue, Apr 4, 2017 at 8:38 AM, Henrik Austad <henrik@austad.us> wrote:
> 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


Thanks for these comments, Henrik.
I have reviewed  examples of how to use SCHED_DEADLINE, yet I am not sure:
Does it use POSIX or non-POSIX timers ?
I ask because we've seen some issue with POSIX timers in some kernel
version, architectures.

Ran