Posts Tagged ‘state machines’

Economics 101: UML in Embedded Systems

Tuesday, April 17th, 2012 Miro Samek

With UML, just as with anything else in the embedded space, the ultimate criterion for success is the return on investment (ROI). Sure there are many factors at play, such as “coolness factor”, yearning for a “silver bullet” and truly “automatic programming” all fueled by the aggressive marketing rhetoric of tool vendors. But ultimately, to be successful, the benefits of a method must outweigh the learning curve, the cost of tools, the added maintenance costs, the hidden costs of “fighting the tool” and so on.

As it turns out, the ROI of UML is lousy unless the models are used to generate substantial portions of the production code. Without code generation, the models inevitably fall behind and become more of a liability than an asset. In this respect I tend to agree with the “UML Modeling Maturity Index (UMMI)“, invented by Bruce Douglass. According to the UMMI, without code generation UML can reach at most 30% of its potential, and this is assuming correct use of behavioral modeling. Without it, the benefits are below 10%. This is just too low to outweigh all the costs.

Unfortunately, code generation capabilities have been always associated with complex, expensive UML tools with a very steep learning curve and a price tag to match. With such a big investment side of the ROI equation, it’s quite difficult to reach sufficient return. Consequently, all too often big tools get abandoned and if they continue to be used at all, they end up as overpriced drawing packages.

So, to follow my purely economic argument, unless we make the investment part of the ROI equation low enough, without reducing the returns too much, UML has no chance. On the other hand, if we could achieve positive ROI (something like 80% of benefits for 10% of the cost), we would have a “game changer”.

To this end, when you look closer, the biggest “bang for the buck” in UML with respect to embedded code generation are: (1) hierarchical state machines (UML statecharts) and (2) an embedded real-time framework. Of course, these two ingredients work best together and complement each other. State machines can’t operate in vacuum and need an event-driven framework to provide execution context, thread-safe event passing, event queueing, etc. Framework benefits from state machines for structure and code generation capabilities.

I’m not sure if many people realize the critical importance of a framework, but a good framework is in many ways even more valuable than the tool itself, because the framework is the big enabler of architectural reuse, testability, traceability, and code generation to name just a few. The second component are state machines, but again I’m not sure if everybody realizes the importance of state nesting. Without support for state hierarchy, traditional “flat” state machines suffer from the phenomenon known as “state-transition explosion”, which renders them unusable for real-life problems.

As it turns out, the two critical ingredients for code generation can be had with much lower investment than traditionally thought. An event-driven, real-time framework can be no more complex as a traditional bare-bones RTOS (e.g., see the family of the open source QP frameworks). A UML modeling tool for creating hierarchical state machines and production code generation can be free and can be designed to minimize the problem of “fighting the tool” (e.g., see QM). Sure, you don’t get all the bells and whistles of IBM Rhapsody, but you get the arguably most valuable ingredients. More importantly, you have a chance to achieve a positive ROI on your first project. As I said, this to me is game changing.

Can a lightweight framework like QP and the QM modeling tool scale to really big projects? Well, I’ve seen it used for tens of KLOC-size projects by big, distributed teams and I haven’t seen any signs of over-stressing the architecture or the tool.

Protothreads versus State Machines

Thursday, June 9th, 2011 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.