The scheduler – implementation

The key concepts of RTOS schedulers were covered in a previous article. Here we will look at the facilities offered by Nucleus RTOS and, in much more detail, those provided by Nucleus SE.

Scheduling in Nucleus RTOS

Since Nucleus RTOS is a fully-fledged, well-proven, commercial RTOS, it may be assumed (correctly!) that the scheduler has been carefully designed for the requirements of such a product. It is sophisticated and flexible, giving the developer a wide range of options to address almost any conceivable real-time programming challenge.

The scheduler can support an indefinite number of tasks (only limited really by available resources) and is priority driven. A task may be assigned a priority from 0 to 255, where 0 is the highest priority and 255 the lowest. A task’s priority is dynamic – it may be changed at run time by itself or by another task in the application. Multiple tasks may be assigned the same priority level. In an extreme case, all the tasks may be assigned the same priority, which enables the implementation of a round robin or time sliced scheduling scheme.

If there are multiple tasks at the same priority, they will be scheduled in a round robin fashion, in the order in which they became ready. A task would need to suspend itself or relinquish control to allow the next one to be run. Tasks may also be assigned time slices, which enables a more controlled division of available CPU time.

Task scheduling is 100% deterministic, as might be expected from such a kernel. Tasks may also be dynamically created and destroyed, the process of which is handled by the scheduler seamlessly.

Scheduling in Nucleus SE

I designed all aspects of Nucleus SE to be broadly compatible with Nucleus RTOS, while being simpler and very memory efficient. The scheduler is no exception. It provides many of the capabilities of the Nucleus RTOS scheduler, but is somewhat restricted. Flexibility is achieved by build-time configuration.

A Nucleus SE application may have a maximum of 16 tasks (and a minimum of one, obviously). The kernel does not reserve any tasks for its own use. Although this number could theoretically be increased, the efficiency of algorithms would be compromised; a number of data structures rely on holding a task index number (0 to 15) in a nibble (four bits) and these would need to be redesigned, along with their associated code.

To achieve a balance between flexibility and simplicity (and size), instead of having a single scheduler with multiple capabilities, Nucleus SE offers a choice of four types of scheduler: run to completion, round robin, time slice and priority. The scheduler is selected statically, at configuration (build) time. This selection is described, along with more details of each scheduler type, below in Scheduler Types .

Like all aspects of Nucleus SE, tasks are static objects. They are defined at configuration time and their priority (index) cannot be changed.

Scheduler Types

As outlined above, Nucleus SE offers a choice of four types of scheduler. In common with most aspects of Nucleus SE configuration, this choice is determined by an entry in nuse_config.h – the parameter NUSE_SCHEDULER_TYPE needs to be set appropriately, as illustrated in this extract from the configuration file:

Whichever scheduler is selected, its startup code is called immediately after system initialization. Full details of Nucleus SE initialization will be covered in a future article.

Run to Completion Scheduler
The Run to Completion (RTC) scheduler is the simplest option and should be the first choice if it meets the demands of the application. Each task must complete its work before returning and allowing the scheduler to run the next task.

There is no requirement for a separate stack for each task and all of the code is written in C – no assembly language is needed at all. Here is the entire code of the RTC scheduler.

The code is really just an infinite loop, which calls each task in turn. The array NUSE_Task_Start_Address[] contains pointers to each task’s outer function. The macro PF0 is simply a caste to convert the void pointer to be a pointer to a void function with no parameters. It is simply intended to aid code readability.

Conditional compilation is used to include support for optional functionality: NUSE_SUSPEND_ENABLE determines if tasks may be suspended; NUSE_SCHEDULE_COUNT_SUPPORT determines whether a count of each time a task is scheduled is required. Further details of these may be found in the next article.

Round Robin Scheduler
If a little more flexibility than that afforded by the RTC scheduler is required, the Round Robin (RR) scheduler may be a good choice. It provides the possibility for a task to relinquish control or suspend itself and later continue from the same point. The additional overhead, apart from code complexity and non-portability, is that each task requires its own stack.

The scheduler code is in two parts. The start-up component looks like this:

If initial task state support is enabled (by a setting of NUSE_INITIAL_TASK_STATE_SUPPORT – see Options in the next article) the first ready task is located; otherwise a task index of 0 is used. The context of this task is then loaded using NUSE_Context_Load() . For more detail on context save and restore, see Context Saving in the next article.

The second part of the scheduler is the “reschedule” component:

This code is called when a task relinquishes the CPU or is suspended.

The code selects the next task index to be run and places the value into NUSE_Task_Next , taking into account whether task suspend is enabled or not. The NUSE_CONTEXT_SWAP() macro is then used to invoke a context swap using a software interrupt. For more detail on context save and restore, see Context Saving in the next article.

Priority Scheduler
The Nucleus SE Priority scheduler is, like the other options, designed to provide the required functionality but still be quite simple. As a result, each task has a unique priority – it is not possible to have multiple tasks at any priority level. This priority is inferred from the index of the task – 0 is the highest priority level. The index of a task is determined by its place in the NUSE_Task_Start_Address[] array – a future article will give more details on configuring tasks.

Like the RR and TS schedulers, the Priority scheduler has two components. It shares the start-up component with the RR and TS schedulers, which was illustrated above. The reschedule component is slightly different:

There is no conditional code to account for task suspend not being enabled, as this capability is mandatory for the Priority scheduler; any alternative would be illogical. The NUSE_Reschedule() function takes a parameter, which is a “hint” about which task might be scheduled next – new_task . This value is set when the reschedule is called because another task is woken up. That task’s index is passed as the parameter. The scheduler can then determine whether to perform a context switch by comparing new_task with the current task’s index (NUSE_Task_Active ). If the reschedule is the result of a task being suspended, the parameter will be set to NUSE_NO_TASK and the scheduler simply searches for the highest priority ready task.

Task States

As discussed in an earlier article, all operating systems tend to have a concept of tasks being in a particular “state”. The details differ from one RTOS to another. Here we will look at how Nucleus RTOS and Nucleus SE utilize task states.

Nucleus RTOS Task States
Nucleus RTOS basically supports five task states:

  • Executing – The task which is currently in control of the CPU. Obviously only one task can occupy this state.
  • Ready – A task which is prepared to execute (or continue executing) pending a decision by the scheduler to run it. Typically, the task may be at a lower priority that the one that is executing.
  • Suspended – A task which is “asleep”. It is not considered for scheduling until it is woken up, at which point it will be “ready” and may later continue executing. A task is usually asleep because it is waiting for something to occur: a resource to become available, a time period to elapse or another task to wake it up.
  • Terminated – A task has been “killed”. It is not considered for scheduling until it is reset, at which point it may be “ready” or “suspended”.
  • Finished – A task has completed and exited from its outer function, either by simply exiting the outer block or executing a return statement. It is not considered for scheduling until it is reset, at which point it may be “ready” or “suspended”.

Since Nucleus RTOS supports dynamic creation and destruction of objects – including tasks – a task might also be considered to be in the “deleted” state. However, since once a task is deleted, all of its system resources cease to exist and the task itself no longer exists, so it cannot have a state. The task’s code may still be available, but the task entity would need to be created again.

Nucleus SE Task States
The Nucleus SE task state model is somewhat simpler. There are normally just three states: Executing , Ready and Suspended . The state of each task is stored in NUSE_Task_Status[] , which has values like NUSE_READY – although it never has a value reflecting the Executing state. If task suspend is not enabled (see Options in the next article), only two task states are possible and this array does not exist.

There are multiple possible types of task suspend. If a task is suspended explicitly by itself or by another task, that is termed a “pure suspend” and represented by the status NUSE_PURE_SUSPEND . If task sleep is enabled and a task has suspended itself for a time period, it has the status NUSE_SLEEP_SUSPEND . If API function call blocking is enabled (via NUSE_BLOCKING_ENABLE – see Options in the next article) a task may be suspended, pending the availability of a resource. Each type of object has its own task suspend status of the form NUSE_MAILBOX_SUSPEND , for example. In Nucleus SE, a task may be blocked on a memory partition, an event group, a mailbox, a queue, a pipe or a semaphore.

Thread State
The words “state” and “status” tend to be used quite loosely when discussing the behavior of tasks. There is an additional factor, which I arbitrarily term the “thread state”. This is a global variable – NUSE_Thread_State – which carries an indication of the nature of the code being run. This is relevant to the behavior of many API calls. Possible values are:

  • NUSE_TASK_CONTEXT – The API call was made from a task.
  • NUSE_STARTUP_CONTEXT – The API call was made from the start-up code; the scheduler has not yet been started.
  • NUSE_NISR_CONTEXT and NUSE_MISR_CONTEXT – The API call was made from an interrupt service routine. Interrupts in Nucleus SE will be discussed in detail in a future article.

In the next article, the optional scheduler functionality in Nucleus SE will be detailed and we will take a look at context saving.

Colin Walls has over thirty years experience in the electronics industry, largely dedicated to embedded software. A frequent presenter at conferences and seminars and author of numerous technical articles and two books on embedded software, Colin is an embedded software technologist with Mentor Embedded [the Mentor Graphics Embedded Software Division], and is based in the UK. His regular blog is located at: http://blogs.mentor.com/colinwalls. He may be reached by email at colin_walls@mentor.com

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.