Multitasking is fact of life for most embedded systems developers.
We have little choice in the matter: few systems these days are so
simple that you can dispense with using a task model in your design. Once you've decided to use multitasking, however, the choices start to appear. But which approach to multitasking will you choose?
We have three basic methods of multitasking.
The simplest is the round-robin scheme, a variation of a loop where each task has its turn and runs until finished. Slightly more sophisticated is the time-slice approach, where each task is allowed to run for
a fixed time and is then suspended until the next cycle.
Finally, we have the preemptive model, where the most important ready task runs until it is finished or preempted by a more important task.
The first two methods repetitively cycle through all of the tasks. The third method does not.
Which of these methods is best for a real-time system? I think the preemptive-model method
is the best. Other articles have discussed the first two methods under the heading of "cooperative" multitasking. (See "Heavyweight Tasking," by Philip Koopman, Jr., Embedded SystemsProgramming,
April 1990, pp. 42-52 and "Cooperative Multitasking," by Jack Woehr, Embedded Systems Programming,
April 1990, pp. 54-61.)
Real-time systems are preemptive by their very nature, which is why they use interrupts extensively.
For simple systems, it is often possible to do all processing using interrupt-serviceroutines (ISRs).
his approach is the easiest. However, it is not usually sufficient-especially since new designs are
increasing in complexity.
Most systems have a mix of frequent interrupts, which require little processing, and less frequent
interrupts, which require more processing. Since external events are usually asynchronous, all interrupts caused by them may occur at once.
This situation causes a temporary overload of the processor and can cause subsequent,
frequent interrupts to be missed - resulting in system malfunction. The problem is often solved by moving
extensive processing into background functions. (For purposes of this article, we define background
to be code that is not highly timecritical and that usually runs with interrupts enabled.
We define foreground as highly timecritical code that usually runs with interrupts disabled.)
Using this approach, ISR code is held to a minimum so that interrupts can be reenabled as soon
as possible. (ISRs are usually nonreentrant for speed, so it is customary to not allow them to be interrupted.)
Moving extensive processing into the background solves a major problem for most systems.
However, it introduces the question of how to communicate between the foreground ISRs and the background functions. A common approach is for each ISR to set a flag when a background service is required.
These service flags are monitored by a background code loop (variously called an idle loop or a super loop.) The background loop calls functions as their flags are set.
This approach is basically round-robin scheduling. It works fine if each function has adequate time
to complete before being called again. Background functions are usually non-reentrant (again, for speed.T
They can also use non-sharable resources).
Furthermore, some functions may need to complete within specified time constraints. These factors
often lead to the problem we encountered in the foreground -- a temporary processor overload
resulting in malfunction.
The usual solution to processor overloading is to modify the loop
so that some flags are tested more often than others. Also, long functions may be broken
into fragments so that more urgent functions can run in between the fragments. These performance problems typically occur late in a project and are solved by quick fixes. Under such circumstances.
Well-crafted code degenerates into "spaghetti code."
Spaghetti code is code that has lost its integrity. It has become subverted by a set of requirements
and has lost its clean, simple structure.
Worse, it is not easily extensible and may be understood only by its originator.
Unfortunately, this type of subversion is common. (For the past generation of microprocessor software,
it may be the norm!)
It is my theory that spaghetti code arises from a mismatch between foreground and background. The foreground is characterized by two important attributes: priority and preemption.
A roundrobin or time-sliced background lack these attributes, and that is where the problem lies. Clumsy attempts to fix the background lead to spaghetti code.
Preemption is a natural phenomenon -- as are priorities. We even run our own lives this way. For example, you are programming and the phone rings.
What do you do? You answer it! We are so accustomed to such interruptions,
we scarcely pay any attention to them. Software that allows preemption is bound to handle real-world events better. Here again,
programmers who respond to interrupts and crises are more effective than programmers who refuse to be interrupted.
Let's look at how a real-time, multitasking kernel averts the dreaded Spaghetti Software Syndrome. To start with,
we have the concept of a task. A task is not code; it is a portion of work. In software, the task is translated into a task-control block (TCB), which contains information about the task, a stack for
the task's local variables, and associated code, which often is reentrant so that it can be used by other tasks. A TCB typically includes a forward link, a backward link,a priority, a control block type, a return value, a stack handler, a stack pointer, and a function pointer. Forward and backward links are pointers used to link the task into various queues (only the pointers change; nothing really moves).
The fun field points at the code used by the task. (Code is just a list of instructions telling
the processor how to accomplish the task.) The other fields are not important here. Every kernel has
its own TCB format, this one is just an example.
(This and subsequent examples are based upon smx, a simple multitasking executive.)
Interstate Transfers
The next topic to consider is what task states are allowed.
Figure 1 is an example of task states and task-state transitions. This diagram is representative of
most kernels. NULL means that the task has not been created yet or has been deleted. WAIT
means it is waiting for an event. READY means it is ready to run. RUN means it is actually
running. In a single-processor system, only one task at a time can be in the RUN state. Most of
the time, this task will be the highest-priority task that is ready to run.
If you have ever watched streams of ants, you have some idea of how multitasking systems work
-- organized chaos! Individual ants run into other ants going the opposite direction. They get
turned around, and go off in the wrong direction. Other ants go off in circles. Yet, somehow, the
job of bringing food home to the nest gets done.
Like an ant, a task steadfastly pursues its own little mission. As with an ant colony, the
mechanism for overall system control is not obvious to an observer. It is indeed a minor miracle
resulting from the following:
Usually running the highest priority task when it is ready
Communication from task to task
Communication from foreground service routines to tasks.
To use the first scheme, the scheduler (which is part of the kernel) must occasionally gain control.
We have two mechanisms to accomplish this task. The first is when the current task (the one in the RUN state)
makes a kernel call. Following such a call, control passes to the scheduler.
The kernel call may have suspended the current task (put it into the WAIT state), caused a higher
priority task to become ready, or neither. The scheduler sorts this information and decides whether to continue the current task or run another.
The second way the scheduler gains control is when an interrupt occurs. Following an ISR, control
usually passes to the scheduler. The ISR may have caused a higher priority task to become ready.
Again, the scheduler decides what to do. It gives the system an adaptive nature determined by priorities,
which is a valuable characteristic because it makes the system behave in a reasonable manner
(the most important task runs first). It also makes the system relatively easy to design and tune
by changing priorities.
The remaining two means of system control involve objects provided by the kernel for intertask
communication. Most kernels provide semaphores and message exchanges (also called "mail boxes").
These mail boxes are usable from foreground service routines as well as from tasks.
Some tasks and service routines send messages to exchanges. Other tasks receive messages from exchanges
and process them. If an exchange has no messages, a task attempting to receive a message will be suspended
on the exchange and enter the WAIT state. The next- highest priority task will then run.
When a message is sent to the exchange, the waiting task will be resumed and enter the READY state.
If this task is of higher priority than the current task, which could be any task at this time,
it will run. Messages may pile up at exchanges during periods of peak activity. This situation is not a problem. These messages form a work stream similar to units on an assembly line moving
from one workstation (task) to the next.
Semaphores operate in a similar manner, except
that no messages are involved. A task may wait at a semaphore. Another task may signal the semaphore
causing the waiting task to resume.
Semaphores provide a means for one task to jog another.
Tasking in Practice
So much for theory. What does the code look like? It's pretty straightforward.
To create a task we simply give the task a name and assign it code, such as a C function, and a priority:
atask is a pointer to the task's TCB.
From here on, atask identifies the task. For example, to put the task into the ready queue and
make it ready to run:
start( atask );
The create_task() and start() are kernel calls. The task's code is a C function:
void taskB_main()
{
MCB_PTR m;
if (m = receive( anxchg, SEC ))
/* process m */
else /* alternative action */
}
This task waits up to one second for a message to arrive at anxchg. If no message arrives, then it
takes alternative action.
The main problem I've observed in newcomers to preemptive multitasking is their tendency to
overly control. For example, time-slicing seems to be a security blanket that is hard to give up.
Firing off signals to semaphores, where other tasks may or may not be waiting, seems a difficult
act of faith. Sending messages blindly to exchanges seems overly adventuresome. A strong need
for determinism and sequential ordering exists. Then comes the dawn -- the programmer realizes
that complex, real systems aren't very deterministic. They are best controlled by nonsequential
means! Once you have cleared these conceptual barriers you have a fascinating opportunity to
design real- time systems in a new and, hopefully, better way.
About the author
Ralph Moore graduated in physics from Caltech in 1962. He
did computer research at Honeywell then went to work for
Scientific Data Systems in 1965 as a logic designer. He
started his own consulting business, Micro Digital Associates,
in 1975 doing embedded systems (except no one called them that
then). At that time the 2MHz 8080 cost over $300 in 100 quantity!
Over the years the work mix changed steadily from hardware to
software. In 1988, Mr. Moore designed SMX, a real-time multi-
tasking kernel, and took Micro Digital into the software product
business. Today he continues as chief architect and president
of Micro Digital, Inc. You can contact him at Ralph@smxinfo.com
Network World, an International Data Group publication, is the industry's only newsweekly shaping the future of network computing in the enterprise.
subscribe now
