RTOS Myth #4: The RTOS is in Charge

The Myth: The operating system is in charge and it decides when to switch from one application task to another.

The Truth: A real-time operating system (RTOS) is a very different beast than a multi-user desktop operating system, such as Linux. In fact, an RTOS is simply a library of functions plus a timer tick interrupt handler.

The only opportunities for an RTOS to effect a context switch from one task to another are:

1. If a running task deletes itself (or exits, if your OS allows that). In this case, a function in the RTOS library detects the lack of a running task and can directly invoke the scheduler function to select the next task to run.

2. When a running task blocks, which can only happen by making a function call into the RTOS library.

3. If a running task creates a new task with a priority higher than it's own.

4. When a previously blocked task of higher priority is unblocked, which could happen as a result of:

a. The running task made a function call into the RTOS library (e.g., semaphore post).

b. An interrupt service routine executed with that side effect.

These four (or, five, if you prefer) points of entry into the RTOS are the only mechanisms by which control of the CPU can be transferred from one task to another. They are called "scheduling points".

The implication here is that your application code is actually in charge. If it were to avoid calling into the RTOS library while simultaneously disabling interrupts, the running task could steal control of the CPU for any length of time.

Real-Time Java is Dead

A few months less than ten years ago, I presented a paper at the Embedded Systems Conference (ESC) for the first time. My 1.5 hour course was entitled "Embedded Java" or something similar. This was in Silicon Valley, and the audience was standing room only--despite a rather large room to start with.

I've tracked technical and business developments in the world of embedded and real-time Java for even longer--and written a number of articles on the subject. And so I didn't miss that over the years the audiences for courses on either variant of Java dwindled. After a hopeful year or two too long, I gave up on Java in our space and stopped proposing the topic at ESC.

Then, last Spring, I had the refreshing experience of teaching a two-day hands-on real-time Java programming class in the Netherlands. The room was packed. There was enthusiasm. And these guys were really using Java to develop software (though it wasn't truly embedded code). So I thought I'd try again at ESC and reproposed the topic.

Last week I taught a course called "Real-Time Java Programming" at the ESC Silicon Valley venue. A lot had changed about the audience size. This time, in a room of a similar size, there were many empty chairs and tables. I think there were perhaps 15 people attending this time.

By my reckoning, Java is officially dead in the embedded systems community--especially in the U.S.

Toward a Better Mutex API

A few months ago I blogged that mutexes and semaphores are distinct RTOS primitives. Unfortunately, the APIs of today's most popular commercial RTOSes only add to the confusion for application programmers.

For example, consider the VxWorks API, which not only forces mutexes and semaphores into an inappropriately common-looking API (semMXxx vs. semCXxx) but also adds a third "binary semaphore" type (semBxxx). Micrium's popular uC/OS-II API is preferable to this in that it at least has just two primitive types (OSMutexXxx and OSSemXxx). But the uC/OS-II API also forces programmers to use similar function name suffices--Post() and Pend()--with each.

I propose a new and clearer API such as the following, which is based loosely on uC/OS-II's current API:

int OSSemCreate(SEM * phSem, int cnt)
int OSSemPost(SEM hSem)
int OSSemPend(SEM hSem, int timeout)

int OSMutexCreate(MUTEX * phMutex)
int OSMutexGet(MUTEX hMutex)
int OSMutexPut(MUTEX hMutex)

Wind River would do well to eliminate semBxxx functions and rename the semCXxx functions as semXxx. In addition, the VxWorks API for mutexes should be changed to something like mutexXxx.

Note, too, that this new API is intended to force each mutex object to be created in the 'available' state (i.e., value = 1), as it already is in uC/OS-II. An additional feature of the mutex API should be that any OSMutexPut() call by a task that does not currently own that mutex should fail with an appropriate error code. Together these easily used mutex functions ensure correct usage of mutexes by application developers.

RTOS Myth #2: RMA is for Academics

The Myth: The Rate Monotonic Algorithm (RMA) is an interesting theory but it has no practical meaning for users of real-time operating systems.

The Truth: For starters,

• All of the popular real-time operating systems (e.g., VxWorks, ThreadX, and uC/OS-II) feature fixed-priority preemptive schedulers
  
• RMA is the optimal fixed-priority scheduling algorithm (and note that dynamic-priority algorithms do not degrade gracefully)
  
• Unless you use RMA to assign priorities to RTOS tasks, there are no task-specific performance guarantees; if the processor becomes overly busy in a brief period of time, a critical task may miss its deadline
  

In a nutshell, RMA is the one and only proper way to assign relative priorities to RTOS tasks with deadlines. (Shock of shocks: Deferring to your boisterous colleague Bill's insistence that his task is the most important isn't guaranteed to work!) There's a nice introduction to the RMA technique at http://www.netrino.com/Embedded-Systems/How-To/RMA-Rate-Monotonic-Algorithm/.

The principal benefit of RMA is that the performance of a set of tasks thus prioritized degrades gracefully. Your key "critical set" of tasks can be guaranteed (even proven a priori) to always meet its deadlines--even during periods of transient overload. Dynamic-priority operating systems cannot make this guarantee. Nor can static-priority RTOSes running tasks prioritized in other ways.

Too many of today's real-time systems built with an RTOS are working by accident. Excess processing power can mask a lot of design sins. But if you haven't used RMA to assign priorities, it could just be a matter of time before you get burned.

More Bad RTOS Information

The Internet (and magazines and conferences) are filled with bad information about when to choose an RTOS. In short, the world wants to sell you an RTOS, even when you don't need one or the use of one would overly complicate your software design.

Here are two generalizations from a recent whitepaper:

Operating systems make programming more efficient and better structured, and their use is now frequently justified even in embedded solutions that are relatively small.

and

A clear benefit of using an RTOS is that it reduces time to market, because it simplifies development.

At best, this is misguided advice.

Here's the straight scoop. An RTOS may either "make programming more efficient and better structured" or less efficient and poorly structured; it depends on the nature of the requirements. In many cases, a design composed entirely of state machines is easier to code and works more reliably than one using an RTOS. In other cases, particularly closed-loop control systems, a simple main+ISR approach will work even better.

Embedded C Quiz Results

When we redesigned the Netrino.com website late last year, we thought it'd be fun to challenge our more than 20,000 monthly visitors (mostly embedded software engineers) to a skills test. So we developed a ten question multiple-choice quiz (http://www.netrino.com/Embedded-Systems/Embedded-C-Quiz). And it has been a popular feature of the new site, with a couple hundred participants just in the first two months.

And now the results are starting to come in. We analyzed the early results a couple of ways and discovered something worth talking about: Quiz takers from India did about the same as quiz takers in the U.S. But the rest of the world lagged behind these two groups quite a bit.

There are ten questions in our quiz, and we consider a passing score to be 8 out of 10. A handful of quiz takers have scored 100%, but most score in the 30-90% range, with an overall average at 60.4%. (A little scary, huh?)

Statisically speaking, there were three significant groups of quiz takers by geography. The average score of those taking the quiz from the United States was just shy of 64%. The average for India was not far behind at about 61.2%. However, the rest of the world scored an average of just 55.9%.

What does this say about the state of the profession of embedded software development? Offshoring? The quiz itself?

Breathalizer Source Code to Get a Day in Court

Here's an interesting news story at the intersection of embedded systems and due process:

http://www.news.com/Police-Blotter-Intoxilyzer-code-must-be-disclosed/2100-1030_3-6227951.html

How many potential bugs might a knowledgable expert witness spot in your code? Are the comments in your source accurate and clean enough for a judge or jury to read?

RTOS Myth #1: Mutexes and Semaphores are Interchangeable

The Myth: Mutexes and semaphores are similar--even interchangeable--operating system primitives.

The Truth: Mutexes and semaphores should always be used for distinct purposes, and should thus feature distinct APIs. (My recommendations to RTOS vendors are at the end.)

The cause of the confusion between mutexes and semaphores is historical, dating all the way back to the 1974 invention of the semaphore by Djikstra. Prior to that date, the interrupt-safe task synchronization and signaling mechanisms known to computer scientists were not efficiently scalable for use by more than two tasks. Dijkstra's scalable semaphore could be used for task synchronization (including mutual exclusion) as well as signaling.

After the introduction of commercial real-time operating systems (beginning with VRTX, ca. 1980) and the publication of a 1990 paper on priority inheritance protocols it became apparent that mutexes needed to be more than just semaphores with a binary value. Because of the possibility of unbounded priority inversion, which would break RMA assumptions, ordinary semaphores cannot be used for mutual exclusion.

Many bad sources of information add to the general confusion by introducing the alternate names binary semaphore for mutex and counting semaphore. The current wikipedia entry for semaphore is a prime example.

The correct and appropriate solution is a distinct set of RTOS primitives: one for semaphores and another for mutexes. Mutexes must prevent unbounded priority inversion. The APIs for semaphores and mutexes should be as distinct as possible, as their use is quite different.

Compiler Quality and C's volatile Keyword

At at a meeting with a client yesterday, I was reminded of a conversation we'd had about eighteen months ago at an Embedded Systems Conference. At that time the client, I'll call him John, was having a problem with C's volatile keyword on a PIC microcontroller.

John had written a few lines of C code to swap the contents of two peripheral registers, perhaps something along these lines:

uint8_t  temp;

temp = *pRegisterA;
*pRegisterA = *pRegisterB;
*pRegisterB = temp;

where pRegisterA and pRegisterB were pointers to memory-mapped I/O locations.

Since the data pointed to by pRegisterA and pRegisterB wasn't being used anywhere else in the code, the compiler's optimizer was completely ignoring the above code; outputting zero opcodes of machine code for that sequence.

As John and I discussed then, redeclaring the pointers as pointer to volatile integers (e.g., uint8_t volatile * pRegisterA = /* address */;), should have instructed the compiler to treat those lines of code as sacred and output corresponding machine instructions. Having tried this already, though, his compiler continued to output nothing.

Wow! John didn't realize it at the time but he had just found a bug in his compiler.

I advised John to try another compiler, rather than the free compiler he was using. You generally do get what you pay for with C cross compilers. And, indeed, his problem went away with the new compiler.

Although it is common for embedded programmers to believe their compiler's optimizer is broken when the flaw is really their failure to declare certain variables volatile, this was a genuine case of an internal compiler bug.

Public Course on Multithreaded Programming

This coming January, I'll travel from chilly Baltimore to sunny Miami to teach an in-depth training course about the proper use of real-time operating systems to design multithreaded firmware. The aim of the class is to clarify the safe and correct use of RTOS primitives, such as mutexes, semaphores, and mailboxes.

The two-day course, called Multithreaded Programming with uC/OS-II, will be held January 22-23, 2008 at the Weston, Florida headquarters of RTOS vendor Micrium, just east of the Everglades. Registration is open to the public, but the total number of seats is limited.

The hands-on course involves a mix of lectures and a coordinated series of programming exercises. The target hardware is an ARM9 development board from STMicro. The increasingly popular uC/OS-II real-time operating system will serve as the reference API with compiler and debug tools from IAR Systems.

Full details, including registration instructions, are available at the Micrium website: http://www.micrium.com/support/training.html

MO/HO Market?

I was fascinated to receive the following message from a former colleague in e-mail yesterday:

Do you have any requirements for a Linux C++, Windows .NET, or embedded programmer who can work remotely? I have high speed (1.5 mbps) internet, a wireless router, and 3 laptops in my motorhome. I only need about $25/hr to support my new lifestyle.

Of course, it has become the norm that computer programmers and many other types of professionals can work from their countries of origin or even home offices. Some observers have gone so far as to call this the world is flat effect of the Internet.

But $25/hr for an experienced programmer living as a connected nomad somewhere in America? Could this be the end game for all of us in the computer services business?

Bad Code

Enough with the bad code already! While I’ve been discussing the subject of which language to use for embedded programming and how best to ensure a quality result the past few months, millions of lines of “bad code” have been newly written.

You’ve seen the kind of code I mean: modules and procedures carelessly divided (broken up as if to meet some arbitrary length limit, for example, rather than by purpose); variables randomly named, mostly global, and with a large percentage no longer in use; compiler warnings flagging a myriad of suspicious pointer and type conversions unheeded; comments—what few there are—mostly outdated and in conflict with the nearby code; other comments full of code that once did or meant something to somebody, but now doesn’t (or does it?).

Bad programmers can write bad code in any language. It’s time they and their code were dragged into the light. I’ve encountered bad assembly code, bad C code, and bad C++ code. I’m sure those who program regularly in Ada, Java, and every other language have uncovered bad code in those languages as well.

To achieve the best long-term results, it is often necessary to have the courage to discard such code and rewrite it. If an organization can accept that the existing code was never worth the money spent to develop it in the first place, they can move on and look forward to a brighter future. Ultimately, the costs (including the rewrite) will probably be much lower.

I’ve replaced bad assembly code with new C code that was smaller, more efficient, and easier to maintain. It was also developed more quickly and cheaply than the bad code and had far fewer bugs at integration. I’ve similarly replaced bug-ridden C code with new C++ code that required half the code and data memory—and was just as efficient.

I’m not trying to suggest that C is better than assembly, that C++ is better than C, or even that the original authors in these examples chose the wrong languages to begin with. (I’ve also rewritten bad code in the same language as the original.) I’m just trying to make the point that assembly doesn’t always result in the most compact code; there’s skill involved in achieving that result. And C++ code can be just as compact and efficient as C code—if you know what you’re doing.

That, of course, is the important part: The programmer must know what he is doing. Too often that isn’t the case. However they manage to get themselves hired, bad programmers seem to exist in every organization. The decisions they make and the code they write create more problems, hassles, and bugs than any interviewer can imagine. The costs are unbearable, particularly in real-time/embedded devices.

Well? Don’t just stand there. Do something. If it’s your own code that needs the fixing: read a book like Code Complete and start learning how to write well-structured easy-to-read code, obey the Ten Commandments for C Programmers, and get a copy of lint. The version control system you aren’t using should help you feel comfortable deleting no-longer needed code rather than commenting it out. If the fault lies elsewhere: tell someone who can do something about it before any more serious damage is done.

Quantum Programming

I don’t buy many books about embedded systems. Most books of relevance find their way to me as review copies. I try to read, or at least skim, all those that look promising. Unfortunately, I’ve found that relatively few are worthy of permanent space on my bookshelf or recommendation to others. Which is why I want to tell you about one recent standout.

Perhaps you recall the article “State-Oriented Programming,” which appeared precisely two years ago in Embedded Systems Programming magazine? If not, suffice it to say it described a very simple manual coding technique for turning hierarchical state machines into compact C or C++ programs. Though I was certainly impressed by the authors and their approach, I didn’t then recognize the brilliance of the underlying ideas.

The primary author’s recent publication of a book-length treatment of the topic has helped me see the light. The book, by Miro Samek, is titled Practical Statecharts in C/C++ (CMP Books). However, the title of the book is a major understatement. What stands out in my mind is not the practical nature of the solution it provides to a common recurring problem, but the downright revolutionary ideas behind that solution.

The author’s so-called “Quantum Programming” may ultimately change the way embedded software is designed. Never before has there been a viable alternative to the traditional main()+ISR vs. RTOS problem. Preemptive multitasking only works well in specific scenarios, while main()+ISR comes with its own set of problems when you try to scale it. A third way is needed.

This book presents a solution, based around state machines, that is compact (5KB is all that's typically required), realized in C and C++ (no fee or royalties), of theoretical value in any language (even assembly), and can support multiple state machines running in parallel if necessary. It's also the first good way I've seen to deal with the inheritance of state behavior in hierarchical state machines. Samek calls his implementation the “Quantum Framework.”

Before quantum programming, there were basically three approaches to state machine implementation: switch statements, tables of function pointers, and object-oriented programming constructs. The handling of substates in hierarchical state machines was complex in all three approaches. Hierarchical state machines are common, with part of each state’s behavior being determined by its parent state and the rest by the substate itself. This is difficult to implement in the traditional approaches because it either requires duplication of code or additional function/method calls. At best, the results tend toward spaghetti code.

In a nutshell, the quantum programming technique is a design pattern for direct efficient implementation of flat or hierarchical state machines. It uses the popular and proven UML statecharts as its graphical specification language, and leaves the choice of implementation programming language up to the developer. Hierarchical states are implemented via an externally-driven “event processor,” the use of which ensures that substates need not duplicate the functionality of their parents (and grandparents).

I believe that Miro Samek’s innovative techniques will quickly become popular, and I have already put them to good use. If you read only one book about embedded systems this year, make it Practical Statecharts in C and C++.

Is C Passing?

One of the very first comments I received in response to my editorial for the May 2002 edition of Embedded Systems Programming magazine (subsequently revised and posted to this blog as “Firmware Ethics”) was the following:

You're obviously not a very good programmer and are using an archaic language. Nearly everything you said was biased toward mediocrity. Those of us Ada professionals wish that you would speak for yourself.

Though quite rudely put, the author does suggest an interesting possibility. Could the choice of programming language alone significantly improve the quality and safety of our finished products?

Of the eight suggested professional “ethics,” three (check return codes, enforce coding standards, and run lint regularly) might possibly be removed from the list if we all used a more strongly enforced language. Such a language would need to at least support exceptions, have strict syntax rules, and be strongly typed.

The C programming language fails on the first two counts. C++ adds support for exceptions but does not require programmers to use them. Among the “well-known” languages only Ada and Java meet all three requirements. Both also offer language-level support for multithreading, which enhances program portability. Yet few embedded programmers use either language.

A recent Embedded Systems Programming study suggests that almost three quarters of subscribers use C regularly. C++ is used by about half, with a slight erosion of C’s relative numbers in recent years. Assembly language remains almost as popular as C++, though the trend with that language is clearly toward decreasing use. Despite its strengths, the use of Ada—currently below 5%—is also on the decline. And, though its use is higher and on the increase, Java has a long way to go before it achieves acceptance within the embedded community.

Why not consider a switch? Not all of us develop systems with safety aspects; but perhaps those who do ought to take the issue of language selection seriously at the outset of new projects. How many bugs need to be preventable to make such a transition cost effective?

Many recognize C’s weaknesses and some, like the U.K.’s Motor Industry Software Reliability Association, have even laid down complex ground rules for its use in safety-critical systems. So why stick with C at all? Why should we allow past practice to dictate future language choices? Will it take a future catastrophe to get us to make the change we should today?

Don’t get me wrong. I love C. It was my first programming language and the one I use most competently. In an ideal world, though, the language decision should not be made based on our personal biases and experience. This is a decision that should be based solely on professional standards. But how can we compare languages analytically and measure the results of a transition from one language to another? It would be nice if there were easy answers.

Unfortunately, even if every one of us did switch to some “safer” language, miscommunication and logical errors would continue to be part and parcel of our discipline. To produce quality maintainable code, it would still be necessary to comment our work well, use version control, perform code inspections and regular testing, and measure real-time performance. Though compilers might be able to protect us from shooting ourselves in the foot, they’ll never stop us from being entirely too human.