* Re: EDF - "earliest deadline first" scheduler
@ 2017-04-03 12:53 Ran Shalit
2017-04-04 5:38 ` Henrik Austad
0 siblings, 1 reply; 7+ messages in thread
From: Ran Shalit @ 2017-04-03 12:53 UTC (permalink / raw)
To: Alison Chaiken; +Cc: linux-rt-users
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: EDF - "earliest deadline first" scheduler
2017-04-03 12:53 EDF - "earliest deadline first" scheduler Ran Shalit
@ 2017-04-04 5:38 ` Henrik Austad
2017-04-04 7:30 ` Ran Shalit
0 siblings, 1 reply; 7+ messages in thread
From: Henrik Austad @ 2017-04-04 5:38 UTC (permalink / raw)
To: Ran Shalit; +Cc: Alison Chaiken, linux-rt-users
[-- 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 --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: EDF - "earliest deadline first" scheduler
2017-04-04 5:38 ` Henrik Austad
@ 2017-04-04 7:30 ` Ran Shalit
0 siblings, 0 replies; 7+ messages in thread
From: Ran Shalit @ 2017-04-04 7:30 UTC (permalink / raw)
To: Henrik Austad; +Cc: Alison Chaiken, linux-rt-users
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: EDF - "earliest deadline first" scheduler
2017-04-03 5:06 ` Ran Shalit
@ 2017-04-04 5:42 ` Henrik Austad
0 siblings, 0 replies; 7+ messages in thread
From: Henrik Austad @ 2017-04-04 5:42 UTC (permalink / raw)
To: Ran Shalit; +Cc: Alison Chaiken, linux-rt-users
[-- 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 --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: EDF - "earliest deadline first" scheduler
2017-04-03 2:38 Alison Chaiken
@ 2017-04-03 5:06 ` Ran Shalit
2017-04-04 5:42 ` Henrik Austad
0 siblings, 1 reply; 7+ messages in thread
From: Ran Shalit @ 2017-04-03 5:06 UTC (permalink / raw)
To: Alison Chaiken; +Cc: linux-rt-users
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: EDF - "earliest deadline first" scheduler
@ 2017-04-03 2:38 Alison Chaiken
2017-04-03 5:06 ` Ran Shalit
0 siblings, 1 reply; 7+ messages in thread
From: Alison Chaiken @ 2017-04-03 2:38 UTC (permalink / raw)
To: Ran Shalit; +Cc: linux-rt-users
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* EDF - "earliest deadline first" scheduler
@ 2017-04-02 14:27 Ran Shalit
0 siblings, 0 replies; 7+ messages in thread
From: Ran Shalit @ 2017-04-02 14:27 UTC (permalink / raw)
To: linux-rt-users
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
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2017-04-04 7:30 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-03 12:53 EDF - "earliest deadline first" scheduler Ran Shalit
2017-04-04 5:38 ` Henrik Austad
2017-04-04 7:30 ` Ran Shalit
-- strict thread matches above, loose matches on Subject: below --
2017-04-03 2:38 Alison Chaiken
2017-04-03 5:06 ` Ran Shalit
2017-04-04 5:42 ` Henrik Austad
2017-04-02 14:27 Ran Shalit
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.