The whole truth about RTOS. Article # 9. Scheduler: implementation
The basic principles of the work of the RTOS planners were discussed in the article “Tasks and Planning”. In this article, we look at the features that the Nucleus RTOS offers, as well as in more detail those provided by the Nucleus SE.
Previous articles in the series:
Article # 8. Nucleus SE: Internal Design and Deployment
Article # 7. Nucleus SE: Introduction
Article # 6. Other RTOS services
Article # 5. Interaction between tasks and synchronization
Article # 4. Tasks, Context Switching and Interrupts
Article # 3. Tasks and planning
Article # 2. RTOS: Structure and Real-time Mode
Article # 1. RTOS: introduction.
Planning in the Nucleus RTOS
Since Nucleus RTOS is a full-fledged, well-proven commercial RTOS, we can safely assume that the scheduler was designed in accordance with the requirements of such a product. This complex and flexible operating system provides the developer with a wide range of possibilities for solving virtually any conceivable programming problem in real time.
The scheduler can support an unlimited number of tasks (limited only by available resources) and work with priority management. A task can be assigned a priority from 0 to 255, where 0 is the highest priority and 255 is the lowest. A task has a dynamic priority, that is, it can be changed at run time, either by the task itself or by another. Multiple tasks can be assigned the same priority level. In the extreme case, all tasks can be assigned the same priority, which makes it possible to implement a scheduling policy based on the principle of Round Robin and Time-Slice.
If there are several tasks with the same priority, they will be scheduled using the Round Robin algorithm, in the order in which they were prepared. The task needs to pause or transfer control to start the next task. Tasks can also be assigned time intervals, which provide a more controlled division of the available processor time.
Task planning is 100% deterministic, which is to be expected from a similar core. Tasks can also be dynamically created and destroyed, which, thanks to the scheduler, occurs invisibly to the user.
Planning in the Nucleus SE
I developed all aspects of the Nucleus SE so that they were generally compatible with the Nucleus RTOS, but it was also simpler and more efficient in terms of memory. The scheduler is no exception. It provides many features of the Nucleus RTOS scheduler, but is somewhat limited. Flexibility is achieved by configuration at the time of assembly.
A Nucleus SE application can have a maximum of 16 tasks (and at least one). Although this number could theoretically be increased, the efficiency of the algorithms would be at risk; a number of data structures rely on storing the index number of the task (from 0 to 15) in the nibble (four bits), and they will need to be processed together with the corresponding code.
To achieve a balance between flexibility and simplicity (and size), instead of having one scheduler with multiple capabilities, Nucleus SE offers a choice of one of four types of scheduler: Run to Completion (RTC), Round Robin (RR), Time-Slice ( TS) and Priority. The scheduler is selected statically, at the time of assembly. Details of each type of scheduler are described below in the “Scheduler Types” section.
Like any other aspect of the Nucleus SE, tasks are static objects. They are determined during configuration, and their priority (index) cannot be changed.
Nucleus SE Planners
As stated above, the Nucleus SE offers a choice of one of four types of schedulers. As with most aspects of the Nucleus SE configuration, this choice is determined by writing to nuse_config.h, the NUSE_SCHEDULER_TYPE parameter must be set accordingly, as shown in this snippet from the configuration file:
Regardless of which scheduler is selected, its startup code is called immediately after system initialization. Full details on initialization of the Nucleus SE will be presented in the next article.
Run to Completion Planner
The RTC scheduler is the easiest and most suitable solution if it meets the requirements of the application. Each task must complete its work before performing the return function and allowing the scheduler to perform the next task.
It is not necessary for each task to have a separate stack. All code is written in C, assembly language is not required. Below is the RTC scheduler code in its entirety.
Code is simply an infinite loop that calls each task in turn. The array NUSE_Task_Start_Address  contains pointers to the external function of each task. The PF0 macro is a simple conversion of a void pointer to a pointer to a void function with no parameters. It is designed to ensure readability of the code.
Conditional compilation is used to enable support for additional functions: NUSE_SUSPEND_ENABLE determines whether tasks can be suspended; NUSE_SCHEDULE_COUNT_SUPPORT determines whether a counter value is required each time a task is scheduled. More information about this can be found in the following article.
Round Robin Scheduler
If a bit more flexibility is required than provided by the RTC scheduler, the RR scheduler will do. It allows the task to transfer control or pause, and then continue from the same point. The additional overhead, in addition to code complexity and non-portability, is that each task requires its own stack.
The scheduler code consists of two parts. The startup component looks like this:
If support for the initial state of the task is enabled (using the NUSE_INITIAL_TASK_STATE_SUPPOR T parameter , see “Parameters” in the next article), scheduling begins with the first finished task; otherwise, the task with index 0 is used. The context of this task is then loaded using NUSE_Context_Load () . For more information about saving and restoring context, see the “Saving Context” section in the next article.
The second part of the scheduler is the “re-planning” component:
This code is called when the task releases the CPU or pauses.
The code chooses to run a task with the following index and puts the value on NUSE_Task_Next, taking into account whether task suspension is enabled or not. The macro NUSE_CONTEXT_SWAP () is then used to trigger a context switch using a software interrupt. For more information about saving and restoring context, see the “Saving Context” section in the next article.
The Priority Scheduler in the Nucleus SE, like the other options, is designed to provide the required functionality while being quite simple. As a result, each task has a unique priority; it is impossible to have several tasks with one priority level. The priority is determined by the task index, where 0 is the highest priority level. The index of the task is determined by its place in the array NUSE_Task_Start_Address . The next article will provide more detailed information on setting up tasks.
Like the RR and TS schedulers, the Priority scheduler has two components. The launch component of the Priority scheduler is the same as that of the RR and TS schedulers, as illustrated above. The rescheduling component is somewhat different:
There is no conditional code that could disable the suspension of tasks, since this feature is mandatory for the priority scheduler; any alternative would be illogical. The NUSE_Reschedule () function takes a parameter that “tells” which task can be scheduled next - new_task. This value is set when rescheduling is called because another task is activated. The index of this task is passed as a parameter. The scheduler can then determine whether to perform a context switch by comparing the value of new_task with the index of the current task (NUSE_Task_Active) . If rescheduling is the result of pausing a task, the parameter will be set to NUSE_NO_TASK, and the scheduler will search for the task with the highest priority.
As a rule, all operating systems have the concept of finding tasks in a certain “state”. Details vary depending on the RTOS. In this article, we will look at how Nucleus RTOS and Nucleus SE use task states.
Task Status in the Nucleus RTOS
Nucleus RTOS supports 5 task states.
- Execution: The task that controls the processor at the moment. Obviously, only one task can occupy this state.
- Readiness: a task that is ready for execution (or continuation of execution) before the planner makes a decision to launch it. As a rule, a task has a lower priority than the one that is being executed.
- Suspension: sleeping task. It is not taken into account when planning until it wakes up, and at that moment it will be “ready” and may later continue execution. Usually, a task is in a “sleep” state, because it is waiting for something: when a resource becomes available, when a set period of time has elapsed, or when another task wakes her up.
- Cancellation: the task was "killed." It is not taken into account when planning until it is reset, after which the task will be “ready” or “suspended”.
- Ending: the task is completed and out of its external function, simply by leaving the external block or by executing the “return” instruction. It is not taken into account when planning until it is reset, after which the task will be “ready” or “suspended”.
Task states in the Nucleus SE
The task state model in the Nucleus SE is a bit simpler. There are usually only 3 states: Execution, Readiness and Suspension. The status of each task is stored in NUSE_Task_Status  , which has values such as NUSE_READY , although it never has a value that reflects the status of Execution. If task suspension is not enabled (see “Parameters” in the next article), only two task states are possible, and this array is missing.
There are several possible types of task suspension. If a task is suspended explicitly by itself or by another task, this is called “pure suspend” (“pure” suspension) and is represented by the status NUSE_PURE_SUSPEND. If the sleep state is enabled and the task is suspended for a certain period of time, it has the status
NUSE_SLEEP_SUSPEND. If the blocking API function is enabled (via NUSE_BLOCKING_ENABLE , see “Parameters” in the next article), the task can be suspended until the resource is available. Each object type has its own task suspension status, for example, in the form of NUSE_MAILBOX_SUSPEND. In Nucleus SE, a task can be locked in a section of memory, a group of events, a mailbox, a queue, a channel, or a semaphore.
When discussing the behavior of tasks, the words “Status” and “Status” are usually used rather loosely. There is an additional factor that can conditionally be called the “flow state”. This is a global variable NUSE_Thread_State, which contains an indication of the nature of the executable code. This refers to the behavior of many API calls. Possible values:
- NUSE_TASK_CONTEXT - The API call was made from the task.
- NUSE_STARTUP_CONTEXT - the API call was made from the startup code; the scheduler has not yet been launched.
- NUSE_NISR_CONTEXT and NUSE_MISR_CONTEXT - The API call was made from an interrupt handler. Interrupts in the Nucleus SE will be covered in the next article.
The next article will describe in detail the additional functions of the scheduler in Nucleus SE, as well as the preservation of the context.
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 , e-mail: email@example.com