Supporting orthogonal regions in practical large-scale projectsEmploy statechart heuristics to overcome the asynchronous nature of event exchange among state machines.
Statecharts are useful tools for modeling dynamic system behaviors. Due to the asynchronous nature of event communication employed in statecharts, however, unexpected behaviors may result if statecharts aren't used properly.
To understand how to avoid the common pitfalls in statechart designs, let's first review the basic components in Quantum Framework (QF) and the extension that can better support orthogonal regions. QF is one of the few source-level statechart frameworks available today. It was introduced by Miro Samek in his book Practical Statecharts in C/C++.1 The fundamental statechart engine in QF is called QHsm, where HSM stands for hierarchical state machine. This class is abstract and is inherited by concrete state machines. It provides a public interface for dispatching events to state-handler methods and for checking the current state.
The concrete state machine shown in Figure 1 is passive in the sense that it doesn't run by itself. An external party must call its dispatch()* method to dispatch an event to it.
To integrate an execution context into a state machine, QActive is derived from QHsm to aggregate a thread and an event queue. An instance of QActive is called an active object. In the original QF, there's only one event queue per active object. As an extension to QF, QActiveExt is derived from QActive to include a second queue, called the internal event queue. To distinguish it from the original queue, we call the original queue the main event queue. The use of internal events in statecharts isn't new and a similar idea has been suggested.2 Basically, the thread blocks until the main event queue isn't empty. An event processing cycle called macro step begins when the thread gets an event from the main event queue. The processing of each event is called a micro step, which may generate new events to either the main or internal event queue. After each micro step, the active object checks if the internal event queue is empty. If not, it processes the next internal event in a new micro step. Otherwise, it waits for another event from the main event queue to begin a new macro step. Figure 2 shows the class diagram of QActiveExt and Listing 1 shows the event processing cycles.
An important design heuristic is that an external party must post an event to the main event queue of the target active object. When posting an event to itself, however, an active object can post it to either the main or internal event queue. Posting it to the internal queue3 ensures that it's processed in the same macro step, which is useful to avoid race conditions caused by events already pending in the main queue. On the other hand, posting it to the main event queue prevents it from preempting other main events.
In the Unified Modeling Language, or UML (www.omg.org), orthogonal regions are concurrent substates in a composite state.4 The QHsm and QActive classes don't support orthogonal regions. However, with the use of object composition, it's possible to support certain features of orthogonal regions explicitly. In Figure 3, the active object comprises m state-machine objects, each modeling an orthogonal region.
Figure 4 illustrates a concrete example and Listing 2 shows part of its implementation. As shown, an active object's state-handler method models the composite state (stateB) which delegates events to each of the component state-machine objects (Concrete HSM 1 and 2). Each component state-machine object models one of the orthogonal regions (stateB1 and stateB2) in the composite state.
It's important to note that the delegation of events from the active object to the component state-machine objects is synchronous. Because a component state-machine object doesn't contain any event queues, an event is dispatched to it directly by calling its dispatch() method. When the dispatch() method returns, it's sure that the event has been completely processed by that component state-machine object. This synchronous nature of event dispatching is consistent with the fact that an event is dispatched to all orthogonal regions simultaneously. On the other hand, component state-machine objects communicate with the container active object and among themselves by posting events to either the main or internal event queue of the active object.
Orthogonal regions only exist when the composite state they belong to is active. As shown in Listing 2, they're constructed in the entry action of the composite state (stateB) and destroyed in the exit action. However for efficiency, they may exist in the whole lifetime of the active object, but their use should be limited to when the composite state is active.
In UML, a transition can cross the boundary of an orthogonal region. In other words, it can source from a substate inside an orthogonal region and target a state outside the region, and vice-versa. In the previous implementation, states inside an orthogonal region are represented by the component state-machine object (Concrete HSM 1 and 2 in Figure 4) while states outside the region are represented by the container active object (Concrete Active Class in Figure 4). There's no built-in support for transiting from a state in one object to a state in another object. However, we can get around this by transforming statecharts with internal events (reminders):
- When transiting into an orthogonal region (see Figure 5), we can first transit to the composite state and post an internal event to itself. The composite state will then delegate the internal event to the orthogonal region, which causes it to transit to the target state inside the region.
- When transiting out of an orthogonal region (see Figure 6 and Listing 3), we can post an internal event to the container active object. It causes a transition from the composite state to the target state in the active object. Besides, the exit action of the composite state delegates an event to all orthogonal regions to cause them to transit to a dummy state inside each region (for example, stateB1Idle in region1). This guarantees that all exit actions of the active states in each region are executed.
- When an event to the active object (such as E4 in Figure 6) causes a transition out of the composite state, the composite state's exit action will guarantee that all exit actions of the active states in each region are executed.
Because the communication among active objects is asynchronous, there are possible race conditions that may cause unexpected behaviors. However, heuristics in statechart design could avoid race conditions. Here we illustrate some of the concepts with a digital phone example. Statecharts are used to highlight key points only and are not complete designs.
Figure 7 shows two active objects of the same Connection class. They are used to model concurrent connections in a digital phone. For example, the user can make an outgoing call while putting an existing call on hold. An incoming call can arrive when there is an existing call (call waiting). There is an assumption that a user can't make two outgoing calls at the same time.
However there is a problem with the guard "[other connection NOT in Outgoing]" in Figure 7. An active object shouldn't use another active object's current state as a guard, or they should be modeled as orthogonal regions belonging to the same active object. Though it may seem convenient to call the isIn() method of another active object to find out what state it's in before firing an action or transition, the state might be changed immediately after the state check because active objects are running concurrently. This renders the check meaningless.
Figure 8 shows the correct design using orthogonal regions. Since orthogonal regions are running in the same thread, a region can safely use the state of another region as guards. In the new design, L3Root is the root state of the Layer 3 active object. Once it is initialized, it contains two orthogonal regions ConnectionRoot and ConnectionRoot to handle simultaneous connections. Since the two regions are instances of the same state-machine class, we use a subscript of region ID to distinguish between them.
Because event communication between active objects is asynchronous, in situations where we need to get feedbacks, we should use pairs of request and confirmation(response) events. Even though the framework guarantees event delivery, the request originator can't simply assume that the recipient can successfully handle the request. This is analogous to checking the return value of a function call.
A common mistake is we only handle a request in the state expecting it (the normal case) and ignore it in all other states (exceptional cases). This may result in the request originator waiting forever for the response. One way to overcome this is to instrument a timeout in the originator's wait state. In general, it is wise to have timeouts for any transient wait states so that your active object will not be dead-locked due to unexpected behaviors of other interacting active objects. This enhances the robustness of your design.
Another solution is to respond to a request in all states that it may arrive. Thanks to the hierarchical nature of statecharts, we can reply a default response (usually an error status) in the parent state and override it only in states that actually handle the request. This is illustrated in Figure 8 by L3_INIT_REQ and L3_INIT_CFM. If the active object is in L3Initialized, it can't be initialized again. Instead of silently ignoring L3_INIT_REQ, it'll respond with L3_INIT_CFM(fail) so the originator can detect and handle the error. Yet another approach is to use the deferred event pattern introduced in Miro Samek's book.1 Instead of handling the request in a transient state, we defer the request by saving it aside and recalling it to the main event queue when we exit the transient state. It will ultimately arrive at a state that processes it normally. An example is shown in Figure 9, and I'll explain it shortly.
Instead of sharing resources directly, we should encapsulate resources inside active objects and use a strict event-driven interface to manage the resources. In our digital phone example, we use a User active object to model the phone user. Figure 9 shows part of its statechart in which the user requests a Layer 3 Connection region (a resource) to make an outgoing call. Figure 10 shows how the Layer 3 active object manages the Connection regions.
The User active object requests a Connection region by posting the CONNECTION_ALLOC_REQ to the Layer 3 active object. If an unused region is available, it allocates the region for the user by changing the region's state to InUse with the internal event iALLOC_REGION. The use of an internal event queue here guarantees that the allocation is atomic because it happens within a single macro step. The use of deferred event in state ConnectionAllocWait ensures CALL_CANCELED is not ignored even when the User active object is in an inconvenient state to process it.
To summarize, I've explained how to extend QF to include an internal event queue, which provides a more versatile event-processing model with macro steps and micro steps. It helps avoid certain race conditions by completing all micro steps before starting a new macro step. I've also explained how to support orthogonal regions in QF with object composition. An active object comprises a state-machine object for each orthogonal region. The internal event queue proves to be useful in supporting transitions into and out of orthogonal regions. The second part of the article introduces several heuristics useful in statechart design. They include (1) avoiding the use of another active object's state as guards, (2) using request and response pairs, (3) using timeout in wait states, (4) handling requests in all possible states or deferring them in transient states, and (5) encapsulating shared resources inside active objects. Some of these heuristics depend on orthogonal regions and the internal event queue discussed in the first part of the article.
Orthogonal regions are important building blocks in many practical statechart models. The asynchronous nature of event exchange in state machines is intricate and requires a deeper understanding of the underlying event model. I hope the discussion on internal event queue, orthogonal regions, and heuristics will help you apply statecharts in your real-life projects, whether you're using QF or not.
Lawrence Lo is a staff firmware engineer at Avocent Corp., in Redmond Wash. He has 10 years of experience in embedded software design and is currently working on wireless audio-visual products. Lo holds BEng and MSc degrees in Electrical and Electronics Engineering from the University of Hong Kong. He can be reached at email@example.com.
1#. Samek, Miro. Practical Statecharts in C/C++. CMP Books, 2002.
2. Wasowski, Andrzej and Peter Sestoft. "On the Formal Semantics of VisualSTATE Statecharts." Technical Report TR-2002-19. IT University, Copenhagen, Denmark. September 2002. www.itu.dk/~wasowski/papers/vsfsem.pdf
3. The use of the internal event queue is similar to postLIFO(), such as posting an event to the front of the main event queue. An advantage of having a separate internal event queue is that it preserves the order in which events are posted, rather than reversing it.
4. A composite state containing orthogonal regions is called an AND state.