The Challenges of Real-Time Programming

Youıd think that the concept of ıreal timeı would be pretty straightforward. Unfortunately, thatıs not the case. Hereıs a perspective on real time and its implications for embedded systems development.

Quickıcome up with a one-sentence definition of embedded. With embedded PCs becoming common, and even MIPS chips buried in inexpensive consumer products, embedded is a term whose meaning is ever more nebulous.

So too for the designation real time, a term whose meaning is more in the mind of the beholder than cast in linguistic concrete. In fact, the community recognizes this confusion by defining two sorts of real time: ıhardı and ısoft.ı

A hard real-time task or system is one where an activity simply must be completedıalwaysıby a specified deadline. The deadline may be a particular time or time interval, or may be the arrival of some event. Hard real-time tasks fail, by definition, if they miss such a deadline.

Notice this definition makes no assumptions about the frequency or period of the tasks. It could be a microsecond or a weekıif missing the deadline induces failure, then the task has hard real-time requirements.

Soft real time, though, has a definition as weak as its name. By convention, itıs those systems that arenıt hard real-time, though generally some sort of timeliness requirements exist. If missing a deadline wonıt compromise the integrity of the system, and if generally getting the output in a timely manner is acceptable, then the applicationıs real-time requirements are ısoft.ı Sometimes soft real-time systems are those where multi-valued timeliness is acceptable: bad, better, and best responses are all within the scope of possible system operation.

Interrupts are inexorably linked with real-time systems, as only the interrupt bypasses the time-consuming tedium of polling multiple asynchronous inputs. Yet a surprising number of very fast applications are crippled by the overhead associated with servicing interrupts. Though chip vendors specify interrupt latency in terms of the time the hardware needs to recognize the external event, to firmware folks a more useful measure is time-from-input to the time weıre doing something useful, which may be many dozens of clock cycles. The multiple levels of vectoring needed by the average processor, plus important housekeeping like context pushing, are all ultimately overhead incurred before the code starts doing something useful.

Similarly, the real-time operating system (RTOS) is one of the most important and common tools in the real-time arsenal. Yet the RTOS also provides no guarantee of real-time response.

The first rule of real-time design is to know the worst case performance requirements of each activityıand only then select the right implementation (CPU, hardware design, and firmware organization). Thinking in the time domain, as well as in that of the conventional procedural, is crucial.

Enter the RTOS
A real-time application may employ the lowliest of 4-bit CPUs running a simple polled loop. In fact, these systems tend to be the most deterministic of all since their simple requirements are easy to understand and to satisfy in a timely manner. Fortunately for our job security, most products today manage multiple independent inputs, outputs, and activities. Sure, with enough work a suitably convoluted polling program can handle many complex real-time operations. We can also write our code entirely in hex codes.

Whenever an application manages multiple processes and devices, or handles a variety of activities, an RTOS is a logical tool that lets us simplify the code and help it run better.

Consider the difficulty of building, say, a printer. Without an RTOS, one monolithic hunk of code would have to manage the door switches and paper feeding and communications and the print engineıall at the same time. Add an RTOS and individual tasks each manage one of these activities; except for some status information, no task needs to know much about what any other task is doing. In this case, the RTOS allows us to partition our code in the time domain (each of these activities is running concurrently) and procedurally (each task handles one thing).

An important truism of software engineering is that code complexityıand thus development timeıgrows much faster than program size. Any mechanism that segments the code into many small independent pieces reduces the complexity; after all, this is why we write with lots of functions and not one huge main() program. Clever partitioning yields better programs faster, and the RTOS is probably the most important way to partition code in the time dimension.

At its simplest level, an RTOS is a context switcher. You break your application into multiple tasks and allow the RTOS to execute the tasks in a manner determined by its scheduling algorithm. A round-robin scheduler typically allocates more or less fixed chunks of time to the tasks, executing each one for a few milliseconds or so before suspending it and going to the next ready task in the queue. In this way all tasks get their fair shot at some CPU time.

Another sort of scheduler uses rate monotonic analysis (RMA). If the CPU isnıt completely performance bound, itıs sometimes possible to guarantee hard real-time response by giving each task a priority inversely proportional to the taskıs period. Regardless of scheduling mechanism, all RTOSes include priority schemes so you can statically and dynamically cause the context switcher to allocate more or less time to tasks. Important or time-critical activities get first shot at running. Less important housekeeping tasks run only as time allows. Your code sets the priorities; the RTOS takes care of starting and running the tasks.

If context switching were the only benefit of an RTOS, then none would be more than a few hundred bytes in size. Novice users all too often miss the importance of the sophisticated messaging mechanisms that are a standard part of all commercial operating systems. Queues and mailboxes let tasks communicate safely.

ıSafelyı is important, as global variables, the old standby of the desperate programmer, are generally a Bad Idea and are deadly in any interrupt-driven system. We all know how globals promote bugs by being available to every function in the code; with multitasking systems, they lead to worse conflicts as several tasks may attempt to modify a global, all at the same time.

Instead, the operating systemıs communications resources let you cleanly pass a message without fear of its corruption by other tasks. Properly implemented code lets you generate the real-time analogy of object-oriented programmingıs (OOP) first tenet: encapsulation. Keep all of the taskıs data local, bound to the code itself and hidden from the rest of the system.

For instance, one challenge faced by many embedded systems is managing system status information. Generally lots of different inputs, from door switches to the results of operator commands, affect total status. Maintain the status in a global data structure and youıll surely find it hammered by multiple tasks. Instead, bind the data to a task, and let other tasks set and query it via requests sent through queues or mailboxes. Is this approach slower than using a global? Sure, and it uses more memory, too. Just as we make some compromises in selecting a compiler over an assembler, proper use of an RTOS trades off a bit of raw CPU horsepower for better code thatıs easier to understand and maintain.

Most operating systems give you tools to manage resources. Surely itıs a bad idea for multiple tasks to communicate with a UART or similar device simultaneously. One way to prevent such an occurrence is to lock the resourceıoften by using a semaphore or other RTOS-supplied mechanismıso only one task at a time can access the device.

Priority Inversion
Resource locking and priority systems lead to one of the perils of real-time systems: priority inversion, which is the deadly condition where a low-priority task blocks a ready and willing high-priority task.

Suppose the system is more or less idle. A background (and perhaps unimportant) task asks for and gets exclusive access to a comm port. Itıs locked now, dedicated to the task until released. Suddenly an oh-my-god interrupt occurs that starts off the systemıs highest priority and most critical task. It, too, asks for exclusive comm port access, only to be denied that by the OS because the resource is already in use. The high-priority task is in control; the lower one canıt run and canıt complete its activity and thus release the comm port. The least important activity of all has blocked the most important!

Most operating systems recognize the problem and provide a work-around. For example, in VxWorks you can use mutual exclusion semaphores to enable ıpriority inheritance.ı The task that locks the resource runs at the priority of the highest priority task that is blocked on the same resource. This condition permits the normally less-important task to complete, thus unlocking the resource and allowing the high-priority task to do its thing.

Surveys indicate that even today vast numbers of developers write their own RTOSes, a fact thatıs hard to reconcile with our apparent devotion to software reuse. Something like 80 vendors offer a staggering array of operating systems, ranging from tiny versions for PIC-like CPUs to ones that provide complete windowing GUIs. Pricing is all over the map, as some vendors sell the RTOS outright, while others require royalty payments. Some provide only the binary image of the operating systems; others come with full source. Comparing RTOS prices is difficult at best because of the wide range of pricing models, different CPUs supported, and varying support options. Suffice to say that most RTOSes sell for several thousand dollars. Royalty payments, if any, run around a few bucks per unit or less. And be assured that a commercial RTOS is available for just about any CPU.

Memory requirements are just as diverse, with smaller versions requiring only a few kilobytes; others run into the megabytes. A new wrinkle in the RTOS market appeared last year when Microsoft released Windows CE, which is targeted at applications served by some embedded RTOSes. Itıs already common in PDAs and similar barely embedded products. Will we see it take over more of the truly embedded market? Thatıs a question that only Bill Gates and Las Vegas can answer; suffice to say that today the productıs real-time response is pretty dismal. Microsoft has announced a program to improve CEıs performance, targeting sub-50ıs thread latencies by mid-1999.

An appeal of CE is its built-in GUI, something more and more low-end systems are crying out for. Microsoft isnıt the only vendor of GUIs, though. QNX, for example, a long-time vendor of RTOSes for embedded x86 systems, sells Photon microGUI, which delivers a POSIX API in a reasonably sized footprint. Unlike CE, QNXıs product offers fast multitasking today.

Memory Woes
Using an RTOS also brings new perils. One of the more underreported ones is stack allocation. Most of us are familiar with the scientific way we decide how big the stack should be on the system (take a guess and hope). With an RTOS, the problem is multiplied because every task has its own stack.

Though tedious, computing stack requirements is feasible when coding in assembly language by counting calls and pushes. C (and C++ even more) obscures these details. Run-time calls further distance our understanding of stack use. Recursion, of course, can blow stack requirements sky high.

Given that itıs difficult at best to pick a logical stack value, be prepared to observe stack use after you build the system to ensure that a push doesnıt run off the stack into critical variables.

Because stack size is a guess, write your code from the start with stack problems in mind. In the startup code, or whenever defining a task, fill the taskıs stack with a unique signature like 0x55AA. Then probe the stacks occasionally using your debugger, and see just how many of the assigned locations have been used (the 0x55AA will be gone).

Knowledge is power.
Because the stack is a source of trouble, paranoia is reasonable; you shouldnıt allocate buffers and other sizable data structures as automatics. Watch out: malloc(), a quite logical alternative, brings its own set of problems. A program that dynamically allocates and frees lots of memoryıespecially variably sized blocksıwill fragment the heap. At some point itıs quite possible to have lots of free heap space, but so fragmented that malloc() fails. If your code doesnıt check the allocation routineıs return code to detect this error, it will fail horribly. Of course, detecting the error will also no doubt result in a horrible failure, but it gives you the opportunity to show an error code so youıll have a chance of understanding and fixing the problem.

Sometimes an RTOS will provide alternative forms of malloc() that let you specify which of several heaps to use. If you can constrain your memory allocations to standard-sized blocks, and use one heap per size, fragmentation wonıt occur.

Garbage collectionıwhich compacts the heap from time to timeıis almost unknown in the embedded world. Itıs one of Javaıs strengths and weaknesses, as the time spent compacting the heap generally shuts down all tasking. See P.J. Plaugerıs recent articles on garbage collection for his view of real-time solutions (ıWhy Garbage Collection?,ı January 1998, p. 117; ıGarbage Collection,ı March 1998, p. 133; ıReal-Time Garbage Collection,ı April 1998, p. 137).

Debugging
Any real-time design obviously has time as an integral part of the systemıs success. Itıs naıve to use conventional procedural debuggers, which are targeted at looking at static code and data, to deal with finding the unique problems associated with a time-based design. If youıre not prepared to measure time, youıre ignoring an aspect of the system every bit as important as the difference between == and = in the C code.

Most simple development tools like ROM monitors and BDM debuggers are too deprived of hardware resources to provide much insight into system timing. An exception is HPıs new 16600A tool, which blends a BDM-like CPU probe with a fast logic analyzer. The BDM part gives access to your code and target operation (a high-level debugger correlates to the original source). The logic analyzer supports tracing and time tagging of events. In-circuit emulators, of course, have long included deep trace buffers with time stamp information included. Event timers track time from event A to event B. Though an emulator is the most expensive of all debugging tools, itıs also the most versatile.

However, many modern processors with integrated cache, pipelines, and the like make traditional emulation so difficult and expensive that itıs sometimes not an option. Yet the real-time issues are more severe than ever, due to the increasing complexity of systems. Some tool vendors have taken to instrumenting your code to extract necessary timing information. Applied Microsystemıs CodeTEST products, for example, include a preprocessor that seeds information-generating instructions into your source code, which the tool then detects in real time. The cost is about a 10% performance penalty, but the process does make the invisible visible by giving you a time-based look at the firmware. Debugging changes significantly when using an RTOS. Suppose youıre debugging task A. When single-stepping through that chunk of code, should the other tasks still run at full speed? Suppose a communications task gets stopped every time you set a breakpoint anywhere: that might cause a catastrophic loss of data leading to loss of sync with other processors.

An almost incestuous series of relationships have bloomed between RTOS vendors, debugger companies, and compiler folks to ensure that no matter what RTOS and compiler mix you use, a tool exists that is aware of the RTOSıs internal tables. The debuggers use this information to allow you to work at a high level, setting breakpoints symbolically on different tasks as you glean details about messages and task states from appropriate displays.

Some RTOSes, like VRTX and pSOS, come with pseudo-ıagents,ı small kernels loaded into your code, that communicate with your debugger to pass back all sorts of neat debug info in real time. Essentially running as a separate task, the agent lets you stop a single task as the rest of the code continues to run. Timers and their ISRs continue to run, comm routines are unaffected by debugging, and even DMA activities continue intact. Many low-cost ROM monitors and ROM emulators support these agents. In fact, many RTOSes, such as RTXC, come with a complete debugger designed to let you work with your real-time application in real time.

The Future Depends on Them
In From the Earth to the Moon, Jules Verne described a never-ending battle between the cannon makers and armor vendors. The dynamics of competition served to keep both sorts of products in relative balanceıand the engineers eternally frustrated. The embedded industry is no different. As processors get faster and cheaper, we seem to stress them just as hard as we did in the 8080 days, since applications are getting more complex and demanding. We now have, though, the tools needed (in the form of RTOSes, debuggers, profilers, and the like) to both design a well-structured real-time system, and to understand the time-based behavior of these systems.

If youıre not using an RTOS in your embedded designs today, you surely will be tomorrow. Get familiar with the concepts, as designing tasking code requires a somewhat different viewıthe time domain viewıthan conventional procedural programming. Check out Jean LaBrosseıs free ıC/OS; the companion book is as good of an introduction to using an RTOS as youıre likely to find. See www.ucos-ii.com or www.embedded.com.

Improvements to these tools come almost daily. Keeping on top of the field can help you avoid the fate of the dinosaurs.

Jack G. Ganssle is a lecturer and consultant on embedded development issues. His ıBreak Pointsı column appears monthly in ESP. He can be reached at jack@ganssle.com.

Return to Embedded.com

Send comments to: Webmaster
All material on this site Copyright © 2000
CMP Media Inc. All rights reserved.