We considered multitasking, the property of the operating system to run several quasi-independent programs at the same time. Before we consider the problems in more detail, it is necessary to understand the terms.
Previous articles in the series:
Article # 2. RTOS: Structure and Real Time
Article # 1. RTOS: introduction.
We use the word "task", despite the fact that it does not have an exact meaning. Other terms, “flow” and “process,” are more specialized, and you should understand what they mean and how they differ.
Many RTOS used in embedded applications use a multi-threaded model. At the same time, several threads can be executed occupying the same address space:
This means that context switching is, first of all, switching from one set of processor registers to another. It is simple and fast. The potential danger is that each thread has the ability to access memory that belongs to other threads or the RTOS itself.
An alternative is a multi-process model. If several processes are running, then each process has its own address space and you cannot access memory associated with other processes or RTOS:
This makes context switching more complex and time consuming, since the operating system must properly configure the memory management unit, the memory manager (MMU). Of course, such an architecture is possible only if there is a processor that supports the MMU. Processes are supported by "high-performance" RTOS and most desktop operating systems. Moreover, each process can support splitting into multiple threads, but this property is rarely used in ordinary embedded applications.
If an MMU is available, you can reach a compromise:
Many "streaming" RTOSs support MMUs to protect memory from unauthorized access. Thus, while the task is in context, only part of its code / data and necessary parts of the RTOS are “visible”; the remaining blocks of memory are disabled, and an access attempt will cause an abnormal situation (for ordinary people) / exception (for programmers). This makes context switching a bit more difficult, but the application itself is more secure. This mode can be called “Protected Threads Mode” (Thread Protected Mode) or “Lightweight Process Mode”.
Planners
As we know, the illusion of simultaneous execution of tasks is achieved by allocating processor time to perform each of the tasks. This is the core function of the kernel. The way time is distributed between tasks is called “planning.” Scheduler — software that determines which next task to transfer control to. Scheduler logic and the mechanism that determines when and what should be performed is a scheduling algorithm. In this section, we will look at several scheduling algorithms. Task planning is a vast topic and many books are devoted to it. We will provide the necessary minimum to understand what a particular RTOS can offer in this regard.
Run to Completion Scheduler (RTC)
The RTC scheduler (run-to-completion - “completion to completion”) is very simple and uses minimal resources. This is an ideal service if it meets the requirements of the application. Below is a schedule for a system using the RTC scheduler:
The scheduler in turn calls the top level functions of each task. The task controls the processor (interrupts it) until the top-level function executes the return statement. If the RTOS supports suspending tasks, then any tasks currently suspended are not executed. This topic is covered in the article below; see “Task Suspension”.
The big advantage of the RTC scheduler, in addition to simplicity, is a single stack and portability of the code (no assembler is required). The disadvantage is that the task can “occupy” the processor, so careful development of the program is required. Despite the fact that each time the task is performed from the beginning (unlike other schedulers that allow you to start working from the stop), you can achieve greater flexibility with the help of static “state” variables that define the logic of each subsequent call.
Round Robin (RR) Scheduler
The RR (carousel) scheduler is similar to the RTC, but more flexible and therefore more complex:
However, in the case of the RR scheduler, the task does not need to execute the return statement in the top-level function. It can free the processor at any time by making a call to the RTOS. This call causes the kernel to save the context of the current task (all registers, including the stack pointer and the instruction pointer) and loads the context of the next task in the queue. In some RTOS, the processor can be released (suspend a task) while waiting for the availability of a kernel resource. It is more complicated, but the principle is the same.
The flexibility of the RR scheduler is determined by the ability to continue execution of tasks from the moment of suspension, without making changes to the application code. For flexibility, you have to pay less portability of the code and a separate stack for each task.
Time slice (TS) scheduler
TS Scheduler (time slice - “time quantum”) is a level more complicated than RR. The time is divided into slots (intervals, time slices), where each task can be performed within the interval assigned to it:
In addition to the ability to voluntarily release the processor, the task can be interrupted by a call to the scheduler, executed by the system timer interrupt handler. The idea of assigning a fixed time interval to each task is very attractive (where it is possible): it is easy to understand, and it is very predictable.
The disadvantage of the TS scheduler is that the share of processor time allocated for each task may differ, depending on whether other tasks are suspended and other parts of the slots are free:
The TS scheduler may become more predictable if tasks are implemented in the background. The background task can be executed instead of any suspended task and occupy a time interval when the task is released (or suspends itself).
Obviously, the background task should not perform time-critical work, since the proportion of processor time allocated to it is completely unpredictable: it can never be planned.
Such a decision assumes that each task can predict when it will be scheduled again. For example, if you have slots for 10 ms and 10 tasks, the task knows that if it is released, it will continue execution after 100 ms. With this solution, you can achieve a more flexible setting of time cycles (timings) for application tasks.
The RTOS may provide different time intervals for each task. This provides more flexibility, but is also predictable, as with a fixed interval size. Another option is to allocate more than one interval for the same task if you need to increase the proportion of allocated processor time.
Priority Scheduler
Most RTOSs support prioritized planning. The idea is simple: each task is assigned a priority, and at any time the task that has the highest priority and is “ready” for execution is transferred to the processor:
The scheduler starts when an event occurs (for example, an interrupt or a call to a specific kernel service) that causes a task with a high priority to become “finished”. There are three circumstances under which the scheduler starts working:
• The task is suspended; the scheduler must assign the next task.
• A task prepares a higher priority task (using an API call).
• Interrupt service (Interrupt Service Routine, ISR) prepares a higher priority task. This can be an interrupt handler for an I / O device or the result of a system timer trigger.
The number of priority levels varies (from 8 to several hundred), the threshold values also vary: some RTOS perceive the highest priority as 0, and in others 0 means the lowest priority.
Some RTOS allow only one task at each priority level; others allow somewhat, which greatly complicates the associated data structures. Many operating systems allow you to change the priorities of tasks at run time, which further complicates the processes.
Composite Scheduler
We looked at several planners, but many commercial RTOS offer even more sophisticated solutions that have the characteristics of several algorithms at once. For example, an RTOS can support multiple tasks at each priority level, and then use TS to divide time between several ready-made tasks at the highest level.
Task states
Only one task is performed at any time. In addition to the CPU time spent on the interrupt handler (more on this in the next article) or the scheduler, the “current” task is the one whose code is currently running and whose data is characterized by the current register values. There may be other tasks that are “ready” for launch, and they will be taken into account by the scheduler. In a simple RTOS using the RTC, RR or TS scheduler, that's it. But more often, and always with the Priority-scheduler, tasks can also be in a suspended state, which means that they are not taken into account by the scheduler until they are resumed and go into a “ready” state.
Suspending a Task
Suspending a task can be quite simple: a task is suspended on its own (by calling an API) or another task is suspended. Through another API call, a paused task can be resumed by another task or interrupt handler. This is “unconditional” or “pure” (pure) suspension. Some operating systems call this task "sleeping."
The RTOS can provide the task with the ability to pause (fall asleep) for a certain period of time, after which it resumes (by the system clock). This can be called "falling asleep."
If the RTOS supports “blocking” API calls, a more complex suspension can be used. Such a call allows the task to request a service or resource, which it immediately receives if it is available. Otherwise, it will be suspended until it becomes available. Timeouts can also be defined at which the task resumes if the resource is unavailable for a certain period of time.
Other task states
Many RTOSs support other states, but concepts and definitions vary greatly. For example, the state is “finished”, which simply means that the external function of the task is out (either by returning the code, or just by completing the external function block). In order for the completed task to start again, it will probably need to be somehow reset.
Another option is the “terminated” state. This is similar to a complete suspension (pure), except that the task must be returned to its original state in order to restart.
If the RTOS supports dynamic creation and deletion of tasks (see the next article), this implies another possible task state - “deleted”.
When we worked on our own real-time operating system, the MAXROS MAKS (previously published articles about it), our team “stumbled” on the blog of Colin Walls, an expert in the field of microelectronics and firmware of Mentor Graphics. The articles seemed interesting, they were translated for themselves, but in order not to “write to the table” they decided to publish. I hope they will also be useful to you. If so, then we plan to publish all the translated articles in the series.
About the author: Colin Walls has been working in the electronics industry for more than thirty years, spending a significant amount of time on embedded software. He is now an embedded software engineer in Mentor Embedded (a division of Mentor Graphics). Colin Walls often speaks at conferences and seminars, author of numerous technical articles and two books on embedded software. Lives in the UK. Colin's professional blog: blogs.mentor.com/colinwalls , e-mail: colin_walls@mentor.comThe first and second articles of the cycle are posted
here.