Home > On-Demand Archives > Talks >
Modern Embedded Programming with Hierarchical State Machines and Active Objects
Miro Samek - Watch Now - EOC 2021 - Duration: 41:16
Perhaps you've heard about hierarchical state machines (UML statecharts), modeling tools and automatic code generation, but have never tried them or seen them used in practice.
This presentation will show you, step-by-step, the process of designing and implementing a fun "Fly 'n' Shoot" game to run on an embedded ARM Cortex-M board as well as on your PC.
Specifically, you will see how to partition a problem into loosely coupled, event-driven components called active objects and then how to design interactions among them using sequence diagrams.
Next, you will see how to elaborate the internal behavior of identified active objects with modern hierarchical state machines.
And finally, you will see how the state machines are implemented in C and how this code can be generated automatically.
The session will utilize hands-on demonstrations using EFM32 Pearl-Gecko ARM Cortex-M4 board, the QP/C real-time embedded framework and the QM modeling and code-generation tool.From Davy Baker : What is the minimum size of flash and ram you have seen work worth Active Objects ?
The code size (ROM) of QP RTEF can be about the same as bare-bones RTOS kernel (around 4KB on ARM Cortex-M). This is assuming that QP uses one of the built-in kernels (cooperative QV kernel, preemptive, non-blocking QK kernel, or the dual-mode QXK kernel).
But when it comes to RAM consumption, QP requires less RAM than any traditional RTOS, because the built-in QV and QK kernels use only single stack for all AOs and interrupts. For example, it makes sense to use QP with as little as 1KB or RAM total.
From patelk5 : Are there any concurrency issues to be cognizant of even if Active Objects are used?
The traditional concurrency issues are all related to sharing of resources, so if you don't share anything you should not experience any of them.
The tradeoff with Active Objects is that you now use event passing. The good news is that event passing is handled by the framework (like QP) in a thread-safe manner. But still, there are limitations as to what you can and cannot do with these events. For example, you are not allowed to write to any received event. You are also not allowed to keep using an event after the RTC step. And there are some other restrictions.
Also, additional tradeoff is that queuing of events can sometimes lead to unexpected events being present in your queue, or events might get queued in unexpected order. For example, you might unsubscribe from an event and so you might not expect this event anymore. But the event might be already in your event queue, so it arrives seemingly after you've unsubscribed. Also, due to preemption some AOs might run and post events ahead of other AOs. So this can lead to re-ordering of events.
But all these issues are generally easier to deal with than the classic race conditions or data corruption. The main reason being that classic concurrency hazards do the damage before you can know about it. Here no damage is done until you process the event, so you can design your state machines to deal with the issues.
I have just added several answers to questions asked during the live Q&A session. Please check out that discussion.
From Radu Pralea : This approach (Active Objects, State Machines) seems a very elegant way of expressing the problem in a more optimal and robust way compared to a threading approach (eliminating sharing and (some) timing problems and overheads).
However,:
- it seems (at least at a first glance) a less natural way of thinking about the problem domain (more indirect, i.e. designing the sequence diagram with its constraints (no sharing), compared to a closer to the problem domain modeling approach)
Whether or not a method seems "natural" depends entirely on familiarity. To people familiar with event-driven Active Objects it's exactly the other way around. The traditional "shared-state concurrency and blocking" seem completely unnatural and backwards. For example, Active Objects are closer to the problem domain than blocking threads and mutual exclusion. I was exactly hoping to convey this in my presentation, where the "Tunnel", "Ship" and "Missile" active objects modeled directly the behavior of their real-life counterparts.
- it seems that the sequence diagram doesn't scale very well (I expect it to become less manageable with increasing size/number of concepts, compared to the task oriented design)
Sure, a single sequence diagram can hold only so much information. But who said that you can have only one sequence diagram? In fact, in any non-trivial project you will have many sequence diagrams, typically associated with use cases. Use-cases are in themselves a very useful concept, and I highly recommend to read about them.
Regarding "task oriented design", perhaps you could point me to some resources describing what that is. Do you mean flowcharts describing the sequential code? I know that Jean Labrosse introduced some quite expressive diagrams in his RTOS books, where he depicted semaphores, queues, mutexes, etc. But these are by no means standard, universally understood types of diagrams. In contrast: sequence diagrams and state diagrams (UML statechars) are standardized and have universally understood meaning.
- it seems that it's a less agile way of partitioning the problem: it would work fine for a reasonably sized problem that's very well defined beforehand, but it would require very inconvenient redesigns as the requirements keep coming and/or changing
It is exactly the other way around! Event-driven components are much more extensible than traditional blocking threads, because you can add new events and new event sequences very easily. In contrast, traditional sequential RTOS threads block to wait for events, so adding new events is hard because the system is unresponsive to them. This means that you have to keep adding new threads, just to handle new events. I showed this in my last year's presentation, where I merged two threads into one active object, exactly because the AO was extensible.
I also blogged about it in my post "RTOS, TDD and the ?O? in the S-O-L-I-D rules"
From afwaanquadri : How do you suggest an AO to handle a blocking call? such as a HTTP request.
AO should not block internally, period. So if you have an inherently blocking API, you need to use a regular blocking thread to handle that. Please note that event-driven AOs and traditional blocking threads can be used in the same system and they can cooperate. But what you should never do is to mix event-driven and sequential programming styles within a single thread.
Having said that, HTTP can be handled in a pure event-driven fashion without any blocking. There is an App Note "QP? and lwIP TCP/IP Stack", which shows an HTTP server running inside a non-blocking AO. There is also a companion video showing how this works.
From Alex Burka : Why not use C++?
This presentation used QP/C RTEF and C as the primary language, because 70+% of embedded software is written in C, and it is typically not quite clear to C programmers how to use object-oriented design patterns like "Active Objects".
But QP/C++ RTEF is also available, where it is very clear how to implement object-orientation.
From patelk5 : Is there any advantage of using a sequential code flow (like RTOS or foreground/background) over event-driven code flow (RTEF)? It seems like event-driven is superior in almost every scenario?
Sequential solution is good if the problem is sequential as well. By this I mean that the system needs to handle only a very limited number of event sequences. In that case hard-coding them in sequential code is the simplest.
Trouble is that most real life problems are NOT sequential and the system must handle many event sequences. But typically you don't know it, until you start building your system. This is very insidious, because initially every problem looks sequential, so you start that way. But inevitably you discover some other legitimate event sequences that need to be handled as well, so your sequential code degenerates...
So, yes, I agree that most of the time it is better to assume event-driven architecture that is exactly prepared to handle multiple event sequences.
From Tim Michals : Is there a Linux version of all the tools and examples?
Yes, Linux is supported as both the target to run QP and as development host.
As target, two QP ports to Linux (POSIX) are available in the <qpc|qpcpp>/ports/posix and <qpc|qpcpp>/ports/posix-qv directories. There is an AppNote "QP and POSIX" that describes how QP can work with P-threads and within just one thread. Examples are provided in the <qpc|qpcpp>/examples/workstation directory. There are also videos showing how to run QP on Raspberry Pi (embedded Linux).
Linux as development host is supported as well. Specifically there is a Linux version of the QM modeling tool and other tools (e.g., QSPY) also run on Linux.
Great implementation and really awesome design paradigm that I would like to try get started at the company I work for (which is "unfortunately" very large with very 'set' ways about current designs. But perhaps a new project will come along where it can be introduced.
I am thinking about how this can be applied where there is a object that reads/writes data to NvM. Other tasks might need to read/write, so eventually you will have a kind of 'blocking'. I can think of a task that needs to read data and then perform an action, so it posts a 'read event' to an NvM object, and then subscribes to a "READ_DONE" event. Is this the right way of thinking? And then the NvM object would have a state machine that is serviced on a tick (since it might need to wait for hardware)?
If you encapsulate the NvM inside a dedicated AO, you won't have blocking of other AOs, because you have queuing of events. But you must be careful to adequately size the event queue of the NvM-AO and to also adequately size the event pool from which you'll allocate the events.
You typically don't need to have "READ_DONE" event, just as empty acknowledgements. Instead, you will have NVM_DATA event, which will carry the requested data inside.
Regarding the internal structure of the NvM-AO, yes, it will have a state machine, or maybe two state machines one for reading and an "orthogonal" component state machine for writing (similar to the Mine components of the Tunnel-AO in the game). If the NvM-AO needs to wait for some timeouts, it can use Time-Events (please watch my last year's presentation and the little FreeACT framework).
In the end, having a dedicated NvM-AO has numerous benefits compared to the traditional sharing of the NvM and protecting it with a mutex.
-
NvM-AO will resolve any potential conflicts. For example, two AOs trying to write to the same location at the same time will be naturally sequenced by the event queue of the NvM-AO and RTC (run-to-completion) event processing.
-
NvM-AO can use the "Deferred Event" state pattern to appear always responsive to events.
-
NvM-AO can also much easier implement any wear-leveling algorithms than an alternative when access to NvM is "distributed" among many threads.
-
NvM-AO with clean event-driven interface is more portable if the underlying NvM interface or technology were to change.
-
Finally, note that a dedicated NvM-AO will not slow down the access to the NvM, because the bottleneck is not the CPU. Rather, the bottleneck is the NvM interface and potentially the erase operations when writing.
Of course, this is just your example of NvM management. But similar arguments can be made about most other resources--it usually is better and cleaner to have a "manager" of "broker" to resolve conflicts, streamline access, etc.
Thanks for the detailed response!
I can definitely see the advantages of this event driven AO paradigm, and will definitely try it when the opportunity arises in my professional career (also in a personal project if I get time for that)
Are there good SDD's (software design documents) out there that are available for download? Thank you.
The design documentation for customer's projects done with QP is typically proprietary, so I can't point you there. But it's a good idea to provide an example of an "open source" SDD even for a small application like the "Fly 'n' Shoot" game. I will put it on my TODO list and try to deliver this in the upcoming QP releases.
Thank you for the presentation!
I definitely need to try this pattern both in embedded and Windows ports. Also glad to see Gecko boards represented :)
Are there any concurrency issues to be cognizant of even if Active Objects are used? I presume race conditions could still happen depending on order events are received.
If you really avoid sharing of anything (except events) among active objects, then the classic race conditions and data corruption should NOT happen. They are replaced with "event-races" (due to active object threads preempting each other), which can lead to "unexpected" reordering of events . But event ordering issues are much more tractable than race conditions and corruption, where the damage is already done. In contrast, with re-ordered events no damage is done yet. But yes, you need to design your state machines to handle such unobvious event sequences. With some experience you will develop a sense when such "event races" can happen and when you need to prepare your state machines to handle them. I provide some examples of this in my PSiCC2 book (the section about Time Events).
Thank you Dr. Samek. I will have to complete your book.
I really like the concept of Active Actors
It looks a little like the code that one would create in Visual Basic and attach to a Button Click
Visual Basic is an example of an event-driven architecture, but active objects, at least in the QP framework, have state machines. This is a much more powerful mechanism than simple "event-handlers" from Visual Basic, because a state machine remembers the context (as the current state) from one event to the next. In my last year's talk I exactly used the Visual Basic calculator example to illustrate the problems with simple "event-handlers". I'd highly recommend that you watch that presentation, because it also introduced state machines.
Thank Miro, great talk, amazing job!
just a quick question about event passing. How are they sent/receive? Do you use a queue? a mailbox?
This is a new paradigm for me and I am impressed how nice and clean it is! looking forward to try it out!
Thanks again for sharing
javi
Yes, there is an event queue in each active object. If you are interested in the details, please watch my last year's presentation. Among others, I presented there a minimal, but fully functional implementation of the "Active Object" design pattern on top of FreeRTOS. That little framework was called "FreeACT" (I mentioned it in this talk) with the code available on GitHub (see https://github.com/QuantumLeaps/ ).
I'm already sold and using the QP framework, yet attending these sessions year after year, still amazed by the simplicity and elegance of it. Whenever possible, I avoid going back to traditional RTOSes.
I still learned a 2-3 things from this presentation. Thanks a lot and keep up the good work.
You seem to be well informed about the method, but I'm glad that you were still able to find something new in this presentation. The concepts of active objects and state machines can be implemented in many different ways. But as usual, the devil is in the detail, so to be really useful for deeply embedded MCUs the abstractions have to be implemented efficiently and the supported features need to be chosen very carefully.
Is there any advantage of using a sequential code flow (like RTOS or foreground/background) over event-driven code flow (RTEF)?
You might want to watch my last year's presentation, were exactly I explain the advantages and disadvantages of sequential and event-driven paradigm.
I hope you enjoy the presentation. Please join me for live Q&A session. I'm really looking forward to interesting questions and discussion!
QP contains software tracing facility called QP/Spy. This can output all sorts of data about the system execution, because an active object framework like QP knows so much more about the application. For example, QP framework knows about state machine execution: transitions, state entry/exit, etc. This is much more than software tracing of an RTOS kernel.
So, from this tracing data, the QSPY host application can generate all sorts of outputs, including sequence diagrams. You can also generate output for MATLAB, to analyze your traces in very sophisticated ways.