Using design patterns to identify and partition RTOS tasks: Part 1 - Embedded.com

Using design patterns to identify and partition RTOS tasks: Part 1

A common, but mostly unconscious habit of software developers when theyface a problem is to break it down into its constituent elements, lookfor patterns of behavior and activity, and compare them to the patternsused in similar situations in the past. Usually this process yieldsinformation on how to solve the current problem.

This habit of looking for design patterns can be an effective toolfor the embedded software developer, because it allows him or her toquickly recognize the similarities between present and past problems.It allows the developer to identify the generic aspects of previousproblems and identify whether or not they exist in the programcurrently under development. This intentional use of design patternsmakes the design process better optimized, more robust, and less likelyto result in poor code.

Design patterns are particularly useful for partitioning anapplication into tasks running under an RTOS. Typically, these designpatterns fall into three groups: desynchronizing, synchronizing, andarchitectural.

Desynchronizing patterns are used for tasks that operateasynchronously to one another, allowing prioritization. Synchronizingpatterns are used for controlling access to shared resources.Architectural patterns are used for implementing commonly occurringfunctional themes.

One very important characteristic that drives the division of codeinto tasks, and the associated patterns for those tasks, is theresponse time requirements of your system. If your system has noparticular response requirements—that is, if nothing that the CPU needsto do has a deadline—then you’re likely to write your software withoutusing an RTOS, as a simple polling loop.

If your system really has no response requirements whatever, youmight even get away without using interrupts. Few systems are thatsimple, however, since in most systems the hardware imposes at least afew deadlines. Hardware deadlines include, for example, retrieving acharacter from a serial port UART before the next character arrives andoverwrites the first, or noticing which button a user has pressedbefore the user takes his finger off the button and that information islost. Even simple systems, therefore, usually end up as a mixture ofinterrupt service routines (ISRs) and a polling loop.

Trouble arises when the response time requirements get a little toocomplicated for the interrupts-plus-polling-loop architecture. Imagineyour system has a small display that needs to be updated every 100milliseconds in order to smoothly run some animation. And suppose thepolling loop, as part of its many jobs, must construct the next framefor the animation so that it is ready to be displayed when the 100millisecond timer expires and the timer’s ISR changes the display toshow the new frame.

Now imagine that the animation doesn’t run smoothly because the CPUdoesn’t always get around the polling loop quickly enough to dependablyconstruct the next frame in a timely manner. If ISRs are your onlymechanism for prioritizing CPU work, then you might “solve” thisproblem by moving the code that constructs the next frame for theanimation into the end of the timer ISR in order to guarantee that thenext frame will be ready when the timer interrupt next occurs.

If enough features get added that the polling loop can’t keep upwith, say, the mechanical control your system needs, then, similarly,you might “solve” that problem by moving all of the code for mechanicalcontrol into ISRs. In really bad cases, most of the code ends up inISRs, and the ISRs get so long that they have to poll one another’sdevices because the ISRs themselves are causing other ISRs to misstheir deadlines. You end up with things like the temperature change ISR(which now controls the whole factory) polling the serial port, becauseotherwise 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 thispoint—you introduce a pre-emptive RTOS into your architecture. Thisgives you a way to control priorities and thereby control responsewithout moving more and more code into ISRs. That user interfaceanimation moves into a high priority task, not into an ISR, and theserial port ISR, which will still execute before the animation task,meets its deadlines. The factory control code moves into a task whosepriority is high enough that the factory runs smoothly, not into anISR, where it interferes with noticing whether the user has pushed abutton. This logic brings us to the first and most fundamental taskdesign pattern, found in almost every real-time RTOS-based system:

Task Patterns for Desynchronization
The principal problem with polling loops is that everything that theCPU does in that polling loop is synchronized, that is, things areinvariably executed sequentially as shown in Figure 1 below.

Although this has its good side, as we’ll discuss later, it’s badwhen the problem at hand is meeting deadlines. Everything in a pollingloop waits for everything else. If your linear fit1 code is in the sameloop with the code that controls the anti-lock brakes, the braking codewill have to wait until the linear fit is done before it gets theattention of the CPU. (A linear fit is a compute-intensive mathematicaloperation; it is used here and further on as a typical example of someCPU operation that might take long enough to cause your system to missother deadlines.)

Figure1 Polling Loop Code

Yes, you can play some games to stop the linear fit in the middleand see what’s going on with the brakes, but simple, maintainable, bugfree code is not a likely result of this approach.

These two operations need to be desynchronized: put the linear fitin one task, a lower priority task, and the braking operation inanother, higher priority task. Then the RTOS will ensure that thebraking operation gets the CPU when it needs it, and the linear fitgets the CPU when it is otherwise idle. The high priority task with thebraking code is rather like a junior ISR: it executes ahead ofless-urgent things like the linear fit but behind the very urgent codethat you put in the ISRs. This is the basic desynchronization pattern.

Here are some common desynchronization pattern variations that turnup:

User Interface Operation Pattern. If your user interface does nothing more in response to some user inputthan turn on an LED or some other one- or two-line operation, you’reprobably just going to take care of it in the ISR that tells yoursystem that the user input has arrived.

However, if your user interface code has to remember what menu theuser has been looking at, use the current system state and the identityof the button the user pressed to determine the next menu to present,determine a default choice for that menu, and then put up an elaboratedisplay, then perhaps a lot of that work wants to get moved out of theISR.

If all that code stays in the ISR your system may miss otherdeadlines. User interface work typically has a deadline on the order of100 milliseconds, and 100 milliseconds is plenty of time for an ISR topass a message to a user interface task, for the RTOS to switch to thattask, for a few other ISRs to execute, and for your user interface codeto do what it needs to do. Therefore, a task is the right place forthat code. The priority for that task must reflect the deadline; itmust have a higher priority than a task that, for example, does alinear fit that takes 250 milliseconds of CPU time.

Millisecond Operation Pattern. More generally any operation whose deadline is measured inmilliseconds—not microseconds—is a candidate for a high priority task.Assuming that your system has some serious computing to do at leastonce in a while, then anything that your system must do in millisecondswill miss its deadline if it has to wait for the serious computing tocomplete. (If your system never has any time-consuming CPU activity,then you’re unlikely to have any deadline problems anyway and mightwell stick to a polling loop for your code.)

Operations whose deadlines are measured in microseconds typicallyend up in ISRs in any case. Some examples of things that fall into themillisecond category are (1) Responding after a complete message hasbeen 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 addedenough of some ingredient to a manufacturing mixture.

CPU Hog Pattern. Anyoperation that takes up an amount of CPU time measured in seconds, orperhaps a large number of milliseconds, is a candidate to be moved intoa low priority task. The trouble with CPU-intensive operations is thatthey endanger every deadline in the system. Creating a separate,low-priority task for a CPU-intensive operation gets rid of theinterference. Note that of course moving such an operation into a lowpriority task is the equivalent of moving everything else into a higherpriority task. However, the “put the CPU-hogging operation into a lowpriority task” is often an obvious pattern.

Monitoring Function Pattern. If your system has some monitoring function, something that it alwaysdoes when there’s nothing else to be done, then this operation goesinto a task that becomes the lowest priority task in your system. Thismay even be a “polling task,” which never blocks, but which absorbs allleftover CPU time after all other operations have finished. Forexample, when there’s nothing else to do, the polling task in a systemthat monitors the levels of the gasoline in the underground tanks at agas station measures the levels one more time to see if anything newand interesting has happened.

In Part 2, the authors look at useful task patterns forsynchronization.

Michael Grischy is one of thefounders 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 BradAppletonhttp://www.cmcrossroads.com/bradapp/docs/patterns-intro.html3) “Design Patterns: Elements of Reusable Object-Oriented Software,” byErich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
4), “Pattern-Oriented Software Architecture: A System of Patterns,” byFrank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, andMichael Stal

Leave a Reply

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