A common, but mostly unconscious habit of software developers when they
face a problem is to break it down into its constituent elements, look
for patterns of behavior and activity, and compare them to the patterns
used in similar situations in the past. Usually this process yields
information on how to solve the current problem.
This habit of looking for design patterns can be an effective tool
for the embedded software developer, because it allows him or her to
quickly recognize the similarities between present and past problems.
It allows the developer to identify the generic aspects of previous
problems and identify whether or not they exist in the program
currently under development. This intentional use of design patterns
makes the design process better optimized, more robust, and less likely
to result in poor code.
Design patterns are particularly useful for partitioning an
application into tasks running under an RTOS. Typically, these design
patterns fall into three groups: desynchronizing, synchronizing, and
architectural.
Desynchronizing patterns are used for tasks that operate
asynchronously to one another, allowing prioritization. Synchronizing
patterns are used for controlling access to shared resources.
Architectural patterns are used for implementing commonly occurring
functional themes.
One very important characteristic that drives the division of code
into tasks, and the associated patterns for those tasks, is the
response time requirements of your system. If your system has no
particular response requirements—that is, if nothing that the CPU needs
to do has a deadline—then you’re likely to write your software without
using an RTOS, as a simple polling loop.
If your system really has no response requirements whatever, you
might even get away without using interrupts. Few systems are that
simple, however, since in most systems the hardware imposes at least a
few deadlines. Hardware deadlines include, for example, retrieving a
character from a serial port UART before the next character arrives and
overwrites the first, or noticing which button a user has pressed
before the user takes his finger off the button and that information is
lost. Even simple systems, therefore, usually end up as a mixture of
interrupt service routines (ISRs) and a polling loop.
Trouble arises when the response time requirements get a little too
complicated for the interrupts-plus-polling-loop architecture. Imagine
your system has a small display that needs to be updated every 100
milliseconds in order to smoothly run some animation. And suppose the
polling loop, as part of its many jobs, must construct the next frame
for the animation so that it is ready to be displayed when the 100
millisecond timer expires and the timer’s ISR changes the display to
show the new frame.
Now imagine that the animation doesn’t run smoothly because the CPU
doesn’t always get around the polling loop quickly enough to dependably
construct the next frame in a timely manner. If ISRs are your only
mechanism for prioritizing CPU work, then you might “solve” this
problem by moving the code that constructs the next frame for the
animation into the end of the timer ISR in order to guarantee that the
next frame will be ready when the timer interrupt next occurs.
If enough features get added that the polling loop can’t keep up
with, say, the mechanical control your system needs, then, similarly,
you might “solve” that problem by moving all of the code for mechanical
control into ISRs. In really bad cases, most of the code ends up in
ISRs, and the ISRs get so long that they have to poll one another’s
devices because the ISRs themselves are causing other ISRs to miss
their deadlines. You end up with things like the temperature change ISR
(which now controls the whole factory) polling the serial port, because
otherwise serial port characters get lost. This may seem like fantasy,
but we’ve seen code like this.
At this point—ideally, rather before your code gets to this
point—you introduce a pre-emptive RTOS into your architecture. This
gives you a way to control priorities and thereby control response
without moving more and more code into ISRs. That user interface
animation moves into a high priority task, not into an ISR, and the
serial port ISR, which will still execute before the animation task,
meets its deadlines. The factory control code moves into a task whose
priority is high enough that the factory runs smoothly, not into an
ISR, where it interferes with noticing whether the user has pushed a
button. This logic brings us to the first and most fundamental task
design pattern, found in almost every real-time RTOS-based system:
Task Patterns for Desynchronization
The principal problem with polling loops is that everything that the
CPU does in that polling loop is synchronized, that is, things are
invariably executed sequentially as shown in Figure 1 below.
Although this has its good side, as we’ll discuss later, it’s bad
when the problem at hand is meeting deadlines. Everything in a polling
loop waits for everything else. If your linear fit1 code is in the same
loop with the code that controls the anti-lock brakes, the braking code
will have to wait until the linear fit is done before it gets the
attention of the CPU. (A linear fit is a compute-intensive mathematical
operation; it is used here and further on as a typical example of some
CPU operation that might take long enough to cause your system to miss
other deadlines.)
 |
| Figure
1 Polling Loop Code |
Yes, you can play some games to stop the linear fit in the middle
and see what’s going on with the brakes, but simple, maintainable, bug
free code is not a likely result of this approach.
These two operations need to be desynchronized: put the linear fit
in one task, a lower priority task, and the braking operation in
another, higher priority task. Then the RTOS will ensure that the
braking operation gets the CPU when it needs it, and the linear fit
gets the CPU when it is otherwise idle. The high priority task with the
braking code is rather like a junior ISR: it executes ahead of
less-urgent things like the linear fit but behind the very urgent code
that you put in the ISRs. This is the basic desynchronization pattern.
Here are some common desynchronization pattern variations that turn
up:
User Interface Operation Pattern.
If your user interface does nothing more in response to some user input
than turn on an LED or some other one- or two-line operation, you’re
probably just going to take care of it in the ISR that tells your
system that the user input has arrived.
However, if your user interface code has to remember what menu the
user has been looking at, use the current system state and the identity
of the button the user pressed to determine the next menu to present,
determine a default choice for that menu, and then put up an elaborate
display, then perhaps a lot of that work wants to get moved out of the
ISR.
If all that code stays in the ISR your system may miss other
deadlines. User interface work typically has a deadline on the order of
100 milliseconds, and 100 milliseconds is plenty of time for an ISR to
pass a message to a user interface task, for the RTOS to switch to that
task, for a few other ISRs to execute, and for your user interface code
to do what it needs to do. Therefore, a task is the right place for
that code. The priority for that task must reflect the deadline; it
must have a higher priority than a task that, for example, does a
linear fit that takes 250 milliseconds of CPU time.
Millisecond Operation Pattern.
More generally any operation whose deadline is measured in
milliseconds—not microseconds—is a candidate for a high priority task.
Assuming that your system has some serious computing to do at least
once in a while, then anything that your system must do in milliseconds
will miss its deadline if it has to wait for the serious computing to
complete. (If your system never has any time-consuming CPU activity,
then you’re unlikely to have any deadline problems anyway and might
well stick to a polling loop for your code.)
Operations whose deadlines are measured in microseconds typically
end up in ISRs in any case. Some examples of things that fall into the
millisecond category are (1) Responding after a complete message has
been received from another system over the serial port; (2)
Constructing a suitable response to a network frame and sending it; and
, (3) Turning off the valve when sensors tell us that we’ve added
enough of some ingredient to a manufacturing mixture.
CPU Hog Pattern. Any
operation that takes up an amount of CPU time measured in seconds, or
perhaps a large number of milliseconds, is a candidate to be moved into
a low priority task. The trouble with CPU-intensive operations is that
they endanger every deadline in the system. Creating a separate,
low-priority task for a CPU-intensive operation gets rid of the
interference. Note that of course moving such an operation into a low
priority task is the equivalent of moving everything else into a higher
priority task. However, the “put the CPU-hogging operation into a low
priority task” is often an obvious pattern.
Monitoring Function Pattern.
If your system has some monitoring function, something that it always
does when there’s nothing else to be done, then this operation goes
into a task that becomes the lowest priority task in your system. This
may even be a “polling task,” which never blocks, but which absorbs all
leftover CPU time after all other operations have finished. For
example, when there’s nothing else to do, the polling task in a system
that monitors the levels of the gasoline in the underground tanks at a
gas station measures the levels one more time to see if anything new
and interesting has happened.
In Part 2, the authors look at useful task patterns for
synchronization.
Michael Grischy is one of the
founders of Octave Software Group,
a software development consulting firm. David Simon, also a founder,
has recently retired from Octave Software.
References:
1) “Design Patterns for Tasks in Real-Time Systems,” Class ETP-241,
Spring 2005
2) “Patterns and Software: Essential Concepts and Terminology,” by Brad
Appleton
http://www.cmcrossroads.com/bradapp/docs/patterns-intro.html
3) “Design Patterns: Elements of Reusable Object-Oriented Software,” by
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
4), “Pattern-Oriented Software Architecture: A System of Patterns,” by
Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, and
Michael Stal
