embedded software boot camp

Protothreads versus State Machines

June 9th, 2011 by Miro Samek

For a number of years I’ve been getting questions regarding Protothreads and comparisons to state machines. Here is what I think.

Protothreads are an attempt to write event-driven code in a sequential way. To do so, protothreads introduce a concept of “blocking abstraction” to event-driven programming–something that event-driven programming is trying to get rid of in the first place.

Obviously, to be compatible with event-driven programming, protothreads cannot *really* block, at least not in the same sense as traditional threads of a conventional blocking RTOS can. Instead, a protothread is still called for every event and still *returns* to the caller without really blocking. However, when a given event does not match the “blocking abstraction”, the protothread returns without doing anything and without progressing. Only when the current event matches the “blocking abstraction” the protothread advances to the next “blocking abstraction” and also returns. Please note that protothreads allow standard flow control statements, such as IF-THEN-ELSE and WHILE loops between any two “blocking abstractions”. Therefore the program feels more “natural” for designers used to the traditional sequential programming style. You simply see the expected sequence of events.

Protothreads are indeed a simplification, but only for *sequential problems*, in which only specific sequences of events are valid and all other sequences are invalid. Examples for using protothreads include the sequence of events for initializing a radio modem.

However, protothreads lose their advantage entirely if there are many valid sequences of events. This is actually the most common situation in event-driven systems. State machines are capable to handle multiple sequences of events easily. In fact, state machines are getting simpler when the sequence of events matters less. In contrast, protothreads are getting more and more complex when they need to accept more sequences of events.

So, in the end, protothreads are an attempt to replace state machines, which are considered complex and messy by the inventors of the protothread mechanism. But, the “messiness” of state machines is obviously a very subjective statement. A good state machine implementation technique can remove many (most) accidental difficulties of coding state machines. I mean, if a state machine as depicted in a state diagram is simple, and if the code does not reflect this simplicity, the problem is with the implementation technique, not with the inherent complexity of a state machine.

The bottom line: good state machine implementation techniques eliminate most reasons for using protothreads. State machines are far more generic and flexible, because they can easily handle multiple sequences of events. In comparison, protothreads are intentionally crippled state machines that transition implicitly from one “blocking abstraction” to another executing code in between as the “actions” on such implicit transition.

Is an RTOS really the best way to design embedded systems?

June 7th, 2011 by Miro Samek

LinkedIn RTE group

Recently I’ve been involved in a discussion on the LinkedIn Real-Time Embedded Engineering group, which I started with the question “Is an RTOS really the best way to design embedded systems?“.

The discussion, which has swollen to way over 600 comments by now, has sometimes low signal to noise ratio, but I believe it is still interesting.

I consider this discussion to be a continuation of the topic from my April blog post I hate RTOSes.

As before, my main point is centered on the fundamental mismatch of using the sequential programming paradigm (RTOS or superloop) to solve problems that are event-driven by nature.

I’m really curious what the visitors to EmbeddedGurus think.

Rapid Prototyping with QP and Arduino

February 21st, 2011 by Miro Samek

Arduino (see arduino.cc) is an open-source electronics prototyping platform, designed to make digital electronics more accessible to non-specialists in multidisciplinary projects. Arduino has gained popularity, because it provides both hardware and compatible software focused on developing working prototypes. By making it easier to build the first prototype, Arduino lowers the barrier of entry to the field of modern microelectronics and enables a host of new applications.

However, programming the Arduino microcontroller (Atmel AVRmega) remains a challenge. Traditionally, Arduino programs are written in a sequential manner, which means that whenever an Arduino program needs to synchronize with some external event, such as a button press, arrival of a character through the serial port, or a time delay, it explicitly waits in-line for the occurrence of the event. Waiting “in-line” means that the Arduino processor spends all of its cycles constantly checking for some condition in a tight loop (called the polling loop).

Although this approach is functional in many situations, it doesn’t work very well when there are multiple possible sources of events whose arrival times and order you cannot predict and where it is important to handle the events in a timely manner. The fundamental problem is that while a sequential program is waiting for one kind of event (e.g., a button press), it is not doing any other work and is not responsive to other events (e.g., characters from the serial port).

Another big problem with the sequential program structure is wastefulness in terms of power dissipation. Regardless of how much or how little actual work is being done, the Arduino processor is always running at top speed, which drains the battery quickly and prevents you from making truly long-lasting battery-powered devices.

Event-Driven Programming for Arduino

For these and other reasons experienced programmers turn to the long-know design strategy called event-driven programming, which requires a distinctly different way of thinking than conventional sequential programs. All event-driven programs are naturally divided into the application, which actually handles the events, and the supervisory event-driven infrastructure (framework), which waits for events and dispatches them to the application. The control resides in the event-driven framework, so from the application standpoint, the control is inverted compared to a traditional sequential program.

It turns out that the QP/C++ state machine framework beautifully complements the Arduino platform and provides everything you need to build responsive, robust, and power-efficient Arduino programs based on modern hierarchical state machines. In many ways the open source QP/C++ state machine framework is like a modern real-time operating system (RTOS) specifically designed for executing event-driven state machines. The free QM™ graphical modeling tool takes Arduino programming to the next level, by enabling automatic code generation of complete Arduino sketches.

The QP Development Kit (QDK) for Arduino is different from most other QDKs available from state-machine.com in that it is self-contained and includes the simplified and compacted source-code version of the QP/C++ framework. The QDK-Arduino is designed to plug directly into the Arduino IDE to become immediately useful without building a binary library. The extensive Application Note “Event Driven Arduino Programming with QP” describes the main concepts and how to get started.

Linear statechart notation

November 15th, 2010 by Miro Samek

The traditional fully 2-dimensional structure of UML state diagrams is too much rope to hang yourself with. There is no standard drawing order or pattern; some designers start from the top, some from the middle, and others just “go with the flow”. Transitions can originate at any state edge and go in any direction, so they are easy to miss in any nontrivial diagram because you don’t know exactly where to look.

In many ways, UML state diagrams resemble the old way of drawing tree structures (e.g., a family tree) with the root in the middle and branches fanning out in all directions. But today nobody draws hierarchical structures that way anymore. If you look at your file-system explorer you will see the hierarchical structure of directories and files arranged linearly, top-to-bottom. The “linear statechart notation” that I would like to propose here is based on the same idea.

The goal of the “linear statechart notation” is to make the diagrams more structured and legible by reducing the use of horizontal dimension.

As an example of the “linear notation” consider the state diagram shown in the screen shot from the free QM tool.  (This statechart shows the lifescycle of a space ship in a simple “Fly ‘n’ Shoot” game.) First please take a look at the hierarchical model explorer pane on the left-side of the screen. You see the Ship object, its attributes and methods followed by the Statechart with the hierarchically arranged elements below. Now, please take a look at the state diagram in the middle. You will see the one-to-one correspondence between the diagram and the explorer view. Please note that the state diagram is essentially 1-dimensional.

Finally, please take a look at the right-hand side, which is a screenshot of the *generated code* in the Eclipse-based tool (Atollic TrueSTUDIO in this case). The generated code corresponds to the state “flying”, which is highlighted in the diagram. Interestingly, the code itself is an extension of the “linear notation” that zooms into the “flying” state. Again, just go from the top to bottom in the code, inside the “flying” state in the diagram, and in the “flying” element in the model explorer. You see exactly the same elements represented in the same order, from the entry action, through the events TIME_TICK, PLAYER_TRIGGER, DESTROYED_MINE, HIT_WALL, and HIT_MINE. I think this consistency and tracibility is great.

I’d like to hear your comments about the proposed notation. I also hope that this post explains a bit how the free QM tool works and generates code.

Free state machine tool for embedded systems

November 6th, 2010 by Miro Samek

I realize that I stalled a little my series about RTOSes, event-driven programming, state machines and frameworks for embedded systems. I certainly will come back to this subject, but today I wanted to let you know about a new, free, graphical tool for drawing state machines and generating production-quality embedded code.

Traditionally, such tools haven’t particularly caught on in the embedded space, mainly because too often such tools fail to pull their own weight. Developers find themselves fighting the tool at every step of the way: from drawing the diagrams to trying to live in a straight jacket of the code structure it generates.

The new, free QM tool from Quantum Leaps (my company) is different, because it was designed from the ground up around the code-centric approach. Unlike other graphical tools, QM gives you complete control over the generated code structure, directory names, file names, and elements that go into every file. You can mix your own code with the synthesized code and use QM to generate as much or as little of the overall code as you see fit. At the low level, QM respects your graphical layout as much as possible and will not re-attach or re-route connectors, resize nodes, or adjust text annotations. You will find that you don’t need to fight the tool.

Even though a lot of effort went into making QM as UML-compliant, the tool is innovative and might work differently than other graphical state machine tools on the market. For example, QM does not use “pseudostates”, such as the initial pseudostate or choice point. Instead QM uses higher-level primitives of initial-transition and choice-segment, respectively. This simplifies state diagramming immensely, because you don’t need to separately position pseudostates and then connect them. Also, QM introduces a new notation for internal transitions, which allows actual drawing of internal transitions (in standard UML notation internal transitions are just text in the state body). This notation enables showing internal transitions with regular state transitions in a choice point–something that comes up very often in practice and was never addressed well in the standard UML.

The QM tool is available now for a free download and free, unrestricted use from state-machine.com/qm. I’d appreciate any comments about the tool, comparisons to other similar tools, code generation, UML, state machines, etc.