Most real-time operating systems employ preemptive schedulers. This primer on preemption also looks at the kind of multitasking it enables.
By reading the source code of sequential software line by line, you can tell what specific steps it will ask the processor to take—and in what specific order. In fact, if you know all the inputs to a sequential program, you can predict the precise sequence of opcodes the processor will execute and calculate the resulting output values or behaviors. Whether you run such a program fast or slow, you'll get precisely the same response.
Preemption defined
In practice, sequential operation is rare. Consider a simple infinite loop in the main() of a C program for an embedded system. Though it may appear to be sequential, this code is subject to interruption at any time by the hardware. When a peripheral's interrupt fires, the corresponding interrupt service routine (ISR) starts to run, instead of main(). The word describing this process is preemption.
Such preemption means that main() will execute more slowly on the whole than you would otherwise expect. This is because it executes in direct relation to the number and length of interruptions and any overhead associated with saving and restoring the processor's state. In essence, fewer processor cycles will be available to the code in main() as cycles are stolen and consumed by the ISR. Unless there are deadlines to be met, such interruptions do not themselves change the output of the other software; they merely slow it down.
However, since most ISRs handle interrupts from devices being used by the mainline code, their execution implies a change of system state. This state change at the hardware (or a corresponding software state change communicated by the ISR through a variable) may cause a change in the subsequent behavior of the mainline code, which must react appropriately. Not only does it become more difficult to predict what steps the processor will take, but also when and in what order it will take them.
Some processors support nested interrupts. An ISR that interrupts a program could itself be interrupted by the ISR for a higher-priority interrupt. On completion of the higher priority ISR, the original interrupt executes before the mainline code can continue.
As each preemption occurs, the processor's flags, instruction pointer, and the contents of other key registers must be saved (typically in RAM). This is called the context of the code that is preempted; it must be loaded back into the processor before that code resumes execution. In the event of an interrupt, many processors preserve the context automatically (the flags and instruction pointer may be saved on the stack, for example). Anything else that's required must be performed by the ISR's entry and exit code.
Pseudoparallelism
A similar technique can make a processor as responsive to software events as it is (by design) to hardware events. The goal is more or less to divide the software up into a set of individual event handlers called tasks. A preemptive scheduler makes this possible. The scheduler manages the application software's use of the processor to ensure that time-critical events are processed as efficiently as possible.
Each software task is a sequential function, often ending with an infinite loop, that thinks it has the processor all to itself. Each of these tasks is given one specific job, such as reading a sensor, scanning a keypad, logging some kind of data, or updating a display. Each has its own dedicated stack area in RAM and is assigned a priority relative to the others. Together, this set of tasks implements the system's required functionality.
When a higher-priority task preempts a lower-priority task, the steps the scheduler takes are similar to those the processor performs on receipt of an interrupt. First the running task's context must be saved somewhere; then the new task begins. If the new task has run previously, it too will have a saved context, which must be preloaded before it can continue. When the higher-priority task completes, the scheduler saves its final context and restores that of the preempted task. The lower-priority task resumes its execution as if nothing (other than the time shift) had happened to it at all.
Divided up this way, each task's function can be written as though it will have the processor all to itself. In reality, of course, most systems employ just one processor, so only one task (or ISR) can actually run at each instant of time. When no ISRs are active, the scheduler decides which task may use the processor based on the relative priorities of the tasks that are ready to run.
Figure 1 shows the execution timeline for two tasks and an ISR. First, the ISR preempts the lower-priority task. But that ISR's execution makes the higher-priority task ready to use the processor again. So the scheduler selects that task to run after the ISR, further delaying the return to the preempted task. Note that the processor considers the lowest-priority interrupt in a system more important than its highest-priority task.
Figure 1. Nested preemption
Task control
Information about each task, including its starting address (in C, this is often the name of the function that implements it), its relative priority, and the amount of stack space it requires, must be provided to the scheduler. The information is provided by making a system call to "create" the task; though the details of such a call vary by operating system, the effects are generally about the same.
In the task body, you'll likely need to make other system calls related to software events or timing. Many tasks will wait for a particular type of event and do something in response. Some may generate a software event. Others may do something, wait 100ms, and then repeat.
Software events and timeouts can be generated by other tasks and by ISRs. For an example of the latter, consider again the timeline in Figure 1, which shows the effect of an ISR generating an event that the higher-priority task was waiting for. Perhaps the ISR was handling a timer interrupt and the task was waiting for a certain number of those to occur. Because of the new software event, the higher-priority task is also ready to run the next time the scheduler checks.
Task priorities can be set in a variety of ways—even randomly. However, the rate monotonic algorithm (RMA) is the optimal way to ensure key task deadlines are always met.
Webinar: How to Prioritize RTOS Tasks (and Why it Matters)
Preemption tradeoffs
The memory costs of using a preemptive scheduler include extra ROM for the system calls plus RAM for task-specific stacks. Other costs are measured in lost CPU time. For example, the scheduler is software that consumes processor cycles. Context switches and clock ticks can also consume a significant percent of the available time, particularly if they occur frequently.
When tasks share resources such as global variables, data structures, or peripheral control and status registers, an operating system primitive called a mutex must be used to prevent race conditions. Mutexes are an effective means of preventing race conditions, but introduce the possibility of priority inversions.
In certain kinds of applications, the use of preemptive scheduling can simplify the overall software design by allowing it to be broken into tasks, but the approach does have its tradeoffs. As long as you keep those tradeoffs in mind, it's relatively easy to decide if a preemptive scheduler is right for your application.
This article was published in the April 2003 issue of Embedded Systems Programming. If you wish to cite the article in your own work, you may find the following MLA-style information helpful:
Labrosse, Jean and Michael Barr. "Introduction to Preemptive Multitasking," Embedded Systems Programming, April 2003, pp. 55-56.
Related Barr Group Courses:
Reliable Multithreaded Programming
For a full list of Barr Group courses, go to our Course Catalog.
