Using the EDF scheduler

[Joel Sherrill]

On Fri, Jan 17, 2020 at 3:00 PM Gedare Bloom <gedare at rtems.org> wrote:

> 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.)
>

I wondered about a band of high rate periodic tasks that check
for the condition and do it or go to sleep. Binds them to periods
which introduces latency so that's bad.

This would work but likely not be acceptable.

I will pile on that I have no idea if there is an scheduler which
operates this way. If you find one which has good theoretical
credentials, we would love to know about it. Obviously if it exists
and gets implemented, even the better. :)


> 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.
>

The affinity should work if deadline tasks and priority based tasks never
are assigned to the same core.

If you do this, you could experiment with affinity and then consider moving
to a partitioned scheduler setup with some cores running based on
deadline and other cores running threads based on priority.

The SMP EDF scheduler only supports pinning (single core) and not
affinity sets so the clustered scheduling may be the more optimal
alternative.



--joel




>
> Gedare
>
> > Thanks,
> > --
> > Jonathan Brandmeyer
> > _______________________________________________
> > users mailing list
> > users at rtems.org
> > http://lists.rtems.org/mailman/listinfo/users
> _______________________________________________
> users mailing list
> users at rtems.org
> http://lists.rtems.org/mailman/listinfo/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/users/attachments/20200117/44326d2d/attachment-0001.html>