RTOS Scheduling Algorithms

guitardenver wrote on Monday, February 19, 2018:

I am trying to choose the best scheduling algorithm for my application. My application will have periodic tasks, non-periodic tasks and interrupts.

The schedualing algorithm that shows up most on google is RMA (Rate Monotonic Analysis). But this is for periodics tasks and does not seem to account for the possibility of mutual exclusion with a lower priority task. Not to mention the priority of a task is only assigned based on its period. What if I have a task with a period of 1000 Seconds and needs to execute for 3mS? With RMA, it can take all 1000 Seconds to complete that 3mS of work. I need to be able to set a deadline of say 5mS.

I did also see “Deadline Monotonic Analysis” which allows me to put a deadline on a task. But this also does not account for mutual exclusion.

How does one assign task priorities with periodic, non-periodic and interrupts with shared resources using Mutexes? I have read a lot that it’s best practice to make all tasks independent and not share any resources at all. But then why does the mutex exist if it just causes problems?

Is there a way to account for all this with an algorithm? Say I have all taks and their info in a spreadsheet, can I use an algorithm that can say with high centainty that it is schedualable and all critical tasks will meet their deadline?

rtel wrote on Monday, February 19, 2018:

First you have to decide what the requirements of your system are, and how much spare cpu cycles you have. Most applications only have a few, if any, really hard real time requirements and planets of spare cpu cycles, so ensuring the real time responses is not too difficult. Only if you have multiple hard real time requirements and little spare cpu time, or a safety critical system that must be mathematically probable, is such scrutiny required. Do you fall into one of those categories?

richard_damon wrote on Monday, February 19, 2018:

First, note that Tasks and Interrupts are different class of things, and their priorities doen’t directly interract, until you break up the interrupt processing into two piece, by moving part of it into a task-like operation (maybe not quite just a task, as you get features like the FreeRTOS timer/pend function task that can do some things at a lighter weight than using a full task for each thing.

Deadline based priorities I find tend to be a good starting point. Mutex Priority Inheretance helps a lot with your sharing with a lower priority task. You want to get done the short deadline, quick operatations in preference to the operations which have a longer deadline.

PROOF of schedualability is hard in general, but often can be done using known specifics of a given system (and often you need to build the system and measure things to be able to say much in particular, or you are just guessing on how much work an operation really is). When you have shared resources, things get a lot more complicated, as you not only need to know the total work being done, but how much work might need to be done by other operations while they hold a shared resource.

Shared resources are often inevitable, being inherent in the definition of the work needing to be done, accessing a shared device or devices on a shared bus, or needing access to data that needs to be shared amoung the tasks.

guitardenver wrote on Monday, February 19, 2018:

I do not have a safty critical application. We have to read many sensors very fast and make decisions dynamically based on the sensor data. We are talking about processing samples every 25uS or so. I will have it so it’s collecting data for 200uS and then will go into a blocking state for 100uS and that cycle repeats. During those 100uS breaks I need to service communications like USB and other non-standard communication protocols with dealines. Of course that is just one small part of a real world application. But those are the most hard real time requirments.

Many, if not all, shared reasources will be obtained before I start collecting data to ensure no lower priority tasks will cause deadlines to not be hit.

I want to assign priorities with an algorithm and not just assign them to what I think they should be. Is RMA usefull in real world applications? It does not seem to me that application tasks are entirly just periodic with do deadlines during those periods.

All resources I find online are just about RMA. Do you know of some examples or resources on assigning priorities to tasks for a more complicated system with deadlines? What do you use? Are there tools to automate this process and/or simulate worse case conditions? Just stress test the timing even before any code is written. Is this a common thing to do?

I guess i’m looking for resources on how others do RTOS system architecture and a good workflow. Even if my specific application does not merit such detailed analysis, it doesn’t hurt to do it and may prevent issues that can show up in the field later on.

waveringradiant wrote on Monday, February 19, 2018:

If you are going to use RMA (and yes, it is absolutely used in commercial systems with hard real-time deadlines, such as medical devices, automobile ECUs and avionics, just to name a few), it is a very rigorous process.

Unfortunately, I don’t have time to answer all the questions (especially because answers typically beget more questions, the life of a consultant…) but:

  • with RMA, when the deadline is shorter than the period, model the task as though its deadline is its period (*a la *deadline monotonic). So a task that runs once every 24 hrs and must complete its work within 1ms is modeled as though it runs every ms (here we are talking about task priority and period, not CPU utilization, which gets into schedulable bound)

  • for aperiodics, you should know the minimum inter-arrival time (if not, you don’t really have a handle on your system). You can refine what I’m about to say, but the easiest “next step” is to model aperiodics as though they arrive (are scheduled) at the minimum inter-arrival time.

  • Note that ALL of this ONLY applies to tasks with hard real time deadlines. Tasks without hard real time deadlines can be prioritized as you wish, but all of them must be lower than the lowest priority task with a hard deadline

  • RMA has been expanded to include things that the original RMA paper (mid-70s, I think) didn’t address, such as interrupts, shared resoures, and context switch overhead.

I’m about to catch a flight, but if you search “RMA” in conjunction with either “Barr Group” or “Phil Koopman” you’ll find a wealth of information, and probably most of the answers you are looking for.

Disclaimer: I am one of the instructors for Barr Group’s 4/5 day “Embedded Software Boot Camp”, which used to include a half-day or so on hard real time, RMA, task prioritization, schedulable bound, aperiodics, ISRs, shared resources, etc. In its current form (2017 through present) that material isn’t included, but I’m not at liberty to discuss the “why” (nothing bad, quite the contrary actually…) One example of an RMA-related article by Michael Barr can be found at: https://embeddedgurus.com/blog/2010/08/3-things-every-programmer-should-know-about-rma/