Task scheduling with a real time operating system
From time to time, I like to poke around at some RTOS feature or functionality. Today I want to ponder the real core of any operating system: the scheduler. Every embedded system is different and it is, therefore, unsurprising that there are a number of different types of scheduler that might be employed. Different RTOS products offer different options, but I want to try to cover the spectrum of possibilities …
As any software engineer knows, a conventional CPU can only execute one program at a time. The apparent simultaneous execution of multiple threads is achieved by control of the CPU being rapidly swapped between a number of code threads. This swapping process is managed by the scheduler.
A scheduler need not be particularly complex. I have written a few in the course of my career and have never quite forgotten the first time I could clearly observe some code of mine unambiguously multitasking; it seemed somewhat magical, even though I knew exactly what was going on [as I had written every instruction of code involved].
Although it is a slight simplification, I can identify five broad types of scheduler:
Run to completion [RTC]
An RTC scheduler is very simple. Indeed, I have previously [and only slight inaccurately] referred to one as a “one line RTOS”. The idea is that one task runs until it has completed its work, then terminates. Then the next task runs similarly. And so forth until all the tasks have run, when the sequence starts again.
The simplicity of this scheme is offset by the drawback that each task’s allocation of time is totally affected by all the others. The system will not be very deterministic. But, for some applications, this is quite satisfactory. An added level of sophistication might be support for task suspend, which means that one or more tasks may be excluded from the execution sequence until they are required again.
Round robin [RR]
An RR scheduler is the next level of complexity. Tasks are run in sequence in just the same way [with task suspend being a possibility], except that a task does not need to complete its work, it just relinquishes the CPU when convenient to do so. When it is scheduled again, it continues from where it left off.
The greater flexibility of an RR scheduler comes at the cost of complexity. When a task relinquishes the CPU, its context [basically machine register values] needs to be saved so that it can be restored next time the task is scheduled. This process is required for all the other scheduler varieties that I will discuss.
As with RTC, an RR scheduler still relies of each task behaving well and not hanging on to the processor for too long. Both RTC and RR are “cooperative multitasking”.
Time slice [TS]
A TS scheduler is a straightforward example of “preemptive multitasking”. The idea is to divide time into “slots”, each of which might be, say, 1mS. Each task gets to run in a slot. At the end of its allocated time, it is interrupted and the next task run.
The scheduling is not now dependent on tasks being “good citizens”, as time utilization is managed fairly. A system built with a TS scheduler may be fully deterministic [i.e. predictable] – it is truly real time.
Time slice with background task [TSBG]
Although a TS scheduler is neat and tidy, there is a problem. If a task finds that it has no work to do, its only option is to loop – burning CPU time – until it can do something useful. This means that it might waste a significant proportion of its slot and an indefinite number of further slots. Clearly, the task might suspend itself [to be woken again when it is needed], but this messes up the timing of the other tasks.
This is unfortunate, as the determinism of the system is compromised. A solution is to enhance the scheduler so that, if a task suspends itself, the remainder of its slot is taken up by a “background task”; this task would also use the full slots of any suspended tasks. This restores the timing integrity.
What the background task actually does depends on the application, but broadly it must be non-time-citical code – like self-testing. There is, of course, the possibility that the background task will never get scheduled. Also, this special task cannot be suspended.
Priority [PRI]
A common, more sophisticated scheduling scheme is PRI, which is used in many [most] commercial RTOS products. The idea is that each task has a priority and is either “ready” [to run] or “suspended”. The scheduler runs the task with the highest priority that is “ready”. When that task suspends, it runs the one with the next highest priority. If an event occurs, which may have readied a higher priority task, the scheduler is run.
Although more complex, a PRI scheduler give most flexibility for many applications.
Commercial RTOS products, like our own Nucleus RTOS, tend to use a priority scheduling scheme, but allow multiple tasks at each priority level. A time slice mechanism is then employed to allocate CPU time between multiple “ready” tasks of the same priority.
