From Baremetal to RTOS: A review of scheduling techniques
Transitioning from bare-metal embedded software development to a real-time operating system (RTOS) can be a difficult endeavor. Many developers struggle with the question of whether they should use an RTOS or simply use a bare-metal scheduler. One of the goals of this series is to walk developers through the transition and decision making process of abandoning bare-metal thinking and getting up to speed quickly with RTOSes. Before diving into the details of RTOSes, the appropriate first step is review some of the most popular scheduler techniques available to embedded software developers.
From bare-metal to RTOS Quick Links
Technique #1 – Round Robin
The easiest scheduler to implement in software is the Round Robin scheduling technique. Round Robin is so easy to implement because it is a natural way of writing software. Developers simply add new code to the super loop and a task is now added. There is no need to create dynamic and memory expensive objects. Just add code!
One of the biggest problems with a Round Robin approach to scheduling is that the real-time performance of the system is affected every time new code is added. The super loop might be executing once per 100 microseconds but suddenly add new code and now it’s 110 microseconds. That code pieced developed to execute perfectly every is now toast and has to be reworked. The fact of the matter is that using just a Round Robin approach results in constant rework to ensure system timing and can be very difficult to get predictable results for hard real-time requirements.
A simple example of how a Round Robin scheduler works can be seen in Figure 1.
Figure 1 - Round Robin Scheduling
Technique #2 – Round Robin with Interrupts
Bare-metal developers never allowed the issues with Round Robin to get them down. There are dozens of incremental techniques that can be used as a scheduler before having to roll out the big gun (RTOS). The next algorithm that developers have found quite useful over the years is Round Robin scheduling with interrupts. In these applications, any code that has hard real-time requirements or are timing sensitive are moved into an interrupt service routine. An example might be incoming UART data that if left too long could be overwritten by the next incoming data byte. The timing critical section, retrieve the data, is then handled as soon as the interrupt fires by moving the data byte into a circular buffer. Processing the data byte is usually a soft real-time requirement and can be handled by the super loop when it gets around to it.
The interrupt behavior can even be used to create pre-emptive behavior that for simple applications can mimic an RTOS. Careful selection of interrupt priorities and architecting the round robin loop can go a long way towards real-time and reliable behavior before needing to move on to other more advanced scheduling techniques. Figure 2 shows an example of what Round Round with interrupts would look like from a model point of view. On the left is the traditional Round Robin super loop. At any point, an interrupt could fire causes code execution to move from the left to the right and enter the interrupt service routine (ISR). The interrupt would then execute to completion, unless a priority interrupt fires, and then return where it left off on the left side of the diagram.
Figure 2 - Round Robin with Interrupts
Technique #3 – Queued
Queued scheduling is an interesting technique that is an intermediate step between Round Robin with Interrupts and Cooperative scheduling. In most cases it makes sense to just use a Cooperative Scheduler, but it is worth taking a few moments to discuss Queued scheduling. Before discussing the details, examine Figure 3 for a moment.
Figure 3 – Queue Scheduling Behavior
In Queued scheduling, an array of function pointers (queue) is created that initially contains only NULL pointers (Figure 3a). When a task needs to be executed, perhaps triggered by an interrupt for example, a pointer is inserted into the first NULL location. It is possible for multiple tasks to become ready for execution at the same time. When this occurs, the scheduler simply executes one task at a time (Figure 3b) in a Round Robin fashion until the queue is once again empty (Figure 3c and Figure 3D). Once a task has been executed, its function pointer location in the queue is returned to a NULL pointer.
Technique #4 – Cooperative
Cooperative schedulers are probably one of the most widely used bare-metal scheduling algorithms available to developers. A Cooperative scheduler resides in a very small memory footprint and can be easily configured to handle any number of tasks. A Cooperative scheduler consists of a simple structure that contains that contains a function pointer to the task to be executed, the period at which the task needs to be executed and last time the task was executed. Developers will often create an array of tasks that contain all of this critical task information.
The algorithm itself is pretty simple and straight forward. The system is first initialized and then a background timer is used to keep track of time. The scheduler reads the system tick and then loops through each of the tasks defined for the system and calculates whether it is time to execute the task or not. If so, the task is executed, otherwise the next task is checked. When more than one task needs to run, they are executed in a Round Robin fashion. Developers still need to take care to monitor their system execution times to make sure during the worst case, when all tasks have to execute, that all of the deadlines are still met.
Developers interested in learning more about Cooperative schedulers can download an example here. The scheduler can be ran with any microcontroller and only requires that a single timer be setup to get the scheduler working.
Figure 4 – Cooperative Scheduler (High Level)
Technique #5 – Real-time Operating System
The last technique that we are going to touch on is the RTOS. The RTOS is the most powerful scheduler a real-time developer can use and also the most complicated. The RTOS can usually be configured to use a number of deterministic scheduling algorithms that guarantee task deadlines are met. Each task has its own separate task control block that contains its own stack, function and ID among other parameters. Each task can literally be viewed as its own separate application. The RTOS also comes with a wide variety of synchronization and communication tools such as semaphores, mutexes and message queues.
RTOSes are a powerful tool for embedded software developers but can sometimes be overkill. For simple 8-bit or 16-bit applications a Cooperative scheduler may work perfectly fine and use far less memory. When developers are faced with using a complex 32-bit microcontrollers with more than 32 kB of flash and 4 kB of RAM, the use of a RTOS begins to make a lot of sense. Many 32-bit applications require the use of USB, TCP/IP and file systems which can be very difficult to develop for bare-metal applications. Most third party middleware is designed to integrate seamless with an RTOS.
To use an RTOS or not use an RTOS, that is the real question. Each scheduling algorithm has its own advantages and disadvantages. We have examined the most commonly used scheduling algorithms which forms a basis for making such a determination. The next step is to learn when and why to use an RTOS. Stay tuned!
|Jacob Beningo is an embedded software consultant who currently works with clients in more than a dozen countries to dramatically transform their businesses by improving product quality, cost and time to market. He has published more than 200 articles on embedded software development techniques, is a sought-after speaker and technical trainer and holds three degrees which include a Masters of Engineering from the University of Michigan. Feel free to contact him here, at his website www.beningo.com, and sign-up for his monthly Embedded Bytes Newsletter here.|
First, Jacob leaves out prioritized cooperative scheduling. In this scheme the tasks are prioritized and event-driven, and once whatever task that is running is finished, the highest-priority task that's ready to run gets the processor. It's probably the only "bare metal" method that I've used in the last 20 years.
Second, using an RTOS isn't really a 32-bit thing -- it's more a memory size thing. There are ARM Cortex M0 processors out there that address the space used by 8-bitters quite nicely, but they don't really have the memory space to support an RTOS -- nor are the applications for which they're appropriate really complex enough to demand an RTOS.
Third, even on a 32-bit processor, an RTOS can cause a time hit. Task switches just take many more clock ticks than interrupts. If you have an application that's small but needs to squeeze everything out of the processor that it can, then you should tread carefully. In such circumstances you either need to abandon the RTOS, or you need to have heavier-weight ISRs than you might otherwise feel is wise.
For all that -- good post!
I agree that the use of an RTOS is not just a 32-bit thing. I occasionally over generalize. I've used them in 16 bit applications often but for simple applications keep it bare-metal. In my next post I'm going to discuss in more detail when an RTOS should and shouldn't be used. Some of the points that you've mentioned will definitely be discussed.
Are there dedicated strategies for watchdog handling depending of the scheduler/RTOS used ?
now i learned how the concepts iam using are called ;)
on uC baremetal things iam doing some mixture of round robin and cooperative scheduler:
my main loop basically is a round robin approach - and some sub-modules called from there have there own cooperative scheduler type logic - so it is very modular - but therefore not optimized ;)
but in most cases for me its not soo relevant to be exactly spot on timing..
Very Nice overview on the schedulers. Could not download the samples. Probably server may be busy.
By the way, Round Robin with Interrupts seems to be the most used technique. Migrating from it to subsequently described methods appears to be very difficult for a common embedded designer. Synergy platform, from what we get to know from the website, can remove hesitations and straight away help in graduating further.
Microcontroller vendors are definitely in the process of trying to simply the development process for developers using their parts and toolchains.
Best learning experience ever. I have to admit, I have used VxWorks, MTOS-68k, Linux Embedded (hardly RTOS) and VRTX along with a home brew by Bell Northern Research (RIP). For what we did with these RTOSes, all but a few projects could have been written with a bare metal executive.
I miss working with this stuff . Thank you for a look at what I consider the most excellent field in software.
I used to work in an environment where we has four queues, each at a different priority. Each queue was basically a FIFO (round robin within the queue). Any process can fire off a new message at any required priority. The higher priority queue interrupted the lower. It was very scale-able and worked from the highest level executive processor right down to the smallest device processor.
Thanks again for the blog!
I use a variation on your Cooperative Scheduler that includes task priority. My changes include:
- get and check the system time before each task
- restart scanning the task list after a task is run, this creates a task priority because the first task is checked for execution
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.