Posts Tagged ‘rtos’

RTOS Myth #2: RMA is for Academics

Thursday, March 6th, 2008 Michael Barr

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.

Go back to RTOS Myth #1 or forward to RTOS Myth #3.

More Bad RTOS Information

Thursday, February 28th, 2008 Michael Barr

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.

RTOS Myth #1: Mutexes and Semaphores are Interchangeable

Monday, January 28th, 2008 Michael Barr

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.

Go on to RTOS Myth #2.

Are all RTOSes the Same?

Wednesday, January 23rd, 2008 Michael Barr

Having just, coincidentally, returned from teaching a two-day hands-on RTOS course in Florida, I was greeted this morning by the following message from an RTOS company president in my inbox:

Recently, I have had a statement by you thrown at me. The statement essentially said that all RTOSes are the same, or something to that effect. Obviously, you and I both know that there are differences, some large and some small. The problem is that people listen to what you say and I think they may have misunderstood you. So what were you trying to say? I’d like to know so I can rebut them with your own words when they quote you.

This reply is probably best handled publicly. Having used several commercially successful RTOSes (including both of the current top two according to Embedded Systems Design); written one of my own (ADEOS) for a book; taught OS theory as adjunct faculty at the University of Maryland; and also written and spoken of non-preemptive RTOS alternatives in several venues, I am quite opinionated on the subject. A few years back I was even interviewed about RTOSes on a PBS television show called American Business Review.

Here are a few of my past RTOS articles, which may provide additional background for this post:

I believe the opening paragraph of that last article concisely sums up an opinion I’ve often expressed–and which may have been the basis of the remark aimed at the RTOS vendor who e-mailed.

Every commercial RTOS employs a priority-based preemptive scheduler. This despite the fact that real-time systems vary in their requirements and real-time scheduling doesn’t have to be so uniform. Multitasking and meeting deadlines is certainly not a one-size-fits-all problem.

But my e-mail correspondent is correct that there are differences large and small. Here are some of the most obvious differences between the various commercial RTOSes:

  1. At the API level, each RTOS is unique. Though every RTOS has functions for creating a new task, acquiring a mutex, and posting to a message queue, the specific function names and parameter lists differ “by brand”. Individual programmers may find one RTOS’ API more comfortable or logical than another.
  2. To support true real-time scheduling via RMA, each RTOS must provide the following:

    1. A guarantee that the highest-priority task ready to use the CPU is the one actually running at all times
    2. A bounded worst-case context switch time
    3. A bounded worst-case interrupt latency
    4. A mechanism to automatically prevent unbounded priority inversion during mutex contention

    An RTOS that doesn’t do one of these things is, obviously, different from the others–but most do. But the specifics may vary. In particular, the precise timing of those worst-case times may differ from one RTOS to the next on one processor to the next. In addition, the details of the chosen priority inversion workaround will make a difference in the RMA calculation mathematics.

  3. Some RTOSes can use the MMU and others can’t

Hopefully, this clarifies both that I think commercial RTOSes are somewhat commodity products and that there are, nonetheless, obvious differences.

Public Course on Multithreaded Programming

Tuesday, November 6th, 2007 Michael Barr

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