QP/C
7.2.2
Real-Time Embedded Framework
Event-driven systems work by responding to Events. In general, the system's response to a given Event depends both on the nature of that Event (captured in its Signal) and on the history of events the system has received.
In practice not all aspects of the full "history of past events" are relevant. The simplified history consisting only of aspects that are consequential for the system's response to future events is called the Relevant History.
State is an equivalence class of past histories of a system, all of which are equivalent in the sense that the future behavior of the system given any of these past histories will be identical. Thus, the concept of "State" is the most efficient representation of the Relevant History of the system. It is the minimum information that captures only the relevant aspects for the future behavior and abstracts away all irrelevant aspects.
Transition is a change from one State to another during the lifetime of a system. In event-driven systems, a change from one state to another can be caused only by an event. The events that triggers a Transition is called Triggering Event or just Trigger of the Transition.
State Machine is the set of all States (equivalence classes of relevant histories), plus all the Transitoins (rules for changing States). An important benefit of the State Machine formalizm is the expressive graphical representation of State Machines in form of state diagrams.
Hierarchical State Machine (a.k.a. UML statechart) is an advanced formalism which extends the traditional state machines in several ways. The most important innovation of UML state machines over classical state machines is the introduction of hierarchically nested states. The value of state nesting lies in avoiding repetitions, which are inevitable in the traditional “flat” state machine formalism. The semantics of state nesting allow substates to define only the differences in behavior from the superstates, thus promoting sharing and reuse of behavior.
State Machines, and Hierarchical State Machines, in particular, can be implemented in many different ways. A specific way of implementing a state machine will be called here a State Machine Implementation Strategy, and it can be characterized by the following properties:
No single State Machine Implementation Strategy can be optimal for all circumstances, and therefore QP Framework shall support multiple and interchangeable strategies (see REQ-QP-02_20).
The event processing inside a state machine is called dispatching an event to the state machine, and it requires interaction between the QP Framework and the QP Application:
The "State Machine Specification" is provided inside the QP Application and is prepared according to the rules defined by the chosen State Machine Implementation Strategy in QP Framework. Typically an implementation strategy represents a state machine as several elements, such as states, transitions, etc.
The "State Machine Specification" can mean state machine code (when the state machine is coded manually) or a state machine model (when the state machine is specified in a modeling tool, like "QM"). Either way, it is highly recommended to think of the state machine implementation as the specification of state machine elements, not merely code. This notion of "specifying" a state machine rather than coding it can be reinforced by selecting an expressive and fully traceable state machine implementation strategy, see REQ-QP-02_40. The advantage of a traceable implementation is that each artifact at all levels of abstraction (design to code) unambiguously represents an element of a state machine.
A state machine is executed in QP Framework by the "State Machine Processor" that decides which elements of the "State Machine Specification" to call (see also srs_intro_inv). Once called, the chosen part of the "State Machine Specification" executes some actions and returns back to the "State Machine Processor" (QP Framework) with the status information as to what has happened. For example, the returned status might inform the "State Machine Processor" that a state transition needs to be taken, or that the event needs to be propagated to the superstate in the hierarchical state machine.
The "State Machine Processor" is a passive software component that needs to be explicitly called from some control thread to dispatch each event to the given state machine object. The most important restriction is that the dispatch operation must necessarily run to completion (Run-to-Completion processing) before another event can be dispatched to the same state machine object.
| QP Framework shall provide support for state machines both for Active Objects and for passive event-driven objects in the Application |
|---|
| Description Support for hierarchical state machines (HSMs) means that QP Framework will provide a set of rules for "State Machine Specifications" in the Application as well as the matching implementation of the "State Machine Processor" to handle events according to HSM semantics defined in requirements in this section. |
| QP Framework shall support multiple and interchangeable State Machine Implementation Strategies |
|---|
| Description QP Application can choose the State Machine Implementation Strategy (out of a set of supported strategies) through the type of a state machine object. Based on that type, QP Framework shall then resolve the matching "State Machine Processor" (matching dispatch method) at run-time. Moreover, QP Framework shall allow Applications to add their State Machine Implementation Strategies, and QP Framework shall still resolve the matching (application-defined) dispatch method based on the type of the state machine object. |
| Background Application-defined State Machine Implementation Strategies might be useful for special purposes, such as components with stringent performance requirements (but perhaps fewer state machine features) or test doubles (in TDD). |
| QP Framework shall provide a State Machine Implementation Strategy optimized for "manual coding" |
|---|
Description
|
| QP Framework should provide a State Machine Implementation Strategy optimized for "automatic code generation" |
|---|
| Description "Optimized for automatic code generation" means the implementation may contain some redundant information to improve the efficiency of the state machine execution. Also, such a strategy can support more advanced state machine features (see REQ-QP-02_21) than a strategy constrained by the limitations of "manual coding" (see REQ-QP-02_20). |
| Background In automatically generated code not intended for manual maintenance, the restrictions of the "manual coding" can be relaxed. In that case, a State Machine Implementation Strategy "optimized for automatic code generation" offers the application developers a choice of higher-performance and/or more features than the strategy "optimized for manual coding." For example, an implementation may contain "transition tables" with information about the chains of state exit and entry actions to execute for a given transition (instead of determining the state exit and entry at run-time). This optimization might require adjusting multiple "transition tables" when changing the hierarchical nesting of a single state, which is considered unsuitable for manual coding (see REQ-QP-02_20). However, optimizations of that kind are trivial for an automatic code generator. |
| All State Machine Implementation Strategies provided by QP Framework shall be bidirectionally traceable |
|---|
| Description Bi-directional traceability of a State Machine Implementation Strategy means that the rules of the "State Machine Specification" are such that:
|
| Background Traceability between design and implementation is a required property for many functional safety standards. |
| All State Machine Implementation Strategies provided by QP shall allow Applications to easily access the current event |
|---|
| Description The current event, with its Signal and Parameters, must be available during the RTC processing within the state machine. The access should be computationally inexpensive (e.g., via a pointer). |
| All State Machine Implementation Strategies provided by QP shall allow Applications to easily access the instance variables associated with a given state machine |
|---|
| Description One of the main characteristics of Active Objects is their strict encapsulation. While QP Framework cannot strictly enforce such encapsulation, the framework should allow the QP Application to hide such access from the outside of the AO. At the same time, the framework should allow for easy and computationally inexpensive access to the internal attributes of an Active Object from within the AO, such as from its internal state machine. A good example of implementing such a policy is the concept of class encapsulation in OOP, where the internal attributes are accessible to the class operations (e.g., via the this pointer) and are harder to access from the outside. |
| All State Machine Implementation Strategies provided by QP Framework might supply a method for checking if a state machine is in a given state |
|---|
| Description The "is-in" state operation returns 'true' if the current state of the state machine is equal or is a substate of the given state. Otherwise, the "is-in" operation returns 'false'. |
| Background This operation is intended to be used only for state machines that run in the same thread of execution. For example, a given Active Object could use the "is-in" check on one of the "Orthogonal Components" owned by that Active Object. |
| All State Machine Implementation Strategies provided by QP Framework shall support hierarchical state machines with features specified in the sub-requirements 02_3x |
|---|
Description 
|
| All State Machine Implementation Strategies provided by QP Framework shall support states capable of holding hierarchically nested substates |
|---|
| Description An example state is shown in Figure 02_30[A]. This is a composite state because it holds other states (called substates). A state that holds no other states is shown in Figure 02_30[A1]. Such a state is called a leaf state. The State Machines Implementation Strategies in QP need to represent both types of states. Moreover, it should be possible to simply add substates to a given state thus making it a composite state as well as remove substates, thus making it a leaf state. Also, it should be possible to simply change the nesting of a given state from one superstate to another (including moving it to the implicit "top" superstate). |
| All State Machine Implementation Strategies provided by QP Framework shall support entry actions to states |
|---|
| Description Example entry actions to a state are shown in Figure 02_30[B]. Entry actions to a state are optional, meaning that a given state might specify entry actions or not. If any entry actions are defined in a given state, the State Machine Processor in QP must execute these actions whenever that state is entered. Also, entry actions to superstates must be always executed before entry actions to substates. |
| Background Entry actions to a state provide an important mechanism to initialize that state context and QP must guarantee such initialization on any transition path leading to a given state. |
| All State Machine Implementation Strategies provided by QP Framework shall support exit actions from states |
|---|
| Description Example exit actions from a state are shown in Figure 02_30[C]. Exit actions from a state are optional, meaning that a given state might specify exit actions or not. If any exit actions are defined in a given state, the State Machine Processor in QP must execute these actions whenever that state is exited. Also, exit actions to superstates must be always executed after exit actions from substates. |
| Background Exit actions from a state provide an important mechanism to cleanup that state context, and QP must guarantee such cleanup on any transition path leading out of a given state. |
| All State Machine Implementation Strategies provided by QP Framework shall support nested initial transitions in composite states |
|---|
Description Initial Transition Execution Sequence
|
Examples On the other hand, the execution sequence for the initial transition nested directly in state "s1" in Figure 02_30 is as follows:
|
| All State Machine Implementation Strategies provided by QP Framework shall support transitions between states at any level of nesting |
|---|
Description Main-Source State Main-Target State Self-Transition Transition Execution Sequence
In most state transitions, the main-source state is exited, and the main target is entered. The only exceptional cases are explained below: Local State Transition Semantics Special Case 2: If the main-target state contains the main_source (e.g., transition E2 in state "s121" in Figure 02_30), the main-target is not entered.
|
Examples Assuming that "s121" is the current state, the execution sequence for the transition s1:E3 (Special Case 1) is as follows: Assuming that "s121" is the current state, the execution sequence for the transition s121:E1 (Special Case 2) is as follows: Assuming that "s222" is the current state, the execution sequence for the self-transition s22:E1 in (see Figure 02_30[E1]) is as follows:
|
| All State Machine Implementation Strategies provided by QP Framework shall support internal transitions in states |
|---|
| Description An example of an internal transition is shown in Figure 02_30[F]. This type of transition causes only the execution of the associated actions. Still, it never leads to a change of the current state, and consequently, it never causes execution of any state exit or state entry actions. An alternative name for internal transition is a *state reaction_. |
| Background Internal transitions (state reactions) are very common in practice. Internal transitions are also different from self-transitions because an internal transition never causes execution of any state exit or state entry actions. |
| All State Machine Implementation Strategies provided by QP Framework shall support guard conditions to be attached to regular and internal transitions |
|---|
Description Disabled Transitions Guard Evaluation s2_E2(); // action associated with the original transition
if (g1()) { // evaluate guard g1()
s2_E2_g1(); // action associated with the path following [g1()]
transition_to(s1); // regular state transition
}
else if (g2()) { // evaluate guard g2()
s2_E2_g2(); // action associated with the path following [g2()]
internal_transition(); // internal state transition
}
else { // disabled transition
propagate_to_superstate(top); // event not handled at this level
}
The Complementary [else] Guard s1_E3(); // action associated with the original transition
if (g3()) { // evaluate guard g3()
s1_E3_g3(); // action associated with the path following [g3()]
transition_to_deep_history_of(s22); // transition to history (deep)
}
else { // explicit complementary [else] guard
s1_E3_else(); // action associated with the path following [else]
transition_to(s21); // regular state transition
}
|
| All State Machine Implementation Strategies provided by QP Framework shall support top-most initial transition that shall be explicitly triggered independently from instantiation of the state machine object |
|---|
Description The execution of the top-most initial transition is intentionally separated from the instantiation of the state machine object, to allow applications to fully control the initialization performed in the actions to the top-most initial transition. |
| Background The instantiation of state machine objects might occur in an undefined order, even before the entry point into the application (before the main() function in C++). This is typically before the target hardware or the underlying real-time kernel has been properly initialized. |
| All State Machine Implementation Strategies provided by QP Framework should support transitions to history. Both shallow and deep histories shall be supported |
|---|
| Description An example of a transition to deep history is shown in Figure 02_30[H1]. An example of a transition path to shallow history is shown in Figure 02_30[H2]. Transitions to history (deep or shallow) apply only to composite states and represent the most recently active substate. In the case of deep history, the actual current substate is remembered upon the exit from the given composite state. In the case of shallow history, only the direct substate containing the current substate is remembered. Transition to state history means transitioning to that remembered substate. Upon initialization, when a given composite state has never been active before, the transition to history is initialized with the default history, which is the substate pointed to by the transition coming out of the history circle (e.g., Figure 02_30[H1]). |
| Background To support transitions to history, QP Framework needs to supply a mechanism to access the current state (deep history) and the direct substate of the current state. This information needs to be stored upon the exit of a given composite state. Also, the QP Framework needs to transition dynamically to the stored history substate. |
| State Machine Implementation Strategies provided by QP Framework might supply the top-state |
|---|
| Description The top-state is the ultimate root of state hierarchy and typically it is not rendered in the state diagrams. However, the concept can be useful in State Machine Specification as the superstate of states not nested in any other state. In case a given State Machine Implementation Strategy uses the concept of the top-state, QP Framework may provide a top-state element with the default behavior of silently ignoring all events. |
| State Machine Implementation Strategy "optimized for automatic code generation" should support reuse of behavior via submachines |
|---|
| Description A submachine is a composite state with all its nested substates and transitions packaged as a unit (submachine). This unit can then be instantiated inside a given state machine multiple times, wherever that particular composite state is needed. Each instance of a submachine is called submachine-state. |
Background To package a composite state as a unit (submachine), the submachine needs to provide a well-defined interface to the other parts of the state machine. This formal interface consists of entry segments, exit points, and history segments (Figure 02_50[B,C,D]).
|
| State Machine Implementation Strategy "optimized for automatic code generation" should allow applications to add multiple submachines to a given hierarchical state machine |
|---|
Description A submachine added to a given host hierarchical state machine shall operate in the same context as the host state machine. In particular, the submachine shall have access to the same attributes as the host state machine. |
| Background Submachines and their interfaces are typically difficult to implement within the constraints of manual coding. Therefore, the requirement for supporting submachines is limited to the State Machine Implementation Strategy optimized for automatic code generation. |
| The submachines should support entry points |
|---|
| Description An example of an entry segment is shown in Figure 02_50[B]. An entry segment needs to have a name (unique within a given submachine) and needs to target a substate of a given submachine. An entry segment might also have actions to be executed after the submachine is entered, before any other actions in the submachine (such as submachine's entry action or any nested initial transition.) |
| The submachines should support exit points |
|---|
| Description An example of an exit point is shown in Figure 02_50[C]. An exit point needs to have a name (unique within a given submachine) and its purpose is to provide a termination point for all state transitions that exit the submachine. Exit points don't have actions of their own. |
| The submachines should support history segments; Both shallow and deep histories shall be supported. |
|---|
| Description An example of an history segment is shown in Figure 02_50[D]. History segments (deep or shallow) shall operate similarly as transitions to history in composite states. |
| State Machine Implementation Strategy "optimized for automatic code generation" should support submachine-states |
|---|
| Description An example of an submachine state is shown in Figure 02_50[E]. A submachine state is an instance of the given submachine placed in a specific context of the host hierarchical state machine. The context is established by the connections made to the interface of the submachine exposed by the submachine state. Specifically, the context of a submachine state consists of the incoming transitions that terminate on the specific entry points and by exit segments originating on the specific exit points. Additionally, a submachine state can have its own transitions originating on its boundary and terminating on its boundary. |
| State Machine Implementation Strategy "optimized for automatic code generation" should support exit segments |
|---|
| Description An example of an xit segments is shown in Figure 02_50[F]. An exit segment is similar to a transition, except it does not have a trigger, but instead it attaches to a given exit point of a submachine state. |