embedded software boot camp

Slack Scheduling vs. Rate Monotonic Analysis

Friday, October 2nd, 2009 by Michael Barr

The “slack scheduling” technique described in a recent Embedded.com article by Bill Cronk is interesting to me for a few reasons. First, because a traditional priority-based preemptive RTOS used in conjunction with RMA priority assignment offers all of the pros and none of the cons of the described slack scheduling method. And second because slack scheduling may still be valuable when working within a corporate or industry regime, such ARINC-653, that legislates a cyclic executive approach to achieving determinism.

I don’t think the original article addresses either of these points, so I will address them here.

I have written and spoken about RMA extensively in the past. For readers wanting background, start with Introduction to Rate Monotonic Schedule. Then read Why RMA is Not Just for Academics, from which this important and relevant quote:

The principal benefit of RMA is that the performance of a set of tasks thus prioritized degrades gracefully. Your key “critical set” of tasks can be guaranteed (even proven a priori) to always meet its deadlines–even during periods of transient overload. Dynamic-priority operating systems cannot make this guarantee. Nor can static-priority RTOSes running tasks prioritized in other ways.

In plain English, RMA helps you prove (via math) that your interrupt service routines (ISRs) plus the subset of tasks with deadlines will always complete their work on time. Then you can do whatever the heck you want at lower priority levels without messing that up. Consider that with this architecture a ventilator could feature a low priority video game. If the CPU becomes overloaded, only the game’s performance is at risk. The rest (most) of the time the game gets to use all the “slack” CPU cycles left behind by the critical set.

The pros of slack scheduling appear to be:

  • Non-critical tasks (i.e., those without deadline miss consequences) can’t steal CPU cycles needed by critical tasks.
  • Allows slack CPU cycles to be used by the non-critical tasks.
  • No need to ever “terminate any lower criticality [code] that exceeds” its time slot.
  • Client tasks never need to “wait for their server thread to be scheduled”.

All of these pros are common to the RMA+RTOS approach as well.

The cons of slack scheduling appear to be:

  • There is overhead associated with tracking, granting, and requesting slack time (the article doesn’t provide enough info to quantify these).
  • There is overhead associated with waking tasks (or polling instead of interrupts) to see if they need even use any of their allocated time in this cycle.
  • Like all time-partitioned code structures, it is fragile in the face of late-added work items (“the introduction of a new thread may be difficult if there is no room available on the timeline”.

The RMA+RTOS approach suffers none of these downsides.

It is important to understand that the two really powerful and beautiful aspects of RMA are first that tasks outside the critical set need not be budgeted/analyzed at all (they don’t have deadlines anyway) and second that these low priority non-critical tasks have automatic free (no-overhead) use of all the CPU cycles not used by those with deadlines. All of the critical set schedulability analysis is done on worst-case CPU use. Best case and average case may be substantially less. For example, an interrupt that could first worst-case every 1 ms eats up a lot of CPU time on paper only (well, at least until that worst case when it does really consume that much CPU); the actual implementation need not be changed to poll; and every last unused CPU cycle is available for other uses in the real system.

Unfortunately, few embedded software engineers apply RMA at all. And some of those who do, may get the math wrong. There are assumptions and calculations to be handled properly. And that’s where a time-partitioned code structure (a.k.a., cyclic executive or real-time executive) is demonstrably better than RMA+RTOS. And that is probably why ARINC-653 mandates time-partitioned scheduling.

Under a mandate of time-partitioned, the described slack scheduling approach may aid implementers.

Tags: , ,

One Response to “Slack Scheduling vs. Rate Monotonic Analysis”

  1. Michael Barr says:

    A minor point in this article prompted one cool thought that I had never had. When using RMA to assign task priorities with an RTOS, such as Micrium's uC/OS-II, that treats tasks with lower integer priority numbers as more important, it may sometimes be possible to actually use the worst-case (most frequent) inter-arrival time as the priority number.For example, if you had tasks with recurring 1ms, 3ms, 17ms, and 1s worst-case periods you could assign their priorities like this:enum { taskA_prio = 1, taskX_prio = 3, taskB_prio = 17, taskW_prio = 1000 } task_prios;The most frequent task always gets higher relative priority under RMA.Of course, this also requires your problem domain to feature timing resolution (e.g., milliseconds) and range (e.g., 0-1000) that is both human readable and fits within the integer width of your RTOSes priority parameter. uC/OS-II couldn't handle this example, because it uses an 8-bit priority. uC/OS-III, though, could handle that scenerio.

Leave a Reply