Arch 9 - Application Framework Gallium IO

Hierarchical State Machines as Building Blocks

Over the last few episodes, we introduced the concept of finite state machines (FSMs), hierarchical state machines (HSMs) and asynchronous system design. We have looked into using Quantum Platform (QP) to implement HSMs in real-time embedded systems. As our first practical example, we explored the statechart design of an LED pattern generator (GpioOut) and its implementation on an STM32 microcontroller system (STM32L4S5 discovery board).

Imagining we are building a real-life system, we will definitely interface to many more hardware peripherals than a single LED, such as an LCD display, a WiFi module, motor controllers, buttons, sensors, etc. We will also need some high-level coordinators to manage the business logic and interaction among these input and output hardware peripherals.

How do we scale up from a single state machine for the LED driver to a complete system with a multitude of input/output peripherals and interaction logic?

One approach were to augment the existing LED state machine with more states and transitions to take care of other peripherals and interaction logic. Obviously this is not going to work as that single state machine will get over-complicated and hard to manage.

Another approach is to partition the software system into threads running on top of a real-time operating system (RTOS). Each thread takes care of a certain aspect of the system, such as interfacing to an LED, an LCD display or a WiFi module. When we see a need to model some behaviors of a thread explicitly, we will then add a state machine to the thread. This represents a pretty common embedded software architecture these days. We do use state machines sometimes, but we only use them causally on an ad hoc basis.

The reality is the concept of state exists almost everywhere in embedded software, and we just may not realize it. Every time we use a variable, we are remembering a state of some sort. See Architecture 4 – Finite State Machines Gallium IO for a detailed discussion. Here comes the bold idea of QP – Rather than using threads as the building blocks of software, why don’t we use hierarchical state machines as the fundamental building blocks? This encourages developers to think aboutstates upfront and capture them explicitly with statecharts, rather than retrofitting a state model mentally over a bunch of variables and conditional statements in the source code.

This is our approach. We are going to scale up our system around the central idea of everything being a hierarchical state machine (The use of “everything” is figurative as there will be exceptions). We will use HSMs to build low level drivers, command console, network protocol interface, graphical user interface, high level coordinators, etc. We will use QP as the underlying framework to create hierarchical state machines, manage their priorities and preemption (threading support), and provide event communications among HSMs. For details, read Chapter 6 of the PSiCC book by Miro Samek (Book: Practical UML Statecharts in C/C++, 2nd Ed. (state machine.com)).

Furthermore, we create a thin layer of custom framework on top of QP to facilitate its use and add a few unique features to support complex large-scale projects. To start, let’s review the built-in state machine classes of QP, namely QHsm and QActive, and its publish-subscribe features.

QHsm Event Processor

Previously in Architecture 6 – Introduction to QP Gallium IO, we demonstrated how to implement a simple HSM named Demo using QP. This is a recap of the basic ideas:

Derive your application HSM class (e.g. Demo) from the QHsm base class provided by QP (via some intermediate base classes).
Implement each state as a member function of the HSM class.
Handle received events in each state function with a switch-case construct according to the behaviors defined in the corresponding statechart.

Since this is such a fundamental coding pattern, it’s worth showing it again:

QState Demo::S21(Demo * const me, QEvt const * const e) {
    switch (e->sig) {
        case Q_ENTRY_SIG: {
            EVENT(e);
            return Q_HANDLED();
        }
        case Q_EXIT_SIG: {
            EVENT(e);
            return Q_HANDLED();
        }
        case Q_INIT_SIG: {
            EVENT(e);
            return Q_TRAN(&Demo::S211);
        }
        case DEMO_A_REQ: {
            EVENT(e);
            return Q_TRAN(&Demo::S21);
        }
        case DEMO_B_REQ: {
            EVENT(e);
            return Q_TRAN(&Demo::S211);
        }
        case DEMO_G_REQ: {
            EVENT(e);
            return Q_TRAN(&Demo::S11);
        }
    }
    return Q_SUPER(&Demo::S2);
}

QHsm is called an event processor. Its job is to process events dispatched to it (via its public method dispatch()) according to the rules encoded in its state functions. Note the keyword “dispatched” is in passive voice, which means some other objects must call its dispatch() function to pass events to it. In other words a QHsm object does not actively grab events to process on its own. It is passive.

QHsm is useful by itself, since it handles all the complex transition rules of an arbitrarily complex state hierarchy. However it will be even more useful if we can extend QHsm to become active. We call such extension an active object represented by QActive in QP.

Active Object

By active, we mean an active object will automatically wait for events to arrive and dispatch them to an HSM on its own. What does it take to make this happen?

Just think about what you would normally do when using an RTOS. Most likely you would create a thread and have it wait on an event queue for events for arrive. As long as the queue is non-empty, the thread will get the oldest event out of the queue to process. After each event it will loop back to check the queue again, and if the queue is empty it will block on it (i.e. the GetEvent() call will not return until an event arrives). This loop is called an event loop, and it typically looks like this:

void ThreadMain() {
    while (running) {                           // Event loop.
        QEvt const *e = eventQueue.GetEvent();  // Blocking call.
        stateMachine.dispatch(e);               // Handles event in state-machine.
    }
}

This pattern will probably show up many times in a project. Rather than crafting it from scratch every time it would be better for us to apply object-oriented design to:

Encapsulate related concepts together in a class, which means adding a threadand an event queue to a hierarchical state machine. We call it QActive.
Enable code reuse by inheriting application specific classes from common reusable base classes (QHsm and QActive).

In a nutshell, an active object is a hierarchical state machine that has a thread and has an event queue as shown below.

Publish-Subscribe

Using the concept of active objects, we can partition any complex software system into a collection of collaborating active objects. Each active object is assigned with distinct and well-defined responsibilities and they collaborate by exchanging events with each other asynchronously. Altogether they implement the complete system behaviors. Through this architectural pattern, we achieve a high degree of decoupling or separation of concerns.

There are different ways active objects can post events to each other. One pattern is called publish-subscribe which is provided by QP.

QP serves as an event broker in this pattern. Active objects exchange events through QP. As a result, they do not call public methods (API) of other active objects directly, and therefore do not need to maintain references to other active objects. Maintaining references to other objects involve object lifetime and ownership management, which can be complicated and can easily cause dangling pointers or memory leak issues.

An active object publishes an event via this QP API:

QF::publish_(QEvt const * const e)

QP will post this event to the event queues of any active objects that have subscribed to this event type via this API:

void QActive::subscribe(enum_t const sig)

The advantages of publish-subscribe include a high degree of flexibility and decoupling since there are no linkages among active objects (i.e. there are no direct function calls from one object to another). It is very easy to drop in another component as long as it subscribes to the same events.

Another advantage of this type of event-driven architecture is that there is minimal data sharing between threads, thanks to the encapsulation of a thread within the active object class which provides a private context for the thread. That context, in form of data members of the class, includes everything the thread needs to access directly. When threads do not share data, there is little need to use a mutex and the whole class of issues related to mutexes and data contention disappear. See the diagram above on Active Object for an illustration of a private context within each active object.

Nevertheless, the broadcast nature of publish-subscribe can be problematic to ensure reliability. A publisher does not know if there are any subscribers of a published event, and if so who they are. It is therefore difficult to implement return-event paths for confirmations and responses (i.e. event handshaking). We might be caught by race-conditions that are very hard to track down. In order to avoid potential pitfalls of the publish-subscribe pattern, we opt to bypass it in our architecture and instead use a direct addressing pattern which combines the benefits of loose coupling among state machines and strict enforcement of event handshaking. We will look into it in the next few episodes.

Appendix – Memory Pool

In embedded systems it is very common to use custom block-based memory pools to manage dynamic memory explicitly, rather than using the built-in heap-based allocator in the standard library. QP provides an efficient implementation of memory pools for event passing and other general uses. See Chapter 6.5 Event Memory Management of the PSiCC book by Miro Samek (Book: Practical UML Statecharts in C/C++, 2nd Ed. (state machine.com)) for a detailed discussion. Below is a block diagram illustrating the key concepts.