Tasks and scheduling
Tasks, Threads and Processes
We have already considered the multi-tasking concept – multiple quasi-independent programs apparently running at the same time, under the control of an operating system. Before we look at tasks in more detail, we need to straighten out some more terminology.
We use the word “task” – and I will continue to do so – but it does not have a very precise meaning. Two other terms – “thread” and “process” – are more specific and we should investigate what they mean and how they are differentiated.
Most RTOSes used in embedded applications employ a multi-thread model. A number of threads may be running and they all share the same address space:
This means that a context swap is primarily a change from one set of CPU register values to another. This is quite simple and fast. A potential hazard is the ability of each thread to access memory belonging to the others or to the RTOS itself.
The alternative is the multi-process model. If a number of processes are running, each one has its own address space and cannot access the memory associated with other processes or the RTOS:
This makes the context swap more complex and time consuming, as the OS needs to set up the memory management unit (MMU) appropriately. Of course, this architecture is only possible with a processor that supports an MMU. Processes are supported by “high end” RTOSes and most desktop operating systems. To further complicate matters, there may be support for multiple threads within each process. This latter capability is rarely exploited in conventional embedded applications.
A useful compromise may be reached, if an MMU is available, thus:
Many thread-based RTOSes support the use of an MMU to simply protect memory from unauthorized access. So, while a task is in context, only its code/data and necessary parts of the RTOS are “visible”; all the other memory is disabled and an attempted access would cause an exception. This makes the context switch just a little more complex, but renders the application more secure. This may be called “Thread Protected Mode” or “Lightweight Process Model”.
As we know, the illusion that all the tasks are running concurrently is achieved by allowing each to have a share of the processor time. This is the core functionality of a kernel. The way that time is allocated between tasks is termed “scheduling”. The scheduler is the software that determines which task should be run next. The logic of the scheduler and the mechanism that determines when it should be run is the scheduling algorithm. We will look at a number of scheduling algorithms in this section. Task scheduling is actually a vast subject, with many whole books devoted to it. The intention here is to just give sufficient introduction that you can understand what a given RTOS has to offer in this respect.
Run to Completion (RTC) Scheduler
RTC scheduling is very simplistic and uses minimal resources. It is, therefore, an ideal choice, if the application’s needs are fulfilled. Here is the timeline for a system using RTC scheduling:
The scheduler simply calls the top level function of each task in turn. That task has control of the CPU (interrupts aside) until the top level function executes a return statement. If the RTOS supports task suspension, then any tasks that are currently suspended are not run. This is a topic discussed below; see Task Suspend.
The big advantages of an RTC scheduler, aside from its simplicity, are the need for just a single stack and the portability of the code (as no assembly language is generally required). The downside is that a task can “hog” the CPU, so careful program design is required. Although each task is started “from the top” each time it is scheduled – unlike other kinds of schedulers which allow the code to continue from where it left off – greater flexibility may be programmed by use of static “state” variables, which determine the logic of each sequential call.
Round Robin (RR) Scheduler
An RR scheduler is similar to RTC, but more flexible and, hence, more complex. In the same way, each task is run in turn (allowing for task suspension), thus:
However, with the RR scheduler, the task does not need to execute a return in the top level function. It can relinquish the CPU at any time by making a call to the RTOS. This call results in the kernel saving the context (all the registers – including stack pointer and program counter) and loading the context of the next task to be run. With some RTOSes, the processor may be relinquished – and the task suspended – pending the availability of a kernel resource. This is more sophisticated, but the principle is the same.
The greater flexibility of the RR scheduler comes from the ability for the tasks to continue from where they left off without any accommodation in the application code. The price for this flexibility is more complex, less portable code and the need for a separate stack for each task.