Using the EDF scheduler

Gedare Bloom gedare at rtems.org
Fri Jan 17 21:00:18 UTC 2020


Hi Jonathan,

On Fri, Jan 17, 2020 at 11:33 AM Jonathan Brandmeyer
<jbrandmeyer at planetiq.com> wrote:
>
> We're using the SMP EDF scheduler in our application, and I want to make sure that I understand its semantics correctly when using it in conjunction with both priority-based and deadline-based tasks.
>
Below you are quoting from the documentation on the uniprocessor EDF
scheduler. The two schedulers are different.
See: https://docs.rtems.org/branches/master/c-user/scheduling_concepts.html#earliest-deadline-first-smp-scheduler

You can still use the RM Manager to set up periodic tasks with the SMP
processor.

> "It assumes that tasks have priorities equal to deadlines" -> It is the responsibility of the application author to give task priorities which are actually equal to deadlines.  Otherwise, the utilization guarantee is not valid.
>
> "This EDF is initially preemptive, however, individual tasks may be declared not-preemptive." -> Tasks are preemptive unless they set the scheduling mode to RTEMS_NO_PREEMT.  Using the rate monotonic manager does not make a task non-preemptive.
>
> "The tasks with an active deadline have a higher priority than the background tasks."  -> Any task which is using the rate monotonic manager will preempt a task which does not when the rate-monotonic task is ready to run.
>
The RM Manager is distinct from the scheduler and does not itself
control preemption.

> "Deadlines are declared using only Rate Monotonic manager which goal is to handle periodic behavior. Period is always equal to deadline." -> It's not actually possible to give a task a deadline independent of its period.  The task's deadline is implied by the previous call to rtems_rate_monotonic_period().
>
I think this is still the case in SMP EDF.

> I'd like to use the rate monotonic manager to schedule some tasks, while using the rtems_event_send and posix condition variables to schedule others.  In my application, it turns out that some of the tasks which are being made ready to run by an ISR via rtems_event_send have stricter requirements than the rate-monotonic tasks.  They also usually execute with a period that is much finer than the kernel time quantum.
>
That is interesting. This might require to augment the scheduler or
roll your own period management logic. It might be nice to allow the
EDF schedulers to support a band of priority that is higher than
deadlines. Off the top of my head though I don't know if there are any
such schedulers with proven schedulability tests in the literature.

> What is the best way to get event-,  condvar-, or queue-managed tasks to cooperate with rate-monotonic tasks?  If I restrict rate-monotonic tasks to just one core with the affinity API, then it sounds like the other core will always be free to schedule event-triggered tasks + the remainder of the rate-monotonic core.  What other tools are available for this purpose?
>
That's probably the easiest way, and least likely to cause trouble
from a schedulability perspective if you have hard real-time
constraints.

>From the theory side, this problem is usually addressed using a
(sporadic) server. Basically, you create some periodic task at the
prioritization that you want (e.g., the shortest relative deadline in
the system to usually get the highest priority) and then the server
uses its budget to execute the event-based tasks. There are several
variations with pros/cons. However, these do not allow for the
event-based tasks to be the most responsive in general; with EDF,
unless you use relative deadline = 1, there can always be some other
task with a shorter absolute deadline. Also, if the server budget gets
consumed you have to wait for replenishment. I'm not up-to-date with
the latest in SMP schedulers with servers. (Shame on me.)

There is not much support available out-of-the-box in RTEMS for
servers, other than some academic implementation of the constant
bandwidth server (CBS) for uniprocessor EDF.

Gedare

> Thanks,
> --
> Jonathan Brandmeyer
> _______________________________________________
> users mailing list
> users at rtems.org
> http://lists.rtems.org/mailman/listinfo/users


More information about the users mailing list