The whole truth about RTOS from Colin Walls. Article # 3. Tasks and Planning

Original author: Colin Walls
  • Transfer


We examined multitasking, the property of the operating system to run several quasi-independent programs at the same time. Before we take a closer look at the tasks, we need to deal with the terms.

Previous articles in the series:
Article # 2. RTOS: Structure and Real-Time Mode
Article # 1. RTOS: introduction.

We use the word "task", although 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 RTOSs used in embedded applications use a multi-threaded model. Several threads can be executed simultaneously, 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 to the RTOS itself.

An alternative is the 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 difficult and time consuming, since the operating system must appropriately configure the memory management unit, the memory manager (English Memory Management Unit, MMU). Of course, such an architecture is only possible with a processor that supports MMU. The processes are supported by "high-performance" RTOS and most desktop OS. Moreover, each process can support splitting into several threads, but this property is rarely used in ordinary embedded applications.

If an MMU is available, a compromise can be reached:



Many "streaming" RTOSs support MMUs to protect memory from unauthorized access. Thus, while the task is in context, only a part of its code / data and the necessary sections of the RTOS are “visible”; the remaining memory blocks are disabled, and an access attempt will cause an emergency (for ordinary people) / exception (for programmers). This makes context switching a little more difficult, but the application itself is more secure. This mode can be called “Thread Protected Mode” or “Lightweight Process Mode”.

Planners



As we know, the illusion of the simultaneous execution of tasks is achieved by allocating processor time to complete each of the tasks. This is the core function of the kernel. The method of distributing time between tasks is called "planning." Scheduler — software that determines which next task to transfer control to. The logic of the scheduler and the mechanism that determines when and what should be executed is the planning algorithm. In this section, we look at several planning algorithms. Task planning is an extensive 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) is very simple and consumes minimal resources. This is an ideal service if it meets the requirements of the application. Below is the graph for a system using the RTC scheduler: The



scheduler takes turns invoking the top-level functions of each task. The task controls the processor (interrupts it) until the top-level function executes the return statement return. If the RTOS supports the suspension of tasks, then any tasks currently suspended are not executed. This topic is discussed in the article below, see "Pausing a task."

A great advantage of the RTC scheduler, in addition to simplicity, is a single stack and portability of the code (assembly is not required). The downside is that the task can “take” 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 work from the stopping place), you can achieve more flexibility with the help of static variables of the “state”, which determine the logic of each subsequent call.

Scheduler Round Robin (RR)



The RR scheduler ("carousel") is similar to 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. She can free the processor at any time by making an RTOS call. This call causes the kernel to save the context of the current task (all registers, including the stack pointer and command pointer) and load the context of the next task in the queue. In some RTOSs, the processor can be freed (pause the task) in anticipation of the availability of the kernel resource. This is more complicated, but the principle is the same.

The flexibility of the RR scheduler is determined by the ability to continue to perform 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 Scheduler (TS)



Scheduler TS (time slice - "time slice") to a level more complex 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 being able to voluntarily free 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 period to each task is very attractive (where possible): it is easy to understand, and it is very predictable.
The disadvantage of the TS scheduler is that the percentage 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 can become more predictable if tasks in the background are implemented. The background task can be performed instead of any suspended task and take up the time interval when the task is released (or pauses itself).



Obviously, the background task should not perform time-critical work, since the share of processor time allocated to it is absolutely unpredictable: it can never be scheduled.

Such a solution assumes that each task can predict when it will be planned again. For example, if you have slots for 10 ms and 10 tasks, the task knows that if it is freed, it will continue to execute after 100 ms. With this solution, you can achieve more flexible configuration of time cycles (timings) for application tasks.
The RTOS can provide different time slots for each task. This provides more flexibility, but also as 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 the allocated processor time.

Priority Scheduler



Most RTOS support priority-based planning. The idea is simple: each task is given priority, and at any time the task that has the highest priority and is “ready” for execution is passed to the processor: The



scheduler starts when an event occurs (for example, an interrupt or call to a specific kernel service) that forces a task with a high priority becomes "finished". There are three circumstances in which the scheduler begins to work:
• The task is suspended; the scheduler must schedule the next task.
• A task prepares a higher priority task (using an API call).
• An interrupt handler (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.
The number of priority levels varies (from 8 to several hundred), threshold values ​​also vary: some RTOSs perceive the highest priority as 0, while in others 0 means the lowest priority.
Some RTOS allow only one task at each priority level; others allow a few, 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 examined several planners, however, 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 split the time between several ready-made tasks at the highest level.

Task states



At any given time, only one task is performed. In addition to the processor 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 executing 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 all. But more often, and always with a 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 state of "readiness".

Pause a task



Pausing a task can be quite simple: the task pauses on its own (by calling the API) or another task pauses it. Through another API call, a suspended task can be resumed by another task or interrupt handler. This is an “unconditional” or “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 (according to the system clock). This can be called "falling asleep."

If the RTOS supports “blocking” API calls, more sophisticated suspension can be used. Such a call allows the task to request a service or resource that it will immediately receive 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 RTOS support other states, but concepts and definitions vary widely. For example, the state is “finished”, which simply means that the external function of the task has exited (either by returning the code or just by completing the external function block). In order for the completed task to start running again, it will probably need to be reset somehow.

Another option is the terminated state. This is similar to a complete suspension (pure), except that the task must be reset to restart.

If the RTOS supports the dynamic creation and deletion of tasks (see the following article), this implies another possible state of the task - “deleted”.

When we worked on our own real-time operating system, RTOS MAX(previously published articles about it), our team "came across" the blog of Colin Walls (Colin Walls), an expert in the field of microelectronics and embedded software company Mentor Graphics. Articles seemed interesting, translated them 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 over thirty years, devoting most of his time to firmware. He is now a firmware engineer at Mentor Embedded (a division of Mentor Graphics). Colin Walls often speaks at conferences and seminars, the author of numerous technical articles and two books on firmware. Lives in the UK. Colin's Professional Blog:blogs.mentor.com/colinwalls , e-mail: colin_walls@mentor.com


The first and second articles of the cycle are posted here.

Also popular now: