Tasks and scheduling - Embedded.com

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.

Continue to page 2 >>

Time Slice (TS) Scheduler
A TS scheduler is the next step in complexity from RR. Time is divided into “slots”, with each task being allowed to execute for the duration of its slot, thus:

In addition to being able to relinquish the CPU voluntarily, a task is preempted by a scheduler call made from a clock tick interrupt service routine. The idea of simply allocating each task a fixed time slice is very appealing – for applications where it fits the requirements – as it is easy to understand and very predictable.

The only downside of simple TS scheduling is the proportion of CPU time allocated to each task varies, depending upon whether other tasks are suspended or relinquish part of their slots, thus:

A more predictable TS scheduler can be constructed if the concept of a “background” task is introduced. The idea, shown here, is for the background task to be run instead of any suspended tasks and to be allocated the remaining slot time when a task relinquishes (or suspends itself).

Obviously the background task should not do any time-critical work, as the amount of CPU time it is allocated is totally unpredictable – it may never be scheduled at all.

This design means that each task can predict when it will be scheduled again. For example, if you have 10ms slots and 10 tasks, a task knows that, if it relinquishes, it will continue executing after 100ms. This can lead to elegant timing loops in application tasks.

An RTOS may offer the possibility for different time slots for each task. This offers greater flexibility, but is just as predictable as with fixed slot size. Another possibility is to allocate more than one slot to the same task, if you want to increase its proportion of allocated processor time.

Priority Scheduler
Most RTOSes support Priority scheduling. The idea is simple: each task is allocated a priority and, at any particular time, whichever task has the highest priority and is “ready” is allocated the CPU, thus:

The scheduler is run when any “event” occurs (e.g. interrupt or certain kernel service calls) that may cause a higher priority task being made “ready”. There are broadly three circumstances that might result in the scheduler being run:

  • The task suspends itself; clearly the scheduler is required to determine which task to run next.

  • The task readies another task (by means of an API call) of higher priority.

  • An interrupt service routine (ISR) readies another task of higher priority. This could be an input/output device ISR or it may be the result of the expiration of a timer (which are supported my many RTOSes – we will look at them in detail in a future article).

The number of levels of priority varies (from 8 to many hundreds) and the significance of higher and lower values differs; some RTOSes use priority 0 as highest, others as lowest.

Some RTOSes only allow a single task at each priority level; others permit multiple tasks at each level, which complicates the associated data structures considerably. Many OSes allow task priorities to be changed at runtime, which adds further complexity.

Composite Scheduler
We have looked at RTC, RR, TS and Priority schedulers, but many commercial RTOS products offer more sophisticated schedulers, which have characteristics of more than one of these algorithms. For example, an RTOS may support multiple tasks at each priority level and then use time slicing to divide time between multiple ready tasks at the highest level.

Task States
At any one moment in time, just one task is actually running. Aside from CPU time spent running interrupt service routines (more on that in the next article) or the scheduler, the “current” task is the one whose code is currently being executed and whose data is characterized by the current register values. There may be other tasks that are “ready” (to run) and these will be considered when the scheduler is executed. In a simple RTOS, using a Run to Completion, Round Robin or Time Slice scheduler, this may be the whole story. But, more commonly, and always with a Priority scheduler, tasks may also be in a “suspended” state, which means that they are not considered by the scheduler until they are resumed and made “ready”.

Task Suspend
Task suspension may be quite simple – a task suspends itself (by making an API call) or another task suspends it. Another API call needs to be made by another task or ISR to resume the suspended task. This is an “unconditional” or “pure” suspend. Some OSes refer to a task as being “asleep”.

An RTOS may offer the facility for a task to suspend itself (go to sleep) for a specific period of time, at the end of which it is resumed (by the system clock ISR, see below). This may be termed “sleep suspend”.

Another more complex suspend may be offered, if an RTOS supports “blocking” API calls. Such a call permits the task to request a service or resource, which it will receive immediately if it is available, otherwise it is suspended until it is available. There may also be a timeout option whereby a task is resumed if the resource is not available in a specific timeframe.

Other Task States
Many RTOSes support other task states, but the definition of these and the terminology used varies. Possibilities include a “finished” state, which simply means that the task’s outermost function has exited (either by executing a return or just ending the outer function block). For a finished task to run again, it would probably need to be reset in some way.

Another possibility is a “terminated” state. This is like a pure suspend, except that the task must be reset to its initial state in order to run again.

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

Next Time
In the next article we will take a further look at tasks, the context switch mechanism and interrupts. Earlier articles in this series include: Introducing: RTOS Revealed and Program structure and real time

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

3 thoughts on “Tasks and scheduling

  1. “Hi Colin,nnI am trying to better understand different system run-time scenarios in bare metal with ISRs versus RTOSes. So in a bare metal system, you can have a situation where the system architecture has ISR prioritization (sometimes you can set the p

    Log in to Reply

Leave a Reply

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