Introduction to Preemptive Multitasking
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 takeand 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.
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.
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: Nested preemption
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.
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 wayseven randomly. However, the rate monotonic algorithm (RMA) is the optimal way to ensure key task deadlines are always met.
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. (There will be more on this and related topics in a future installment of Beginner's Corner.) 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.
Jean Labrosse is founder and president of Micrium. He is the author of MicroC/OS-II: The Real-Time Kernel and Embedded Systems Building Blocks, both published by CMP Books. Jean holds a masters in engineering from the University of Sherbrooke in Canada. His e-mail address is email@example.com.
Michael Barr is the editor in chief of Embedded Systems Programming. He has written real-time embedded software for communications and control systems applications, among others. He is the author of the books Programming Embedded Systems in C and C++ (O'Reilly & Associates) and, with Jack Ganssle, CMP Books' new Embedded Systems Dictionary. Contact him at firstname.lastname@example.org.